Handling a strict positive semidefinite constraint in CVX

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?

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?

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.

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.

@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.

Mark,

Would you kindly suggest some reference material (of any kind: book, paper etc…) on normalization for this particular topic. I’m also experiencing difficulties with very small violating eigenvalues.

Well, there’s this thread, plus Prescribing tolerance for positivedefiniteness , which you started.

And as I mentioned earlier in this thread, you can use MOSEK as solver under CVX with non-default tolerance
cvx_solver_settings('MSK_DPAR_INTPNT_CO_TOL_PFEAS',1e-12)
I don’t think I’d try to go smaller than that. 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.

https://docs.mosek.com/9.0/rmosek/parameters.html

MSK_DPAR_INTPNT_CO_TOL_PFEAS
Primal feasibility tolerance used by the interior-point optimizer for conic problems.
Default:
1.0e-8
Accepted:
[0.0; 1.0]

Do you think that by proceeding as you suggsted I’d end up with a big hammer to better tackle the following difficulty:

`

87|0.787|0.255|6.3e-05|1.1e-10|2.1e+01|-1.205410e+04 -2.923188e+03| 0:0:02|
stop: progress is bad

 number of iterations   = 87
 primal objective value = -1.20441655e+04
 dual   objective value = -2.92322152e+03
 gap := trace(XZ)       = 1.90e+01
 relative gap           = 1.27e-03
 actual relative gap    = -6.09e-01
 termination code       = -5
 Status: Failed  `

Even though the termination code is \textbf{FAILED}, the solution is numeric, but as the documentation says it is not to be trusted. Indeed,there are teeny-weeny small negative eigenvalues. I kind of have the feeling that my problem has to do with the either the solver or CVX as opposed to the formulation. I kindly ask for your opinion on it.

Sometimes it fails due to stop: primal infeas has deteriorated too much, 1.5e-01

SDPT3 is not able to solve the problem as you formulated. Either try another solver or improve the formulation. Because you have not shown your formulation, readers aren’t able to provide you advice on how to do so.