×
Li, Jianling; Huang, Renshuai; Jian, Jinbao

A superlinearly convergent QP-free algorithm for mathematical programs with equilibrium constraints. (English) Zbl 1410.90216

Appl. Math. Comput. 269, 885-903 (2015).
Summary: In this paper, based on the smoothing techniques and the working set techniques, a QP-free algorithm for mathematical programs with equilibrium constraints (MPEC for short) is presented. Firstly, by Fischer-Burmeister function and smoothing techniques, the discussed problem is approximated by a smooth constrained optimization problem. Secondly, the working set, which is used to construct systems of linear equations, is generated by pivoting operation. At each iteration, the search direction is yielded by solving two or three systems of equations with the same coefficient matrix. Under mild conditions, the global convergence and superlinear convergence are shown. Moreover, we can conclude that the current iterative point is an exact stationary point of the discussed problem if the proposed algorithm stops after finite iterations. Finally, preliminary numerical results are reported.

Cited in 5 Documents

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Keywords:

equilibrium constraints; mathematical programs; QP-free algorithm; global convergence; superlinear convergence

Software:

MacMPEC
Cite Review PDF
Full Text: DOI

References:

[1] Luo, Z. Q.; Pang, J. S.; Ralph, D., Mathematical Programs with Equilibrium Constraints (1996), Cambridge University Press
[2] Outrata, J.; Kocvara, M.; Zowe, J., Nonsmooth approach to optimization problems with equilibrium constraints (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Netherlands · Zbl 0947.90093
[3] Jiang, H. Y.; Ralph, D., Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM J. Optim., 10, 779-808 (2000) · Zbl 0955.90134
[4] Jian, J. B., A superlinearly convergent implicit smooth SQP algorithm for mathematical programs with nonlinear complementarity constraints, Comput. Optim. Appl., 31, 335-361 (2005) · Zbl 1122.90095
[5] Li, J. L.; Jian, J. B., A superlinearly convergent SSLE algorithm for optimization problems with linear complementarity constraints, J. Global Optim., 33, 477-510 (2005) · Zbl 1097.90063
[6] Fukushima, M.; Luo, Z. Q.; Pang, J. S., A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 10, 5-34 (1998) · Zbl 0904.90153
[7] Jian, J. B.; Li, J. L.; Mo, X. D., A strongly and superlinearly convergent SQP algorithm for optimization problems with linear complementarity constraints, Appl. Math. Optim., 54, 17-46 (2006) · Zbl 1136.90514
[8] Zhu, Z. B.; Zhang, K. C., A superlinearly convergent SQP algorithm for mathematical programs with linear complementarity constraints, Appl. Math. Comput., 172, 222-244 (2006) · Zbl 1098.65072
[9] Lin, G. H.; Fukushima, M., A modified relaxation scheme for mathematical programs with complementarity constraints, Ann. Oper. Res., 133, 63-84 (2005) · Zbl 1119.90058
[10] Steffensen, S.; Ulbrich, M., A new relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 20, 2504-2539 (2010) · Zbl 1231.90350
[11] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Prog., 137, 257-288 (2013) · Zbl 1262.65065
[12] Luo, H. Z.; Sun, X. L.; Xu, Y. F.; Wu, H. X., On the convergence properties of modified augmented Lagrangian methods for mathematical programming with complementarity constraints, J. Global Optim., 46, 217-232 (2010) · Zbl 1191.90069
[13] 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
[14] Gao, Z. Y.; He, G. P.; Wu, F., A sequential systems of linear equations method with arbitrary initial point, Sci. China, 27, 24-33 (1997)
[15] Qi, H. D.; Qi, L. Q., A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization, SIAM J. Optim., 11, 113-132 (2000) · Zbl 0999.90038
[16] Tits, A. L.; Wachter, A.; Bakhtiari, S.; Urban, T. J.; Lawrence, C. T., A primal-dual interior-point method for nonlinear programming with strong global and local convergence Pproperties, SIAM J. Optim., 14, 173-199 (2003) · Zbl 1075.90078
[17] Jian, J. B.; Quan, R.; Cheng, W. X., A feasible QP-free algorithm combining the interior point method with active set for constrained optimization, Comput. Math. Appl., 58, 1520-1533 (2009) · Zbl 1189.90199
[18] Ma, C. F.; Liang, G. P., A new successive approximation damped Newton method for nonlinear complementarity problems, J. Math. Res. Expo., 23, 1-6 (2003) · Zbl 1026.90086
[19] Cottle, R. W.; Pang, J. S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press Boston · Zbl 0757.90078
[20] Jian, J. B.; Pan, H. Q., A strongly sub-feasible primal-dualquasi interior-point algorithm for nonlinear inequality constrained optimization, Appl. Math. Comput., 266, 560-578 (2015) · Zbl 1410.90201
[21] Jian, J. B., Fast Algorithms for Smooth Constrained Optimization: Theoretical Analysis and Numerical Experiments (2010), Science Press
[23] De, J. F.A.; Pantoja, O.; Mayne, D. Q., Exact penalty function algorithm with simple updating of the penalty parameter, J. Optim. Theory Appl., 69, 441-467 (1991) · Zbl 0724.90065
[24] Fletcher, R.; Leyffer, S., Solving mathematical programs with complementarity constraints as nonlinear programs, Optim. Methods Softw., 19, 15-40 (2004) · Zbl 1074.90044
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.