Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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

share|cite|improve this question
A tiny remark: In your Cauchy Schwarz argument, you still need to exhibit $a_i$ which match the lower bound you found. – Alex R. Jul 2 '12 at 16:34
up vote 0 down vote accepted

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.

share|cite|improve this answer

\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<n$ in terms of $a_n$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


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.