A guide to conic optimisation and its applications

Letchford, Adam N.; Parkes, Andrew J.

doi:10.1051/ro/2018034

Letchford, Adam N.¹ ; Parkes, Andrew J.¹

RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1087-1106.

Résumé

Most OR academics and practitioners are familiar with linear programming (LP) and its applications. Many are however unaware of conic optimisation, which is a powerful generalisation of LP, with a prodigious array of important real-life applications. In this invited paper, we give a gentle introduction to conic optimisation, followed by a survey of applications in OR and related areas. Along the way, we try to help the reader develop insight into the strengths and limitations of conic optimisation as a tool for solving real-life problems.

MR Zbl

DOI : 10.1051/ro/2018034

Classification : 90-01, 90C22, 90C90
Mots clés : Conic optimisation, second-order cone programming, semidefinite programming

Affiliations des auteurs :

Letchford, Adam N. ¹ ; Parkes, Andrew J. ¹

@article{RO_2018__52_4-5_1087_0,
     author = {Letchford, Adam N. and Parkes, Andrew J.},
     title = {A guide to conic optimisation and its applications},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1087--1106},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {4-5},
     year = {2018},
     doi = {10.1051/ro/2018034},
     mrnumber = {3878619},
     zbl = {1411.90256},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018034/}
}

TY  - JOUR
AU  - Letchford, Adam N.
AU  - Parkes, Andrew J.
TI  - A guide to conic optimisation and its applications
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 1087
EP  - 1106
VL  - 52
IS  - 4-5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018034/
DO  - 10.1051/ro/2018034
LA  - en
ID  - RO_2018__52_4-5_1087_0
ER  -

%0 Journal Article
%A Letchford, Adam N.
%A Parkes, Andrew J.
%T A guide to conic optimisation and its applications
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 1087-1106
%V 52
%N 4-5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018034/
%R 10.1051/ro/2018034
%G en
%F RO_2018__52_4-5_1087_0

Letchford, Adam N.; Parkes, Andrew J. A guide to conic optimisation and its applications. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1087-1106. doi : 10.1051/ro/2018034. http://www.numdam.org/articles/10.1051/ro/2018034/

Bibliographie
Cité par

[1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13–51. | DOI | MR | Zbl

[2] F. Alizadeh and D. Goldfarb, Second-order cone programming. Math. Program. 95 (2003) 3–51. | DOI | MR | Zbl

[3] F. Alizadeh, J.-P.A. Haeberly and M.L. Overton, Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77 (1997) 111–128. | DOI | MR | Zbl

[4] M. Anjos and J.B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization. Vol. 166 of International Series in OR/MS. Springer, New York (2012). | MR | Zbl

[5] K.M. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43 (2009) 471–484. | DOI | MR | Zbl

[6] K.M. Anstreicher, On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136 (2012) 233–251. | DOI | MR | Zbl

[7] K.M. Anstreicher and S. Burer, Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124 (2010) 33–43. | DOI | MR | Zbl

[8] D. Avis and J. Umemoto, Stronger linear programming relaxations of max-cut. Math. Program. (2003) 97 451–469. | DOI | MR | Zbl

[9] X. Bao, N.V. Sahinidis and M. Tawarmalani, Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129 (2011) 129–157. | DOI | MR | Zbl

[10] S.J. Benson, Y. Ye and X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10 (2000) 443–461. | DOI | MR | Zbl

[11] A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs. Oper. Res. Lett. 25 (1999) 1–13. | DOI | MR | Zbl

[12] A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second order cone. Math. Oper. Res. 26 (2001) 193–205. | DOI | MR | Zbl

[13] D. Bertsekas, Nonlinear Programming, 3rd edn. Athena Scientific, Bellmont, MA (2016). | MR | Zbl

[14] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). | DOI | MR | Zbl

[15] G. Braun, S. Fiorini, S. Pokutta and D. Steurer, Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40 (2015) 756–772. | DOI | MR | Zbl

[16] S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (2009) 479–495. | DOI | MR | Zbl

[17] S. Burer, Copositive programming, in Handbook on Semidefinite, Conic and Polynomial Optimization, edited by M. Anjos and J.B. Lasserre. Springer, New York (2012) 201–218. | DOI | MR

