Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- List of symbols
- 1 Introduction and message of the book
- PART I POSITIVE POLYNOMIALS AND MOMENT PROBLEMS
- PART II POLYNOMIAL AND SEMI-ALGEBRAIC OPTIMIZATION
- PART III Specializations and extensions
- 13 Convexity in polynomial optimization
- 14 Parametric optimization
- 15 Convex underestimators of polynomials
- 16 Inverse polynomial optimization
- 17 Approximation of sets defined with quantifiers
- 18 Level sets and a generalization of the Löwner–John problem
- Appendix A Semidefinite programming
- Appendix B The GloptiPoly software
- References
- Index
13 - Convexity in polynomial optimization
Published online by Cambridge University Press: 05 February 2015
- Frontmatter
- Dedication
- Contents
- Preface
- List of symbols
- 1 Introduction and message of the book
- PART I POSITIVE POLYNOMIALS AND MOMENT PROBLEMS
- PART II POLYNOMIAL AND SEMI-ALGEBRAIC OPTIMIZATION
- PART III Specializations and extensions
- 13 Convexity in polynomial optimization
- 14 Parametric optimization
- 15 Convex underestimators of polynomials
- 16 Inverse polynomial optimization
- 17 Approximation of sets defined with quantifiers
- 18 Level sets and a generalization of the Löwner–John problem
- Appendix A Semidefinite programming
- Appendix B The GloptiPoly software
- References
- Index
Summary
The moment-SOS approach described in Chapter 6 as well as its extensions in Chapter 11 aim at solving difficult nonconvex (and in general NP-hard) optimization problems. On the other hand, a large class of convex optimization problems can be solved efficiently and sometimes in time polynomial in the input size of the problem. Therefore the moment-SOS approach should have the highly desirable feature of somehow recognizing “easy” problems, for example convex problems. That is, when applied to such problems it should show some significant improvement or a particular nice behavior not necessarily valid in the general case. Otherwise
would one trust an optimization method aimed at solving difficult problems which behaves poorly on relatively “easy” problems?
Probably not! The impact of convexity on the moment-SOS approach is one of the issues investigated in this chapter. We will show that indeed the moment-SOS approach recognizes a large class of convex problems. In particular, the first semidefinite relaxation of the hierarchy (6.3) is exact for SOS-convex problems (among which are linear and convex quadratic programs), i.e., finite convergence takes place at the first step in the hierarchy. But we also provide algebraic characterization of convexity for basic semi-algebraic sets and polynomials as well as some of their specific properties.
Convexity and polynomials
We first introduce some material which shows that in the presence of convexity some of the results presented in Chapter 2 have a nice specialization.
13.1.1 Algebraic certificates of convexity for sets
We first consider the problem of detecting whether some given basic semialgebraic set K as in (5.2) is convex. By detecting, we mean that if K is convex then one can obtain a certificate (or a proof) of convexity by some algorithm.
The geometric characterization of convexity
λx + (1 − λ) y ∈ K, ∀x, y ∈ K, λ ∈ (0, 1)
is not a certificate because it cannot be checked by an algorithm. In fact, detection of convexity is a difficult problem.
- Type
- Chapter
- Information
- An Introduction to Polynomial and Semi-Algebraic Optimization , pp. 197 - 220Publisher: Cambridge University PressPrint publication year: 2015