PaperlayerView exact revision on arXiv

Source-linked AI summary

DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization

Amir Ali Ahmadi, Anirudha Majumdar

arXiv:1706.02586v3math.OCcs.DSeess.SYstat.ML

TL;DR

SOS optimization is limited by the scale of the semidefinite programs it requires. The paper develops DSOS and SDSOS as LP- and SOCP-based subsets of SOS optimization, and reports scalable applications alongside retained theoretical guarantees and accuracy–computation tradeoffs.

  • Problem

    Large-scale semidefinite programs limit the problem sizes that traditional SOS optimization can handle.

  • Method

    The paper introduces DSOS and SDSOS optimization over tractable subsets of SOS polynomials, using linear and second-order cone programming.

  • Results

    Numerical experiments cover polynomial optimization, statistics and machine learning, derivative pricing, and control theory, while theoretical SOS-style guarantees remain available.

  • Takeaways & Limitations

    DSOS and SDSOS provide a computation-time and solution-quality tradeoff for SOS and broader semidefinite-programming applications where scalability is limiting.

  • Takeaways & Limitations

    Some improved approximation systems are not SOCP-representable, and removing an evenness assumption can require doubling variables and degree.

Abstract

from arXiv · show

In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear programming and second-order cone programming-based alternatives to sum of squares optimization that allow one to trade off computation time with solution quality. These are optimization problems over certain subsets of sum of squares polynomials (or equivalently subsets of positive semidefinite matrices), which can be of interest in general applications of semidefinite programming where scalability is a limitation. We show that some basic theorems from SOS optimization which rely on results from real algebraic geometry are still valid for DSOS and SDSOS optimization. Furthermore, we show with numerical experiments from diverse application areas---polynomial optimization, statistics and machine learning, derivative pricing, and control theory---that with reasonable tradeoffs in accuracy, we can handle problems at scales that are currently significantly beyond the reach of traditional sum of squares approaches. Finally, we provide a review of recent techniques that bridge the gap between our DSOS/SDSOS approach and the SOS approach at the expense of additional running time. The Supplementary Material of the paper introduces an accompanying MATLAB package for DSOS and SDSOS optimization.

1. Introduction.

SOS optimization addresses broad nonnegativity-constrained problems through semidefinite programming, but its computational cost limits scalability. The paper introduces DSOS and SDSOS as more scalable LP- and SOCP-based alternatives that trade solution quality for computation time.

  • Optimizing over nonnegative polynomials underlies applications including polynomial optimization, shape-constrained regression, probability bounds, and control-system analysis.
  • SOS optimization converts many nonnegative-polynomial problems into semidefinite programs, providing polynomial-time algorithms for broad classes of otherwise NP-hard problems.
  • DSOS and SDSOS replace SOS optimization with LP- and SOCP-based frameworks that are more conservative but significantly more scalable.They are designed to trade computation time against solution quality and can also apply to general semidefinite-programming applications.
  • Control systems and robotics: In control, polynomial Lyapunov-function searches yield inner approximations of regions of attraction, with DSOS/SDSOS constraints offering more efficient but generally more conservative computation.

2. Review of the semidefinite programming-based approach and computational consid-

SOS certificates express polynomial nonnegativity through positive semidefinite Gram matrices, enabling semidefinite-programming formulations. Their matrix size and numerical cost motivate seeking cheaper sufficient conditions based on LP and SOCP.

  • SOS certificates can prove nonnegativity globally or on semialgebraic sets, with Putinar’s result guaranteeing representations for positive polynomials under an Archimedean condition.
  • A polynomial of degree 2d is SOS exactly when it has a symmetric positive semidefinite Gram matrix satisfying coefficient-matching constraints.
  • A degree-4 polynomial in 50 variables has 316251 coefficients and a Gram matrix with 879801 decision variables, placing such SOS problems beyond current practical reach.
  • The paper asks whether stricter-than-SOS nonnegativity conditions can be cheaper to optimize and proposes subsets solvable by linear programming or second-order cone programming.
  • LP and SOCP formulations offer more efficient solving, better numerical conditioning, and access to mature high-performance solvers than semidefinite programs.

3. DSOS and SDSOS Optimization.

