0
$\begingroup$

I am interested in solving the following equality constrained quadratic (?) problem. \begin{align} \min_{u^{H}u=1}~(u^{H}A_1u) \\\ s.t.~ u^{H}A_2u=0 \end{align}

$A_1$ and $A_2$ are $N\times N$ hermitian matrices. $u$ is the unit-norm $N\times 1$ complex vector I need to find. I have worked on it a bit and I am reaching no where. I was trying to numerically solve it with an augmented lagrangian method. I am not a mathematician and I need to implement this. So an iterative algorithm that gives reasonable performance is also fine with me.

PREVIOUS VERSION OF THE QUESTION

\begin{align} \max_{u^{H} u=1}~|u^{H}A_1u| \\ s.t.~ u^{H}A_2u=0 \end{align}

I have this idea that the more smooth problem \begin{align} \max_{u^{H}u=1}~(u^{H}A_1u)(u^{H}A_1u) \\\ s.t.~ u^{H}A_2u=0 \end{align} is same as the first one in the sense it gives the same optimal $u$.

EDIT-2

In fact, after some thought, it looks like solving the following two optimization problems

\begin{align} \max_{u^{H}u=1}~(u^{H}A_1u) \\\ s.t.~ u^{H}A_2u=0 \end{align}

AND

should give me the optimal solution for the original problem

$\endgroup$
2

1 Answer 1

3
$\begingroup$

You can solve $\min\{u^HA_1u\mid u^HA_2 u=0, u^Hu=1\}$ by semidefinite optimization.

Here's why. Let $\lambda(t)$ be the smallest eigenvalue of $A_1+tA_2$. Then for any $t\in \mathbb{R}$ you have $$\lambda(t)=\min_{u^Hu=1} u^H(A_1+tA_2)u\leq \min\{u^HA_1u\mid u^HA_2 u=0, u^Hu=1\}$$ because any feasible solution $u$ of the RHS problem is also a feasible solution of the LHS problem, with the same objective value. In fact \begin{equation}\max_{t\in \mathbb{R}} \lambda(t)=\min\{u^HA_1u\mid u^HA_2 u=0, u^Hu=1\}.\end{equation} (Proof: Suppose to the contrary that there is strict inequality in the above and that the maximum is attained at $t^*$. Consider $$U=\{u\mid u^Hu=1, \lambda(t^*)=u^H(A_1+t^*A_2)u\}.$$ If $u^HA_2u>0$ for all $u\in U$, then $\lambda(t^*+\epsilon)>\lambda(t^*)$ for some $\epsilon>0$.

Similarly, if $u^HA_2u<0$ for all $u\in U$, then $\lambda(t^*-\epsilon)>\lambda(t^*)$ for some $\epsilon>0$.

If there is a $u\in U$ with $u^HA_2u=0$, then $$\lambda(t^*)=u^H(A_1+t^*A_2)u=u^HA_1u=\min\{u^HA_1u\mid u^HA_2 u=0, u^Hu=1\},$$ contradiction.

Now $U$ is nonempty, so contains some $v$ with $v^HA_2v>0$ and some $w$ with $w^HA_2w<0$. Then some linear combination $u$ of $v$ and $w$ is in $U$ and has $u^HA_2u=0$, QED)

Now $$\max_{t\in \mathbb{R}} \lambda(t)=\max\{z\mid A_1+tA_2-zI\text{ is positive semidefinite}, t,z\in\mathbb{R} \}.$$

This can be computed by any semidefinite solver (say Sedumi, or CVX).

$\endgroup$
6
  • $\begingroup$ Thanks for the excellent answer. I could come up with a similar formulation using lagrangian method where $\lambda_1$ and $\lambda_2$ (lagrangian multipliers) played the role of $t$ and $z$. I believe both are same. But the way you proved the gap between the two problems is same was really beautiful. But I actually wanted to avoid this kind of solution which requires the use of a convex package. I was wondering if we could come up with a iterative algorithm for this question. Convergence to global optimum is not necessarily needed. $\endgroup$ Nov 22, 2012 at 17:51
  • 1
    $\begingroup$ Well, if you have a method at your disposal for computing the smallest eigenvalue of a Hermitian matrix, then you can evaluate $\lambda(t)$ for any $t$. As $t\mapsto\lambda(t)$ is concave, solving $\max_t \lambda(t)$ can be done by standard methods, say bisection. $\endgroup$ Nov 22, 2012 at 18:50
  • $\begingroup$ I will check out that idea. Do you think your solution still holds if your idea is generalized to multiple constraints, i.e. $u^{H}A_2u=0$,$u^{H}A_3u=0$ and so on (with all of them being hermitian matrices). $\endgroup$ Nov 23, 2012 at 4:01
  • $\begingroup$ I expect that there are examples with two constraints $u^HA_iu=0$ where there is a gap. My argument to close the gap really breaks when there are more constraints. Each set $\{u\in U\mid u^HA_iu=0\}$ will be nonempty, but there need not be a common point to all these sets. $\endgroup$ Nov 23, 2012 at 7:29
  • $\begingroup$ Actually, you will have $\{u\in U∣ u^HAu=0}\neq \emptyset$ for all linear combinations $A$ of $A_,\ldots,A_k$. But still that is not enough to force a common point I guess. $\endgroup$ Nov 23, 2012 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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