Handling a strict positive semidefinite constraint in CVX


#1

I’m attempting to solve a linear semidefinite program with the standard form

min dot(a,f)
subject to a_1O_1+…+a_nO_n + M >= 0

where a is a real vector being optimized, f is a constant vector. {O_j} is a set of orthonormal hermitian matrices and M is a positive definite hermitian matrix (typically the smallest eigenvalue ~ 10^-12). For my application, it is necessary that the positivity constraint is strictly satisfied. I have read the section on strict inequalities and it doesn’t appear that any of the suggested solutions are applicable. Is it possible to somehow transform this problem to enforce the constraint (the solution for a does not need to be “exact”) with CVX or some other solver?


(Mark L. Stone) #2

Per http://cvxr.com/cvx/doc/dcp.html#strict-inequalities

If normalization is not a valid approach for your model, you may simply need to convert the strict inequality into a non-strict one by adding a small offset; e.g., convert x > 0 to, say, x >= 1e-4. Note that the bound needs to be large enough so that the underlying solver considers it numerically significant.

Do you find this approach to be unacceptable?


#3

I had tried that, however for the set of {O_j} that are often used there does not exist a linear combination so that a_1O_1+…+a_nO_n + M >= 1e-4. When I add this offset I get that the problem is infeasible. I believe that the offset for the solution to be feasible would need to be ~1e-12 but such an offset becomes numerically insignificant to the underlying solver.


(Mark L. Stone) #4

1e-8 wouldn’t work? Have you tried your best on scaling?

Your best prospects might be using MOSEK as solver under CVX. It seems to have the best numerics and accuracy of the general purpose off-the-shelf LMI solvers.

If you really need to get this right with tight tolerances, then see if you can find a quad precision solver (not in CVX)… I’m not aware of any, but I’m sure one could be written, if not already. Let us know if you find one. Or even higher precision. Of course, will be in software, so slow.

Or maybe VSDP: Verified SemiDefinite Programming http://www.ti3.tuhh.de/jansson/vsdp/ (not under CVX)… I don’;t kno w whether that will find your solution, or be stuck if underlying intlab interval calculations arre only in outward-rounded double precision.


(Mark L. Stone) #5

@awinick You can try using MOSEK as solver under CVX with non-default tolerance.

cvx_solver_settings('MSK_DPAR_INTPNT_CO_TOL_PFEAS',1e-12)
This might not normally be recommended, but I think it can result in a tighter tolerance of min eigenvalue on semidefinite constraints. Feel free to try it and experiment.