Optimization and Feasibility Test of a Polynomial Matrix Inequality

[Yan Wang]

Hi Lofberg,

I tried to minimize a linear cost function (a scalar decision variable) with one LMI, two scalar inequalities and one polynomial matrix inequality. I used the command "solvemoment"  to solve this problem with moment relaxation (order 3). The SeDuMi solver returns "4 Numerical problems". The SDPT3 solver returns "5 Lack of progress". Therefore, I had to manually decrease the value of the scalar decision variable (cost function) to a level at which I can accept and tested the feasibility of all the constraints. Both SeDuMi and SDPT3 give the same return results shown just now. Then, I use the command "checkset" to show the residual, which can be seen below. In my opinion, this is a feasible set with respect to the given value of the cost function. But I still don't know why the solvers cannot return the "Successfully solved" information in both minimization problem and feasibility problem. 

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   ID|      Constraint|                             Type|   Primal residual|

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

|   #1|   Numeric value|                Matrix inequality|        2.1322e-17|

|   #2|   Numeric value|           Elementwise inequality|        1.7519e-05|

|   #3|   Numeric value|           Elementwise inequality|        2.8583e-13|

|   #4|   Numeric value|   Matrix inequality (polynomial)|        2.2322e-19|

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

[Johan Löfberg]

Are you saying

solvemoment(Constraints,Objective)

gave you numerical problems, and then you changed that to

solvemoment([Constraints,Objective<=value])

and the numerical problems remained, but when you checked the solution, the solution was actually feasible?

It is not too surprising. Semidefinite programming is tricky, and solvers often run into issues. That is exactly the reason why you always should check the solution to see if it is acceptable.

Semidefinite programs that arise in relaxations can easily lead to large numerically challenging problems. Consider the following small problem

sdpvar x y

C = [x >= 0, y >= 0, x*y >= 1]

solvemoment(C,y,[],4)

SDPT3 ends up with unknown error (but a feasible (poor) solution with y = .22) and SeDuMi ends with numerical problems, but also a feasible solution with y = .12 (all solvers I tried failed to compute a reasonably good solution)

The problem is most likely the fact that the problem does not have a minimizer, but only an infimizer, i.e., the optimal solution is y=0 and x=inf. Hence, the solver problably gets in a situation where it can make massive steps in some variables related to x, but almost no step in y. I would not be surprised if the numerical conditioning would be poor then, causing the solver to bail out.

Of course, the problem can be solved directly without a relaxation

solvesdp([x 1;1 y] >= 0,y)

and it is actually solved (i.e., returning a very small y) rather easily despite the unbounded region and lack of minimizer. Just wanted to point out that you easily can construct examples where most solvers fail