×

Lifting mathematical programs with complementarity constraints. (English) Zbl 1250.90094

A problem of minimization of a criterion \(f(x)\) subject to a constraint \[ x\in M = \left\{ x\in{\mathbb{R}}^n\;| \, (F_j^1(x),F_j^2(x))\in L, j=1,2,\ldots,k \right\} \] where \[ L=\left\{(a,b)\in\mathbb{R}^2\;| a\geq0,\,b\geq0,\, ab=0\right\} \] is called a problem of mathematical programming with complementary constraints (MPCC). The set \(L\) is not smooth. Instead of approximating \(L\) with a smooth set in \(\mathbb{R}^2\), the authors propose to interpret the set \(L\) as the orthogonal projection of a smooth set in \(\mathbb{R}^3\). The proposed lifting construction transforms an MPCC into a smooth problem with additional \(k\) parameters. The extended problem inherits some properties of the original MPCC. For example, it is obtained that the modified problem inherits the the linear independence constraint qualification from the original MPCC. The criticality in the modified problem is equivalent to the weak stationarity in the original MPCC.
A modified problem is perturbed by adding to the target criterion a linear functional, which is the dot product of a vector \(t\) and a vector whose components are the additional variables. Such a perturbation is called tilting. For a weakly stationary point \(\bar{x}\) in the original MPCC, tilting stability means that there exists a family of critical points for the respective tilted problems, which is continuous in \(t\) and which yields \(\bar{x}\) for \(t=0\). It is obtained that if \(\bar{x}\) is a nondegenerate {C}-stationary point for the original {MPCC}, then it is tilting stable and the respective critical points in tilted problems are unique and, in a certain sense, regular.
The authors present results of computations for a number of examples. A comparison between the lifting method and direct smoothing of the original MPCC suggests that both methods produce accurate results. However, the direct smoothing approach performs faster, which is attributed to the multi-step nature of the lifting approach.

MSC:

90C31 Sensitivity, stability, parametric optimization
65K05 Numerical mathematical programming methods

Software:

