Solving SDP problem with LMI constraint

I am trying to solve a SDP problem with the LMI constraint.

A is a n\times n symmetric matrix, b is a n-vector, and \gamma>0.

||Ax - b|| \leq \gamma

I reformulate this into a SDP problem by introducing a LMI constraint using the Schur complement:

cvx_begin sdp
variable gamma
variable x(n)
minimize gamma
subject to
[gamma (Ax-b);
x-b)’ gamma^2;] >= 0

Error appears:
Both sides of an SDP constraint must be affine.

< Original first paragraph is corrected below. The following paragraph still applies.>

Are you just doing this for the sake of knowledge? It is more efficient to solve a Second Order cone constraint (such as you have), as a Second Order Cone (SOC) Constraint, norm(A*x-b) <= gamma, than as an SDP (LMI) constraint. CVX will convert any 2 by 2 SDP constraint (which would include this one, if n = 1) into an SOC constraint before providing it to the solver.

1 Like

Yep, I am actually trying to reformulate some LP problems into SDP so that I can be more familiar with SDP mode in CVX. It works perfectly but may I ask if the same trick can be applied to this error whenever it appears?

There is a trick which can sometimes be applied, including in this case (presuming there are no other occurrences of gamma in the problem). If there is an occurrence of gamma^2 in a matrix constrained to being psd, and gamma does not appear by itself (other than as gamma^2) anywhere in the entire CVX program, then a variable gamma_squared, declared as nonnegative, can be used instead of gamma^2. In that case, it is not necessary to declare gamma_squared as nonnegative, because the optimizer will only consider nonnegative values of gamma_squared, because negative values would make the constraint infeasible.

I see, thanks a lot. But actually my formulation is taking square from both sides (the norm and gamma). So, when I apply Schur complement, the square of gamma should also be retained in the LMI. I actually typed sth wrong in the original question, the LMI should be
[eye(n) (Ax-b);
x-b)’ gamma^2;] >= 0.

Yes, I was careless in not correcting your not having the Identity matrix on the diagonal. So you should use gamma_squared.

Thanks a lot! It works perfectly now!