Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints.

*(English)*Zbl 1406.90114##### MSC:

90C30 | Nonlinear programming |

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

65K05 | Numerical mathematical programming methods |

49M37 | Numerical methods based on nonlinear programming |

##### Keywords:

mathematical programs with complementarity constraints; second order methods; M-stationarity
PDF
BibTeX
Cite

\textit{R. Andreani} et al., SIAM J. Optim. 28, No. 3, 2574--2600 (2018; Zbl 1406.90114)

Full Text:
DOI

##### References:

[1] | R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, Second-order negative-curvature methods for box-constrained and general constrained optimization, Comput. Optim. Appl., 45 (2010), pp. 209–236, . · Zbl 1187.90265 |

[2] | R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18 (2007), pp. 1286–1309, . · Zbl 1151.49027 |

[3] | R. Andreani, C. Dunder, and J. M. Martínez, Nonlinear-programming reformulation of the order-value optimization problem, Math. Methods Oper. Res., 61 (2005), pp. 365–384, . · Zbl 1114.90464 |

[4] | R. Andreani, G. Haeser, and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization, 60 (2011), pp. 627–641, . · Zbl 1225.90123 |

[5] | R. Andreani, G. Haeser, A. Ramos, and P. J. S. Silva, A second-order sequential optimality condition associated to the convergence of optimization algorithms, IMA J. Numer. Anal., 37 (2017), pp. 1902–1929, . · Zbl 1433.90156 |

[6] | R. Andreani, G. Haeser, M. L. Schuverdt, and P. J. S. Silva, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135 (2012), pp. 255–273, . · Zbl 1262.90162 |

[7] | R. Andreani, J. M. Martínez, A. Ramos, and P. J. S. Silva, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26 (2016), pp. 96–110, . · Zbl 1329.90162 |

[8] | M. Anitescu, Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints, SIAM J. Optim., 16 (2005), pp. 120–145, . · Zbl 1099.65050 |

[9] | M. Anitescu, On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints, SIAM J. Optim., 15 (2005), pp. 1203–1236, . · Zbl 1097.90050 |

[10] | M. Anitescu, P. Tseng, and S. J. Wright, Elastic-mode algorithms for mathematical programs with equilibrium constraints: Global convergence and stationarity properties, Math. Program., 110 (2007), pp. 337–371, . · Zbl 1119.90050 |

[11] | E. G. Birgin and J. M. Martínez, Improving ultimate convergence of an augmented Lagrangian method, Optim. Methods Softw., 23 (2008), pp. 177–195, . · Zbl 1211.90222 |

[12] | E. G. Birgin and J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, Fundam. Algorithms 10, SIAM, Philadelphia, PA, 2014, . |

[13] | E. G. Birgin and J. M. Martínez, Large-scale active-set box-constrained optimization method with spectral projected gradients, Comput. Optim. Appl., 23 (2002), pp. 101–125, . · Zbl 1031.90012 |

[14] | E. G. Birgin and J. M. Martínez, Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput. Optim. Appl., 51 (2012), pp. 941–965, . · Zbl 1244.90216 |

[15] | E. G. Birgin, J. M. Martínez, and M. Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal., 23 (2003), pp. 539–559, . · Zbl 1047.65042 |

[16] | S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), pp. 333–359, . · Zbl 1140.90493 |

[17] | F. Facchinei, H. Jiang, and L. Qi, A smoothing method for mathematical programs with equilibrium constraints, Math. Program., 85 (1999), pp. 107–134, . · Zbl 0959.65079 |

[18] | M. C. Ferris and J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997), pp. 669–713, . · Zbl 0891.90158 |

[19] | M. L. Flegel and C. Kanzow, On the Guignard constraint qualification for mathematical programs with equilibrium constraints, Optimization, 54 (2005), pp. 517–534, . · Zbl 1147.90397 |

[20] | M. L. Flegel and C. Kanzow, A direct proof for M-stationarity under MPEC-GCQ for mathematical programs with equilibrium constraints, in Optimization with Multivalued Mappings, S. Dempe and V. Kalashnikov, eds., Springer, Boston, MA, 2006, pp. 111–122, . · Zbl 1125.90062 |

[21] | M. L. Flegel, C. Kanzow, and J. V. Outrata, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Anal., 15 (2007), pp. 139–162, . · Zbl 1149.90143 |

[22] | R. Fletcher and S. Leyffer, Numerical Experience with Solving MPECs as NLPs, Numerical Analysis Report 210, University of Dundee, 2002. |

[23] | R. Fletcher, S. Leyffer, D. Ralph, and S. Scholtes, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM J. Optim., 17 (2006), pp. 259–286, . · Zbl 1112.90098 |

[24] | L. Guo, G.-H. Lin, and J. J. Ye, Second-order optimality conditions for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 158 (2013), pp. 33–64, . · Zbl 1272.90089 |

[25] | L. Guo, G.-H. Lin, D. Zhang, and D. Zhu, An MPEC reformulation of an EPEC model for electricity markets, Oper. Res. Lett., 43 (2015), pp. 262–267, . · Zbl 1408.91164 |

[26] | M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl., 4 (1969), pp. 303–320, . · Zbl 0174.20705 |

