Abstract
We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems arise naturally from diverse applications. We review known approximation results as well as negative (inapproximability) results from the recent literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ausiello G, D’Atri A and Protasi M (1980). Structure preserving reductions among convex optimization problems. J Comput Syst Sci 21: 136–153
Barvinok (2007) A integration and optimization of multivariate polynomials by restriction onto a random subspace. Found Comput Math (to appear)
Bellare M and Rogaway P (1995). The complexity of approximating a nonlinear program. Math Program 69: 429–441
Blum L, Shub M and Smale S (1989). On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull Am Math Soc (NS) 21(1): 1–46
Bomze IM (2002). Regularity versus degeneracy in dynamics, games and optimization: a unified approach to different aspects. SIAM Rev 44(3): 394–414
Bomze I and De Klerk E (2002). Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J Glob Optim 24(2): 163–185
Burer S (2006) On the copositive representation of binary and continuous nonconvex quadratic programs. Manuscript. http://dollar.biz.uiowa.edu/~burer/papers/021-copos.pdf
Faybusovich L (2004). Global optimization of homogeneous polynomials on the simplex and on the sphere. In: Floudas, C and Pardalos, P (eds) Frontiers in global optimization, pp 109–121. Kluwer, Dordrecht
Garey MR and Johnson DS (1979). Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, Publishers, San Fransisco
Goemans MX and Williamson DP (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6): 1115–1145
Håstad J (1999). Clique is hard to approximate within |V 1-ε|. Acta Math 182: 105–142
Håstad J (2001). Some optimal inapproximability results. J ACM 48: 798–859
Hesthaven JS (1998). From electrostatics to almost optimal nodal sets for polynomial interpolation in a simplex. SIAM J Numer Anal 35(2): 655–676
Horn M (2006). Optimal algorithms for global optimization in case of unknown Lipschitz constant. J Complex 22: 50–70
Khachiyan L (1979). A polynomial time algorithm in linear programming. Sov Math Dokl 20: 191–194
Maharry J, Pasechnik DV, Richter B and Salazar G (2006). Improved bounds for the crossing numbers of K m,n and K n . SIAM J Discrete Math 20: 189–202
de Klerk E, den Hertog D, Elabwabi G (2007a) On the complexity of optimization over the standard simplex. Eur J Oper Res (to appear)
de Klerk E, Laurent M, Parrilo P (2007b) A PTAS for the minimization of polynomials of fixed degree over the simplex. Theor Comput Sci (to appear)
Motwani R and Raghavan P (1995). Randomized algorithms. Cambridge University Press, Cambridge
Motzkin TS and Straus EG (1965). Maxima for graphs and a new proof of a theorem of Túran. Can J Math 17: 533–540
Nemirovsky AS and Yudin DB (1983). Problem complexity and method efficiency in optimization. Wiley–Interscience, New York
Nesterov Y (1998). Semidefinite relaxation and nonconvex quadratic optimization. Optim Methods Softw 9: 141–160
Nesterov Y (2003) Random walk in a simplex and quadratic optimization over convex polytopes. CORE Discussion Paper 2003/71, CORE-UCL
Nesterov Y, Wolkowicz H and Ye Y (2000). Semidefinite programming relaxations of nonconvex quadratic optimization. In: Wolkowicz, H, Saigal, R, and Vandenberghe, L (eds) Handbook of semidefinite programming, pp 361–419. Kluwer, Norwell
Novak E (1988) Deterministic and stochastic error bounds in numerical analysis. In: Lecture Notes in Mathematics, vol. 1349. Springer, Heidelberg
Parrilo PA (2000) Structured semidefinite programs and semi-algebraic geometry methods in robustness and optimization. PhD Thesis, California Institute of Technology, Pasadena, California, USA. Available at: http://www.cds.caltech.edu/~pablo/
Pólik I, Terlaky T (2007) A survey of the S-lemma. SIAM Rev (to appear)
Polyak BT (1998). Convexity of quadratic transformations and its use in control and optimization. J Optim Theory Appl 99: 553–583
Ramana M (1997). An exact duality theory for semidefinite programming and its complexity implications. Math Program Ser B 77(2): 129–162
Traub JF, Wasilkowski GW and Woźniakowski H (1988). Infomation-based complexity. Academic Press, Inc., New York
Vavasis SA (1991). Nonlinear optimization: complexity issues. Oxford University Press, New York
Vavasis SA (1992). Approximation algorithms for concave quadratic programming. In: Floudas, CA and Pardalos, P (eds) Recent advances in global optimization, pp 3–18. Princeton University Press, New Jersey
Weirauch K (1998). Computable analysis. Springer, Heidelberg
Yakubovich VA (1973) The S-procedure and duality theorems for nonconvex problems of quadratic programming, vol. 1. Vestnik Leningrad. University, pp 81–87
Author information
Authors and Affiliations
Corresponding author
Additional information
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
de Klerk, E. The complexity of optimizing over a simplex, hypercube or sphere: a short survey. cent.eur.j.oper.res. 16, 111–125 (2008). https://doi.org/10.1007/s10100-007-0052-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10100-007-0052-9
Keywords
- Computational complexity
- Global optimization
- Linear and semidefinite programming
- Approximation algorithms