Voir la notice de l'article provenant de la source Numdam
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.
Letchford, Adam N. 1 ; Parkes, Andrew J. 1
@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ro/2018034/
[1] , Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13–51. | MR | Zbl | DOI
[2] and , Second-order cone programming. Math. Program. 95 (2003) 3–51. | MR | Zbl | DOI
[3] , and , Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77 (1997) 111–128. | MR | Zbl | DOI
[4] and , Handbook on Semidefinite, Conic and Polynomial Optimization. Vol. 166 of International Series in OR/MS. Springer, New York (2012). | MR | Zbl
[5] , Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43 (2009) 471–484. | MR | Zbl | DOI
[6] , On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136 (2012) 233–251. | MR | Zbl | DOI
[7] and , Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124 (2010) 33–43. | MR | Zbl | DOI
[8] and , Stronger linear programming relaxations of max-cut. Math. Program. (2003) 97 451–469. | MR | Zbl | DOI
[9] , and , Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. 129 (2011) 129–157. | MR | Zbl | DOI
[10] , and , Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10 (2000) 443–461. | MR | Zbl | DOI
[11] and , Robust solutions of uncertain linear programs. Oper. Res. Lett. 25 (1999) 1–13. | MR | Zbl | DOI
[12] and , On polyhedral approximations of the second order cone. Math. Oper. Res. 26 (2001) 193–205. | MR | Zbl | DOI
[13] , Nonlinear Programming, 3rd edn. Athena Scientific, Bellmont, MA (2016). | MR | Zbl
[14] and , Convex Optimization. Cambridge University Press, Cambridge (2004). | MR | Zbl | DOI
[15] , , and , Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40 (2015) 756–772. | MR | Zbl | DOI
[16] , On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (2009) 479–495. | MR | Zbl | DOI
[17] , Copositive programming, in Handbook on Semidefinite, Conic and Polynomial Optimization, edited by and . Springer, New York (2012) 201–218. | MR | DOI
[18] and , On non-convex quadratic programming with box constraints. SIAM J. Optim. 20 (2009) 1073–1089. | MR | Zbl | DOI
[19] and , Local minima and convergence in low-rank semidefinite programming. Math. Program. 103 (2005) 427–444. | MR | Zbl | DOI
[20] and , A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113 (2008) 259–282. | MR | Zbl | DOI
[21] and , Relative entropy optimization and its applications. Math. Program. 161 (2017) 1–32. | MR | Zbl | DOI
[22] , Maximization of a linear function of variables subject to linear inequalities, in Activity Analysis of Production and Allocation, edited by Wiley, New York (1951) 339–347. | MR | Zbl
[23] , Programming and Extensions. Princeton University Press, Princeton, NJ (1963). | MR | Zbl
[24] , and , A new semidefinite programming relaxation for the quadratic assignment problem and its computational perspectives. INFORMS J. Comput. 27 (2015) 378–391. | MR | Zbl | DOI
[25] , and , 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] and , Combinatorial properties and the complexity of an eigenvalue approximation of the max-cut problem. Eur. J. Combin. 14 (1993) 313–333. | MR | Zbl | DOI
[27] and , Geometry of Cuts and Metrics. Springer-Verlag, Berlin (1997). | MR | Zbl | DOI
[28] ,Copositive programming: a survey, in Recent Advances in Optimization and its Applications in Engineering, edited by et al. Springer, Berlin (2010) 3–20. | DOI
[29] and , Semidefinite programming relaxation for nonconvex quadratic programs. J. Glob. Optim. 10 (1997) 367–380. | MR | Zbl | DOI
[30] , and , Complexity results for the gap inequalities for the max-cut problem. Oper. Res. Lett. 40 (2012) 149–152. | MR | Zbl | DOI
[31] , and , Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237–267. | MR | Zbl | DOI
[32] , An extended conic formulation for geometric optimization. Found. Comput. Decis. Sci. 25 (2000) 161–174. | MR | Zbl
[33] and , Conic formulation for ℓp-norm optimization. J. Optim. Th. Appl. 122 (2004) 285–307. | MR | Zbl | DOI
[34] , Semidefinite programming in combinatorial optimization. Math. Program. 79 (1997) 143–161. | MR | Zbl | DOI
[35] and , Combinatorial optimization, in Handbook of Semidefinite Programming, edited by , and . Springer, New York (2000) 343–360. | MR | Zbl | DOI
[36] and , Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (1995) 1115–1145. | MR | Zbl | DOI
[37] , Interior point methods 25 years later. Eur. J. Oper. Res. 218 (2012) 587–601. | MR | Zbl | DOI
[38] , and , The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981) 169–197. | MR | Zbl | DOI
[39] , and , Geometric Algorithms and Combinatorial Optimization. Wiley, New York (1988). | MR | Zbl | DOI
[40] , Discrete problems, in A Survey of Numerical Analysis, edited by . McGraw-Hill, New York (1962) 518–542. | MR
[41] , How many parts to make at once. Factory 10 (1913) 135–136, 152.
[42] , Clique is hard to approximate within n1−ϵ. Acta Math. 182 (1999) 105–142. | MR | Zbl | DOI
[43] , Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952–969. | MR | Zbl | DOI
[44] , Semidefinite programming. Eur. J. Oper. Res. 137 (2002) 461–482. | MR | Zbl | DOI
[45] and , Solving quadratic (0, 1)-programs by semidefinite programs and cutting planes. Math. Program. 82 (1998) 291–315. | MR | Zbl | DOI
[46] and , A spectral bundle method for semidenite programming. SIAM J. Optim. 10 (1999) 673–696. | MR | Zbl | DOI
[47] , Computing the nearest correlation matrix—A problem from finance. IMA J. Numer. Anal. 22 (2002) 329–343. | MR | Zbl | DOI
[48] , Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2012). | MR | Zbl | DOI
[49] , and , Introduction to Global Optimization, 2nd edn. Kluwer, Dortrecht (2000). | MR | DOI
[50] , Matrix completion problems: a survey, in Matrix Theory and Applications, edited by . American Mathematical Society, Providence, RI (1990) 171–198. | MR | Zbl | DOI
[51] , A polynomial algorithm in linear programming. Soviet Math. Doklady 20 (1979) 191–194. | Zbl
[52] and , A unifying framework for several cutting plane methods for semidefinite programming. Optim. Meth. Soft. 21 (2006) 57–74. | MR | Zbl | DOI
[53] and , Interior-point methods for second-order cone programming and OR applications. Comput. Optim. Appl. 28 (2004) 255–285. | MR | Zbl | DOI
[54] , Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796–817. | MR | Zbl | DOI
[55] , A connection betweeen positive semidefinite and Euclidean distance matrix completion problems. Lin. Alg. Appl. 273 (1998) 9–22. | MR | Zbl | DOI
[56] , A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming. Math. Oper. Res. 28 (2003) 470–496. | MR | Zbl | DOI
[57] and , On a positive semidefinite relaxation of the cut polytope. Lin. Alg. Appl. 223/224 (1995) 439–461. | MR | Zbl | DOI
[58] and , Gap inequalities for the cut polytope. Eur. J. Combin. 17 (1996) 233–254. | MR | Zbl | DOI
[59] and , Semidefinite programming and integer programming, in Handbook on Discrete Optimization, edited by et al. Elsevier Amsterdam (2005) 393–514. | Zbl | DOI
[60] and , SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in Advances in Convex Analysis and Global Optimization, edited by and Kluwer, Dortrecht (2001) 119–134. | MR | Zbl | DOI
[61] , , and , Euclidean distance geometry and applications. SIAM Rev. 56 (2014) 3–69. | MR | Zbl | DOI
[62] , , and , Applications of second-order cone programming. Lin. Alg. Appl. 284 (1998) 193–228. | MR | Zbl | DOI
[63] , On the Shannon capacity of a graph. IEEE Trans. Inform. Th. IT-25 (1979) 1–7. | MR | Zbl | DOI
[64] , Semidefinite programs and combinatorial optimization, in Recent Advances in Algorithms and Combinatorics, edited by and Springer, New York (2003) 137–194. | MR | Zbl
[65] and , Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1 (1991) 166–190. | MR | Zbl | DOI
[66] , , , and , Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27 (2010) 20–34. | DOI
[67] , , and , Regularization methods for semidefinite programming. SIAM J. Optim. 20 (2009) 336–356. | MR | Zbl | DOI
[68] , Portfolio selection. J. Finance 7 (1952) 77–91.
[69] , Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems. J. Combin. Optim. 5 (2001) 151–166. | MR | Zbl | DOI
[70] , The state-of-the-art in conic optimization software, in Handbook on Semidefinite, Conic and Polynomial Optimization, edited by and . Springer, New York (2012) 671–686. | MR | DOI
[71] , Copositive quadratic forms. Nat. Bur. Stand. Rep. 1818 (1952) 11–22.
[72] and , Some -complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. | MR | Zbl | DOI
[73] and , Interior Point Methods in Convex Programming: Theory and Applications. SIAM Press, Philadelphia, PA (1994). | MR
[74] , and , Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, in Handbook of Semidefinite Programming, edited by , and . Springer, New York (2000) 361–419. | MR | Zbl | DOI
[75] , and , The algebraic degree of semidefinite programming. Math. Program. 122 (2010) 379–405. | MR | Zbl | DOI
[76] , SOS is not Obviously Automatizable, Even Approximately. ECCC Report No. 141 (2016). | MR
[77] , On the facial structure of set packing polyhedra. Math. Program. 5 (1973) 199–215. | MR | Zbl | DOI
[78] , Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96 (2003) 293–320. | MR | Zbl | DOI
[79] and , Non-polyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5 (1995) 467–487. | MR | Zbl | DOI
[80] , and , A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7 (1995) 51–73. | MR | Zbl | DOI
[81] and , The expected relative error of the polyhedral approximation of the max-cut problem. Oper. Res. Lett. 16 (1994) 191–198. | MR | Zbl | DOI
[82] , and , A boundary point method to solve semidefinite programs. Computing, 78 (2009) 277–286. | MR | Zbl | DOI
[83] , An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems. PhD thesis, Johns Hopkins University, Baltimore, MD (1993). | MR
[84] , An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77 (1997) 129–162. | MR | Zbl | DOI
[85] , Semidefinite relaxations for integer programming, in 50 Years of Integer Programming 1958-2008, edited by et al. Springer, Heidelberg (2010) 687–726. | Zbl | DOI
[86] , Semidefinite relaxations for partitioning, assignment and ordering problems. 4OR 10 (2012) 321–346. | MR | Zbl | DOI
[87] , Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 (1938) 522–536. | MR | JFM | DOI
[88] C. Seligman, Online Astronomy Text. Available at: http://cseligman.com/text/history/ellipses.htm (1993).
[89] and , A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3 (1990) 411–430. | MR | Zbl | DOI
[90] , Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25 (1987) 1–11. | MR | Zbl
[91] , Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25 (1990) 163–168. | MR | Zbl | DOI
[92] , and , Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems. Math. Program. Comput. 5(2013) 1–25. | MR | Zbl | DOI
[93] , Semidefinite optimization. Acta Numerica 10 (2001) 515–560. | MR | Zbl | DOI
[94] and , Semidefinite programming. SIAM Rev. 38 (1996) 49–95. | MR | Zbl | DOI
[95] , , and , Large-scale binary quadratic optimization using semidefinite relaxation and applications. IEEE Trans. Patt. Anal. Mach. Intel. 39 (2017) 470–485. | DOI
[96] , and , Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2 (2010) 203–230. | MR | Zbl | DOI
[97] , and , Handbook of Semidefinite Programming. Vol. 27 of International Series in OR/MS. Springer, New York (2000). | MR | Zbl
[98] and , Semidefinite programming for discrete optimization and matrix completion problems. Discr. Appl. Math. 123 (2002) 513–577 | MR | Zbl | DOI
[99] , Solving certain singly constrained convex optimization problems in production planning. Oper. Res. Lett. 1 (1982) 246–252. | MR | Zbl | DOI
Cité par Sources :