DSOS and SDSOS optimize over inner approximations to SOS polynomials, replacing semidefinite programs with more scalable LP and SOCP formulations. Hierarchies extend these cones while retaining several asymptotic guarantees.

  • 3. DSOS and SDSOS Optimization.: DSOS and SDSOS approximate SOS polynomials from the inside using more tractable cones.These cones are subsets of SOS and, consequently, provide conservative approximations to nonnegative polynomials.
  • 3.1. The cones of dsos and sdsos polynomials.: DSOS optimization has an LP representation, while SDSOS optimization has an SOCP representation, with polynomial size for fixed degree.The corresponding matrix representations use diagonally dominant and scaled-diagonally-dominant Gram matrices.
  • 3.1. The cones of dsos and sdsos polynomials.: Replacing SDPs with LPs and SOCPs produces significant speedups and enables systematic inner approximations of semidefinite programs.The matrix cones underlying DSOS and SDSOS are respectively diagonally dominant and scaled diagonally dominant.
  • 3.2. The cone of r-dsos and r-sdsos polynomials and asymptotic guarantees.: The r-dsos and r-sdsos hierarchies improve approximations as the hierarchy level increases and can sometimes outperform SOS nonnegativity tests for r ≥1.The paper illustrates this behavior on a parametric family of bivariate quartics.
  • 3.2. The cone of r-dsos and r-sdsos polynomials and asymptotic guarantees.: Every even positive definite form is r-dsos for some r, yielding LP- and SOCP-based converging hierarchies of lower bounds for compact polynomial optimization.A general positive-definite form also becomes r-dsos after the theorem’s variable-and-degree transformation.
  • 3.2. The cone of r-dsos and r-sdsos polynomials and asymptotic guarantees.: The evenness assumption is necessary for the direct theorem, because some positive definite quadratic forms are not r-sdsos for any r.The paper notes that improved proof systems or a transformation doubling variables and degree can address the broader setting.

4. Numerical examples and applications.

The paper evaluates DSOS and SDSOS through numerical examples centered on obtaining lower bounds for homogeneous polynomial optimization on the unit sphere. This problem is strongly NP-hard even for quartics.

  • 4. Numerical examples and applications.: The numerical section studies minimizing a homogeneous degree-2d polynomial on the unit sphere.The problem’s optimal value is related to an SOS-based lower-bound formulation.
  • 4. Numerical examples and applications.: The sphere-constrained homogeneous polynomial optimization problem is strongly NP-hard even when d = 2.The paper uses this setting to motivate computational lower-bound methods.
  • 4. Numerical examples and applications.: SOS optimization provides lower bounds for polynomial optimization problems, including the sphere-constrained problem considered here.The passage frames these bounds as an important application of sum of squares optimization.

4.1. Lower bounds on polynomial optimization problems.

DSOS and SDSOS replace SOS semidefinite constraints with LP- and SOCP-based relaxations for lower-bounding quartic forms, trading some optimality for substantially greater scalability.

  • 4.1. Lower bounds on polynomial optimization problems.: DSOS, SDSOS, 1-DSOS, 1-SDSOS, and SOS provide alternative lower bounds for quartic forms with fully dense random coefficients.The experiments vary the number of variables from 5 to 70.
  • 4.1. Lower bounds on polynomial optimization problems.: The reported bound coincides with the true global optimum when a point on the sphere supplies a matching upper bound.This establishes exactness for the corresponding instance.
  • 4.1. Lower bounds on polynomial optimization problems.: The DSOS and SDSOS relaxations scale to n = 70, whereas SOS cannot handle n larger than 25 because of memory constraints.The increased scalability comes with suboptimality that the authors describe as tolerable in many applications.
  • 4.1. Lower bounds on polynomial optimization problems.: SOS programs cannot be executed beyond n = 25, while DSOS and SDSOS programs at n = 70 take only a few minutes.Memory constraints also prevent execution beyond n = 70 in these experiments.

4.2. Copositive programming and combinatorial optimization.

