# A certain type of quadratic problem.

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

-
Looks like a perfect example of the rubber duck debugging technique codinghorror.com/blog/2012/03/rubber-duck-problem-solving.html ... –  Federico Poloni Nov 22 '12 at 11:00
Oh I am sorry if it is so, what needs to be done to make it otherwise? –  dineshdileep Nov 22 '12 at 11:31

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 $$\max_{t\in \mathbb{R}} \lambda(t)=\min\{u^HA_1u\mid u^HA_2 u=0, u^Hu=1\}.$$ (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).

-
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. –  dineshdileep Nov 22 '12 at 17:51
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. –  Rudi Pendavingh Nov 22 '12 at 18:50
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). –  dineshdileep Nov 23 '12 at 4:01
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. –  Rudi Pendavingh Nov 23 '12 at 7:29
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. –  Rudi Pendavingh Nov 23 '12 at 7:47