1
$\begingroup$

Problem:

I need to find the minimum of the expression: $\sum_{k=1}^{n}a_{k}^{2}+\left(\sum_{k=1}^n a_k\right)^2$ subject to the constraint: $\sum_{k=1}^{n}p_{k}a_{k}=1$ This problem can be solved using Cauchy-Schwarz inequality as follows: $1=\sum_{k=1}^{n}p_{k}a_{k}=\sum_{k=1}^{n}(p_{k}-\beta )a_{k}+\beta (\sum_{k=1}^{n}a_{k})\leqslant (\sum_{k=1}^{n}(p_{k}-\beta )^{2}+\beta ^{2})((\sum_{k=1}^{n}a_{k}^{2})+(\sum_{k=1}^{n}a_{k})^{2})\Rightarrow \sum_{k=1}^{n}a_{k}^{2})+(\sum_{k=1}^{n}a_{k})^{2}\geqslant (\sum_{k=1}^{n}(p_{k}-\beta )^{2}+\beta ^{2})^{-1}$ for any real $\beta$ . The value of $\beta$ that maximizes the expression: $\left(\sum_{k=1}^{n}(p_{k}-\beta )^2+\beta^2\right)^{-1}$ is : $\beta =\frac{1}{n+1}\sum_{k=1}^{n}p_{k}$ and the value of the expression for this particular value of $\beta$ is: $\frac{n+1}{(n+1)\sum_{k=1}^{n}p_{k}^{2}-\left(\sum_{k=1}^{n}p_{k}\right)^{2}}$

However, I am interested to see a solution busing the Lagrange Multipliers method. I considered: $f(a_1,a_2,\ldots,a_n)=\sum_{k=1}^n a_k^2+\left(\sum_{k=1}^n a_k\right)^2$

and $g(a_{1},a_{2},\ldots,a_{n})=\sum_{k=1}^{n}p_{k}a_{k}=1$

Then, I need to solve the system: $\bigtriangledown f=\lambda \bigtriangledown g$ together with $g(a_{1},a_{2},\ldots,a_{n})=\sum_{k=1}^{n}p_{k}a_{k}=1$. I found that $\lambda=2(\sum_{k=1}^{n}a_{k}^{2}+(\sum_{k=1}^{n}a_{k})^{2})$. But I couldn't find an explicit formula for $a_{k}$, $k=1,2,\ldots,n$. If anyone finds a way to solve this system, please share :)

  • 0
    A tiny remark: In your Cauchy Schwarz argument, you still need to exhibit $a_i$ which match the lower bound you found.2012-07-02

3 Answers 3

0

\begin{equation} \nabla f = \lambda \nabla g \Rightarrow D_if = \lambda D_ig \end{equation} Hence, \begin{eqnarray} & & 2a_i + 2(\sum_{k}a_k)^{2} = \lambda p_i\\ &\Leftrightarrow & 4a_i + 2(\sum_{k,k\neq i}a_k) = \lambda p_i \\ & \Leftrightarrow & a_i = \dfrac{\lambda p_i - 2(\sum_{k,k\neq i}a_k)}{4} \end{eqnarray} Then, we need to solv the folowwing sistem $ \left\{ \begin{array}{ccccccccc} 4a_1 + 2a_2 +2a_3 +\cdots -2a_n=\lambda p_1\\ 2a_1 +4a_2 +2a_3+\cdots-2a_n= \lambda p_2\\ \vdots\\ 2a_1+2a_2+2a_3+ \cdots +4a_n= \lambda p_n. \end{array} \right. $ Then, $ \left\{ \begin{array}{ccccccccc} 2a_1 + 0+0+\cdots -2a_n=\lambda(p_1-p_n)\\ 0+2a_2+0+ \cdots -2a_n =\lambda(p_2-p_n)\\ \vdots \\ 2a_1+2a_2+2a_3+ \cdots +4a_n= \lambda p_n. \end{array} \right. $ Then, \begin{equation} 4a_n-2(n-1)a_n=\lambda\left \{(\sum_{k}p_k) +p_n -(n-1)p_n\right \} \end{equation} and we can find $a_n$ next we can find $a_i,i in terms of $a_n$.

1

Let $a=(a_1,\ a_2,\ \cdots,\ a_n)^T$. Then the required optimization is the following $\min\quad a^T(I+11^T) a\\\mathrm{s.t.}\quad p^T a=1$ where $p=(p_1,\ p_2,\ \cdots,\ p_n)^T$. The Lagrangian is $\mathcal{L}(a,\lambda)=a^T(I+11^T) a+\lambda(1-p^T a)\\\implies \nabla_a \mathcal{L}=2(I+11^T)a-\lambda p\\\implies \nabla_a\mathcal{L}=0\implies a=\lambda/2(I+11^T)^{-1}p\\=\frac{\lambda}{2}\left(I-\frac{11^T}{n+1}\right)p$ using Sherman-Morrison identity. This along with the constraint produces $\lambda=\frac{2}{\|p\|^2-\frac{(p^T 1)^2}{n+1}}$ Putting this value in the expression for $a$ gives you a solution for $a$.

Note that this solution is guaranteed to minimize the objective since the objective is a convex function and the constraint is a linear constarin,making the problem a convex optimization problem. So the KKT solutions (the one obtained using Lagrangian) is the global minimizer.

0

Try the following: let $A:=\sum_{i=1}^na_k$ , $P=\sum_{i=1}^np_i$ and $Q=\sum_{i=1}^np_i^2$.

You should have that $2a_k+\sum_{i=1}^na_i=\lambda p_k$ which can be written as $2a_k+2A=\lambda p_k$. Sum both sides over $k$ to get $2A+2nA=\lambda P$ so that $\lambda=2A(n+1)/P$. Now multiply the original equation by $p_k$ and sum, to get $2+2PA=Q\lambda=2QA(n+1)/P$, so now you can solve for $A$ in terms of $P,Q$. Once you have that, use the original equation by writing $2a_k=\lambda p_k-2A$ and plugging in everything you've found in terms of $P,Q$. Note that there could be other solutions and that you would need to test whether this a maximum or minimum.