The paper applies DSOS and SDSOS hierarchies to copositive formulations of combinatorial problems, using tractable inner approximations of the copositive cone.

  • 4.2. Copositive programming and combinatorial optimization.: The independent set number of a graph can be represented as the optimum of a copositive program.Copositive programming exactly models several combinatorial and nonconvex optimization problems.
  • 4.2. Copositive programming and combinatorial optimization.: A copositive matrix corresponds to a nonnegative quartic form, enabling r-DSOS and r-SDSOS inner approximations optimized through LP and SOCP.The SOS counterpart uses semidefinite programming.
  • 4.2. Copositive programming and combinatorial optimization.: The r-DSOS hierarchy dominates the Pólya LP because diagonal dominance is less restrictive than requiring a diagonal Gram matrix with nonnegative entries.The same hierarchy guarantee therefore extends from the Pólya LP to r-DSOS and r-SDSOS.
  • 4.2. Copositive programming and combinatorial optimization.: For the complement of an icosahedron graph, SOS gives an exact upper bound, and the second levels of the r-DSOS and r-SDSOS hierarchies also give exact bounds.The graph has 12 nodes and independent set number 3.

4.3. Convex regression in statistics.

The convex regression experiment fits polynomial functions while enforcing convexity through nonnegativity of a Hessian-associated polynomial, then compares DSOS, SDSOS, and SOS formulations.

  • 4.3. Convex regression in statistics.: Convexity is imposed by requiring the Hessian-associated function wT H(x)w to be nonnegative.For bounded-degree polynomial functions, this produces an optimization problem whose nonnegativity constraint can be replaced by DSOS, SDSOS, or SOS.
  • 4.3. Convex regression in statistics.: The regression problem uses 300 random vectors in R20 drawn independently from the standard normal distribution.The function values are generated separately and include independent standard-normal noise.
  • 4.3. Convex regression in statistics.: Degree-4 DSOS and SDSOS models achieve significantly smaller fitting errors than degree-2 SOS, while degree-4 SOS does not run because of memory constraints.Tables 4 and 5 report fitting errors and running times for these formulations.

4.4. Options pricing.

The options-pricing experiments use DSOS and SDSOS-style approximations to obtain tractable price bounds from moment information, with SDDP often retaining accuracy while reducing computation time.

  • 4.4. Options pricing.: Option-price upper bounds are formulated from payoff functions, moment constraints, and expectations over Martingale measures.The paper considers the case where the mean and covariance matrix of stock prices are known.
  • 4.4. Options pricing.: Replacing the positive-semidefinite condition in the copositive formulation with diagonal or scaled-diagonal dominance yields DDP or SDDP bounds.The original positive-semidefinite formulation produces SDP bounds.
  • 4.4. Options pricing.: For three underlying assets, SDP with MOSEK gives exact bounds, SDDP is almost identical, and DDP is loose and unchanged across strike prices.SDPNAL+ reaches two-decimal accuracy at tolerance 10^-9, while its default 10^-6 tolerance is slightly inaccurate.
  • 4.4. Options pricing.: For 50 underlying assets, SDDP produces a bound very close to SDP with an approximately 100-fold speedup over MOSEK and 90-fold speedup over SDPNAL+.DDP has comparable running time but a less tight bound.

4.5. Sparse PCA.

The paper formulates sparse PCA through rank-constrained matrix optimization and develops LP/SOCP relaxations by replacing positive semidefiniteness with diagonally dominant cones. Numerical examples show comparable sparse-PCA quality while retaining scalability advantages.

  • Sparse PCA is formulated as a rank-constrained matrix optimization problem involving covariance matrix A and sparsity threshold k.
  • Dropping the rank constraint and replacing cardinality with an l1-norm constraint yields the DSPCA semidefinite relaxation.
  • The framework obtains LP and SOCP relaxations by replacing X ⪰0 with membership in dual diagonally dominant or scaled diagonally dominant cones.
  • The relaxed optimal values upper bound the SDP solution, while rank-one solutions make the relaxation tight and otherwise provide approximate loadings through the dominant eigenvector.
  • For five 100 × 100 covariance-matrix examples, DDP and SDDP produced optimal values close to SDP, with comparable sparsity and explained variance.

4.6. Applications in control theory.

The paper applies DSOS and SDSOS programming to region-of-attraction computation and controller synthesis in nonlinear systems. These formulations trade conservatism for substantially lower runtimes and greater scalability than SOS programming.

  • Region of attraction: Lyapunov inequalities certify that a sublevel set of V is contained in a system’s region of attraction.For polynomial dynamics, replacing SOS constraints with DSOS or SDSOS constraints computes inner approximations more efficiently, generally with greater conservatism.
  • Region of attraction: For the 6-link pendulum, SDSOS produced an ROA only slightly more conservative than SOS, whereas DSOS produced a much smaller but potentially useful ROA.
  • Region of attraction: 9.67 seconds and 25.9 seconds were required by DSOS and SDSOS, versus 1526.5 seconds with MOSEK and 23676.5 seconds with SeDuMi for SOS.
  • Scalability: For systems with more than 12 states, SOS programs were too large to run, while DSOS and SDSOS handled almost twice as many states.
  • Humanoid robot control: The ATLAS model has 30 states and 14 inputs; an SDSOS-designed balancing controller stabilized a very wide range of initial conditions.
  • Accuracy trade-off: DSOS and SDSOS improve solving times and scalability but inevitably lose some solution accuracy relative to SOS.

