A Semidefinite Optimization and Conic Optimization
113
Theorem A.1. Theorem A.2 is stated in Horn and Johnson (1990, Section 7.1) as the
definition of a PSD matrix (there are various equivalent ways of defining positive
semidefiniteness).
SDO, often referred to as semidefinite programming or SDP for short, has
been studied in different forms since at least the 1940s. The interest in SDO
grew dramatically during the 1990s because of the extension of polynomial-time
interior-point methods for LO to the solution of SDO problems, and hence to
SOCO problems. Some applications of SDO followed soon after this development,
such as the solution of linear matrix inequalities in control theory, and the design
of polynomial-time approximation schemes for the maximum-cut and stable-set
problems. This outburst of activity led to the publication of the Handbook of
Semidefinite Programming (Wolkowicz et al 2000) that provided an account of much
of the activity in SDO up to 2000.
The research activity continued into the 2000s and increased further via interactions with algebraic geometry through the close connections between semidefinite
matrices and polynomial optimization problems. This decade of developments
brought about several important new results and is documented in the Handbook
on Semidefinite, Conic and Polynomial Optimization (Anjos and Lasserre 2011).
In particular, these developments raised the profile and importance of polynomial
optimization; see, e.g., Lasserre (2010). Much of the ongoing activity can be
followed on preprint websites such as ArXiv (https://arxiv.org) and Optimization
Online (https://www.optimization-online.org).
A detailed treatment of the important SDO problem (A.3) is given in Wolkowicz
and Anjos (2002). The links between (A.3) and the SDO relaxation of the stableset problem underlying Lovász’s famous theta function were studied in Laurent
et al (1997). The equivalence of a 2 × 2 PSD constraint and a 3-dimensional
SOC constraint was first observed and applied in Kim and Kojima (2003). The
equivalence (A.6) follows from the Schur complement theorem; this result is stated
as Theorem 7.7.6 in Horn and Johnson (1990). Alizadeh and Goldfarb (2003) and
Lobo et al (1998) provide in-depth presentations of the SOC, algorithms for SOCO,
and classes of optimization problems that can be formulated using SOCO.
References
Alizadeh F, Goldfarb D (2003) Second-order cone programming. Mathematical Programming
95(1):3–51
Anjos MF (2017) Chapter 9: Conic linear optimization. In: Advances and trends in optimization
with engineering applications. SIAM, pp 107–120
Anjos MF, Lasserre JB (2011) Handbook on semidefinite, conic and polynomial optimization, vol
166. Springer Science & Business Media
Horn R, Johnson C (1990) Matrix analysis. Cambridge University Press, Cambridge
Kim S, Kojima M (2003) Exact solutions of some nonconvex quadratic optimization problems via
SDP and SOCP relaxations. Comput Optim Appl 26(2):143–154
Lasserre JB (2010) Moments, positive polynomials and their applications, vol 1. World Scientific
113
Theorem A.1. Theorem A.2 is stated in Horn and Johnson (1990, Section 7.1) as the
definition of a PSD matrix (there are various equivalent ways of defining positive
semidefiniteness).
SDO, often referred to as semidefinite programming or SDP for short, has
been studied in different forms since at least the 1940s. The interest in SDO
grew dramatically during the 1990s because of the extension of polynomial-time
interior-point methods for LO to the solution of SDO problems, and hence to
SOCO problems. Some applications of SDO followed soon after this development,
such as the solution of linear matrix inequalities in control theory, and the design
of polynomial-time approximation schemes for the maximum-cut and stable-set
problems. This outburst of activity led to the publication of the Handbook of
Semidefinite Programming (Wolkowicz et al 2000) that provided an account of much
of the activity in SDO up to 2000.
The research activity continued into the 2000s and increased further via interactions with algebraic geometry through the close connections between semidefinite
matrices and polynomial optimization problems. This decade of developments
brought about several important new results and is documented in the Handbook
on Semidefinite, Conic and Polynomial Optimization (Anjos and Lasserre 2011).
In particular, these developments raised the profile and importance of polynomial
optimization; see, e.g., Lasserre (2010). Much of the ongoing activity can be
followed on preprint websites such as ArXiv (https://arxiv.org) and Optimization
Online (https://www.optimization-online.org).
A detailed treatment of the important SDO problem (A.3) is given in Wolkowicz
and Anjos (2002). The links between (A.3) and the SDO relaxation of the stableset problem underlying Lovász’s famous theta function were studied in Laurent
et al (1997). The equivalence of a 2 × 2 PSD constraint and a 3-dimensional
SOC constraint was first observed and applied in Kim and Kojima (2003). The
equivalence (A.6) follows from the Schur complement theorem; this result is stated
as Theorem 7.7.6 in Horn and Johnson (1990). Alizadeh and Goldfarb (2003) and
Lobo et al (1998) provide in-depth presentations of the SOC, algorithms for SOCO,
and classes of optimization problems that can be formulated using SOCO.
References
Alizadeh F, Goldfarb D (2003) Second-order cone programming. Mathematical Programming
95(1):3–51
Anjos MF (2017) Chapter 9: Conic linear optimization. In: Advances and trends in optimization
with engineering applications. SIAM, pp 107–120
Anjos MF, Lasserre JB (2011) Handbook on semidefinite, conic and polynomial optimization, vol
166. Springer Science & Business Media
Horn R, Johnson C (1990) Matrix analysis. Cambridge University Press, Cambridge
Kim S, Kojima M (2003) Exact solutions of some nonconvex quadratic optimization problems via
SDP and SOCP relaxations. Comput Optim Appl 26(2):143–154
Lasserre JB (2010) Moments, positive polynomials and their applications, vol 1. World Scientific