[18] S. Burer and A.N. Letchford, On non-convex quadratic programming with box constraints. SIAM J. Optim. 20 (2009) 1073–1089. | DOI | MR | Zbl

[19] S. Burer and R.D.C. Monteiro, Local minima and convergence in low-rank semidefinite programming. Math. Program. 103 (2005) 427–444. | DOI | MR | Zbl

[20] S.A. Burer and D. Vandenbussche, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113 (2008) 259–282. | DOI | MR | Zbl

[21] V. Chandrasekaran and P. Shah, Relative entropy optimization and its applications. Math. Program. 161 (2017) 1–32. | DOI | MR | Zbl

[22] G.B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, in Activity Analysis of Production and Allocation, edited by T.C. Koopmans. Wiley, New York (1951) 339–347. | MR | Zbl

[23] G.B. Dantzig, Programming and Extensions. Princeton University Press, Princeton, NJ (1963). | MR | Zbl

[24] E. De Klerk, R. Sotirov and U. Truetsch, A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives. INFORMS J. Comput. 27 (2015) 378–391. | DOI | MR | Zbl

[25] J.A. De Loera, R. Hemmecke and M. Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization. Vol. 14 of SIAM-MOS Series on Optimization. SIAM, Philadelphia, PA (2013). | MR | Zbl

[26] C. Delorme and S. Poljak, Combinatorial properties and the complexity of an eigenvalue approximation of the max-cut problem. Eur. J. Combin. 14 (1993) 313–333. | DOI | MR | Zbl

[27] M.M. Deza and M. Laurent, Geometry of Cuts and Metrics. Springer-Verlag, Berlin (1997). | DOI | MR | Zbl

[28] M. Dür,Copositive programming: a survey, in Recent Advances in Optimization and its Applications in Engineering, edited by M. Diehl et al. Springer, Berlin (2010) 3–20. | DOI

[29] T. Fujie and M. Kojima, Semidefinite programming relaxation for nonconvex quadratic programs. J. Glob. Optim. 10 (1997) 367–380. | DOI | MR | Zbl

[30] L. Galli, K. Kaparis and A.N. Letchford, Complexity results for the gap inequalities for the max-cut problem. Oper. Res. Lett. 40 (2012) 149–152. | DOI | MR | Zbl

[31] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237–267. | DOI | MR | Zbl

[32] F. Glineur, An extended conic formulation for geometric optimization. Found. Comput. Decis. Sci. 25 (2000) 161–174. | MR | Zbl

[33] F. Glineur and T. Terlaky, Conic formulation for ℓ_p-norm optimization. J. Optim. Th. Appl. 122 (2004) 285–307. | DOI | MR | Zbl

[34] M.X. Goemans, Semidefinite programming in combinatorial optimization. Math. Program. 79 (1997) 143–161. | DOI | MR | Zbl

[35] M.X. Goemans and F. Rendl, Combinatorial optimization, in Handbook of Semidefinite Programming, edited by H. Wolkowicz, E. Saigal and L. Vandenberghe. Springer, New York (2000) 343–360. | DOI | MR | Zbl

[36] M.X. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (1995) 1115–1145. | DOI | MR | Zbl

[37] J. Gondzio, Interior point methods 25 years later. Eur. J. Oper. Res. 218 (2012) 587–601. | DOI | MR | Zbl

[38] M. Grötschel, L. Lovász and A.J. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981) 169–197. | DOI | MR | Zbl

[39] M. Grötschel, L. Lovász and A.J. Schrijver, Geometric Algorithms and Combinatorial Optimization. Wiley, New York (1988). | DOI | MR | Zbl

[40] M. Hall Jr., Discrete problems, in A Survey of Numerical Analysis, edited by J. Todd. McGraw-Hill, New York (1962) 518–542. | MR

[41] F.M. Harris, How many parts to make at once. Factory 10 (1913) 135–136, 152.

[42] J. Håstad, Clique is hard to approximate within n^1−ϵ. Acta Math. 182 (1999) 105–142. | DOI | MR | Zbl

[43] C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952–969. | DOI | MR | Zbl

[44] C. Helmberg, Semidefinite programming. Eur. J. Oper. Res. 137 (2002) 461–482. | DOI | MR | Zbl

