Minimizing $\sum_{i=1}^n \frac{x_i^2}{w_i}$ subject to $\sum_{i=1}^n x_i=1$

Question

Minimize $\displaystyle\sum_{i=1}^n \frac{x_i^2}{w_i}$ subject to $\displaystyle\sum_{i=1}^n x_i=1$.

The answer is $x_i=\displaystyle\frac{w_i}{\sum_i w_i}$ but I don't know why apart from plugging it in after finding the first derivative and setting to $0$. A hint is appreciated!

Edit: I get $$\begin{align} \Lambda(v_j,\lambda) &= \sigma^2\sum\frac{v_j^2}{w_j}+\lambda\left(\sum v_j-1\right) \\ \frac{d}{dv_j}\Lambda(v_j,\lambda) &= 2\sigma^2\sum\frac{v_j}{w_j}+\lambda=0 \\ \frac{d}{d\lambda}\Lambda(v_j,\lambda) &= \sum v_j-1 = 0. \end{align}$$ Then $\lambda=-2\sigma^2\sum\frac{v_j}{w_j}$.

Not sure what's supposed to happen next.

Answer 1

Without loss of generality $\sum\limits_{i=1}^nw_i=1$.

Now you can complete the squares like this $$\sum_{i=1}^n\frac{x_i^2-2x_iw_i+w_i^2}{w_i}=\sum_{i=1}^n\frac{(x_i-w_i)^2}{w_i}$$ And note that $\sum\limits_{i=1}^n\frac{2x_iw_i}{w_i}=\sum\limits_{i=1}^n2x_i=2$ is a constant, so it's equivalent to minimizing this sum of squares.

So $x_i=w_i$ is the only minimum, because $\sum\limits_{i=1}^nx_i=\sum\limits_{i=1}^nw_i=1$ and if $x_i\ne w_i$ for any $i$, we can't have a minimum.

This is your answer as by assuming $\sum\limits_{i=1}^nw_i=1$ we just replaced each $w_i$ by $\frac{w_i}{\sum_{i=1}^nw_i}$.

Answer 2

$ \def\b{\beta}\def\l{\lambda}\def\o{{\tt1}}\def\p{\partial} \def\LR#1{\left(#1\right)} \def\BR#1{\Big[#1\Big]} \def\op#1{\operatorname{#1}} \def\trace#1{\op{Tr}\LR{#1}} \def\Diag#1{\op{Diag}\LR{#1}} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\c#1{\color{red}{#1}} \def\CLR#1{\c{\LR{#1}}} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} $For problems with simple constraints, a useful approach is to convert it into an unconstrained problem.

Introduce an unconstrained vector $u$ and define the variables $$\eqalign{ x &= \frac{u}{\o:u} &\qiq \o:x=\frac{\o:u}{\o:u}=1 \\ v &= \o\oslash w &\qiq v\odot w=\o \\ V &= \Diag v &\qiq Vw =\o \\ W &= \Diag w &\qiq VW = I \\ \b &= v:\LR{x\odot x} \\ }$$ where $\{\,:\,\}$ denotes the Frobenius product, $\{\odot/\oslash\}$ denote the Hadamard product/quotient, $\o$ is the all-ones vector, and $\,\b\,$ is your cost function.

Calculate the gradient of $\b$ with respect to $u$ and solve for the optimal vector $$\eqalign{ d\b &= v:\LR{2x\odot dx} \\ &= \LR{2v\odot x}:{dx} \\ &= 2Vx:\c{dx} \\ &= 2Vx:\CLR{\frac{(\o:u)\,du-(\o:du)\,u}{(\o:u)^2}} \\ &= \fracLR{2Vu}{\o:u}:\LR{\frac{(1:u)\,I-\c{u\o^T}}{(\o:u)^2}}du \\ &= 2\LR{\frac{(\o:u)\,I-\c{\o u^T}}{(\o:u)^2}}\fracLR{Vu}{\o:u}:du \\ \grad{\b}{u} &= \fracLR{2V}{(\o:u)^3}\BR{(\o:u)\,u-\LR{u^TVu}w} \;\doteq\; 0 \\ u &= \fracLR{u^TVu}{\o:u}w \qiq \c{u_* = \l w} \\ }$$ Thus the optimal $u_*$ vector is a scalar multiple of $w$.

It is not necessary to determine the multiplier $\l$ to calculate the optimal $x$ $$\eqalign{ x_* &= \frac{u_*}{\o:u_*} = \frac{\l w}{\o:\l w} = \frac{w}{\o:w} \\ }$$