Squared Functional Systems and Optimization Problems

By Yurii E. Nesterov. 2000

546 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Control and Systems Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/01871dcfe1b6312bed8865ed3db3cf00933207c7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Control and Systems Engineering

In Numerical Analysis

Citations in the corpus

Robust Optimization (2021, unknown): “Here is the description (originating from [64]):”
Optimal Designs for Rational Function Regression (2010, background): “On the other hand, functions expressible as sums of squares of functions from a given finite-dimensional functional space (such as polynomials of a fixed degree) are semidefinite representable; see Nesterov (2000) for a constructive proof of this claim.”
On Cones of Nonnegative Quadratic Functions (2003, unknown): “Download date: 16. feb. 2019 No. 2001-26 ON CONES OF NONNEGATIVE QUADRATIC FUNCTIONS By Jos F. Sturm and Shuzhong Zhang April 2001 ISSN 0924-7815”
Lectures on modern convex optimization - analysis, algorithms, and engineering applications (2001, background): “Nesterov [24], it can be done via semidefinite programming: The set of all nonnegative (on the entire axis, or on a given ray, or on a given segment) polynomials of a given degree is SDr.”
Self-regularity - a new paradigm for primal-dual interior-point algorithms (2002, methodology): “) Here is the description (originating from [87]): Lemma 14.”
Symmetry groups, semidefinite programs, and sums of squares (2002, background): “such a decomposition, if it exists, can be found using convex optimization, and in particular, semidefinite programming (see [22, 19 ,17] and the references therein).”
Sums of Squares, Moment Matrices and Optimization Over Polynomials (2009, methodology): “As the polynomial optimization problem (1.1) is NP-hard, several authors, in particular Lasserre [65–67], Nesterov [95], Parrilo [103, 104], Parrilo and Sturmfels [107], Shor [138–141], have proposed to approximate the problem (1.1) by a hierarchy of convex (in fact, semidefinite) relaxations.”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, background): “Even determining if a stationary point is a local minimum is (generally) NP-hard (Murty and Kabadi, 1987; Nesterov, 2000).”
Global Optimization with Polynomials and the Problem of Moments (2000, background): “Even more, as mentioned in Nesterov [13], the global unconstrained minimization of a 4-degree polynomial is an NP-hard problem.”
LMI Techniques for Optimization Over Polynomials in Control: A Survey (2010, background): “SOSpolynomials have been exploited since long time, see for instance the pioneering works [2], [3].”
Introducing SOSTOOLS: a general purpose sum of squares programming solver (2002, background): “SOSTOOLS is developed as a consequence of the recent interest in sum of squares polynomials [14, 1, 13, 9, 10, 7 , 6], partly due to the fact that these techniques provide convex relaxations for many hard problems such as global, constrained, and boolean optimization.”
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (2000, background): “In this direction, in [66] it has been shown that the natural self-concordant barrier for the cone of positive definite univariate polynomials is essentially optimal.”
Generalized KYP lemma: unified frequency domain inequalities with design applications (2005, background): “Other generalizations of the KYP lemma include those in [8]–[10] where FDIs for polynomials are considered in the discrete-time setting.”