[45] C. Helmberg and F. Rendl, Solving quadratic (0, 1)-programs by semidefinite programs and cutting planes. Math. Program. 82 (1998) 291–315. | DOI | MR | Zbl

[46] C. Helmberg and F. Rendl, A spectral bundle method for semidenite programming. SIAM J. Optim. 10 (1999) 673–696. | DOI | MR | Zbl

[47] N. Higham, Computing the nearest correlation matrix—A problem from finance. IMA J. Numer. Anal. 22 (2002) 329–343. | DOI | MR | Zbl

[48] R.A. Horn, Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2012). | DOI | MR | Zbl

[49] R. Horst, P.M. Pardalos and N. Thoai, Introduction to Global Optimization, 2nd edn. Kluwer, Dortrecht (2000). | DOI | MR

[50] C.R. Johnson, Matrix completion problems: a survey, in Matrix Theory and Applications, edited by C.R. Johnson. American Mathematical Society, Providence, RI (1990) 171–198. | DOI | MR | Zbl

[51] L.G. Khachiyan, A polynomial algorithm in linear programming. Soviet Math. Doklady 20 (1979) 191–194. | Zbl

[52] K. Krishnan and J.E. Mitchell, A unifying framework for several cutting plane methods for semidefinite programming. Optim. Meth. Soft. 21 (2006) 57–74. | DOI | MR | Zbl

[53] Y.-J. Kuo and H.D. Mittelmann, Interior-point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004) 255–285. | DOI | MR | Zbl

[54] J.B. Lasserre, Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796–817. | DOI | MR | Zbl

[55] M. Laurent, A connection betweeen positive semidefinite and Euclidean distance matrix completion problems. Lin. Alg. Appl. 273 (1998) 9–22. | DOI | MR | Zbl

[56] M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28 (2003) 470–496. | DOI | MR | Zbl

[57] M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope. Lin. Alg. Appl. 223/224 (1995) 439–461. | DOI | MR | Zbl

[58] M. Laurent and S. Poljak, Gap inequalities for the cut polytope. Eur. J. Combin. 17 (1996) 233–254. | DOI | MR | Zbl

[59] M. Laurent and F. Rendl, Semidefinite programming and integer programming, in Handbook on Discrete Optimization, edited by K. Aardal et al. Elsevier Amsterdam (2005) 393–514. | DOI | Zbl

[60] C. Lémaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in Advances in Convex Analysis and Global Optimization, edited by N. Hadjisawas and P.M. Pardalos. Kluwer, Dortrecht (2001) 119–134. | DOI | MR | Zbl

[61] L. Liberti, C. Lavor, N. Maculan and A. Mucherino, Euclidean distance geometry and applications. SIAM Rev. 56 (2014) 3–69. | DOI | MR | Zbl

[62] M.S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming. Lin. Alg. Appl. 284 (1998) 193–228. | DOI | MR | Zbl

[63] L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Th. IT-25 (1979) 1–7. | DOI | MR | Zbl

[64] L. Lovász, Semidefinite programs and combinatorial optimization, in Recent Advances in Algorithms and Combinatorics, edited by B. Reed and C.L. Sales. Springer, New York (2003) 137–194. | MR | Zbl

[65] L. Lovász and A.J. Schrijver, Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1 (1991) 166–190. | DOI | MR | Zbl

[66] Z.-Q. Luo, W.-K. Ma, A.M.-C. So, Y. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27 (2010) 20–34. | DOI

[67] J. Malick, J. Povh, F. Rendl and A. Wiegele, Regularization methods for semidefinite programming. SIAM J. Optim. 20 (2009) 336–356. | DOI | MR | Zbl

[68] H.M. Markowitz, Portfolio selection. J. Finance 7 (1952) 77–91.

[69] J.E. Mitchell, Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems. J. Combin. Optim. 5 (2001) 151–166. | DOI | MR | Zbl

[70] H.D. Mittelmann, The state-of-the-art in conic optimization software, in Handbook on Semidefinite, Conic and Polynomial Optimization, edited by M. Anjos and J.B. Lasserre. Springer, New York (2012) 671–686. | DOI | MR

