×

SOS-convex semialgebraic programs and its applications to robust optimization: a tractable class of nonsmooth convex optimization. (English) Zbl 1393.90083

Summary: In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with \(\ell_{1}\)-egularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting.

MSC:

90C25 Convex programming
90C22 Semidefinite programming
90C31 Sensitivity, stability, parametric optimization

Software:

CVX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahmadi, AA; Parrilo, PA, A complete characterization of the gap between convexity and SOS-convexity, SIAM J. Optim., 23, 811-833, (2013) · Zbl 1295.52009 · doi:10.1137/110856010
[2] Belousov, EG; Klatte, D, A Frank-Wolfe type theorem for convex polynomial programs, Comp. Optim. Appl., 22, 37-48, (2002) · Zbl 1029.90054 · doi:10.1023/A:1014813701864
[3] Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. analysis, algorithms, and engineering applications. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia PA (2001) · Zbl 0986.90032
[4] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton U.P., Princeton (2009) · Zbl 1221.90001 · doi:10.1515/9781400831050
[5] Bochnak, J., Coste, M., Roy, M.F.: Real Algebraic Geometry, vol. 36, p. x + 430. Springer, Berlin (1998) · Zbl 0912.14023 · doi:10.1007/978-3-662-03718-8
[6] Borwein, J.M., Vanderwerff, J.D.: Convex Functions: Constructions, Characterizations and Counterexamples Encyclopedia of Mathematics and Its Applications, vol. 109. Cambridge University Press, Cambridge (2010) · Zbl 1191.26001 · doi:10.1017/CBO9781139087322
[7] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[8] Bertsimas, D; Sim, M, The price of robustness, Oper. Res., 52, 35-53, (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065
[9] Bertsimas, D; Brown, DB; Caramanis, C, Theory and applications of robust optimization, SIAM Rev., 53, 464-501, (2011) · Zbl 1233.90259 · doi:10.1137/080734510
[10] CVX Research, Inc.C.VX.: Matlab software for disciplined convex programming, version 2.0. http://cvxr.com/cvx (2011) · Zbl 1338.90452
[11] Dinh, D., Goberna, M.A., López, M.A., Volle, M.: A unifying approach to robust convex infinite optimization duality. to appear in J. Optim. Theory & Appl. https://doi.org/10.1007/s10957-017-1136-x (2017) · Zbl 1373.90101
[12] Goberna, MA; Jeyakumar, V; Li, G; López, MA, Robust linear semi-infinite programming duality under uncertainty, Math. Program., 139, 185-203, (2013) · Zbl 1282.90204 · doi:10.1007/s10107-013-0668-6
[13] Goldfarb, D; Iyengar, G, Robust convex quadratically constrained programs, Math. Program., 97, 495-515, (2003) · Zbl 1106.90365 · doi:10.1007/s10107-003-0425-3
[14] Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs, recent advances in learning and control. In: Blondel, V., Boyd, S., Kimura, H. (eds.) Lecture notes in control and information sciences, pp. 95-110. Springer (2008) · Zbl 1205.90223
[15] Helton, JW; Nie, JW, Semidefinite representation of convex sets, Math. Program., 122, 21-64, (2010) · Zbl 1192.90143 · doi:10.1007/s10107-008-0240-y
[16] Jeyakumar, V; Li, G, Strong duality in robust convex programming: complete characterizations, SIAM J. Optim., 20, 3384-3407, (2010) · Zbl 1228.90075 · doi:10.1137/100791841
[17] Jeyakumar, V; Li, G, A new class of alternative theorems for SOS-convex inequalities and robust optimization, Appl. Anal., 94, 56-74, (2015) · Zbl 1338.90302 · doi:10.1080/00036811.2013.859251
[18] Jeyakumar, V; Li, G, Exact SDP relaxations for classes of nonlinear semidefinite programming problems, Oper. Res. Letters, 40, 529-536, (2012) · Zbl 1287.90047 · doi:10.1016/j.orl.2012.09.006
[19] Jeyakumar, V; Li, G; Vicente-Pérez, J, Robust SOS-convex polynomial optimization problems: exact SDP relaxations, Optim. Letters, 9, 1-18, (2015) · Zbl 1338.90452 · doi:10.1007/s11590-014-0732-z
[20] Jeyakumar, V; Vicente-Pérez, J, Dual semidefinite programs without duality gaps for a class of convex minimax programs, J. Optim. Theory Appl., 162, 735-753, (2014) · Zbl 1312.90087 · doi:10.1007/s10957-013-0496-0
[21] Lasserre, J.B.: Moments, Positive Polynomials and their Applications. Imperial College Press, London (2009) · doi:10.1142/p665
[22] Lasserre, JB, Convexity in semialgebraic geometry and polynomial optimization, SIAM J. Optim., 19, 1995-2014, (2008) · Zbl 1181.90216 · doi:10.1137/080728214
[23] Jeyakumar, V; Li, GY; Lee, GM, A robust von Neumann minimax theorem for zero-sum games under bounded payoff uncertainty, Oper. Res. Letters, 39, 109-114, (2011) · Zbl 1218.91006 · doi:10.1016/j.orl.2011.02.007
[24] Lee, GM; Pham, TS, Stability and genericity for semialgebraic compact programs, J. Optim. Theory Appl., 169, 473-495, (2016) · Zbl 1338.90320 · doi:10.1007/s10957-016-0910-5
[25] Li, G; Jeyakumar, V; Lee, GM, Robust conjugate duality for convex optimization under uncertainty with application to data classification, Nonlinear Anal., 74, 2327-2341, (2011) · Zbl 1233.90231 · doi:10.1016/j.na.2010.11.036
[26] Zou, H; Hastie, T, Regularization and variable selection via the elastic net, J. R. Statist. Soc. B, 67, 310-320, (2005) · Zbl 1069.62054
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.