Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 37 (2003) no. 2, pp. 99-117.

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.

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.

DOI : https://doi.org/10.1051/ro:2003016
Classification : 49M35,  90C05,  26B25
Mots clés : interior point methods, karmarkar algorithm, multiplicative and additive potential functions, barrier function
@article{RO_2003__37_2_99_0,
     author = {Coulibaly, Adama and Crouzeix, Jean-Pierre},
     title = {Les effets de l'exposant de la fonction barri\`ere multiplicative dans les m\'ethodes de points int\'erieurs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {99--117},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {2},
     year = {2003},
     doi = {10.1051/ro:2003016},
     zbl = {1069.90108},
     language = {fr},
     url = {http://www.numdam.org/articles/10.1051/ro:2003016/}
}
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 - Recherche Opérationnelle
PY  - 2003
DA  - 2003///
SP  - 99
EP  - 117
VL  - 37
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2003016/
UR  - https://zbmath.org/?q=an%3A1069.90108
UR  - https://doi.org/10.1051/ro:2003016
DO  - 10.1051/ro:2003016
LA  - fr
ID  - RO_2003__37_2_99_0
ER  - 
Coulibaly, Adama; 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 - Recherche Opérationnelle, Tome 37 (2003) no. 2, pp. 99-117. doi : 10.1051/ro:2003016. http://www.numdam.org/articles/10.1051/ro:2003016/

[1] Y. Chabrillac et J.-P. Crouzeix, Definiteness and semi-definiteness of quadratic forms. Linear Algebra Appl. 63 (1984) 283-292. | MR 766515 | Zbl 0548.15027

[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. Programming 56 (1992) 223-232. | MR 1183648 | Zbl 0777.90056

[4] J.-P. Crouzeix et R. Kebbour, Index multiplicatifs de convexité/concavité et applications. Cahiers Centre Études Rech. Opér. 34 (1992) 7-24. | MR 1199191 | Zbl 0784.90071

[5] G. De Ghelinck et J.-Ph. Vial, A polynomial Newton method for linear programming. Algorithmica 1 (1989) 425-453. | MR 880732 | Zbl 0629.90058

[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. Algorithmica 6 (1991) 153-181. | MR 1093008 | Zbl 0718.90064

[8] C.C. Gonzaga, On lower bounds updates in primal potential reduction methods for linear programming. Math. Programming 52 (1991). | MR 1148179 | Zbl 0754.90034

[9] E.V. Haynsworth, Determination of the inertia of a partitioned hermitian matrix. Linear Algebra Appl. 1 (1968) 73-81. | MR 223392 | Zbl 0155.06304

[10] H. Imaï, On the convexity of the multiplicative version of Karmarkar's potential function. Math. Programming 40 (1988) 29-32. | Zbl 0657.90060

[11] M. Iri et H. Imaï, A mutiplicative barrier function method for linear programming. Algorithmica 1 (1986) 455-482. | MR 880733 | Zbl 0641.90048

[12] N.K. Karmarkar, A new polynomial time algorithm for linear programming. Combinatorica 4 (1984) 373-395. | MR 779900 | Zbl 0557.90065

[13] N.K. Karmarkar et K.G. Ramakrishnan, Computational results of an interior point algorithm for large scale linear program. Math. Programming 52 (1991) 55-586. | MR 1148186 | Zbl 0739.90042

[14] M. Kojima, S. Mizumo et A. Yoshise, An O(nL) 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. A 89 (2001) 505-516. | MR 1814553 | Zbl 0990.90130

[16] M.J. Todd et Y. Yu, A Centered projective algorithm for linear programming. Math. Oper. Res. 15 (1990) 508-529. | MR 1064215 | Zbl 0722.90044

[17] T. Tsuchiya, Quadratic convergence of the Iri-Imaïalgorithm for degenerate linear programming problems. J. Optim. Theory Appl. 87 (1995) 703-726. | Zbl 0840.90101

[18] Y. Ye, K.O. Kortanek et S. Huang, Near boundary behavior of primal-dual potential reduction algorithm for linear programming. Math. Programming 58 (1993) 243-255. | MR 1216493 | Zbl 0780.90066

[19] S. Zhang, Convergence property of the Iri-Imaï algorithm for some smooth convex programming problems. J. Optim. Theory Appl. 82 (1994) 121-137. | Zbl 0819.90073

Cité par Sources :