Gettings Started

SOSOpt is dedicated to solving the sums-of-squares (SOS) optimization problem, offering advanced support for multiple evaluations and substitutions of decision variables. The SOS optimization problem under consideration is formulated as:

\[ \begin{array}{ll} \text{find} & \theta, \\ \text{minimize} & c(\theta) + q(\theta)^\top q(\theta) \\ % c^\top \theta + (Q \theta)^\top Q \theta \\ \text{subject to} & p_k(x; \theta) \in \Sigma[x] \quad \forall k \\ & l(\theta) = 0. % & A \theta = b. \end{array} \]

where \(c(\theta)\), \(q(\theta)\), \(p_k(x; \theta)\), and \(l(\theta)\) are polynomial expression in polynomial variable \(x\) and decision variable \(\theta\). When solving the SOS problem, an exception is raised when one of these polynomial expression does not depend linearly on the decision variable \(\theta\).

Compared to other SOS libraries, SOSOpt defines standalone constraints, not requiring a link to a concrete SOS problem. In SOSTOOLS, a Program object is used to define the SOS constraint sosineq(Program, r);. In SumOfSqaures.jl, a model object is used to define the SOS constraint @constraint(model, r >= 0). The state object takes a comparable role of such an object as a container of shared data. However, in SOSOpt, the usage of an SOS constraint returned by the function sosopt.sos_constraint is not restricted to a single SOS program, making this approach more modular when working with different SOS problems. The state object is created as follows.

state = sosopt.init_state()

Variables

The polynomial variable \(x\) and decision variable \(\theta\) are both build within the PolyMat ecosystem. By convention, native PolyMat variables -- created via polymat.define_variable -- are interpretated as polynomial variables. In contrast, decision variables are introduced by extending the PolyMat framework with a new variable type. The following example defines a polynomial variable \(x\) and a decision variable \(\theta\) consisting of three components and uses them to construct a polynomial expression.

import sosopt
import polymat

# define a polynomial variable
x = polymat.define_variable('x')

# define three decision variables
theta_0 = sosopt.define_variable('theta_0')
theta_1 = sosopt.define_variable('theta_1')
theta_2 = sosopt.define_variable('theta_2')

# parametrized polynomial containing both polynomial and decision variable
r = theta_0 + theta_1 * x + theta_2 * x**2

Alternatively, the construction of a fully parametrized polynomial -- involving the specification of a decision variable for each coefficient of the polynomial -- is automated using the sosopt.define_polynomial function:

# creates a monomial vector [1 x x^2]
monomials = x.combinations(degrees=range(3))

# creates a parametrized polynomial r = r_0 + r_1 x + r_2 x^2
state, r = sosopt.define_polynomial(name='r', monomials=monomials).apply(state)

# returns a polymat vector [r_0, r_1, r_2] containing the coefficients
r.coefficient

Furthermore, a parametrized polynomial matrix can be created by additionally specifying the row and col arguments:

Q = sosopt.define_polynomial(
    name='Q', 
    monomials=monomials,
    n_rows=n, n_cols=m,
)

Polynomial Constraints

The polynomial constraints in the SOS problem can be defined in SOSOpt as follows:

Zero Polynomial Constraint

This polynomial constraint ensures that a polynomial expression is zero as a polynomial: All coefficients of the polynomials must be zero.

The following constraint:

state, r_zero_constraint = sosopt.zero_polynomial_constraint(
    name='r_zero',
    equal_to_zero=r,
).apply(state)

enforces the coefficients of \(r(x)\) to be zero:

\[\text{Coeff}(r(x)) = 0.\]

SOS Constraint

This polynomial constraint ensures that a scalar polynomial expression belongs to the SOS Cone.

The following constraint:

state, r_sos_constraint = sosopt.sos_constraint(
    name='r_sos',
    greater_than_zero=r,
).apply(state)

enforces the SOS constraint:

\[r(x) \in \Sigma[x].\]

SOS Matrix Constraint

This polynomial constraint ensures a polynomial matrix expression belongs to the SOS Matrix Cone.

The following constraint:

state, q_sos_constraint = sosopt.sos_matrix_constraint(
    name='q_sos',
    greater_than_zero=q,
).apply(state)

enforces the SOS constraint:

\[v^\top q(x) v \in \Sigma[x, v].\]

Quadratic Module Constraint

This polynomial constraint defines a non-negativity condition on a subset of the states space using a quadratic module construction following Putinar's Positivstellensatz.

The following constraint:

state, r_qm_constraint = sosopt.quadratic_module_constraint(
    name='r_qm',
    greater_than_zero=r,
    domain=sosopt.set_(
        smaller_than_zero={'w': w},
    )
).apply(state)

enforces the SOS constraints:

\[\gamma_w(x) \in \Sigma[x]\]

\[r(x) + \gamma_w(x) w(x) \in \Sigma[x].\]

Defining an SOS Problem

An SOS problem is defined using the sosopt.sos_problem function taking as arguments: - lin_cost: Scalar expression \(c(\theta)\) defining the linear cost. - quad_cost: Vector expression \(q(\theta)\) defining the quadratic cost \(q(\theta)^\top q(\theta)\). - constraints: SOS and equality constraints - solver: SDP solver selection (CVXOPT or MOSEK)

problem = sosopt.sos_problem(
    lin_cost=Q.trace(),
    quad_cost=Q.diag(),
    constraints=(r_sos_constraint,),
    solver=polymat.cvxopt_solver,
)

# solve SOS problem
state, result = problem.solve().apply(state)

The solve method converts the SOS problem to an SDP, solves the SDP using the provided solver, and maps the result to a dictionary result.symbol_values.

See examples/boxconstraints for a full example on how to define and solve an SOS problem.