Sequential systems of linear equations method for general constrained optimization without strict complementarity.

*(English)*Zbl 1078.65055The authors propose a new infeasible sequential systems of linear equations (SSLE) algorithm for solving an equality and inequality constrained optimization problem (P), based on an \(\mathit{l}_1 - \text\textit{l}_\infty\) exact penalty function and the extended active set identification technique. The initial point of the new algorithm may be any point in the \(\alpha\)-perturbation set of the feasible set. At each iteration, only two or three reduced linear equations with the same coefficients are solved to obtain the search direction.

An automatic adjustment rule for the choice of penalty parameter is also incorporated in the new algorithm which ensures that the penalty parameter be updated only finitely many times. Under a linear independence condition, the algorithm globally converges to a KKT point of the problem (P). It is shown that the convergence rate of the new algorithm is one-step superlinear without strict complementarity and under a condition weaker than the strong second-order sufficiency condition. Many numerical experiments show the good properties of the new algorithm.

An automatic adjustment rule for the choice of penalty parameter is also incorporated in the new algorithm which ensures that the penalty parameter be updated only finitely many times. Under a linear independence condition, the algorithm globally converges to a KKT point of the problem (P). It is shown that the convergence rate of the new algorithm is one-step superlinear without strict complementarity and under a condition weaker than the strong second-order sufficiency condition. Many numerical experiments show the good properties of the new algorithm.

Reviewer: Nada Djuranović-Miličić (Belgrade)

##### Keywords:

sequential systems of linear equations method; linear independence; strict complementarity; global convergence; superlinear convergence; algorithm; constrained optimization; penalty function; active set identification technique; numerical experiments
PDF
BibTeX
XML
Cite

\textit{Y. Wang} et al., J. Comput. Appl. Math. 182, No. 2, 447--471 (2005; Zbl 1078.65055)

Full Text:
DOI

##### References:

[1] | Bonnans, J.F., Local analysis of Newton type methods for variational inequalities and nonlinear programming, Appl. math. optim., 29, 161-186, (1994) · Zbl 0809.90115 |

[2] | Facchinei, F., Minimization of \(\mathit{SC}^1\)-function and the maratos effect, Oper. res. lett., 17, 131-137, (1995) · Zbl 0843.90108 |

[3] | Facchinei, F., Robust recursive quadratic programming algorithm model with global and superlinear convergence properties, J. optim. theory appl., 92, 543-579, (1997) · Zbl 0871.90058 |

[4] | Facchinei, F.; Fischer, A.; Kanzow, C., On the accurate identification of active constraints, SIAM J. optim., 9, 14-32, (1999) · Zbl 0960.90080 |

[5] | A.L. Tits, A. Wächter, S. Bakhtiari et al., A primal – dual interior point method for nonlinear programming with strong global and local convergence properties. ISR Technical Report TR 2002-29, University of Maryland, College Park, 2002. · Zbl 1075.90078 |

[6] | Facchinei, F.; Lucidi, S., Quadratically and superlinearly convergent algorithm for the solution of inequality constrained minimization problems, J. optim. theory appl., 85, 265-289, (1995) · Zbl 0830.90125 |

[7] | F. Facchinei, S. Lucidi, L. Palagi, A truncated Newton algorithm for large scale box constrained optimization, Technical Report 15-99, Dipartimento di Informatica e Sistemistica, University di La Sapienza, Roma, 1999. · Zbl 1035.90103 |

[8] | Gao, Z.; He, G.; Wu, F., Sequential systems of linear equation algorithm with arbitrary initial point, Sci. China (ser. A), 27, 24-33, (1997) |

[9] | Gao, Z.; He, G.; Wu, F., Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints, J. optim. theory appl., 95, 371-397, (1997) · Zbl 0892.90163 |

[10] | Gao, Z.; He, G.; Wu, F., Sequential systems of linear equations algorithm for nonlinear optimization problems—general constrained problems, Appl. math. comput., 147, 211-226, (2004) · Zbl 1044.65051 |

[11] | W. Hock, K. Schittkowski, Test problems for nonlinear programming codes, Lecture Notes in Economics and Mathematical Systems, vol. 187, Springer, Berlin, 1981. · Zbl 0452.90038 |

[12] | Kanzow, C.; Qi, H., A QP-free constrained Newton-type method for variational inequality problems, Math. programming, 85, 81-106, (1999) · Zbl 0958.65078 |

[13] | Lucidi, S., New results on a continuously differentiable penalty function, SIAM J. optim., 2, 558-574, (1992) · Zbl 0761.90089 |

[14] | Panier, E.R.; Tits, A.L.; Herskovits, J.N., A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. control optim., 26, 788-811, (1988) · Zbl 0651.90072 |

[15] | M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, Numerical Analysis (Proceedings of the 7th Biennial Conference, University of Dundee, 1977), Lecture Notes in Mathematics, vol. 630, Springer, Berlin, 1978, pp. 144-157. |

[16] | Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. oper. res., 18, 227-244, (1993) · Zbl 0776.65037 |

[17] | Qi, H.; Qi, L., A new QP-free globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. optim., 11, 113-132, (2000) · Zbl 0999.90038 |

[18] | Qi, L.; Yang, Y., Globally and superlinearly convergent QP-free algorithm for nonlinear constrained optimization, J. optim. theory appl., 113, 297-323, (2002) · Zbl 1027.90089 |

[19] | Y. Yang, L. Qi, A feasible sequential systems of linear equations method for inequality constrained optimization, AMR00/27, Applied Mathematics Report, University of New South Wales, Sydney, 2000. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.