An interior point algorithm for convex quadratic programming with strict equilibrium constraints
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 1, pp. 13-33.

We describe an interior point algorithm for convex quadratic problem with a strict complementarity constraints. We show that under some assumptions the approach requires a total of $O\left(\sqrt{n}L\right)$ number of iterations, where $L$ is the input size of the problem. The algorithm generates a sequence of problems, each of which is approximately solved by Newton’s method.

DOI : https://doi.org/10.1051/ro:2005002
Mots clés : convex quadratic programming with a strict equilibrium constraints, interior point algorithm, Newton's method
@article{RO_2005__39_1_13_0,
author = {Benouahboun, Rachid and Mansouri, Abdelatif},
title = {An interior point algorithm for convex quadratic programming with strict equilibrium constraints},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {13--33},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
doi = {10.1051/ro:2005002},
zbl = {1102.90041},
mrnumber = {2166343},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2005002/}
}
TY  - JOUR
AU  - Benouahboun, Rachid
AU  - Mansouri, Abdelatif
TI  - An interior point algorithm for convex quadratic programming with strict equilibrium constraints
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2005
DA  - 2005///
SP  - 13
EP  - 33
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2005002/
UR  - https://zbmath.org/?q=an%3A1102.90041
UR  - https://www.ams.org/mathscinet-getitem?mr=2166343
UR  - https://doi.org/10.1051/ro:2005002
DO  - 10.1051/ro:2005002
LA  - en
ID  - RO_2005__39_1_13_0
ER  - 
Benouahboun, Rachid; Mansouri, Abdelatif. An interior point algorithm for convex quadratic programming with strict equilibrium constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 1, pp. 13-33. doi : 10.1051/ro:2005002. http://www.numdam.org/articles/10.1051/ro:2005002/

[1] H.P. Benson, Optimization over the efficient set. J. Math. Anal. Appl. 98 (1984) 562-580. | Zbl 0534.90077

[2] H.P. Benson, An algorithm for optimizing over the weakly-efficient set. European J. Oper. Res. 25 (1986) 192-199. | Zbl 0594.90082

[3] Y. Chen and M. Florian, O-D demand adjustment problem with cojestion: Part I. Model analysis and optimality conditions. Publication CRT-94-56. | Zbl 0874.90078

[4] C. Cinquini and R. Contro, Optimal design of beams discretized by elastic plastic finite element. Comput. Structures 20 (1985) 475-585. | Zbl 0581.73103

[5] A.V. Fiacco and G.P. Mccormick, Nonlinear Programming: Sequential Unconstrained Minmization Techniques. John Wiley, New York (1968). | MR 243831 | Zbl 0193.18805

[6] D. Gale, The theory of Linear Economic. McGraw-Hill Book Company, New York (1960). | MR 115801

[7] C. Gonzaga, Path-following methods for linear programming. SIAM Rev. 34 (1992) 167-274. | Zbl 0763.90063

[8] D. Goldfarb and S. Liu, An $O\left({n}^{3}L\right)$ primal interior point algorithm for convex quadratic programming. Math. Prog. 49 (1990/91) 325-340. | Zbl 0717.90055

[9] M. Kočvara and J.V. Outrata, On the solution of optimum design problems with variational inequalities, in Recent Advances in Nonsmooth Optimization, edited by D.Z. Du, L. Qi and R. Womersly, World Sciences (November 1995). | MR 1460001 | Zbl 0952.49034

[10] G. Maier, A quadratic programming approach for certain classes of nonlinear structural problems. Meccanica 3 (1968) 121-130. | Zbl 0165.28502

[11] D.C. Monteiro and I. Adler, Interior path following primal-dual algorithms. Part I: Linear programming. Math. Prog. 44 (1989) 27-41. | Zbl 0676.90038

[12] Z.Q. Luo, J.S Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints. Cambridge University Press (1996). | MR 1419501 | Zbl 0898.90006

Cité par Sources :