3
$\begingroup$

This site is really awesome. :) I hope that we can share our ideas through this site!

I have an equation as below,

$$ min \ \ w^HRw \ \ subject \ \ to \ \ w^HR_aw=J_a, \ w^HR_bw=J_b$$

If there is only one constraint such as $w^HR_aw=J_a$ in above expression, it is easy to convert cost function by using Lagrange multiplier i.e.,

$$ J_0 = w^HRw - \lambda(w^HR_aw-J_a). $$

Finally, above cost function converts as Eigenvalue problem i.e.,

$$R_a^{-1}Rw = \lambda w$$

If $R_a$ is invertible, there is always a solution.

However, I have more than TWO constraints, it is hard to calculate this by myself.

Can anyone help to solve this Lagrange multiplier problem?

$\endgroup$
  • $\begingroup$ This was crossposted to MO. In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. $\endgroup$ – Zev Chonoles May 23 '13 at 4:16
  • $\begingroup$ Thank you for comment! I found similar site as you linked also I posted a few hours ago. I thought thy are different sites, so if I post to each site, I expected more answers from them. Thank you! and I will care of it! I already deleted crossposted to MO. :) $\endgroup$ – Creatlee May 23 '13 at 4:25
2
$\begingroup$

Unfortunately, this problem is not a convex optimization problem (despite the tag :)) due to the presence of nonlinear equality constraints. It is indeed fortunate that you can solve the problem analytically with one quadratic equality constraint. But with two, I am not convinced there is even a tractable numerical method.

There is a heuristic that is sometimes used in the convex optimization community that may be of use to you. Your problem is equivalent to: $$\begin{array}{ll} \text{minimize} & \mathop{\textrm{Tr}}(WR) \\ \text{subject to} & \mathop{\textrm{Tr}}(WR_a) = J_a \\ & \mathop{\textrm{Tr}}(WR_b) = J_b \\ & W = ww^H \end{array}$$ This works because $$\mathop{\textrm{Tr}}(WR) =\mathop{\textrm{Tr}}(ww^HR) =\mathop{\textrm{Tr}}(w^HRw) = w^HRw.$$ Now the problem looks convex---except for the last equality constraint. What you do is relax the equality constraint to $W\succeq ww^H$, which means that $W-ww^H$ is positive semidefinite. This in turn can be written as follows: $$W\succeq ww^H \quad\Longleftrightarrow\quad W-ww^H \succeq 0 \quad\Longleftrightarrow\quad \begin{bmatrix} W & w \\ w^H & 1 \end{bmatrix} \succeq 0$$ The result is a semidefinite program in $W$ and $w$: $$\begin{array}{ll} \text{minimize} & \mathop{\textrm{Tr}}(WR) \\ \text{subject to} & \mathop{\textrm{Tr}}(WR_a) = J_a \\ & \mathop{\textrm{Tr}}(WR_b) = J_b \\ & \begin{bmatrix} W & w \\ w^H & 1 \end{bmatrix} ~ \text{p.s.d.} \end{array}$$ This can be readily solved numerically. In fact, it should be relatively inexpensive to do so, because there are only two equality constraints! If you're a MATLAB jockey you can plug this into my toolbox CVX as follows:

