SOS alternations fail to find Lyapunov V in Drake for time reversed Van der Pol

Question

In this notebook, I try to find a V that maximizes the ROA by using alternations, i.e., In this notebook, I try to use alternations (on [λ, ρ] and [V] respectively) to find the largest region of attraction possible on the time-reversed Van der Pol oscillator, following the hw. Specifically, I

0. Initialize using V = x^T P x, where P is from RealContinuousLyapunovEquation.
1. Solve for λ, ρ using the same SOS program as in the class DeepNote, i.e.,
2. Find (any) V that satisfies the same conditions above and also the Lyapunov conditions.

However, the solver fails and is not able to find any V, even if I initialize the guess of V to P.

Questions:

• Is this solver failure something that is expected to happen due to bad numerics? I find it strange that the solver is unable to solve for the second SOS program.
• Is there a solution to this problem?

Answer 1

I think there might be two possible fixes:

1. In bilinear alternation, if you solve a conic optimization problem with an objective, then the solution to this optimization problem is always on the boundary of the feasibility set, namely it is always barely feasible. This barely feasible solution can cause numerical issue in the next iteration. It is better to use a strictly feasible solution.

   Namely if you have a problem

   max c.dot(x)
   s.t x in set
   

   Let's denote the optimal cost as cost_star, then solve a feasibility problem that would "back-off" from the boundary

   find_x
   s.t c.dot(x) >= cost_star - 0.001
       x in set 
   

   You can find an implementation in https://github.com/RobotLocomotion/drake/blob/fd48af23e17dba70bb06bcede2adea3315d30d7b/geometry/optimization/cspace_free_polytope.cc#L252-L286

2. It is possible that your Lagrangian multiplier λ has some very small coefficients, which would cause numerical issues. You can remove these coefficients through lambda.RemoveTermsWithSmallCoefficients() function.