4
$\begingroup$

How do I solve the optimization problem \begin{align} &\min_{\mathbf{x}\in\mathbb{C}^N}\mathbf{x}^H\mathbf{A}\mathbf{x}+2\Re\{\mathbf{b}^H\mathbf{x}\} \\ \mbox{subject to }\\ &\mathbf{x}^H\mathbf{x}=c \end{align} where $c$ is a given positive constant, $\mathbf{A}$ is a $N\times N$ positive (semi) definite matrix, and $\mathbf{b}$ is a given $N\times 1$ complex vector.

$\endgroup$
9
$\begingroup$

This is not a convex optimization problem as written, because $x^Hx=c$ is not a convex constraint. It describes the surface of a hypersphere, which is not convex.

The constraint $x^Hx\leq c$ would be convex, on the other hand. If that relaxation is acceptable to you, then just solve that instead; it's a simple quadratic program. If you need equality, then one thing you can do is solve the convex form first. If the global minimum happens to achieve $x^Hx=c$, then you're done; the solution is the same for your problem and for the convex, relaxed problem. Otherwise, you need to do something else...

What else can you do? Well, it turns out that the $x^Hx \leq c$ version of the problem can be solved globally even if $A$ is not positive semidefinite, and therefore non-convex. It is known as the trust region subproblem, so it has been studied extensively; Google is your friend here. So I think what you may be able to do is adapt the standard Lagrange multiplier technique, which is what is used for the trust region subproblem, for your case. The Lagrangian is

$$L(x,\lambda) = x^HAx + 2\Re{b^Hx} - \lambda( c - x^H x )$$

where $\lambda$ is the Lagrange multiplier. The optimality conditions are

$$\begin{gathered} 2 ( A + \lambda I ) x + 2 b = 0 \\ x^H x = c \end{gathered}$$ So when $A+\lambda I$ is invertible, $$x=-(A+\lambda I)^{-1}b, \quad x^Hx = \| (A+\lambda I)^{-1} b \|_2^2$$ Now you're reduced to searching over the scalar variable $\lambda$ for the value which achieves $x^Hx=c$. Once you have that, then you have your $x$.

Now just to be clear, I don't have an existence proof for you. If you successfully find a $\lambda$, then you should be good. I just don't know if this will always work. For the standard trust region subproblem, it does.

EDIT: I realized that perhaps you're daunted by the complex variables here. Well, there's no need to be; this is easily translated to a real equivalent:

$$\begin{array}{ll} \text{minimize}_{\bar{x}} & \bar{x} \bar{A} \bar{x} + 2 \bar{b} ^T \bar{x} \\ \text{subject to} & \bar{x}^T\bar{x} = c \end{array}$$ where $$\bar{x}\triangleq\begin{bmatrix} \Re{x} \\ \Im{x} \end{bmatrix} \quad \bar{A}\triangleq\begin{bmatrix} \Re{A} & \Im{A} \\ -\Im{A} & \Re{A} \end{bmatrix} \quad \bar{b}\triangleq\begin{bmatrix} \Re{b} \\ \Im{b} \end{bmatrix} $$

$\endgroup$
  • $\begingroup$ sorry for the late reply. I understand the translation between real domain and complex domain. I too think searching for $\lambda$ is the way to go. Do you think this is someway related to waterfilling techniques. Can I apply semi-definite relaxation here? $\endgroup$ – dineshdileep Feb 28 '14 at 4:21
  • $\begingroup$ btw, a big fan of CVX, and use it extensively in my work. It's a privilege to meet you here. $\endgroup$ – dineshdileep Feb 28 '14 at 4:22
  • $\begingroup$ Thanks for the kind words. I see no reason to do anything more complicated here than what I suggest. I say just do bisection on $\lambda$ until you achieve $x^Tx=c$. Don't do relaxation; this is likely to give you the global result, so why screw it up with an approximation? $\endgroup$ – Michael Grant Feb 28 '14 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.