1
$\begingroup$

For any positive numbers $p_k$ how to find the minimum of $\sum\limits_{k=1}^n a_k^2 +(\sum\limits_{k=1}^n a_k)^2$ when $\sum\limits_{k=1}^n p_ka_k=1$?

I saw this problem on my problem book and I tried to solve it. I tried to use Cauchy inequality for $\sum_{k=1}^n a_k^2 $ and I proved that the minimum of $\sum\limits_{k=1}^n a_k^2$ is $\frac{1}{\sum\limits_{k=1}^n \frac{1}{p_k^2}}$ when $a_k =\frac{1}{p_k^2\sum\limits_{k=1}^n\frac{1}{p_k^2}}$ but I couldn't find a way to find the minimum of a$\sum\limits_{k=1}^n a_k^2 +(\sum\limits_{k=1}^n a_k)^2$ . After a lot of time thinking I couldn't do any progress and so I decided to ask here

$\endgroup$
8
  • 2
    $\begingroup$ It seems the Lagrange multiplier method gives the result instantly. $\endgroup$
    – Ryszard Szwarc
    Commented Jan 4 at 11:31
  • $\begingroup$ @RyszardSzwarc The book is about algebraic inequalities but I want any solution of this $\endgroup$
    – pie
    Commented Jan 4 at 11:34
  • $\begingroup$ The Lagrange method gives that $a_k$ should be of the form $a_k=cp_k+d,$ for some $c$ and $d.$ I will wait with posting the answer based on the Lagrange method. I am sure someone will come up with an elementary solution. $\endgroup$
    – Ryszard Szwarc
    Commented Jan 4 at 11:41
  • 1
    $\begingroup$ @RyszardSzwarc Answers based on the Lagrange method are already in the linked post. @ Anyone intending to post a more elementary solution: better post it in the linked post. $\endgroup$
    – Anne Bauval
    Commented Jan 4 at 11:45
  • 1
    $\begingroup$ I think the simplest approach is geometric: we have the program $ \min \|a\|^2 + \langle \mathbf{1},a\rangle^2 : \langle p,a\rangle = 1.$ An immediate observation is that any energy in $a$ orthogonal to both $\mathbf{1}$ and $p$ will only serve to increase the objective without affecting the constraint, so the optimal $a$ lies in $\mathrm{span}\{\mathbf{1},p\},$ whereupon imposing the constraint turns this into optimising a quadratic over the reals, which is elementary. Probably neatest if one expresses $p = \lambda \mathbf{1} + q$ for $q \perp \mathbf{1},$ and answers in terms of $\lambda,q$. $\endgroup$
    – stochasticboy321
    Commented Jan 4 at 12:26

1 Answer 1

Reset to default
1
$\begingroup$

The KKT conditions give you that at the optimum, there exists a $\lambda$ such that, for any $i$, $a_i + \sum_k a_k = \lambda p_i$. This is then a linear system that gives you a unique solution. You tune the lambda to match the condition. Do you expect an explicit formula ?

Edit : Thanks to @SamratMukhopadhyay's answer on the linked post, you can see that the inverse of the system matrix has a simple expression, which leads to an analytic solution. I encourage you to look at it.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged .