Convert a Quadratic Matrix Form Constraint into CVX Form

(Royi) #1


I’d like to solve the problem:

\begin{align*} \arg \min_{X} \quad & \operatorname{tr} \left( {X}^{T} A X \right) \\ \text{subject to} \quad & {X}^{T} X \preceq I \end{align*}

Where A is a PSD Matrix.

Yet CVX can’t handle non scalar Quadratic Forms.
The problem above has 2 quadratic non scalar forms (Objective function and constraints).

My Approach

I found, using Cholesky Decomposition, a matrix Z such that A = {Z}^{T} Z and converted the problem into:

\begin{align*} \arg \min_{X} \quad & {\left\| Z X \right\|}_{F}^{2} \\ \text{subject to} \quad & {X}^{T} X \preceq I \end{align*}

Where {\left\| \cdot \right\|}_{F} is the Frobenius Norm.

My Problem

I can’t make CVX handle:

((mX.' * mX) - mI) == semidefinite(numCols);

Is there an equivalent scalar form of the constraint which CVX will be able to handle?

(Mark L. Stone) #2

Edit: Reply below was based on original post specifying X^TX \succeq I and is no longer applicable .

The constraint is going in the wrong direction to be convex. It is a non-convex BMI.

If you were willing to constrain X to be square symmetric positive definite, you could use
[X eye(n);eye(n) X] == semidefinite(2*n)
But this is not the problem you specified, so I am marking this non-convex.

(Royi) #3

@Mark_L_Stone, I made a typing mistake. It should be \preceq .
I edited the question accordingly (It is Convex).

Regarding X , no it is not guaranteed to be Square.

So the trick you mentioned - [X eye(n);eye(n) X] == semidefinite(2*n) to impose quare symmetric positive definite isn’t valid here.

I thought something like norm( X.' * X, 2) <= 1 but it won’t work as well:

Disciplined convex programming error:
    Only scalar quadratic forms can be specified in CVX

(Mark L. Stone) #4

Use Schur complement to model X^TX \preceq I

variable X(numRows,numCols)
[eye(numCols) X';X eye(numRows)] == semidefinite(numCols + numRows)

Edit: Note that more parsimoniously, you could instead use norm(x) <= 1, which is also equivalent to X^TX \preceq I and I think would get boiled down inside CVX to more or less the same thing as the above Schur complement formulation.