Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T09:14:26.284Z Has data issue: false hasContentIssue false
  • English
  • Français

Les effets de l'exposant de la fonction barrière multiplicativedans les méthodes de points intérieurs

Published online by Cambridge University Press:  15 November 2003

Adama Coulibaly  and
Jean-Pierre Crouzeix
Adama Coulibaly
Affiliation:
UFR Math.-Info., Université de COCODY, BP 582, Abidjan 22, Côte d'Ivoire.
Jean-Pierre Crouzeix
Affiliation:
CUST et LIMOS, Université Blaise Pascal, Campus des Cézaux, 63174 Aubière, France.
Get access

Abstract

Les méthodes de points intérieurs en programmation linéaireconnaissent un grand succès depuis l'introductionde l'algorithme de Karmarkar. La convergence de l'algorithme repose sur unefonction potentielle qui, sous saforme multiplicative, fait apparaître un exposant p. Cet exposantest, de façongénérale, choisi supérieur au nombre de variables n du problème.Nous montrons dans cetarticle que l'on peut utiliser des valeurs dep plus petites que n. Ceci permet d'améliorer le conditionnement dela méthode au voisinage de la solution optimale.

Keywords

Interior point methodsKarmarkar algorithmmultiplicative and additive potential functionsbarrier function.
Type
Research Article
Information
RAIRO - Operations Research , Volume 37 , Issue 2 , April 2003 , pp. 99 - 117
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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