1

How can the following expression be minimized wrt w: $$ \frac{w^T D w}{w^T S w}, $$ where $w \in \mathbf{R}^n$, $D \in \mathbf{R}^{n \times n}$ symmetric, and $S \in \mathbf{R}^{n \times n}$ symmetrix positive definite.

Please give me some hints on how to do this. Does setting the derivative to zero do the job? If yes please help me how to calculate the derivative.

Tom
  • 13

3 Answers3

2

Note that this is a generalized eigenvalue problem, i.e, you are looking for the largest generalized eigenvalue of the pair $(D,S)$. Alternatively, introduce $S=R^TR$ and $z = Rw$. You then have $\min_z \frac{z^T R^{-T}DR^{-1}z}{z^Tz}$ which by homogenity is $\min_{z^Tz=1} z^T R^{-T}DR^{-1}z$ which is the definition of the smallest eigenvalue (and associated eigenvector)

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
1

Setting the derivative equal to zero will indeed do the job. Define $f,g:\Bbb R^n \to \Bbb R$ by $f(w) = w^TDw$, $g(w) = w^TSw$. We have $$ f'(w) = \nabla f = 2Dw\\ g'(w) = \nabla g = 2Sw $$ We then have a "quotient rule" of sorts: $$ \nabla(f(w)/g(w)) = \frac{\nabla f(w)g(w) - f(w)\nabla g(w)}{[g(w)]^2} = \\ \frac{2Dw (w^TSw) - 2(w^TDw)Sw}{(w^TSw)^2} $$ So, it suffices to solve $$ [D(w w^T)S - S(w w^T)D]w = 0 $$ It may help to note that $$ D(w w^T)S - S(w w^T)D = \\ (D-S)(ww^T)(D+S) - Dww^TD - Sww^TS $$

Ben Grossmann
  • 225,327
1

Let $F(w)=\dfrac{w^T D w}{w^T S w}$. Since $S$ is positive definite, the logarithm $$\log F(w)=\ln(w^T D w)-\ln(w^T S w)$$ is well-defined and so the condition $0=\dfrac{\partial F}{\partial w}=F(w)\dfrac{\partial}{\partial w}\left(\log F\right)$ is satisfied if either $F(w)$ or $\dfrac{\partial}{\partial w}\left(\log F\right)$ vanish. For the first case, we need $w^T D w=0$; the second requires $$\dfrac{\partial}{\partial w}\left(\log F\right)=\dfrac{\partial}{\partial w}\left(\log w^T D w\right)-\dfrac{\partial}{\partial w}\left(\log w^T S w\right)=\dfrac{2Dw}{w^T D w}-\dfrac{2Sw}{w^T S w}=0$$ which implies $Dw (w^T S w)=(S w)w^T D w$.

This is the same condition found by Omnomnomnom, but I'll provide a different suggestion. Observe that the minimization condition and the definition of $F(w)$ together imply $$(Dw)w^T D w=F(Dw)w^T S w=F(Sw)w^T D w$$ which means that either $w^T D w=0$ (the first condition found earlier) or $(D-F S)w=0$. In the former case the objective function is minimized by finding $F(z)$ such that $F(z)=w^T D w=0$. In the latter, we minimize by finding $F$ such that $D-FS$ has a null eigenvector $w$.

Dominik
  • 14,396
Semiclassical
  • 15,842
  • Thanks for your all help! I understand the quotation rule approach and the trick using logarithms, but I still don't see how a solution for $w$ that minimizes the expressen can be calculated (the last paragraph of your post). For the 1st condition do I need to choose $w$ in the nullspace of D? For the 2nd codition do you mean $D-F(w)S$ by $(D-FS)$? Thanks again for your help! – Tom Sep 26 '14 at 15:16
  • $w$ in the nullspace of $D$ will suffice. (I suspect that's necessary and sufficient, but I haven't done rigorous linear algebra ina while.) 2) Yes, that's what I mean for the second; I dropped the dependence since having $w$ in the nullspace of $D-F(w)S$ is equivalent to $D-FS$ not having full rank. @Tom
  • – Semiclassical Sep 26 '14 at 15:26