Solving Mathematical Programs with Equilibrium Constraints
Tóm tắt
This paper aims at developing effective numerical methods for solving mathematical programs with equilibrium constraints. Due to the existence of complementarity constraints, the usual constraint qualifications do not hold at any feasible point, and there are various stationarity concepts such as Clarke, Mordukhovich, and strong stationarities that are specially defined for mathematical programs with equilibrium constraints. However, since these stationarity systems contain some unknown index sets, there has been no numerical method for solving them directly. In this paper, we remove the unknown index sets from these stationarity systems successfully, and reformulate them as smooth equations with box constraints. We further present a modified Levenberg–Marquardt method for solving these constrained equations. We show that, under some weak local error bound conditions, the method is locally and superlinearly convergent. Furthermore, we give some sufficient conditions for local error bounds, and show that these conditions are not very stringent by a number of examples.
Tài liệu tham khảo
Luo, Z.Q., Pang, J.S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge, UK (1996)
Outrata, J.V., Kocvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Kluwer Academic Publishers, Boston (1998)
Ye, J.J., Zhu, D.L., Zhu, Q.J.: Exact penalization and necessary optimality conditions for generalized bilevel programming problems. SIAM J. Optim. 7, 481–507 (1997)
Guo, L., Lin, G.H., Ye, J.J.: Stability analysis for parametric mathematical programs with geometric constraints and its applications. SIAM J. Optim. 22, 1151–1176 (2012)
Guo, L., Lin, G.H., Ye, J.J., Zhang, J.: Sensitivity analysis for parametric mathematical programs with equilibrium constraints. SIAM J. Optim. 24, 1206–1237 (2014)
Scheel, H.S., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000)
Ye, J.J.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 307, 350–369 (2005)
Ye, J.J., Ye, X.Y.: Necessary optimality conditions for optimization problems with variational inequality constraints. Math. Oper. Res. 22, 977–997 (1997)
Fukushima, M., Lin, G.H.: Smoothing methods for mathematical programs with equilibrium constraints. In: Proceedings of the ICKS’04, pp. 206–213. IEEE Computer Society Press, Los Alamitos (2004)
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming Theory and Algorithms. Wiley, New York (1993)
Kanzow, C., Yamashita, N., Fukushima, M.: Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 172, 375–397 (2004)
Fan, J.Y., Yuan, Y.X.: On the quadratic convergence of the Levenberg–Marquardt method without nonsingularity assumption. Computing 74, 23–39 (2005)
Behling, R., Fischer, A.: A unified local convergence analysis of inexact constrained Levenberg–Marquardt methods. Optim. Lett. 6, 927–940 (2012)
Wu, Z., Ye, J.J.: First-order and second-order conditions for error bounds. SIAM J. Optim. 14, 621–645 (2003)
Hoffman, A.J.: On approximate solutions of systems of linear equalities. J. Res. Nat. Bur. Stand. 49, 263–265 (1952)
Jourani, A.: Constraint qualifications and Lagrange multipliers in nondifferentiable programming problems. J. Optim. Theory Appl. 81, 533–548 (1994)
Minchenko, L., Stakhovski, S.: Parametric nonlinear programming problems under the relaxed constant rank condition. SIAM J. Optim. 21, 314–332 (2011)
Guo, L., Ye, J.J., Zhang, J.: Mathematical programs with geometric constraints in Banach spaces: enhanced optimality, exact penalty, and sensitivity. SIAM J. Optim. 23, 2295–2319 (2013)
Scholtes, S., Stöhr, M.: Exact penalization of mathematical programs with complementarity constraints. SIAM J. Control Optim. 37, 617–652 (1999)
Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17, 259–286 (2006)
Huang, X.X., Yang, X.Q., Teo, K.L.: Partial augmented Lagrangian method and mathematical programs with complementarity constraints. J. Global Optim. 35, 235–254 (2006)
Yang, X.Q., Huang, X.X.: Lower-order penalty methods for mathematical programs with complementarity constraints. Optim. Methods Softw. 19, 693–720 (2004)