×

zbMATH — the first resource for mathematics

Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra. (English) Zbl 1435.90097
Summary: We consider minimizing a conic quadratic objective over a polyhedron. Such problems arise in parametric value-at-risk minimization, portfolio optimization, and robust optimization with ellipsoidal objective uncertainty; and they can be solved by polynomial interior point algorithms for conic quadratic optimization. However, interior point algorithms are not well-suited for branch-and-bound algorithms for the discrete counterparts of these problems due to the lack of effective warm starts necessary for the efficient solution of convex relaxations repeatedly at the nodes of the search tree. In order to overcome this shortcoming, we reformulate the problem using the perspective of the quadratic function. The perspective reformulation lends itself to simple coordinate descent and bisection algorithms utilizing the simplex method for quadratic programming, which makes the solution methods amenable to warm starts and suitable for branch-and-bound algorithms. We test the simplex-based quadratic programming algorithms to solve convex as well as discrete instances and compare them with the state-of-the-art approaches. The computational experiments indicate that the proposed algorithms scale much better than interior point algorithms and return higher precision solutions. In our experiments, for large convex instances, they provide up to 22x speed-up. For smaller discrete instances, the speed-up is about 13x over a barrier-based branch-and-bound algorithm and 6x over the LP-based branch-and-bound algorithm with extended formulations. The software that was reviewed as part of this submission was given the Digital Object identifier doi:10.5281/zenodo.1489153.

MSC:
90C20 Quadratic programming
90C49 Extreme-point and pivoting methods
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahmed, S., Atamtürk, A.: Maximizing a class of submodular utility functions. Math. Program. 128, 149-169 (2011) · Zbl 1218.90221
[2] Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13-51 (1995) · Zbl 0833.90087
[3] Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program. 95, 3-51 (2003) · Zbl 1153.90522
[4] Atamtürk, A., Goméz, A.,: Submodularity in conic quadratic mixed 0-1 optimization. arXiv preprint arXiv:1705.05918, (2016). BCOL Research Report 16.02, UC Berkeley
[5] Atamtürk, A., Jeon, H.: Lifted polymatroid inequalities for mean-risk optimization with indicator variables. arXiv preprint arXiv:1705.05915, (2017). BCOL Research Report 17.01, UC Berkeley
[6] Atamtürk, A., Narayanan, V.: Cuts for conic mixed-integer programming. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 16-29. Springer, Berlin (2007) ISBN 978-3-540-72792-7 · Zbl 1136.90518
[7] Atamtürk, A., Narayanan, V.: Polymatroids and risk minimization in discrete optimization. Oper. Res. Lett. 36, 618-622 (2008) · Zbl 1210.90127
[8] Atamtürk, A., Narayanan, V.: The submodular 0-1 knapsack polytope. Discrete Optim. 6, 333-344 (2009) · Zbl 1179.90270
[9] Atamtürk, A., Deck, C., Jeon, H.: Successive quadratic upper-bounding for discrete mean-risk minimization and network interdiction. arXiv preprint arXiv:1708.02371, (2017). BCOL Reseach Report 17.05, UC Berkeley. Forthcoming in INFORMS Journal on Computing
[10] Aybat, N.S., Iyengar, G.: A first-order smoothed penalty method for compressed sensing. SIAM J. Optim. 21, 287-313 (2011) · Zbl 1219.90123
[11] Belloni, A., Chernozhukov, V., Wang, L.: Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika 98, 791-806 (2011) · Zbl 1228.62083
[12] Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., Mahajan, A.: Mixed-integer nonlinear optimization. Acta Numerica 22, 1131 (2013) · Zbl 1291.65172
[13] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23, 769-805 (1998) · Zbl 0977.90052
[14] Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1-13 (1999) · Zbl 0941.90053
[15] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2001) · Zbl 0986.90032
[16] Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009) · Zbl 1221.90001
[17] Bertsimas, D., Sim, M.: Robust discrete optimization under ellipsoidal uncertainty sets (2004) (unpublished)
[18] Bertsimas, D., King, A., Mazumder, R., et al.: Best subset selection via a modern optimization lens. Ann. Stat. 44, 813-852 (2016) · Zbl 1335.62115
[19] Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74, 121-140 (1996) · Zbl 0855.90090
[20] Borchers, B., Mitchell, J.E.: An improved branch and bound algorithm for mixed integer nonlinear programs. Comput. Oper. Res. 21, 359-367 (1994) · Zbl 0797.90069
[21] Çay, S.B., Pólik, I., Terlaky, T.: Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames, May 2017. ISE Technical Report 17T-006, Lehigh University
[22] Dantzig, G.B., Orden, A., Wolfe, P.: The generalized simplex method for minimizing a linear form under linear inequality restraints. Pac. J. Math. 5, 183-196 (1955) · Zbl 0064.39402
[23] Dinh, T., Fukasawa, R., Luedtke, J.: Exact Algorithms for the Chance-Constrained Vehicle Routing Problem, pp. 89-101. Springer, New York (2016) · Zbl 1419.90093
[24] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R., et al.: Least angle regression. Ann. Stat. 32, 407-499 (2004) · Zbl 1091.62054
[25] El Ghaoui, L., Oks, M., Oustry, F.: Worst-case value-at-risk and robust portfolio optimization: a conic programming approach. Oper. Res. 51, 543-556 (2003) · Zbl 1165.91397
[26] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. Springer, New York (2013) · Zbl 0795.49001
[27] Ishii, H., Shiode, S., Nishida, T., Namasuya, Y.: Stochastic spanning tree problem. Discrete Appl. Math. 3, 263-273 (1981) · Zbl 0466.90056
[28] Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302-311. ACM (1984) · Zbl 0557.90065
[29] Leyffer, S.: Integrating SQP and branch-and-bound for mixed integer nonlinear programming. Comput. Optim. Appl. 18, 295-309 (2001) · Zbl 1009.90074
[30] Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl 284, 193-228 (1998) · Zbl 0946.90050
[31] Megiddo, N.: On finding primal- and dual-optimal bases. INFORMS J. Comput. 3, 63-65 (1991) · Zbl 0755.90056
[32] Nemirovski, A., Scheinberg, K.: Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems. Math. Program. 72, 273-289 (1996) · Zbl 0853.90092
[33] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127-152 (2005) · Zbl 1079.90102
[34] Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics (1994). URL http://epubs.siam.org/doi/abs/10.1137/1.9781611970791
[35] Nesterov, Y.E., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324-364 (1998) · Zbl 0922.90110
[36] Nikolova, E., Kelner, J.A., Brand, M., Mitzenmacher, M.: Stochastic shortest paths via quasi-convex maximization. In: European Symposium on Algorithms, pp. 552-563. Springer, New York (2006) · Zbl 1131.05317
[37] Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225-249 (2005) · Zbl 1099.90047
[38] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc Ser. B (Methodological) 58, 267-288 (1996) · Zbl 0850.62538
[39] Van de Panne, C., Whinston, A.: Simplicial methods for quadratic programming. Naval Res. Log. Q. 11(3-4), 273-302 (1964) · Zbl 0136.14104
[40] Vielma, J.P., Dunning, I., Huchette, J., Lubin, M.: Extended formulations in mixed integer conic quadratic programming. Math. Program. Comput. (2015). https://doi.org/10.1007/s125312-016-0113-y · Zbl 1387.90165
[41] Wolfe, P.: The simplex method for quadratic programming. Economet. J. Economet. Soc. 27, 382-398 (1959) · Zbl 0103.37603
[42] Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optim. 12, 782-810 (2002) · Zbl 1007.90079
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.