[71] T.S. Motzkin, Copositive quadratic forms. Nat. Bur. Stand. Rep. 1818 (1952) 11–22.

[72] K.G. Murty and S.N. Kabadi, Some $𝒩𝒫$ -complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. | DOI | MR | Zbl

[73] Y. Nesterov and A. Nemirovsky, Interior Point Methods in Convex Programming: Theory and Applications. SIAM Press, Philadelphia, PA (1994). | MR

[74] Y. Nesterov, H. Wolkowicz and Y. Ye, Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, in Handbook of Semidefinite Programming, edited by H. Wolkowicz, E. Saigal and L. Vandenberghe. Springer, New York (2000) 361–419. | DOI | MR | Zbl

[75] J. Nie, K. Ranestad and B. Sturmfels, The algebraic degree of semidefinite programming. Math. Program. 122 (2010) 379–405. | DOI | MR | Zbl

[76] R. O’Donnell, SOS is not Obviously Automatizable, Even Approximately. ECCC Report No. 141 (2016). | MR

[77] M.W. Padberg, On the facial structure of set packing polyhedra. Math. Program. 5 (1973) 199–215. | DOI | MR | Zbl

[78] P. Parrilo, Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96 (2003) 293–320. | DOI | MR | Zbl

[79] S. Poljak and F. Rendl, Non-polyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5 (1995) 467–487. | DOI | MR | Zbl

[80] S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7 (1995) 51–73. | DOI | MR | Zbl

[81] S. Poljak and Zs. Tuza, The expected relative error of the polyhedral approximation of the max-cut problem. Oper. Res. Lett. 16 (1994) 191–198. | DOI | MR | Zbl

[82] J. Povh, F. Rendl and A. Wiegele, A boundary point method to solve semidefinite programs. Computing, 78 (2009) 277–286. | DOI | MR | Zbl

[83] M. Ramana, An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems. PhD thesis, Johns Hopkins University, Baltimore, MD (1993). | MR

[84] M.V. Ramana, An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77 (1997) 129–162. | DOI | MR | Zbl

[85] F. Rendl, Semidefinite relaxations for integer programming, in 50 Years of Integer Programming 1958-2008, edited by M. Jünger et al. Springer, Heidelberg (2010) 687–726. | DOI | Zbl

[86] F. Rendl, Semidefinite relaxations for partitioning, assignment and ordering problems. 4OR 10 (2012) 321–346. | DOI | MR | Zbl

[87] I.J. Schoenberg, Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 (1938) 522–536. | DOI | JFM | MR

[88] C. Seligman, Online Astronomy Text. Available at: http://cseligman.com/text/history/ellipses.htm (1993).

[89] H.D. Sherali and W.P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3 (1990) 411–430. | DOI | MR | Zbl

[90] N.Z. Shor, Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25 (1987) 1–11. | MR | Zbl

[91] N.Z. Shor, Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25 (1990) 163–168. | DOI | MR | Zbl

[92] A. Skajaa, E.D. Andersen and Y. Ye, Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems. Math. Program. Comput. 5(2013) 1–25. | DOI | MR | Zbl

[93] M.J. Todd, Semidefinite optimization. Acta Numerica 10 (2001) 515–560. | DOI | MR | Zbl

[94] L. Vanderberghe and S. Boyd, Semidefinite programming. SIAM Rev. 38 (1996) 49–95. | DOI | MR | Zbl

[95] P. Wang, C. Shen, A. Van Den Hengel and P.H.S. Torr, Large-scale binary quadratic optimization using semidefinite relaxation and applications. IEEE Trans. Patt. Anal. Mach. Intel. 39 (2017) 470–485. | DOI

[96] Z. Wen,D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2 (2010) 203–230. | DOI | MR | Zbl

[97] H. Wolkowicz, E. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming. Vol. 27 of International Series in OR/MS. Springer, New York (2000). | MR | Zbl

[98] H. Wolkowicz and M.F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems. Discr. Appl. Math. 123 (2002) 513–577 | DOI | MR | Zbl

[99] H. Ziegler, Solving certain singly constrained convex optimization problems in production planning. Oper. Res. Lett. 1 (1982) 246–252. | DOI | MR | Zbl

Cité par Sources :