Fetching the paper…
Reading the bibliography…
This thesis settles a number of questions related to computational complexity and algebraic, semidefinite programming based relaxations in optimization and control.
NP-hardness of deciding convexity of quartic polynomials and related problems
A. A. Ahmadi, A. Olshevsky, P. A. Parrilo, and J. N. Tsitsiklis · 1908
Earlier work this paper cites.
Über die Zerlegung Definiter Funktionen in Quadrate
E. Artin · 1927
Earlier work this paper cites.
A decision method for elementary algebra and geometry
A. Tarski · 1951
Earlier work this paper cites.
A new decision method for elementary algebra
A. Seidenberg · 1954
Earlier work this paper cites.
A note on the joint spectral radius
G. C. Rota and W. G. Strang · 1960
Earlier work this paper cites.
Quasi-concave programming
K. J. Arrow and A. C. Enthoven · 1961
Earlier work this paper cites.
On non-negative forms in real variables some or all of which are non-negative
P. H. Diananda · 1962
Earlier work this paper cites.
Pseudo-convex functions
O. L. Mangasarian · 1965
Earlier work this paper cites.
Maxima for graphs and a new proof of a theorem of Turán
T. S. Motzkin and E. G. Straus · 1965
Earlier work this paper cites.
Stability of Motion
W. Hahn · 1967
Earlier work this paper cites.
The arithmetic-geometric inequality
T. S. Motzkin · 1967
Earlier work this paper cites.
Nonlinear Programming
O. L. Mangasarian · 1969
Earlier work this paper cites.
Algebraic unsolvability of the problem of Lyapunov stability and the problem of topological classification of singular points of an analytic system of differential equations
V. I. Arnold · 1970
Earlier work this paper cites.
Convex Analysis
R. T. Rockafellar · 1970
Earlier work this paper cites.
On pseudo-convex functions of nonnegative variables
R. W. Cottle and J. A. Ferland · 1971
Earlier work this paper cites.
There cannot be an algorithm for integer programming with quadratic constraints
R. G. Jeroslow · 1973
Earlier work this paper cites.
Some definite polynomials which are not sums of squares of real polynomials
R. M. Robinson · 1973
Earlier work this paper cites.
Second order conditions for pseudo-convex functions
P. Mereau and J. G. Paquet · 1974
Earlier work this paper cites.
Positive semidefinite biquadratic forms
M. D. Choi · 1975
Earlier work this paper cites.
Problems of present day mathematics, XVII (Dynamical systems and differential equations)
V. I. Arnold · 1976
Earlier work this paper cites.
Extremal positive semidefinite forms
M. D. Choi and T. Y. Lam · 1977
Earlier work this paper cites.
Testing and imposing monotonicity, convexity and quasiconvexity constraints
L. J. Lau · 1978
Earlier work this paper cites.
Computers and Intractability
M. R. Garey and D. S. Johnson · 1979
Earlier work this paper cites.
Asymptotic stability of an equilibrium position of a family of systems of linear differential equations
V. L. Kharitonov · 1979
Earlier work this paper cites.
The geometry of homogeneous polynomial dynamical systems
J. Baillieul · 1980
Earlier work this paper cites.
Real zeros of positive semidefinite forms. I
M. D. Choi, T.-Y. Lam, and B. Reznick · 1980
Earlier work this paper cites.
Matrix-theoretic criteria for the quasiconvexity of twice continuously differentiable functions
J. A. Ferland · 1981
Earlier work this paper cites.
On the complexity of integer programming
C. H. Papadimitriou · 1981
Earlier work this paper cites.
Criteria for quasiconvexity and pseudoconvexity: relationships and comparisons
J. P. Crouzeix and J. A. Ferland · 1982
Earlier work this paper cites.
Integer programming with a fixed number of variables
H. W. Lenstra · 1983
Earlier work this paper cites.
Stability properties of autonomous homogeneous polynomial differential systems
N. Samardzija · 1983
Earlier work this paper cites.
Some NP-complete problems in quadratic and nonlinear programming
K. G. Murty and S. N. Kabadi · 1987
Earlier work this paper cites.
Real and complex analysis
W. Rudin · 1987
Earlier work this paper cites.
Class of global minimum bounds of polynomial functions
N. Z. Shor · 1987
Earlier work this paper cites.
Global stabilizability of homogeneous vector fields of odd degree
A. Andreini, A. Bacciotti, and G. Stefani · 1988
Earlier work this paper cites.
Some algebraic and geometric computations in PSPACE
J. Canny · 1988
Earlier work this paper cites.
Criteria of asymptotic stability of differential and difference inclusions encountered in control theory
A. Molchanov and Y. Pyatnitskiy · 1989
Earlier work this paper cites.
Open questions in complexity theory for numerical optimization
P. M. Pardalos and S. A. Vavasis · 1992
Earlier work this paper cites.
Homogeneous Lyapunov function for homogeneous continuous vector fields
L. Rosier · 1992
Earlier work this paper cites.
On Arnold’s Hilbert symposium problems
N. C. A. da Costa and F. A. Doria · 1993
Earlier work this paper cites.
Several NP-hard problems arising in robust stability analysis
A. Nemirovskii · 1993
Earlier work this paper cites.
Complexity in Numerical Optimization
P. M. Pardalos, editor · 1993
Earlier work this paper cites.
Lagrange multipliers and optimality
R. T. Rockafellar · 1993
Earlier work this paper cites.
Undecidable Hopf bifurcation with undecidable fixed point
N. C. A. da Costa and F. A. Doria · 1994
Earlier work this paper cites.
The stabilization of homogeneous cubic vector fields in the plane
M. A. Hammamia and H. Jerbia · 1994
Earlier work this paper cites.
Interior point polynomial methods in convex programming
Y. E. Nesterov and A. Nemirovski · 1994
Earlier work this paper cites.
Matrix Analysis
R. A. Horn and C. R. Johnson · 1995
Earlier work this paper cites.
An Introduction to Symbolic Dynamics and Coding
D. Lind and B. Marcus · 1995
Earlier work this paper cites.
Uniform denominators in Hilbert’s 17th problem
B. Reznick · 1995
Earlier work this paper cites.
From linear to nonlinear: some complexity comparisons
E. D. Sontag · 1995
Earlier work this paper cites.
On the difficulty of deciding the convexity of polynomials over simplexes
B. Guo · 1996
Earlier work this paper cites.
L. Vandenberghe and S. Boyd · 1996
Earlier work this paper cites.
The Lyapunov exponent and joint spectral radius of pairs of matrices are hard- when not impossible- to compute and to approximate
J. N. Tsitsiklis and V. Blondel · 1997
Earlier work this paper cites.
Simultaneous contractibility
T. Ando and M.-H. Shih · 1998
Earlier work this paper cites.
Overview of complexity and decidability results for three classes of elementary nonlinear systems
V. D. Blondel and J. N. Tsitsiklis · 1998
Cited alongside, same era.
Multiple Lyapunov functions and other analysis tools for switched and hybrid systems
M. S. Branicky · 1998
Cited alongside, same era.
Computation of piecewise quadratic Lyapunov functions for hybrid systems
M. J. A. Rantzer · 1998
Cited alongside, same era.
Theory of Linear and Integer Programming
A. Schrijver · 1998
Cited alongside, same era.
A note on stability of arbitrarily switched homogeneous systems
D. Angeli · 1999
Cited alongside, same era.
Complexity of stability and controllability of elementary hybrid system
V. D. Blondel and J. N. Tsitsiklis · 1999
Cited alongside, same era.
Minimizing polynomials via sum of squares over the gradient ideal
J. Nie, J. Demmel, and B. Sturmfels · 2006
Later among the works it cites.
Polynomial games and sum of squares optimization
P. A. Parrilo · 2006
Later among the works it cites.
Sums of squares on real algebraic surfaces
C. Scheiderer · 2006
Later among the works it cites.
Matrix sum of squares relaxations for robust semidefinite programs
C. W. Scherer and C. W. J. Hol · 2006
Later among the works it cites.
Explicit SOS decomposition of univariate polynomial matrices and the Kalman-Yakubovich-Popov lemma
E. M. Aylward, S. M. Itani, and P. A. Parrilo · 2007
Later among the works it cites.
Boundedness of the domain of definition is undecidable for polynomial ODEs
D. S. Graca, J. Buescu, and M. L. Campagnolo · 2007
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The boundedness of all products of a pair of matrices is undecidable
V. D. Blondel and J. N. Tsitsiklis · 2000
Cited alongside, same era.
A survey of computational complexity results in systems and control
V. D. Blondel and J. N. Tsitsiklis · 2000
Cited alongside, same era.
Homogeneous state feedback stabilization of homogeneous systems
L. Grüne · 2000
Cited alongside, same era.
Homogeneous systems: stability, boundedness and duality
L. Moreau, D. Aeyels, J. Peuteman, and R. Sepulchre · 2000
Cited alongside, same era.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
P. A. Parrilo · 2000
Cited alongside, same era.
On a decomposition of multivariable forms via LMI methods
P. A. Parrilo · 2000
Cited alongside, same era.
Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
N. Gvozdenović and M. Laurent · 2007
Later among the works it cites.
On Hilbert’s construction of positive polynomials
B. Reznick · 2007
Later among the works it cites.
Non-monotonic Lyapunov functions for stability of nonlinear and switched systems: theory and computation
A. A. Ahmadi · 2008
Later among the works it cites.
Non-monotonic Lyapunov functions for stability of discrete time nonlinear and switched systems
A. A. Ahmadi and P. A. Parrilo · 2008
Later among the works it cites.
Stability and robustness analysis of nonlinear systems via contraction metrics and SOS programming
E. M. Aylward, P. A. Parrilo, and J. J. E. Slotine · 2008
Later among the works it cites.
A survey on continuous time computations
O. Bournez and M. L. Campagnolo · 2008
Later among the works it cites.
Establishing convexity of polynomial Lyapunov functions and their sublevel sets
G. Chesi and Y. S. Hung · 2008
Later among the works it cites.
The complexity of optimizing over a simplex, hypercube or sphere: a short survey
E. de Klerk · 2008
Later among the works it cites.
Stabilization of switched systems via composite quadratic functions
T. Hu, L. Ma, and Z. Lin · 2008
Later among the works it cites.
Convexity in semialgebraic geometry and polynomial optimization
J. B. Lasserre · 2008
Later among the works it cites.
Representation of nonnegative convex polynomials
J. B. Lasserre · 2008
Later among the works it cites.
Approximation of the joint spectral radius using sum of squares
P. A. Parrilo and A. Jadbabaie · 2008
Later among the works it cites.
Undecidability in number theory
B. Poonen · 2008
Later among the works it cites.
Optimization of Lyapunov invariants in analysis and implementation of safety-critical software systems
M. Roozbehani · 2008
Later among the works it cites.
Distributed Lyapunov functions in analysis of graph models of software
M. Roozbehani, A. Megretski, E. Frazzoli, and E. Feron · 2008
Later among the works it cites.
Lecture notes on optimal control
A. L. Tits · 2008
Later among the works it cites.
A positive definite polynomial Hessian that does not factor
A. A. Ahmadi and P. A. Parrilo · 2009
Later among the works it cites.
Convex forms that are not sums of squares
G. Blekherman · 2009
Later among the works it cites.
Special issue on positive polynomials in control
G. Chesi and D. Henrion (editors) · 2009
Later among the works it cites.
Homogeneous polynomial forms for robustness analysis of uncertain systems
G. Chesi, A. Garulli, A. Tesi, and A. Vicino · 2009
Later among the works it cites.
Decidability and undecidability in dynamical systems
E. Hainry · 2009
Later among the works it cites.
The joint spectral radius: theory and applications
R. Jungers · 2009
Later among the works it cites.
Biquadratic optimization over unit spheres and semidefinite programming relaxations
C. Ling, J. Nie, L. Qi, and Y. Ye · 2009
Later among the works it cites.
Polynomial matrix inequality and semidefinite representation
J. Nie · 2009
Later among the works it cites.
Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions
M. M. Peet · 2009
Later among the works it cites.
On the equivalence of algebraic conditions for convexity and quasiconvexity of polynomials
A. A. Ahmadi and P. A. Parrilo · 2010
Later among the works it cites.
Nonnegative polynomials and sums of squares
G. Blekherman · 2010
Later among the works it cites.
On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems
E. de Klerk and M. Laurent · 2010
Later among the works it cites.
CVX: Matlab software for disciplined convex programming, version 1.21
M. Grant and S. Boyd · 2010
Later among the works it cites.
Semidefinite representation of convex sets
J. W. Helton and J. Nie · 2010
Later among the works it cites.
Certificates of convexity for basic semi-algebraic sets
J. B. Lasserre · 2010
Later among the works it cites.
A converse sum of squares Lyapunov result: an existence proof based on the Picard iteration
M. M. Peet and A. Papachristodoulou · 2010
Later among the works it cites.
An elementary proof of Hilbert’s theorem on ternary quartics
A. Pfister and C. Scheiderer · 2010
Later among the works it cites.
Joint spectral characteristics of matrices: a conic programming approach
V. Y. Protasov, R. M. Jungers, and V. D. Blondel · 2010
Later among the works it cites.
LQR-Trees: Feedback motion planning via sums of squares verification
R. Tedrake, I. R. Manchester, M. M. Tobenkin, and J. W. Roberts · 2010
Later among the works it cites.
Convex ternary quartics are sos-convex
A. A. Ahmadi, G. Blekherman, and P. A. Parrilo · 2011
Later among the works it cites.
Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
A. A. Ahmadi, R. Jungers, P. A. Parrilo, and M. Roozbehani · 2011
Later among the works it cites.
A globally asymptotically stable polynomial vector field with no polynomial Lyapunov function
A. A. Ahmadi, M. Krstic, and P. A. Parrilo · 2011
Later among the works it cites.
A complete characterization of the gap between convexity and sos-convexity
A. A. Ahmadi and P. A. Parrilo · 2011
Later among the works it cites.
Converse results on existence of sum of squares Lyapunov functions
A. A. Ahmadi and P. A. Parrilo · 2011
Later among the works it cites.
A convex polynomial that is not sos-convex
A. A. Ahmadi and P. A. Parrilo · 2011
Later among the works it cites.
On higher order derivatives of Lyapunov functions
A. A. Ahmadi and P. A. Parrilo · 2011
Later among the works it cites.
Symmetric sums of squares in degree four
G. Blekherman and C. B. Riener · 2011
Later among the works it cites.
On the computational complexity of membership problems for the completely positive cone and its dual
P. Dickinson and L. Gijben · 2011
Later among the works it cites.
A converse sum of squares Lyapunov result with a degree bound
M. M. Peet and A. Papachristodoulou · 2011
Later among the works it cites.
A Positivstellensatz for projective real varieties
C. Scheiderer · 2011
Later among the works it cites.