Free Access
Issue
RAIRO-Oper. Res.
Volume 52, Number 4-5, October–December 2018
Page(s) 1087 - 1106
DOI https://doi.org/10.1051/ro/2018034
Published online 22 November 2018
  • F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13–51. [Google Scholar]
  • F. Alizadeh and D. Goldfarb, Second-order cone programming. Math. Program. 95 (2003) 3–51. [Google Scholar]
  • F. Alizadeh, J.-P.A. Haeberly and M.L. Overton, Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77 (1997) 111–128. [Google Scholar]
  • 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). [Google Scholar]
  • K.M. Anstreicher, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43 (2009) 471–484. [CrossRef] [Google Scholar]
  • K.M. Anstreicher, On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136 (2012) 233–251. [Google Scholar]
  • K.M. Anstreicher and S. Burer, Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124 (2010) 33–43. [Google Scholar]
  • D. Avis and J. Umemoto, Stronger linear programming relaxations of max-cut. Math. Program. (2003) 97 451–469. [Google Scholar]
  • 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. [Google Scholar]
  • S.J. Benson, Y. Ye and X. Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10 (2000) 443–461. [Google Scholar]
  • A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs. Oper. Res. Lett. 25 (1999) 1–13. [CrossRef] [Google Scholar]
  • A. Ben-Tal and A. Nemirovski, On polyhedral approximations of the second order cone. Math. Oper. Res. 26 (2001) 193–205. [CrossRef] [Google Scholar]
  • D. Bertsekas, Nonlinear Programming, 3rd edn. Athena Scientific, Bellmont, MA (2016). [Google Scholar]
  • S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, Cambridge (2004). [CrossRef] [Google Scholar]
  • G. Braun, S. Fiorini, S. Pokutta and D. Steurer, Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40 (2015) 756–772. [CrossRef] [Google Scholar]
  • S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (2009) 479–495. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • S. Burer and A.N. Letchford, On non-convex quadratic programming with box constraints. SIAM J. Optim. 20 (2009) 1073–1089. [Google Scholar]
  • S. Burer and R.D.C. Monteiro, Local minima and convergence in low-rank semidefinite programming. Math. Program. 103 (2005) 427–444. [Google Scholar]
  • 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. [Google Scholar]
  • V. Chandrasekaran and P. Shah, Relative entropy optimization and its applications. Math. Program. 161 (2017) 1–32. [Google Scholar]
  • 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. [Google Scholar]
  • G.B. Dantzig, Programming and Extensions. Princeton University Press, Princeton, NJ (1963). [Google Scholar]
  • 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. [Google Scholar]
  • 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). [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • M.M. Deza and M. Laurent, Geometry of Cuts and Metrics. Springer-Verlag, Berlin (1997). [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • T. Fujie and M. Kojima, Semidefinite programming relaxation for nonconvex quadratic programs. J. Glob. Optim. 10 (1997) 367–380. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237–267. [Google Scholar]
  • F. Glineur, An extended conic formulation for geometric optimization. Found. Comput. Decis. Sci. 25 (2000) 161–174. [Google Scholar]
  • F. Glineur and T. Terlaky, Conic formulation for p-norm optimization. J. Optim. Th. Appl. 122 (2004) 285–307. [CrossRef] [Google Scholar]
  • M.X. Goemans, Semidefinite programming in combinatorial optimization. Math. Program. 79 (1997) 143–161. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • M.X. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42 (1995) 1115–1145. [CrossRef] [MathSciNet] [Google Scholar]
  • J. Gondzio, Interior point methods 25 years later. Eur. J. Oper. Res. 218 (2012) 587–601. [Google Scholar]
  • M. Grötschel, L. Lovász and A.J. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1 (1981) 169–197. [CrossRef] [MathSciNet] [Google Scholar]
  • M. Grötschel, L. Lovász and A.J. Schrijver, Geometric Algorithms and Combinatorial Optimization. Wiley, New York (1988). [CrossRef] [Google Scholar]
  • M. Hall Jr., Discrete problems, in A Survey of Numerical Analysis, edited by J. Todd. McGraw-Hill, New York (1962) 518–542. [Google Scholar]
  • F.M. Harris, How many parts to make at once. Factory 10 (1913) 135–136, 152. [Google Scholar]
  • J. Håstad, Clique is hard to approximate within n1−ϵ. Acta Math. 182 (1999) 105–142. [CrossRef] [MathSciNet] [Google Scholar]
  • C. Helmberg, Fixing variables in semidefinite relaxations. SIAM J. Matrix Anal. Appl. 21 (2000) 952–969. [Google Scholar]
  • C. Helmberg, Semidefinite programming. Eur. J. Oper. Res. 137 (2002) 461–482. [Google Scholar]
  • C. Helmberg and F. Rendl, Solving quadratic (0, 1)-programs by semidefinite programs and cutting planes. Math. Program. 82 (1998) 291–315. [Google Scholar]
  • C. Helmberg and F. Rendl, A spectral bundle method for semidenite programming. SIAM J. Optim. 10 (1999) 673–696. [Google Scholar]
  • N. Higham, Computing the nearest correlation matrix—A problem from finance. IMA J. Numer. Anal. 22 (2002) 329–343. [CrossRef] [MathSciNet] [Google Scholar]
  • R.A. Horn, Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2012). [CrossRef] [Google Scholar]
  • R. Horst, P.M. Pardalos and N. Thoai, Introduction to Global Optimization, 2nd edn. Kluwer, Dortrecht (2000). [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • L.G. Khachiyan, A polynomial algorithm in linear programming. Soviet Math. Doklady 20 (1979) 191–194. [Google Scholar]
  • K. Krishnan and J.E. Mitchell, A unifying framework for several cutting plane methods for semidefinite programming. Optim. Meth. Soft. 21 (2006) 57–74. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • J.B. Lasserre, Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796–817. [Google Scholar]
  • M. Laurent, A connection betweeen positive semidefinite and Euclidean distance matrix completion problems. Lin. Alg. Appl. 273 (1998) 9–22. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • M. Laurent and S. Poljak, On a positive semidefinite relaxation of the cut polytope. Lin. Alg. Appl. 223/224 (1995) 439–461. [CrossRef] [Google Scholar]
  • M. Laurent and S. Poljak, Gap inequalities for the cut polytope. Eur. J. Combin. 17 (1996) 233–254. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • L. Liberti, C. Lavor, N. Maculan and A. Mucherino, Euclidean distance geometry and applications. SIAM Rev. 56 (2014) 3–69. [CrossRef] [Google Scholar]
  • M.S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming. Lin. Alg. Appl. 284 (1998) 193–228. [CrossRef] [Google Scholar]
  • L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inform. Th. IT-25 (1979) 1–7. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • L. Lovász and A.J. Schrijver, Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1 (1991) 166–190. [Google Scholar]
  • 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. [Google Scholar]
  • J. Malick, J. Povh, F. Rendl and A. Wiegele, Regularization methods for semidefinite programming. SIAM J. Optim. 20 (2009) 336–356. [Google Scholar]
  • H.M. Markowitz, Portfolio selection. J. Finance 7 (1952) 77–91. [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • T.S. Motzkin, Copositive quadratic forms. Nat. Bur. Stand. Rep. 1818 (1952) 11–22. [Google Scholar]
  • K.G. Murty and S.N. Kabadi, Some Formula -complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. [Google Scholar]
  • Y. Nesterov and A. Nemirovsky, Interior Point Methods in Convex Programming: Theory and Applications. SIAM Press, Philadelphia, PA (1994). [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • J. Nie, K. Ranestad and B. Sturmfels, The algebraic degree of semidefinite programming. Math. Program. 122 (2010) 379–405. [Google Scholar]
  • R. O’Donnell, SOS is not Obviously Automatizable, Even Approximately. ECCC Report No. 141 (2016). [Google Scholar]
  • M.W. Padberg, On the facial structure of set packing polyhedra. Math. Program. 5 (1973) 199–215. [Google Scholar]
  • P. Parrilo, Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96 (2003) 293–320. [Google Scholar]
  • S. Poljakand F. Rendl, Non-polyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5 (1995) 467–487. [Google Scholar]
  • S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7 (1995) 51–73. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • J. Povh, F. Rendl and A. Wiegele, A boundary point method to solve semidefinite programs. Computing, 78 (2009) 277–286. [CrossRef] [Google Scholar]
  • M. Ramana, An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems. PhD thesis, Johns Hopkins University, Baltimore, MD (1993). [Google Scholar]
  • M.V. Ramana, An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77 (1997) 129–162. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • F. Rendl, Semidefinite relaxations for partitioning, assignment and ordering problems. 4OR 10 (2012) 321–346. [CrossRef] [Google Scholar]
  • I.J. Schoenberg, Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 (1938) 522–536. [CrossRef] [Google Scholar]
  • C. Seligman, Online Astronomy Text. Available at: http://cseligman.com/text/history/ellipses.htm (1993). [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • N.Z. Shor, Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25 (1987) 1–11. [Google Scholar]
  • N.Z. Shor, Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25 (1990) 163–168. [Google Scholar]
  • 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. [Google Scholar]
  • M.J. Todd, Semidefinite optimization. Acta Numerica 10 (2001) 515–560. [Google Scholar]
  • L. Vanderberghe and S. Boyd, Semidefinite programming. SIAM Rev. 38 (1996) 49–95. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • Z. Wen, D. Goldfarb and W. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2 (2010) 203–230. [Google Scholar]
  • H. Wolkowicz, E. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming. Vol. 27 of International Series in OR/MS. Springer, New York (2000). [Google Scholar]
  • H. Wolkowicz and M.F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems. Discr. Appl. Math. 123 (2002) 513–577 [CrossRef] [Google Scholar]
  • H. Ziegler, Solving certain singly constrained convex optimization problems in production planning. Oper. Res. Lett. 1 (1982) 246–252. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.