How can I reformulate a matrix quadratic form in the constraint

Nonconvex
1

I have the following problem:

Say that we’re given the matrices S(m,m), Y(n,m) and X(n,m) and we need to find the matrix A(n,n) as follows

begin_cvx 
variable A(n,n);
Minimize(norm(A,1)) 
subject to
S==(Y-A*X)'*(Y-A*X); 
norm(A,'fro')<=epsilon;
end_cvx

cvx doesn’t accept the form of (Y-AX)’(Y-A*X) so I wonder how I can reformulate this constraint giving that both my function and my constraint are convex…

Thanks.

2

This problem as written is not convex. Equality constraints must be affine. Consider the constraint a^2=1. While a^2 is convex in a, the constraint is equivalent to a\in\{-1,1\}, which is not a convex region.

3

But if we add another constraint norm(A,‘fro’) <=epsilon the set {S=(Y-Ax)’(Y-A*X) s.t. norm(A,‘fro’)<=epsilon} becomes definitely convex and hence convex constraint.

4

The set is not convex. Take n=1, S=1, Y=0, X=1, Then the set of A such that A^2=1 and A^2<=epsilon is either {-1,1} (if epsilon >= 1) or else doesn’t depend on that nonconvex constraint at all.

5

So do you mean that (Y-AX)’(Y-A*X) is not convex form in A??!!!

6

I know that the inequality constraint should be convex and the equality constraint should be affine. But I even tried to use norm(S-(Y-AX)’(Y-AX),1)<=epsilon or S-(Y-AX)’(Y-AX)<=epsilon*ones(m,m) cvx doesn’t accept that since it has a big limitation in accepting the convex matrix forms…

7

No, the matrix form (Y-AX)’(Y-AX) is not convex.

8

The problem simply is not convex as written. CVX cannot solve it.

Even if you converted the equality constraint to an inequality, it is not convex. That is, if you wrote

S >= (Y-A*X)'*(Y-A*X)

this creates n*(n+1)/2 unique inequalities. The inequalities on the diagonal are convex, but the ones off the diagonal are not.

If you intend for the inequality to be interpreted in the conic, positive semidefinite sense, then CVX will still not be able to solve it as written, but it can be reformulated in a convex manner. First, you need to use cvx_begin sdp instead of cvx_begin. And then you can write

[ S, ( Y - A * X )' ; Y - A * X, eye(n) ] >= 0;

(I might have the transposes backwards here—you may need to swap the (1,2) and (2,1) elements above. Check that yourself). You can confirm for yourself that this is is equivalent to the quadratic matrix inequality. Note that all of this assumes that S is positive definite.

1 Like