×

A comparison of solution approaches for the numerical treatment of or-constrained optimization problems. (English) Zbl 1461.65175

Summary: Mathematical programs with or-constraints form a new class of disjunctive optimization problems with inherent practical relevance. In this paper, we provide a comparison of three different solution methods for the numerical treatment of this problem class which are inspired by classical approaches from disjunctive programming. First, we study the replacement of the or-constraints as nonlinear inequality constraints using suitable NCP-functions. Second, we transfer the or-constrained program into a mathematical program with switching or complementarity constraints which can be treated with the aid of well-known relaxation methods. Third, a direct Scholtes-type relaxation of the or-constraints is investigated. A numerical comparison of all these approaches which is based on three essentially different model programs from or-constrained optimization closes the paper.

MSC:

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

Software:

Ipopt
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Balas, E., Disjunctive Programming (2018), Cham: Springer, Cham · Zbl 1414.90001
[2] Bazaraa, MS; Sherali, HD; Shetty, CM, Nonlinear Programming: Theory and Algorithms (1993), New York: Wiley, New York · Zbl 0774.90075
[3] Benko, M.; Gfrerer, H., New verifiable stationarity concepts for a class of mathematical programs with disjunctive constraints, Optimization, 67, 1, 1-23 (2018) · Zbl 1398.90169 · doi:10.1080/02331934.2017.1387547
[4] Clarke, FH, Optimization and Nonsmooth Analysis (1983), New York: Wiley, New York · Zbl 0582.49001
[5] Clason, C.; Deng, Y.; Mehlitz, P.; Prüfert, U., Optimal control problems with control complementarity constraints, Optim. Methods Softw., 35, 1, 142-170 (2019) · Zbl 1429.49025 · doi:10.1080/10556788.2019.1604705
[6] Clason, C.; Rund, A.; Kunisch, K., Nonconvex penalization of switching control of partial differential equations, Syst. Control Lett., 106, 1-8 (2017) · Zbl 1376.49035 · doi:10.1016/j.sysconle.2017.05.006
[7] De Luca, T.; Facchinei, F.; Kanzow, C., A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75, 3, 407-439 (1996) · Zbl 0874.90185 · doi:10.1007/BF02592192
[8] De Luca, T.; Facchinei, F.; Kanzow, C., A theoretical and numerical comparison of some semismooth algorithms for complementarity problems, Comput. Optim. Appl., 16, 2, 173-205 (2000) · Zbl 0964.90046 · doi:10.1023/A:1008705425484
[9] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[10] Facchinei, F.; Jiang, H.; Qi, L., A smoothing method for mathematical programs with equilibrium constraints, Math. Program., 85, 1, 107-134 (1999) · Zbl 0959.65079 · doi:10.1007/s10107990015a
[11] Facchinei, F.; Soares, J., A new merit function for nonlinear complementarity problems and a related algorithm, SIAM J. Optim., 7, 1, 225-247 (1997) · Zbl 0873.90096 · doi:10.1137/S1052623494279110
[12] Fischer, A., A special Newton-type optimization method, Optimization, 24, 3-4, 269-284 (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795
[13] Flegel, ML; Kanzow, C., Abadie-type constraint qualification for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 124, 3, 595-614 (2005) · Zbl 1090.90200 · doi:10.1007/s10957-004-1176-x
[14] Flegel, ML; Kanzow, C.; Outrata, JV, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Anal., 15, 2, 139-162 (2007) · Zbl 1149.90143 · doi:10.1007/s11228-006-0033-5
[15] Fletcher, R.; Leyffer, S.; Ralph, D.; Scholtes, S., Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM J. Optim., 17, 1, 259-286 (2006) · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[16] Fukushima, M.; Luo, ZQ; Pang, JS, A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints, Comput. Optim. Appl., 10, 1, 5-34 (1998) · Zbl 0904.90153 · doi:10.1023/A:1018359900133
[17] Galántai, A., Properties and construction of NCP functions, Comput. Optim. Appl., 52, 3, 805-824 (2012) · Zbl 1282.90194 · doi:10.1007/s10589-011-9428-9
[18] Gfrerer, H., Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints, SIAM J. Optim., 24, 2, 898-931 (2014) · Zbl 1298.49021 · doi:10.1137/130914449
[19] Grossmann, IE, Review of nonlinear mixed-integer and disjunctive programming techniques, Optim. Eng., 3, 3, 227-252 (2002) · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[20] Grossmann, IE; Lee, S., Generalized convex disjunctive programming: nonlinear convex Hull relaxation, Comput. Optim. Appl., 26, 1, 83-100 (2003) · Zbl 1030.90069 · doi:10.1023/A:1025154322278
[21] Hoheisel, T.; Kanzow, C.; Schwartz, A., Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints, Math. Program., 137, 1, 257-288 (2013) · Zbl 1262.65065 · doi:10.1007/s10107-011-0488-5
[22] Hooker, JN, Logic, optimization, and constraint programming, INFORMS J. Comput., 14, 4, 295-321 (2002) · Zbl 1238.90002 · doi:10.1287/ijoc.14.4.295.2828
[23] Kanzow, C., Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17, 4, 851-868 (1996) · Zbl 0868.90123 · doi:10.1137/S0895479894273134
[24] Kanzow, C.; Mehlitz, P.; Steck, D., Relaxation schemes for mathematical programmes with switching constraints, Optim. Methods Softw. (2019) · Zbl 1489.65086 · doi:10.1080/10556788.2019.1663425
[25] Kanzow, C.; Schwartz, A., A new regularization method for mathematical programs with complementarity constraints with strong convergence properties, SIAM J. Optim., 23, 2, 770-798 (2013) · Zbl 1282.65069 · doi:10.1137/100802487
[26] Kanzow, C.; Yamashita, N.; Fukushima, M., New NCP-functions and their properties, J. Optim. Theory Appl., 94, 1, 115-135 (1997) · Zbl 0886.90146 · doi:10.1023/A:1022659603268
[27] Leyffer, S.; Dempe, S.; Kalashnikov, V., Complementarity constraints as nonlinear equations: theory and numerical experience, Optimization with Multivalued Mappings: Theory, Applications, and Algorithms, 169-208 (2006), Boston: Springer, Boston · Zbl 1190.90240
[28] Luo, ZQ; Pang, JS; Ralph, D., Mathematical Programs with Equilibrium Constraints (1996), Cambridge: Cambridge University Press, Cambridge
[29] Mehlitz, P., On the linear independence constraint qualification in disjunctive programming, Optimization (2019) · Zbl 1528.90258 · doi:10.1080/02331934.2019.1679811
[30] Mehlitz, P., Stationarity conditions and constraint qualifications for mathematical programs with switching constraints, Math. Program. (2019) · Zbl 1480.90230 · doi:10.1007/s10107-019-01380-5
[31] Mordukhovich, B., Variational Analysis and Generalized Differentiation (2006), Berlin: Springer, Berlin
[32] Outrata, JV; Kočvara, M.; Zowe, J., Nonsmooth Approach to Optimization Problems with Equilibrium Constraints (1998), Dordrecht: Kluwer Academic, Dordrecht · Zbl 0947.90093
[33] Rockafellar, RT; Wets, RJB, Variational Analysis, Grundlehren der mathematischen Wissenschaften (1998), Berlin: Springer, Berlin · Zbl 0888.49001
[34] Scholtes, S., Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J. Optim., 11, 4, 918-936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[35] Steffensen, S.; Ulbrich, M., A new relaxation scheme for mathematical programs with equilibrium constraints, SIAM J. Optim., 20, 5, 2504-2539 (2010) · Zbl 1231.90350 · doi:10.1137/090748883
[36] Sun, D.; Qi, L., On NCP-functions, Comput. Optim. Appl., 13, 1, 201-220 (1999) · Zbl 1040.90544 · doi:10.1023/A:1008669226453
[37] Tröltzsch, F., Optimal Control of Partial Differential Equations (2009), Wiesbaden: Vieweg, Wiesbaden · Zbl 1320.49001
[38] Vinter, R., Optimal Control (2000), New York: Birkhäuser, New York · Zbl 0952.49001
[39] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[40] Ye, JJ, Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints, J. Math. Anal. Appl., 307, 1, 350-369 (2005) · Zbl 1112.90062 · doi:10.1016/j.jmaa.2004.10.032
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.