A feasible sequential linear equation method for inequality constrained optimization

Yu Fei Yang, Dong Hui Li, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)

Abstract

In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m × m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems.
Original languageEnglish
Pages (from-to)1222-1244
Number of pages23
JournalSIAM Journal on Optimization
Volume13
Issue number4
DOIs
Publication statusPublished - 20 Nov 2003

Keywords

  • Active set strategy
  • Global convergence
  • Optimization
  • Sequential linear equation algorithm
  • Superlinear convergence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Cite this