The effect of the parameter of the potential function on the conditioning of interior point methods

Adama Coulibaly; Jean-Pierre Crouzeix

RAIRO - Operations Research (2010)

  • Volume: 37, Issue: 2, page 99-117
  • ISSN: 0399-0559

Abstract

top
Potential functions in interior point methods are used to determine descent directions and to prove the convergence. They depend on a parameter which is usually taken equal to or greater than the size of the problem. Actually, smaller values give a better conditioning of the method near an optimal solution. This assertion is illustrated by a few numerical experiments.

How to cite

top

Coulibaly, Adama, and Crouzeix, Jean-Pierre. "Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs." RAIRO - Operations Research 37.2 (2010): 99-117. <http://eudml.org/doc/105285>.

@article{Coulibaly2010,
abstract = { Les méthodes de points intérieurs en programmation linéaire connaissent un grand succès depuis l'introduction de l'algorithme de Karmarkar. La convergence de l'algorithme repose sur une fonction potentielle qui, sous sa forme multiplicative, fait apparaître un exposant p. Cet exposant est, de façon générale, choisi supérieur au nombre de variables n du problème. Nous montrons dans cet article que l'on peut utiliser des valeurs de p plus petites que n. Ceci permet d'améliorer le conditionnement de la méthode au voisinage de la solution optimale. },
author = {Coulibaly, Adama, Crouzeix, Jean-Pierre},
journal = {RAIRO - Operations Research},
keywords = {Interior point methods; Karmarkar algorithm; multiplicative and additive potential functions; barrier function.; interior point methods; barrier function; convexity},
language = {fre},
month = {3},
number = {2},
pages = {99-117},
publisher = {EDP Sciences},
title = {Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs},
url = {http://eudml.org/doc/105285},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Coulibaly, Adama
AU - Crouzeix, Jean-Pierre
TI - Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 2
SP - 99
EP - 117
AB - Les méthodes de points intérieurs en programmation linéaire connaissent un grand succès depuis l'introduction de l'algorithme de Karmarkar. La convergence de l'algorithme repose sur une fonction potentielle qui, sous sa forme multiplicative, fait apparaître un exposant p. Cet exposant est, de façon générale, choisi supérieur au nombre de variables n du problème. Nous montrons dans cet article que l'on peut utiliser des valeurs de p plus petites que n. Ceci permet d'améliorer le conditionnement de la méthode au voisinage de la solution optimale.
LA - fre
KW - Interior point methods; Karmarkar algorithm; multiplicative and additive potential functions; barrier function.; interior point methods; barrier function; convexity
UR - http://eudml.org/doc/105285
ER -

References

top
  1. Y. Chabrillac et J.-P. Crouzeix, Definiteness and semi-definiteness of quadratic forms. Linear Algebra Appl.63 (1984) 283-292.  
  2. A. Coulibaly, Méthodes de points intérieurs en programmation linéaire, Thèse de doctorat de l'Université Blaise Pascal. Clermont-Ferrand (1994).  
  3. J.-P. Crouzeix, J.A. Ferland et S. Schaible, Generalized convexity of functions on affine subspaces and applications. Math. Programming56 (1992) 223-232.  
  4. J.-P. Crouzeix et R. Kebbour, Index multiplicatifs de convexité/concavité et applications. Cahiers Centre Études Rech. Opér.34 (1992) 7-24.  
  5. G. De Ghelinck et J.-Ph. Vial, A polynomial Newton method for linear programming. Algorithmica1 (1989) 425-453.  
  6. C.C. Gonzaga, A Simple presentation of Karmarkar's algorithm, Technical Report. Department of Mathematics, Federal University of Santa Catarina, Brasil (2002).  
  7. C.C. Gonzaga, Search direction for interior linear programming methods. Algorithmica6 (1991) 153-181.  
  8. C.C. Gonzaga, On lower bounds updates in primal potential reduction methods for linear programming. Math. Programming 52 (1991).  
  9. E.V. Haynsworth, Determination of the inertia of a partitioned hermitian matrix. Linear Algebra Appl.1 (1968) 73-81.  
  10. H. Imaï, On the convexity of the multiplicative version of Karmarkar's potential function. Math. Programming40 (1988) 29-32.  
  11. M. Iri et H. Imaï, A mutiplicative barrier function method for linear programming. Algorithmica1 (1986) 455-482.  
  12. N.K. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica4 (1984) 373-395.  
  13. N.K. Karmarkar et K.G. Ramakrishnan, Computational results of an interior point algorithm for large scale linear program. Math. Programming52 (1991) 55-586.  
  14. M. Kojima, S. Mizumo et A. Yoshise, An O ( n L ) iteration potential reduction algorithm for linear complementarity problems, Research Report No. B-217. Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan (1988).  
  15. P. Maréchal, On the convexity of the multiplicative potential and penalty function and related topics. Math. Programming Ser. A89 (2001) 505-516.  
  16. M.J. Todd et Y. Yu, A Centered projective algorithm for linear programming. Math. Oper. Res.15 (1990) 508-529.  
  17. T. Tsuchiya, Quadratic convergence of the Iri-Imaïalgorithm for degenerate linear programming problems. J. Optim. Theory Appl.87 (1995) 703-726.  
  18. Y. Ye, K.O. Kortanek et S. Huang, Near boundary behavior of primal-dual potential reduction algorithm for linear programming. Math. Programming58 (1993) 243-255.  
  19. S. Zhang, Convergence property of the Iri-Imaï algorithm for some smooth convex programming problems. J. Optim. Theory Appl.82 (1994) 121-137.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.