J. Comp. Math., 24 (2006), pp. 591-608.

A New Constraints Identification Technique-Based QP-Free Algorithm For The Solution Of Inequality Constrained Minimization Problems

Chang-yin Zhou 1, Guo-ping He 2, Yong-li Wang 2

1 Department of Mathematics, Shanghai Jiao Tong University, Shanghai 200240, China
2 College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510, China

Received 2004-3-20 Revised 2005-12-9 Online 2006-9-14 Accepted


In this paper, we propose a feasible QP-free method for solving nonlinear inequality constrained optimization problems. A new working set is proposed to estimate the active set. Specially, to determine the working set, the new method makes use of the multiplier information from the previous iteration, eliminating the need to compute a multiplier function. At each iteration, two or three reduced symmetric systems of linear equations with a common coefficient matrix involving only constraints in the working set are solved, and when the iterate is sufficiently close to a KKT point, only two of them are involved. Moreover, the new algorithm is proved to be globally convergent to a KKT point under mild conditions. Without assuming the strict complementarity, the convergence rate is superlinear under a condition weaker than the strong second-order sufficiency condition. Numerical experiments illustrate the efficiency of the algorithm.

Key words: QP-free method; Optimization; Global convergence; Superlinear convergence; Constraints identification technique.


The Global Science Journal