5. Improvements on DSOS and SDSOS optimization.

The paper develops iterative LP and SOCP inner-approximation methods that improve DSOS and SDSOS approximations of semidefinite programs. Change-of-basis and column-generation schemes progressively tighten these approximations while retaining scalable conic formulations.

  • Iterative change of basis: DD(U) inner approximations are optimized by LPs, while SDD(U) inner approximations are optimized by SOCPs.Both parameterize positive semidefinite matrices through a fixed change-of-basis matrix U.
  • Iterative change of basis: Each change-of-basis iteration uses an optimal solution to define the next basis, guaranteeing nonincreasing DSOS and SDSOS upper bounds.For DSOS, the next basis is a Cholesky factor of the current optimal solution; analogous reasoning applies to SDSOS.
  • Iterative change of basis: The SDSOS sequence approaches the SDP optimum faster in practice than the DSOS sequence.After one iteration, the SOCP approximation nearly fills the randomly generated spectrahedron.
  • Column generation: Column generation successively adds carefully selected positive semidefinite matrices or two-column matrices to LP and SOCP approximations.Pricing subproblems choose columns that bring each relaxation’s optimal value closer to the SDP value.
  • Column generation: Five column-generation iterations improve DD and SDD inner approximations of a randomly generated spectrahedron.The figure compares DD on the left with SDD on the right for an objective directed northeast.
  • Factor-width k matrices with k > 2: Factor-width cones form increasingly accurate inner approximations to the positive semidefinite cone, with FW^2_n equal to the SDD cone and FW^n_n equal to the full cone.Intermediate factor-width values outperform SDD approximations, but FW^3_n lacks an SOCP representation.
  • Computational implications: The paper reports applications reaching degree-4 polynomial optimization with up to 70 variables and stabilizing control design with up to 30 state variables.These results use reasonable solution-quality tradeoffs and are presented as substantially beyond standard SOS capabilities without additional structure or specialized solvers.

6. Conclusions.

The paper concludes that DSOS and SDSOS provide scalable alternatives to SOS while preserving several theoretical guarantees. Its experiments and reviewed extensions support broader applications, although improved approximations require additional computation.

  • (S)DSOS retains asymptotic guarantees including nonnegativity certificates, arbitrarily tight copositive-program approximations, and convergent polynomial-optimization lower bounds.
  • Bridging methods can improve DSOS/SDSOS approximations toward SOS at the cost of additional computation time.The paper identifies quantifying these one-shot and adaptive tradeoffs as a future research direction.
  • LP- and SOCP-based relaxations trade solution quality for scalability across applications where SOS programming is used.

7. Supplementary Material: Software Toolbox.

The supplementary material introduces a MATLAB toolbox for constructing and solving DSOS, SDSOS, and SOS programs. It documents polynomial manipulation, decision-variable creation, constraint specification, solver options, and solution access.

  • Installation: The toolbox is installed through SPOT’s MATLAB package and requires running spot install.m to configure paths and compile mex functions.
  • Polynomial manipulation: SPOT’s msspoly class creates and manipulates polynomial variables, vectors, monomials, derivatives, substitutions, and polynomial expressions.
  • Program construction: The spotsosprog class constructs optimization programs with free variables and DSOS, SDSOS, or SOS constraints.
  • Solving and outputs: Supported solvers include MOSEK, Gurobi, and SeDuMi, and the solution structure provides diagnostics and access to optimized variables.
  • Matrix variables: The toolbox supports symmetric, diagonally dominant, scaled diagonally dominant, positive semidefinite, and corresponding dual matrix variables.
  • Constraint specification: Constraint functions specify equality, polynomial-equality, nonnegativity, DD, SDD, and PSD conditions on affine decision-variable expressions.
Loading 1706.02586v3…