Complex Quadratic Programming Problem

Question

I have a quadratic programming problem as follows:

\begin{equation} \min_x \|Ax+b\|_2 \end{equation} with no constraints. If A,x, and b are real, It would be a straight forward QP problem that can be also written as follows: \begin{equation} \min_x \; \frac{1}{2}x^T J x + c^T x \end{equation} where $J=A^TA$ and $c = A^Tb$. Such problems can be handled by Matlab. However, in my case, $A$, $x$, and $b$ are all complex, and therefore can't be solved by Matlab (My only tool at the moment). Of course, the target function (the norm) is real.

My question: Any Idea on how to reform such a problem to get a real QP problem so I can use Matlab to solve it?

Thanks.

Answer 1

Because the problem involves complex variables, I find it more aesthetic to use $z$ as a complex vector, rather than $x$. The problem is the same as minimizing $$f(z):=(Az+b)^\dagger\,(Az+b)=z^\dagger\,(A^\dagger A)\,z+\big(b^\dagger A z+z^\dagger A^\dagger b\big)+b^\dagger b\,,$$ where $(\_)^\dagger$ denotes the Hermitian conjugate operator.

You have two choices here. First, you can translate everything into real variables. Let $z=x+y\text{i}$, where $x$ and $y$ are real vectors. Similarly, write $A=B+C\text{i}$ and $b=c+d\text{i}$, where $B$, $C$, $c$, and $d$ are real matrices. Thus, if $w$ is the double-sized vector $\begin{bmatrix}x\\y\end{bmatrix}$, then you can minimize $$\phi(w):=f(x+y\text{i})=\|Ew+h\|_2^2$$ instead, where $$E:=\begin{bmatrix}B&-C\\C&B\end{bmatrix}$$ and $$h:=\begin{bmatrix}c\\d\end{bmatrix}\,.$$ This is a real quadratic programming, so you should know how to deal with it.

Alternatively, you can use some complex differentiation. Note that $$\frac{\partial f}{\partial z}=z^\dagger(A^\dagger A)+b^\dagger A\,.$$ Hence, if $z=\tilde{z}$ is an optimal vector, then $$\tilde{z}^\dagger(A^\dagger A)+b^\dagger A=0\,,$$ or $$(A^\dagger A)^\dagger \tilde{z}+A^\dagger b=0\,,$$ whence $$A^\dagger A\,\tilde{z}+A^\dagger b=0\,.$$ This shows that $$\tilde{z}=-(A^\dagger A)^{\text{pinv}}\,A^\dagger b+k= -A^{\text{pinv}}b+k\,,$$ where $k\in \ker(A)$. Here, $(\_)^\text{pinv}$ denotes the pseudoinverse operator.

Answer 2

An alternative to the solution provided int the existing answer is to use an optimization modeling package which does the reformulation to real variables automatically for you under the hood, and calls a standard solver which only accepts real variables.

Such packages under MATLAB include CVX and YALMIP.

Here is how to do it in CVX:

cvx_begin
variable x(size(A,2)) complex
minimize(norm(A*x+b))
% specify constraints, if any
cvx_end

at the conclusion of which, the optimal value of x will be available in the MATLAB session as a complex vector.

CVX reformulates this under the hood to only have real variables, and as a Second Order Cone Problem (SOCP). The SOCP formulation can be numerically more robust than the QP formulation in the other answer, because there is no "squaring" of the condition number, because only $A$, and not $A^TA$, appears in the SOCP formulation.