Sum‐of‐squares Optimization

A polynomial sum-of-squares optimization problem takes the form

$$\begin{array}{l c r} \min & F(\xi,\pi), & \xi = (\xi_\mathrm{l}, \xi_\mathrm{c}) \\\ \text{s.t.} & \gamma_\mathrm{lb} \unlhd G_\mathrm{l}(\xi,\pi) \unlhd \gamma_\mathrm{ub}, & G_\mathrm{c}(\xi,\pi) \in \mathcal K_c \\\ \text{and} & \xi_\mathrm{lb} \unlhd \xi_\mathrm{l} \unlhd \xi_\mathrm{ub}, & \xi_\mathrm{c} \in \mathcal K_x \end{array}$$

where $F$ is a scalar-valued function, the constraints $G_\mathrm{l}$ and $G_\mathrm{c}$ take polynomial values, and $\unlhd$ denotes a coefficient-wise inequality; $\mathcal K_c$ and $\mathcal K_x$ are convex cones in the space of polynomials. The pairs of polynomials $(\xi_\mathrm{lb}, \gamma_\mathrm{lb})$ denote lower bounds and $(\xi_\mathrm{ub}, \gamma_\mathrm{ub})$ denote upper bounds.

Nonconvex interface

General, nonconvex sum-of-squares optimization problems with nonlinear objective and constraints functions are solved by the nonconvex/nonlinear interface.

S = casos.nlsossol('S','sequential',struct('x',xi,'f',F,'g',G,'p',pi),opts)

initializes the nonconvex/nonlinear solver named 'S' using a sequential optimization algorithm reminiscent of a generalized Newton method^[CL2023]. Options are provided as structure opts including optional fields opts.Kx and opts.Kc describing, respectively, the cones $\mathcal K_x$ and $\mathcal K_c$. See polynomial cones for details.

sol = S('lbx',lbx,'ubx',ubx,'lbg',lbg,'ubg',ubg)

evaluates the SOS solver S providing (optional) arguments to describe $\xi_\mathrm{lb}$, $\xi_\mathrm{ub}$ and $\gamma_\mathrm{lb}$, $\gamma_\mathrm{ub}$.

Affine interface

A sum-of-squares problem is affine if $F$ is a linear (or quadratic) form in $\xi$ and $G = (G_\mathrm{l}, G_\mathrm{c})$ are affine functions in $\xi$.

S = casos.sossol('S','solver',struct('x',xi,'f',F,'g',G,'p',pi),opts)

initializes the SOS solver named 'S' by relaxation to a convex optimization problem using the convex solver 'solver'. See Conic optimization for supported solvers. Options are provided as structure opts including optional fields opts.Kx and opts.Kc describing, respectively, the cones $\mathcal K_x$ and $\mathcal K_c$. See polynomial cones for details.

Quasiconvex interface

A quasiconvex sum-of-squares problems takes the form

$$\begin{array}{l c r} \min & \pm t, & \xi = (\xi_\mathrm{l}, \xi_\mathrm{c}) \\\ \text{s.t.} & \gamma_\mathrm{lb} \unlhd G_\mathrm{l}(t,\xi,\pi) \unlhd \gamma_\mathrm{ub}, & G_\mathrm{c}(t,\xi,\pi) \in \mathcal K_c \\\ \text{and} & \xi_\mathrm{lb} \unlhd \xi_\mathrm{l} \unlhd \xi_\mathrm{ub}, & \xi_\mathrm{c} \in \mathcal K_x \end{array}$$

where $t$ enters affinely into $G = (G_\mathrm{l}, G_\mathrm{c})$ and $G(t, \xi, \pi)$ is affine in $\xi$ for any $t \in \mathbb R$. For details on quasiconvex sum-of-squares programming, refer to [SB2010].

S = casos.qcsossol('S','bisection',struct('x',xi,'f',±t,'g',G,'p',pi),opts)

initializes the quasiconvex SOS solver named 'S' by bisection over convex sum-of-squares optimization problems. Options are provided as structure opts including optional fields opts.Kx and opts.Kc describing, respectively, the cones $\mathcal K_x$ and $\mathcal K_c$. See polynomial cones for details.

References

[SB2010]: P. Seiler and G. J. Balas, ‘Quasiconvex sum-of-squares programming’, in 49th IEEE Conference on Decision and Control, Atlanta, GA, 2010, pp. 3337–3342. doi: 10.1109/CDC.2010.5717672.

[CL2023]: T. Cunis and B. Legat, ‘Sequential sum-of-squares programming for analysis of nonlinear systems’, in 2023 American Control Conference, San Diego, CA, 2023, pp. 756–762. doi: 10.23919/ACC55779.2023.10156153.