A certain type of quadratic problem.

Question

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

Answer 1

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).