[27] | T. Hoheisel, C. Kanzow, and A. Schwartz, Convergence of a local regularization approach for mathematical programmes with complementarity or vanishing constraints, Optim. Methods Softw., 27 (2012), pp. 483–512, . · Zbl 1266.90170 |

[28] | T. Hoheisel, C. Kanzow, and A. Schwartz, Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Program., 137 (2013), pp. 257–288, . · Zbl 1262.65065 |

[30] | X. M. Hu and D. Ralph, Convergence of a penalty method for mathematical programming with complementarity constraints, J. Optim. Theory Appl., 123 (2004), pp. 365–390, . |

[31] | A. F. Izmailov, M. V. Solodov, and E. I. Uskov, Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints, SIAM J. Optim., 22 (2012), pp. 1579–1606, . · Zbl 1274.90385 |

[32] | A. Kadrani, J.-P. Dussault, and A. Benchakroun, A new regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 20 (2009), pp. 78–103, . · Zbl 1187.65064 |

[33] | A. Kadrani, J. P. Dussault, and A. Benchakroun, A globally convergent algorithm for MPCC, EURO J. Comput. Optim., 3 (2015), pp. 263–296, . |

[34] | C. Kanzow and A. Schwartz, Mathematical programs with equilibrium constraints: Enhanced Fritz John-conditions, new constraint qualifications, and improved exact penalty results, SIAM J. Optim., 20 (2010), pp. 2730–2753, . · Zbl 1208.49016 |

[35] | C. Kanzow and A. Schwartz, A new regularization method for mathematical programs with complementarity constraints with strong convergence properties, SIAM J. Optim., 23 (2013), pp. 770–798, . · Zbl 1282.65069 |

[36] | C. Kanzow and A. Schwartz, The price of inexactness: Convergence properties of relaxation methods for mathematical programs with complementarity constraints revisited, Math. Oper. Res., 40 (2015), pp. 253–275, . · Zbl 1344.90058 |

[37] | S. Leyffer, G. López-Calva, and J. Nocedal, Interior methods for mathematical programs with complementarity constraints, SIAM J. Optim., 17 (2006), pp. 52–77, . · Zbl 1112.90095 |

[38] | G.-H. Lin and M. Fukushima, A modified relaxation scheme for mathematical programs with complementarity constraints, Ann. Oper. Res., 133 (2005), pp. 63–84, . · Zbl 1119.90058 |

[39] | X. Liu and J. Sun, Generalized stationary points and an interior-point method for mathematical programs with equilibrium constraints, Math. Program., 101 (2004), pp. 231–261, . · Zbl 1076.90059 |

[40] | H. Z. Luo, X. L. Sun, and Y. F. Xu, Convergence properties of modified and partially-augmented Lagrangian methods for mathematical programs with complementarity constraints, J. Optim. Theory Appl., 145 (2010), pp. 489–506, . · Zbl 1213.90230 |

[41] | Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996, . |

[42] | J. Outrata, M. Kocvara, and J. Zowe, Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, 1st ed., Nonconvex Optim. Appl. 28, Springer, New York, 1998, . · Zbl 0947.90093 |

[43] | J. V. Outrata, Optimality conditions for a class of mathematical programs with equilibrium constraints: Strongly regular case, Kybernetika, 35 (1999), pp. 177–193. · Zbl 1274.90484 |

[44] | E. E. Ovtchinnikov, Jacobi correction equation, line search, and conjugate gradients in hermitian eigenvalue computation I: Computing an extreme eigenvalue, SIAM J. Numer. Anal., 46 (2008), pp. 2567–2592, . · Zbl 1176.65043 |

[45] | M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, R. Fletcher, ed., Academic Press, New York, 1969, pp. 283–298. |

[46] | A. Ramos, Mathematical Programs with Equilibrium Constraints: A Sequential Optimality Condition, New Constraint Qualifications and Algorithmic Consequences, , 2016. |

[47] | R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12 (1974), pp. 268–285, . · Zbl 0257.90046 |

[48] | H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Math. Oper. Res., 25 (2000), pp. 1–22, . · Zbl 1073.90557 |

[49] | S. Scholtes, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11 (2001), pp. 918–936, . · Zbl 1010.90086 |

[50] | S. Steffensen and M. Ulbrich, A new relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 20 (2010), pp. 2504–2539, . · Zbl 1231.90350 |

[51] | H. Xu, J.-S. Pang, F. Ordón͂ez, and M. Dessouky, Complementarity models for traffic equilibrium with ridesharing, Transp. Res. B Methodol., 81 (2015), pp. 161–182, . |

[52] | X. Yang and X. Huang, Convergence analysis of an augmented Lagrangian method for mathematical programs with complementarity constraints, Nonlinear Anal., 63 (2005), pp. e2247–e2256, https://doi.org/10.1016/j.na.2005.03.027. |

[53] | X. Q. Yang and X. X. Huang, Lower-order penalty methods for mathematical programs with complementarity constraints, Optim. Methods Softw., 19 (2004), pp. 693–720, . · Zbl 1068.90102 |

[54] | J. J. Ye, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307 (2005), pp. 350–369, . · Zbl 1112.90062 |

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.