×

zbMATH — the first resource for mathematics

An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation. (English) Zbl 07379934
Summary: The worst-case linear optimization (WCLO) with uncertainties in the right-hand-side of the constraints often arises from numerous applications such as systemic risk estimate in finance and stochastic optimization, which is known to be NP-hard. In this paper, we investigate the efficient global algorithm for WCLO based on its nonlinear semidefinite relaxation (SDR). We first derive an enhanced nonlinear SDR for WCLO via secant cuts and RLT approaches. A secant search algorithm is then proposed to solve the nonlinear SDR and its global convergence is established. Second, we propose a new global algorithm for WCLO, which integrates the nonlinear SDR with successive convex optimization method, initialization and branch-and-bound, to find a globally optimal solution to the underlying WCLO within a pre-specified \(\epsilon \)-tolerance. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to the WCLO instances.
MSC:
90C47 Minimax problems in mathematical programming
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher, K., Semidefinite programming versus the reformulation linearization technique for nonconvex quadratically constrained quadratic programming, J. Glob. Optim., 43, 471-484 (2009) · Zbl 1169.90425
[2] Anstreicher, K.; Burer, S., Computable representations for convex hulls of lowdimensional quadratic forms, Math. Program. (Ser. B), 124, 33-43 (2010) · Zbl 1198.90311
[3] Ben-Tal, A., Robust convex optimization, Math. Oper. Res., 23, 4, 769-805 (1998) · Zbl 0977.90052
[4] Ben-Tal, A.; Ghaoui, L.; El Nemirovski, A., Robust Optimization (2009), Princeton: Princeton University Press, Princeton
[5] Ben-Tal, A.; Goryashko, A.; Guslitzer, E., Adjustable robust solutions of uncertain linear programs, Math. Program., 99, 2, 351-376 (2004) · Zbl 1089.90037
[6] Ben-Tal, A.; Nemirovski, A., Robust solutions of uncertain linear programs, Oper. Res. Lett., 25, 1, 1-14 (1999) · Zbl 0941.90053
[7] Bertsimas, D.; Brown, D.; Caramanis, C., Theory and applications of robust optimization, SIAM Rev., 53, 3, 464-501 (2011) · Zbl 1233.90259
[8] Bertsimas, D.; Goyal, V., On the power of robust solutions in two-stage stochastic and adaptive optimization problems, Math. Oper. Res., 35, 2, 284-305 (2010) · Zbl 1218.90141
[9] Bertsimas, D.; Goyal, V., On the power and limitations of affine policies in two-stage adaptive optimization, Math. Program., 34, 2, 491-531 (2012) · Zbl 1267.90083
[10] Birge, J.; Louveaux, F., Introduction to Stochastic Programming (1997), Berlin: Springer, Berlin · Zbl 0892.90142
[11] Burer, S.; Dong, H., Representing quadratically constrained quadratic programs as generalized copositive programs, Oper. Res. Lett., 40, 3, 203-206 (2012) · Zbl 1245.90080
[12] Burer, S.; Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Math. Program., 113, 2, 259-282 (2008) · Zbl 1135.90034
[13] Burer, S.; Vandenbussche, D., Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Comput. Optim. Appl., 43, 2, 181-195 (2009) · Zbl 1170.90522
[14] Chen, J.; Burer, S., Globally solving nonconvex quadratic programming problems via completely positive programming, Math. Program. Comput., 4, 33-52 (2012) · Zbl 1257.90065
[15] Chen, X.; Sim, M.; Sun, P., A robust optimization perspective on stochastic programming, Oper. Res., 55, 6, 1058-1071 (2007) · Zbl 1167.90608
[16] Clarke, FH, Optimization and Nonsmooth Analysis (1983), New York: Wiley, New York · Zbl 0582.49001
[17] Eisenberg, L.; Noe, T., Systemic risk in financial systems, Manag. Sci., 47, 2, 236-249 (2001) · Zbl 1232.91688
[18] Floudas, C., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P. M. (eds): Handbook of Global Optimization, pp. 217-270. Kluwer Academic Publishers, Boston (1994) · Zbl 0833.90091
[19] Goemans, M.; Williamson, D., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[20] Grant, M., Boyd, S., Ye, Y.: CVX: Matlab software for disciplined convex programming. http://www.stanford.edu/boyd/cvx
[21] IBM ILOG CPLEX. IBM ILOG CPLEX 12.6 user’s manual for CPLEX (2013). http://www.cplex.com
[22] Lasserre, J., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[23] Le Thi, HA; Pham Dinh, T., Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms, J. Glob. Optim., 11, 253-285 (1997) · Zbl 0905.90131
[24] Luo, HZ; Bai, XD; Peng, JM, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, J. Optim. Appl., 180, 3, 964-992 (2019) · Zbl 1409.90130
[25] Luo, HZ; Bai, XD; Lim, G.; Peng, JM, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Math. Program. Comput., 11, 1, 119-171 (2019) · Zbl 1411.90251
[26] Luo, HZ; Ding, XD; Peng, JM; Jiang, RJ; Li, D., Complexity results and effective algorithms for worst-case linear optimization under uncertainties, INFORMS J. Comput., 33, 1, 180-197 (2021) · Zbl 07362310
[27] Nesterov, Y., Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., 9, 140-160 (1998) · Zbl 0904.90136
[28] Pardalos, P., Global optimization algorithms for linearly constrained indefinite quadratic problems, Comput. Math. Appl., 21, 87-97 (1991) · Zbl 0733.90051
[29] Parrilo, P., Semidefinite programming relaxations for semialgebraic problems, Math. Program., 96, 2, 293-320 (2003) · Zbl 1043.14018
[30] Peng, J.; Tao, Z., A nonlinear semidefinite optimization relaxation for the worst-case linear optimization under uncertainties, Math. Program., 152, 1, 593-614 (2015) · Zbl 1327.90106
[31] Peng, J.; Tao, Z.; Luo, HZ; Toh, K., Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, Comput. Optim. Appl., 60, 1, 171-198 (2015) · Zbl 1338.90295
[32] Saxena, A.; Bonami, P.; Lee, J., Convex relaxation of non-convex mixed integer quadratically constrained programs: extended formulations, Math. Program. (Ser. B), 124, 383-411 (2010) · Zbl 1198.90330
[33] Saxena, A.; Bonami, P.; Lee, J., Convex relaxation of nonconvex mixed integer quadratically constrained programs: projected formulations, Math. Program., 130, 359-413 (2011) · Zbl 1229.90144
[34] Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1998) · Zbl 0926.90078
[35] Toh, K.; Todd, M.; Tutuncu, R., SDPT3: Matlab software package for semidefinite programming, Optim. Methods Softw., 11, 12, 545-581 (1999) · Zbl 0997.90060
[36] Vandenbussche, D.; Nemhauser, G., A branch-and-cut algorithm for nonconvex quadratic programming with box constraints, Math. Program., 102, 559-575 (2005) · Zbl 1137.90010
[37] Xu, G.; Burer, S., Robust sensitivity analysis of the optimal value of linear programming, Optim. Methods Softw., 32, 6, 1187-1205 (2017) · Zbl 1382.90105
[38] Ye, Y., Approximating quadratic programming with bound and quadratic constraints, Math. Program., 84, 2, 219-226 (1999) · Zbl 0971.90056
[39] Zheng, XJ; Sun, XL; Li, D., Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, Math. Program. (Ser. B), 129, 301-329 (2011) · Zbl 1236.90089
[40] Zheng, XJ; Sun, XL; Li, D., Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations, J. Glob. Optim., 50, 695-712 (2011) · Zbl 1254.90151
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.