Practical SOS Guide

This section is intended to be a collection of common problems when dealing with SOS programming and possible solution to those problems. We provide some methods that might help to inspect the problems and propose potential solutions based on our own experience.

Solution Algorithms

In this section we provide some commonly used solution methods found in the SOS literature and what can go wrong.

Coordinate Descent

One may encounter bilinear, non-convex problems. To deal with such problem a commonly used strategy is to make use of coordinate descent. Thereby, one has to solve several convex optimization problems in an alternating fashion, by fixing one of the bilinear terms first and solve for the other one. In the next optimization, the previously fixed term becomes now a decision variable and the other is fixed. This scheme is repeated until, e.g. a maximum number of iterations is reached or a subproblem becomes infeasible.

Bisection

Another commonly technique is performing a bisection for quasi-convex problem. Such problems occur if a linear cost function also appears in a bilinear constraint. Thereby, the problem is convexified by fixing the cost via bisection in each step. The bisection interval is further shrunk until e.g. a minimum threshold is reached. Bisection can be used for both minimization or maximization of, for example, increasing the sublevel set of a Lyapunov function.

Sometimes, coordinate descent and bisection are combined, as described next.

$V$-s-iteration

One prominent example of using a coordinate descent in combination with bisections is the $V$-s-iteration scheme. In an alternating fashion one solves for the $s$-multiplier first and then for the Lyapunov function $V$, to compute the largest possible inner estimation of the region of attraction. More precisely, the name should be $\gamma$-$\beta$-$V$ iteration. $\gamma$ and $\beta$ are sought first by two separate bisections. In the last step, one seeks for the Lyapunov function $V$.

Trouble shooting

In the following, we provide some hints to deal with situations where (sub)steps become infeasible.

Infeasibility of the first $\gamma$-step in particular almost always happens if the zero-level set of the Lyapunov derivative is located through or very close to the origin.

Common reasons for the infeasibility of the first $\gamma$-step include:

• Lyapunov equation for linearized dynamics yields no Lyapunov candidate
  • If the zero-level set of the Lyapunov derivative crosses through the origin, check if origin is an equilibrium, remove numerical artifacts
• System state is badly scaled
  • If the zero-level set of the Lyapunov derivative is very close to the origin but virtually parallel to one axis, introduce scaling of the state vector.
• Quasi-convex optimization does not find a feasible $\gamma$-level set
  • If a feasible $\gamma$-level set exists (e.g., a candidate was found by visual inspection) but is very small, e.g., $10^{-3}$ or smaller for a range of $\gamma$ between $0$ and $100$, quasi-convex optimization algorithms such as gsosopt often fail. In this case, increasing the value of the feasible $\gamma$-level set is necessary by down-scaling the Lyapunov candidate function. For the first iteration, if computed using the Lyapunov equation, $A^\top P+ PA=-Q$ this can be done by modifying the parameter $Q$ (unity matrix by default)

Of course, infeasibility of the first $\gamma$-step can also be due to the reasons for infeasibility of any other $\gamma$-step, as described next.

Common reasons for infeasibility of the first $\beta$-step:

• One major reason for infeasibility of the $\beta$-step might lies in a shape function that already lies outside the region-of-attraction (even for the smallest possible $\beta$-level set).
  • This situation can be avoided if the user selects a shape function that lies in the initial region-of-attraction. This can be, for example, visually verified. Another method lies in using a different shape function. For example, instead of using an ellipsoid, one could use a scaled version of the initial Lyapunov function. This shape function is guaranteed to lie in the region-of-attraction.

Infeasibility Inspection

It is quite common to encounter the situation where a SOS problem is/becomes infeasible. In this situation it is desireable to find the cause of the infeasibility. Assume a problem with several (non-convex) constraints. One method to identify the responsible constraint(s) for infeasibility one could simply compute the projection for each constraint to the SOS cone to identify the constraints with the largest distance. In other words, we compute the constraint violation. This might help to identify the constraint(s) that cause the overall problem to fail. Such a projection (for one constraint) reads

$$ \begin{aligned} d^* = \min_{s} \quad & |s - g(\hat x)|_2 \\ \text{s.t.} \quad & s \in \Sigma[x] \end{aligned} $$

where $g(\hat x)$ represents the nonlinear constraint functions evaluated at $\hat x$ which is the current (infeasible) solution and $d^*$ is the minimum distance to the SOS cone. The multiplier $s$ has the same grambasis as the constraint.

Example: Assume a problem with several SOS constraints and that we found (by using the projections) that one constraint is responsible for the overall problem to be infeasible (large distance). This might be caused by:

• The constraint is wrongly setup. The user might double check signs and components if the constraint is correctly setup.
• The multiplier are wrongly selected. One can further inspect the multiplier i.e. are some coefficients (compared to the others) very small. Both information might help to adjust the multiplier degree/monomial terms. After adjusting the problem one can re-compute the problem.

Generating an Initial Guess

In some situation it might be necessary to generate a feasible initial guess for the used polynomials. In this situation one could formulate a nonlinear SOS problem that tries to minimizes the constraint violation. We can modify the above outline projection to

$$ \begin{aligned} &\min_{s, x_r \in \Sigma} \quad & |s - g_n(x_r)|_2 \\ & \text{s.t.} \quad & s, x_r, g_l\in \Sigma \end{aligned} $$

where $s$ is a SOS multiplier, $g_n$ and $g_l$ stand for the nonlinear and linear constraint respectively and $x_r$ are the sought decision variables.

In simple terms, the above optimization seeks for a solution that lies on the constraint manifold, i.e., a feasible solution that fulfills all (SOS) constraints. The above problem is nonlinear and hence techniques such as sequential SOS (with quadratic cost) must be applied. It should be noted that if a feasible solution can be found, this one might be very conservative and not as desired. For example, if one seeks for a Lyapunov function, the provided solution might be very small.