OPECgen; MacMPEC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anitescu M.: On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236 (2005) · Zbl 1097.90050 · doi:10.1137/S1052623402401221
[2] Anitescu M., Tseng P., Wright S.J.: Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math. Program. 110, 337–371 (2007) · Zbl 1119.90050 · doi:10.1007/s10107-006-0005-4
[3] Benson H.Y., Sen A., Shanno D.F., Vanderbei R.J.: Interior point algorithms, penalty methods and equilibrium problems. Comput. Optim. Appl. 34, 155–182 (2006) · Zbl 1121.90124 · doi:10.1007/s10589-005-3908-8
[4] Bouza Allende, G.: Mathematical programs with equilibrium constraints: solution techniques from parametric optimization, Ph.D. thesis, University of Twente (2006)
[5] de Miguel A., Friedlander M., Nogales F., Scholtes S.: An interior-point method for MPECS. SIAM J. Optim. 16, 587–609 (2005) · Zbl 1122.90060 · doi:10.1137/04060754x
[6] Facchinei F., Jiang H., Qi L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 81–106 (1999) · Zbl 0958.65078 · doi:10.1007/s101070050047
[7] 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) · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[8] Fukushima M., Pang J.: Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: Théra, M., Tichatschke, R. (eds) Ill-posed Variational Problems and Regularization Techniques. Lecture Notes in Economics and Mathematical Systems, vol. 447, pp. 99–110, pp. 99–110. Springer, Heidelberg (1999) · Zbl 0944.65070
[9] Fukushima M., Tseng P.: An implementable active-set algorithm for computing a b-stationary point of a mathematical program with linear complementarity constraints. SIAM J. Optim. 12, 724–739 (2002) · Zbl 1005.65064 · doi:10.1137/S1052623499363232
[10] Giallombardo G., Ralph D.: Multiplier convergence in trust region methods with application to convergence of decomposition methods for MPECs. Math. Program. 112, 335–369 (2008) · Zbl 1145.90073 · doi:10.1007/s10107-006-0020-5
[11] Hu X., Ralph D.: Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 (2004) · doi:10.1007/s10957-004-5154-0
[12] Huang X.X., Yang X.Q., Zhu D.L.: A sequential smooth penalization approach to mathematical programs with complementarity constraints. Numer. Funct. Anal. Optim. 27, 71–98 (2006) · Zbl 1119.90051 · doi:10.1080/01630560500538797
[13] Jiang H., Ralph D.: QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13, 25–59 (1999) · Zbl 1040.90500 · doi:10.1023/A:1008696504163
[14] Jiang H., Ralph D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25, 123–150 (2002) · Zbl 1038.90100 · doi:10.1023/A:1022945316191
[15] Jongen H.Th., Jonker P., Twilt F.: Critical sets in parametric optimization. Math. Program. 34, 333–353 (1986) · Zbl 0599.90114 · doi:10.1007/BF01582234
[16] Jongen H.Th., Meer K., Triesch E.: Optimization Theory. Kluwer, Boston (2004)
[17] Jongen H.Th., Möbert T., Rückmann J.-J., Tammer K.: On inertia and Schur complement in optimization. Linear Algebra Appl. 95, 97–109 (1987) · Zbl 0642.90091 · doi:10.1016/0024-3795(87)90028-0
[18] Jongen H.Th., Rückmann J.-J., Shikhman V.: On stability of the feasible set of a mathematical program with complementarity constraints. SIAM J. Optim. 20, 1171–1184 (2009) · Zbl 1213.90242 · doi:10.1137/08072694X
[19] Jongen H.Th., Rückmann J.-J., Shikhman V.: MPCC: critical point theory. SIAM J. Optim. 20, 473–484 (2009) · Zbl 1229.90139 · doi:10.1137/080733693
[20] Kočvara M., Outrata J., Zowe J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Kluwer, Dordrecht (1998) · Zbl 0947.90093
[21] Leyffer, S.: MacMPEC–ampl collection of Mathematical Programs with Equilibrium Constraints. http://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC (2009)
[22] Lin G., Fukushima M.: Hybrid approach with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128, 1–28 (2006) · Zbl 1130.90047 · doi:10.1007/s10957-005-7549-y
[23] Liu X., Perakis G., Sun J.: A robust SQP method for mathematical programs with linear complementarity constraints. Comput. Optim. Appl. 34, 5–33 (2006) · Zbl 1111.90110 · doi:10.1007/s10589-005-3075-y
[24] Luo Z.-Q., Pang J.S., Ralph D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
[25] Luo Z.-Q., Pang J.S., Ralph D.: Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints. In: Migdalas, A., Pardalos, P., Värbrand, P. (eds) Multilevel Optimization: Algorithms, Complexity, and Applications, pp. 209–229. Kluwer Academic Publishers, Dordrecht (1998) · Zbl 0897.90184
[26] Ouellette D.V.: Schur complements and statistics. Linear Algebra Appl. 36, 187–295 (1981) · Zbl 0455.15012 · doi:10.1016/0024-3795(81)90232-9
[27] Poliquin R.A., Rockafellar R.T.: Tilt stability of a local minimum. SIAM J. Optim. 8, 287–299 (1998) · Zbl 0918.49016 · doi:10.1137/S1052623496309296
[28] Raghunathan A.U., Biegler L.T.: Interior point methods for mathematical programs with complementarity constraints. SIAM J. Optim. 15, 720–750 (2005) · Zbl 1077.90079 · doi:10.1137/S1052623403429081
[29] Ralph, D., Stein, O.: Homotopy methods for quadratic programs with complementarity constraints. Preprint No. 120, Department of Mathematics - C, RWTH Aachen University (2006)
[30] Ralph D., Wright S.J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 (2004) · Zbl 1097.90054 · doi:10.1080/10556780410001709439
[31] Scheel H., Scholtes S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 (2000) · Zbl 1073.90557 · doi:10.1287/moor.25.1.1.15213
[32] Scholtes S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[33] Scholtes S., Stöhr M.: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37, 617–652 (1999) · Zbl 0922.90128 · doi:10.1137/S0363012996306121
[34] Stöhr M.: Nonsmooth trust region methods and their applications to mathematical programs with equilibrium constraints. Shaker-Verlag, Aachen (1999)
[35] Wächter A., Biegler L.T.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16, 1–31 (2005) · Zbl 1114.90128 · doi:10.1137/S1052623403426556
[36] Wächter A., Biegler L.T.: Line search filter methods for nonlinear programming: local convergence. SIAM J. Optim. 16, 32–48 (2005) · Zbl 1115.90056 · doi:10.1137/S1052623403426544
[37] Zhang J., Liu G.: A new extreme point algorithm and its application in psqp algorithms for solving mathematical programs with linear complementarity constraints. J. Glob. Optim. 19, 335–361 (2001) · Zbl 1049.90125
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.