How to solve the constrained convex optimization problem with nuclear norm?

Let $f(x,y)=\sum_{i=1}^n\sum_{j=1}^{n}(x_{ij}+\sqrt{-1}y_{ij})B_{ij}(x,y)$

Now I want to solve the following problem: $$\begin{split} &\arg\min_{C} \iint_{[0,1]^2}|(f_x+\sqrt{-1}f_y)-g(f_x-\sqrt{-1}f_y)|^2\mathrm{d}x\mathrm{d}y+\omega\|C\|_{*}\\ s.t. \quad &C_{i1},C_{in},C_{1j},C_{nj}\quad (i=1,\cdots,n;j=1,\cdots,n)\quad \text{are given}. \end{split}$$ Where $C\in\mathbb{C}^{n\times n}$ is a complex matrix with the following form: $$$$C=\left( \begin{array}{cccc} x_{11}+\sqrt{-1}y_{11} & x_{12}+\sqrt{-1}y_{12} & \cdots &x_{1n}+\sqrt{-1}y_{1n} \\ x_{21}+\sqrt{-1}y_{21} & x_{22}+\sqrt{-1}y_{22} & \cdots &x_{2n}+\sqrt{-1}y_{2n} \\ \vdots & \vdots & \ddots& \vdots \\ x_{n1}+\sqrt{-1}y_{n1} & x_{n2}+\sqrt{-1}y_{n2} & \cdots &x_{nn}+\sqrt{-1}y_{nn} \end{array} \right) =X+\sqrt{-1}Y$$$$

$g=sin(xy)+\sqrt{-1}cos(x+y)$, and $\|\cdot\|_{*}$ is the nuclear norm of a matrix.

How to solve this convex problem?

I convert this problrm into the following form: $$\begin{split} &\arg\min_{C} \frac{1}{2}c^TAc+\omega\|C\|_{*}\\ s.t. \quad &x_{i1},y_{i1},x_{in},y_{in},x_{1j},y_{1j},x_{nj},y_{nj}\quad (i=1,\cdots,n;j=1,\cdots,n)\quad \text{are given}. \end{split}$$ where $A$ is a real positive-definite matrix, $c$ is a combination of the vectorization of $X$ and $Y$ which is defined as: $c=(\text{vec}(X),\text{vec}(Y))$.

But I don't know how to solve this.

1 Answer

Easiest approach is to simply use a modelling tool (YALMIP, CVX etc) with any semidefinite programming solver (Mosek, Sedumi,SDPT3 etc). It is a fairly standard problem.

Here is the corresponding YALMIP code (MATLAB modelling toolbox)

X = sdpvar(n,n,'full');
Y = sdpvar(n,n,'full');
C = X + sqrt(-1)*Y
c = [X(:);Y(:)];
Model = [X(:,1) == values,Y(:,1) == someothervalues,...];
optimize(Model,c'*A*c + norm(C,'nuclear');

• How to use ADMM to solve this problem? – panmd Oct 29 '16 at 14:04
• If you are lazy, you simply use the ADMM solver github.com/giofantuzzi/CDCS which is supported in YALMIP. If you want to implement ADMM on your own (to actually exploit nuclear norm structure), I really don't understand the purpose of the question, as it should be obvious how to solve the problem, if you have sufficient insight in the field to implement an ADMM solver for the problem – Johan Löfberg Oct 29 '16 at 14:33
• I really don't know how to solve this problem by ADMM. I solved the classical matrix completion problem before, but I think the question I propose here is a bit different, as the variable $\mathbf{c}$ is real, however, the matrix $\mathcal{C}$ is complex. I don't know how to do the variable splitting. – panmd Oct 29 '16 at 15:29
• You don't have to split the variables. $c^TAc$ is going to be equivalent to some alternative form $\bar{c}^H \bar{A} \bar{c}$, where $\bar{c}=\mathop{\textrm{vec}}(X+iY)$, and $\bar{A}$ is Hermitian. – Michael Grant Oct 29 '16 at 15:33
• A is a real positive-definite matrix, How to transform $c^{T}Ac$ into the alternative form $\bar{c}^H\bar{A}\bar{c}$? I use the method of indetermined coefficients to solve $\bar{A}$, but I can't get the solution. – panmd Oct 30 '16 at 5:45