Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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