An interior point algorithm for convex quadratic programming with strict equilibrium constraints

Rachid Benouahboun; Abdelatif Mansouri

RAIRO - Operations Research - Recherche Opérationnelle (2005)

  • Volume: 39, Issue: 1, page 13-33
  • ISSN: 0399-0559

Abstract

top
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 ( n L ) 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.

How to cite

top

Benouahboun, Rachid, and Mansouri, Abdelatif. "An interior point algorithm for convex quadratic programming with strict equilibrium constraints." RAIRO - Operations Research - Recherche Opérationnelle 39.1 (2005): 13-33. <http://eudml.org/doc/245930>.

@article{Benouahboun2005,
abstract = {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(\sqrt\{n\}L)$ 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.},
author = {Benouahboun, Rachid, Mansouri, Abdelatif},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {convex quadratic programming with a strict equilibrium constraints; interior point algorithm; Newton’s method; Convex quadratic programming with a strict equilibrium constraints; Newton's method},
language = {eng},
number = {1},
pages = {13-33},
publisher = {EDP-Sciences},
title = {An interior point algorithm for convex quadratic programming with strict equilibrium constraints},
url = {http://eudml.org/doc/245930},
volume = {39},
year = {2005},
}

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
PB - EDP-Sciences
VL - 39
IS - 1
SP - 13
EP - 33
AB - 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(\sqrt{n}L)$ 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.
LA - eng
KW - convex quadratic programming with a strict equilibrium constraints; interior point algorithm; Newton’s method; Convex quadratic programming with a strict equilibrium constraints; Newton's method
UR - http://eudml.org/doc/245930
ER -

References

top
  1. [1] H.P. Benson, Optimization over the efficient set. J. Math. Anal. Appl. 98 (1984) 562–580. Zbl0534.90077
  2. [2] H.P. Benson, An algorithm for optimizing over the weakly-efficient set. European J. Oper. Res. 25 (1986) 192–199. Zbl0594.90082
  3. [3] Y. Chen and M. Florian, O-D demand adjustment problem with cojestion: Part I. Model analysis and optimality conditions. Publication CRT-94-56. Zbl0874.90078
  4. [4] C. Cinquini and R. Contro, Optimal design of beams discretized by elastic plastic finite element. Comput. Structures 20 (1985) 475–585. Zbl0581.73103
  5. [5] A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minmization Techniques. John Wiley, New York (1968). Zbl0193.18805MR243831
  6. [6] D. Gale, The theory of Linear Economic. McGraw-Hill Book Company, New York (1960). MR115801
  7. [7] C. Gonzaga, Path-following methods for linear programming. SIAM Rev. 34 (1992) 167–274. Zbl0763.90063
  8. [8] D. Goldfarb and S. Liu, An O ( n 3 L ) primal interior point algorithm for convex quadratic programming. Math. Prog. 49 (1990/91) 325–340. Zbl0717.90055
  9. [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). Zbl0952.49034MR1460001
  10. [10] G. Maier, A quadratic programming approach for certain classes of nonlinear structural problems. Meccanica 3 (1968) 121–130. Zbl0165.28502
  11. [11] D.C. Monteiro and I. Adler, Interior path following primal-dual algorithms. Part I: Linear programming. Math. Prog. 44 (1989) 27–41. Zbl0676.90038
  12. [12] Z.Q. Luo, J.S Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints. Cambridge University Press (1996). Zbl0898.90006MR1419501

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.