How can I solve this optimization problem?

Nonconvex
1

Hello everybody!

I critically need to solve the following problem.
Could you please let me know, how can I solve the following optimization problem in CVX/MATLAB?

X_opt = min_{X} f(X)
s.t. (X^T H X – R) \in {PSD or NSD}

  • X is a matrix in R^(m x n) (n >= m)
  • f(X) = (Y – X C )^T(Y – X C), where Y \in R^m and C\in R^n.
  • PSD(NSD) denotes positive (negative) semi-definite.
  • R and H are real symmetric PSD matrices (R^T = R >=0), (H^T = H >=0).

Actually, I don’t know, how I can represent the constraint properly.

Thank you for your time.

Regards,
Farhad

2

close all; clear all;
m=5; n=6;
%
% X= randn(m,n);
Y= randn(m,n);
C= randn(n,n);
A= orth(randn(m,m));
B= diag(diag(A));
H= A’BA;
D= orth(randn(n,n));
E= diag(diag(D));
R= D’ED;

cvx_begin
variable X(m,n)
minimize ( norm( Y - X * C, ‘fro’ ));
subject to
[R,X’;X,inv(H)] == semidefinite(m+n);
cvx_end

but the results is infeasible,which is not correct.
the original question is not convex.

3

It would be much better to use this objective:

minimize( norm( Y - X * C, 'fro' ) )

this is the square root of the quadratic form you’ve asked for, but the optimization problem is equivalent—and it is always good to avoid quadratic forms when possible; see this section of the users guide.

Unfortunately, you have a much bigger problem: your constraint is not convex. For one thing, requiring that the expression X’HX-R be positive or negative semidefinite is non-convex. If you are concerned only with the PSD case, I believe you can use Schur complements to get a convex result; for example:

[ R, X' ; X, inv(H) ] == semidefinite(m+n)

You’ll need to double check this yourself. But I actually don’t think you can handle the NSD case.

4

chuzheng7, there is a problem with your code: R is not PSD. But if the original question is not convex, he’s stuck. CVX is strictly for convex problems.