cvx_begin sdp
    variable W(n,n) hermitian
    variable w(n)
    minimize(trace(W*R))
    subject to
        trace(W*Ra) == Ja;
        trace(W*Rb) == Jb;
        [ W, w ; w', 1 ] >= 0;
cvx_end

Again, this is a relaxation of your problem: its optimal value will be less than or equal to the optimal value of the original problem, and the value of $w$ it produces is not guaranteed to even satisfy your original equality constraints. And yet, sometimes, that is exactly what happens: this relaxation actually produces $W=ww^T$. If that happens, $w$ is optimal for your original problem. By all means, try it and see if you get lucky.

On the other hand, if $W\neq ww^H$, what do you do? Here's an idea. Define $\mathop{\textrm{Tr}}(WR)=J_0$ to be the optimal value of the objective. Then try this ``rank reducing'' model: $$\begin{array}{ll} \text{minimize} & \mathop{\textrm{Tr}}(W) \\ \text{subject to} & \mathop{\textrm{Tr}}(WR) \leq (1+\lambda) \cdot J_0 \\ & \mathop{\textrm{Tr}}(WR_a) = J_a \\ & \mathop{\textrm{Tr}}(WR_b) = J_b \\ & \begin{bmatrix} W & w \\ w^H & 1 \end{bmatrix} ~ \text{p.s.d.} \end{array}$$ where $\lambda\geq 0$. Note that if $\lambda=0$, you get the exact same result as in the original problem. But letting $\lambda$ be small but nonzero allows the value of $\mathop{\textrm{Tr}}(WR)$ to rise a bit, while reducing $\mathop{\textrm{Tr}}(W)$. Minimizing the trace is a common convex heuristic for reducing the rank of a PSD matrix. It doesn't always work either, but it just might. Try a couple of values of $\lambda>0$ and see what happens.

If all else fails, you might be able to use the values of $W$ and $w$ to construct a nearby point that satisfies your equality constraints but is not necessarily optimal.

EDIT: I just thought of a simplification if $R$ is positive definite. Define $v=R^{1/2}w$ and $V=R^{1/2}W^{1/2}$, and solve this alternative model: $$\begin{array}{ll} \text{minimize} & \mathop{\textrm{Tr}}(V) \\ \text{subject to} & \mathop{\textrm{Tr}}(VR^{-1/2}R_aR^{-1/2}) = J_a \\ & \mathop{\textrm{Tr}}(VR^{-1/2}R_bR^{-1/2}) = J_b \\ & \begin{bmatrix} V & v \\ v^H & 1 \end{bmatrix} ~ \text{p.s.d.} \end{array}$$ Given the solution $(v,V)$ to this model, you can recover $W=R^{-1/2}VR^{-1/2}$, $w=R^{-1/2}v$. What I like about this alternative is that it combines my two-stage approach above into a single stage. You've got the rank-reducing heuristic $\mathop{\textrm{Tr}}(V)$ right there in the model.

$\endgroup$
  • $\begingroup$ Thank you for answering. I will check this through this week. :) I really appreciate to you. :) $\endgroup$ – Creatlee May 25 '13 at 1:43
  • $\begingroup$ By the way, can I ask something? Although I thought several days, I could not understand this equation. $$\begin{array}{} Tr(WR) = Tr(ww^HR) = Tr(w^HRw)=w^HRw \end{array}$$ . $ww^H$ is $M \times M$ matrix, also $R$. Therfore, $ww^HR$ remains as $M \times M$. $\endgroup$ – Creatlee May 25 '13 at 2:11
  • $\begingroup$ Step 1 just uses the substitution $W=ww^H$. Step 2 uses the well-known identity $\mathop{\textrm{Tr}}(AB)=\mathop{\textrm{Tr}}(BA)$ when $AB$ and $BA$ are both valid matrix multiplications. I'm using $A=w$ and $B=w^HR$. Step 3 is simply the fact that $\mathop{\textrm{Tr}}(a)=a$ when $a$ is a scalar. $\endgroup$ – Michael Grant May 25 '13 at 13:26
  • $\begingroup$ Thank you for teaching me. I will try to use this. Thank you. But,, may I ask a question again? I still did not get the process. Because $R$ and $ww^H$ are $M \times M$ matrices. In this situation, $Tr(ww^HR) = Tr(w^HRw)$ can be calculated? $\endgroup$ – Creatlee May 30 '13 at 7:31
  • $\begingroup$ Yes, that equation is valid. After all, $ww^H$ is the product of two separate matrices. So $ww^HR=(ww^H)R=w(w^HR)$. $\endgroup$ – Michael Grant May 30 '13 at 12:36
2
$\begingroup$

Just add an additional Lagrange multiplier for each constraint and consider the Lagrangian $L = f-\sum\lambda_jg_j$ where $f$ is your original function and the $g_j$ are the constraints. In your quadratic form case, you have to solve $$Rw=\lambda_1R_aw+\lambda_2R_bw$$ subject to the constraints.

In total generality, I don't know a slick solution. Are all three matrices positive definite? Do any of them commute?

$\endgroup$
  • $\begingroup$ Thank you for your answer. $\endgroup$ – Creatlee May 23 '13 at 0:55
  • $\begingroup$ Thank you for your answer. Yeah, their all three matrices are positive definite. I tried to solve above equation. If get a closed form solution, is there any information about them? $R_a$, $R_b$, and $R$ are positive definite at least semi-positive definite. Above equation also can be calculated same as Eigenvalue problem? $\endgroup$ – Creatlee May 23 '13 at 1:07
  • $\begingroup$ I doubt you can simultaneously diagonalize all three matrices in general, no. $\endgroup$ – Michael Grant May 23 '13 at 2:58
  • $\begingroup$ @MichaelC.Grant Thank you for your comment. I just want to know there is a solution of closed form or numerical form or not. Because it seems easy problem because there are lots of examples about solving two constraints Lagrange multipliers. In general, my cost function can be written as below, $$ J(w) = w^HRw - \sum_{i=1}^2 \lambda_i *(w^HR_iw-J_i). $$ However, when I tried to solve this like, $$ w^HRw=\lambda_1J_1 + \lambda_2J_2.$$ I was stuck on this situation. Thank you. $\endgroup$ – Creatlee May 23 '13 at 7:48
  • $\begingroup$ If one of them is positive definite, you can change coordinates to make it the identity. In the new coordinate system, consider the two remaining symmetric matrices. You can now change coordinates to diagonalize one of them. This is the best I can think of, in general. (See also math.stackexchange.com/questions/206660/…) Now, if the last two commute, then you can simultaneously diagonalize. $\endgroup$ – Ted Shifrin May 23 '13 at 13:50

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.