Lagrange Multipliers optimization : really short problem.

Question

\begin{align*} &\text{ maximize } \sum_{i=0}^{N_s - 1} a_i^2 h_i^2 \\ &\text{subject to} \sum_{i=0}^{N_s - 1} a_i^2 \leq N_s P \end{align*}

Assume $h_0 \geq h_1 \geq \cdots \geq h_{N_s - 1}$

It is obvious that choosing $a_0 = \sqrt{N_s P}$ and $a_1 = \cdots = a_{N_s - 1} = 0$ will achieve the maximum but I couldn't prove it using Lagrange multipliers or otherwise.

Here's my working:

The lagrangian is $$\mathcal{L}(a_0, a_1, ..., a_{N_s - 1}, \lambda) = \sum_{i=0}^{N_s - 1} a_i^2 h_i^2 - \lambda \sum_{i=0}^{N_s - 1} a_i^2 + \lambda N_s P $$ \begin{align*} \frac{\partial \mathcal{L}}{\partial a_j } &= 2 h_j^2 a_j - 2\lambda a_j = 0\\ \frac{\partial \mathcal{L}}{\partial \lambda} &= -\sum_{i=0}^{N_s - 1} a_i^2 + N_s P = 0 \end{align*}

How to argue about the maximum mathematically?

I also learnt that Lagrange multipliers method can only be used with equality constraints, not inequality constraints.

Can we still use Lagrange with inequality constraints under some circumstances?

Answer 1

How about solving this from first principles...

---

For ease of notation, I'll index from $1$ through $n$, instead of $0$ throus $N-1$. Also, let $r^2 := NP_s$ in your notation. Then $$ \begin{split} \max_{a \in \mathbb R^n,\;\sum_{i=1}^n a_i^2 \le r^2}\sum_{i=1}^n h_i^2a_i^2 &= \inf_{\lambda \ge 0}\max_{a \in \mathbb R^n}\sum_{i=1}^n h_i^2a_i^2 + \lambda(r^2 - \sum_{i=1}^na_i^2)\\ &= \inf_{\lambda \ge 0}\lambda r^2 +\underbrace{\max_{a \in \mathbb R^n} \sum_{i=1}^n (h_i^2 - \lambda)a_i^2}_{(*)}\\ &= \inf_{\lambda \ge 0}\lambda r^2 +\begin{cases}0,&\mbox{ if }\lambda \ge \max_i h_i^2,\\+\infty,&\mbox{ else}\end{cases}\\ &=\inf_{\lambda \ge \max_i h_i^2}r^2\lambda = r^2\max_i h_i^2, \end{split} $$ and the optimum is obtained at $\lambda = h_{i^*}^2$, where $i^*$ is any index for which $h_i$ is maximal. You may call the first step in the derivations above the "method of Lagrange multipliers" ...

Now, with this optimal value of $\lambda$, problem (*) can be rewritten as

$$ r^2h_{i^*}^2 = r^2h_{i^*}^2 + \max_{a \in \mathbb R^n}\sum_{i=1}^n(h_i^2-h_{i^*}^2)a_i^2, $$

which holds iff $\max_{a \in \mathbb R^n}\sum_{i=1}^n(h_i^2-h_{i^*}^2)a_i^2 = 0$.

Thus, to solve the original problem, it suffices to take $$ a_i = \begin{cases}r,&\mbox{ if }i = i^*,\\ 0, &\mbox{ else.}\end{cases} $$

Answer 2

As you've found, we can't just work with an inequality. As I see it, there are two ways to proceed:

One such way would be to show that a necessary condition to achieve the maximum is that $$\sum a_i^2 = N_s P$$ I'll provide a quick sketch of this argument as follows:

• Suppose we have maximised $M = \sum a_i^2 h_i^2$ with some choice of $a_i$ such that $\sum a_i^2 < N_s P$
• Then we can increase some $a_k \mapsto a_k + \varepsilon$ for some $\varepsilon$ of the same sign as $a_k$, whilst keeping $\sum a_i^2 \leq N_s P$
• But then $\sum a_i^2 h_i^2 \mapsto M + (2a_k \varepsilon + \varepsilon^2) h_k^2 \geq M$, which contradicts $M$ being maximal

So we must have $$\sum a_i^2 = N_sP$$ which is our "usual" Lagrange multiplier situation.

---

The alternative is as follows - and this also completes the rest of the calculation for the above method.

Ignore the existing $\leq$ constraint for now, and consider instead the constraint $$\sum a_i^2 = \chi$$ for some unspecified $\chi$, which we'll constrain separately to be at most $N_s P$ later. We proceed as usual (as you have done, differentiating $\mathcal{L}$), finding that for each $i$, either $a_i = 0$ or $h_i^2 = \lambda$. The solution $a_i = 0 \forall i$ trivially minimises rather than maximises, so we discard it. Clearly this means that those non-zero $a_i$ must have equal values of $h_i^2$, specifically $\lambda$, and so our sum becomes $$S = \sum a_i^2 h_i^2 = \sum_{i=0}^{N_s-1} a_i^2 \lambda = \lambda \chi$$ since those with $h_i \neq \lambda$ must have $a_i = 0$ and hence these terms don't contribute to the sum.

Now we must maximise $S$ - but recall our choice of $\lambda$ is restricted to being one of the $h_i^2$. We are given that $h_0^2$ is the greatest (assuming all $h_i \geq 0$).

This leaves us with $\chi$. We return to impose the inequality constraint, which manifests itself as $\chi \leq N_s P$ - this is trivially maximised by $\chi = N_s P$, hence the maximum value of $S$ is $h_0^2 N_s P$.

This means we're technically done if all we want is the maximum value for $S$. If we're worried about what choices of $a_i$ we're allowed, let $j$ be the last index such that $h_j = \lambda$. All those $a_i$ for $i > j$ must be zero, and the remaining constraint on the $a_i$ is precisely $$\sum_{i=0}^j a_i^2 = N_sP$$ which has either two or infinitely many solutions depending on whether $j = 0$ or $j > 0$ respectively, since the constraint on the $a_i$s describes a $j$-sphere.

To explicitly give two examples,

• $j = 0 \implies a_0 = \pm \sqrt{N_s P}$
• $j = 1 \implies a_0 = \sqrt{N_s P} \cos \theta, \; a_1 = \sqrt{N_s P} \sin \theta$ for any $\theta \in [0, 2 \pi]$

Answer 3

Generally, Lagrange multipliers gives information about the structure of the solution and one needs a little more reasoning to get the answer.

In this case, however, Lagrange multipliers gives a solution (there may be more that one maximiser) assuming that $N_sP >0$.

First, note that the feasible set is compact and non empty hence a $\max$ exists.

Second, note that if the constraint is inactive, then you can increase any of the $a_k$s to make the constraint active without decreasing the cost. Hence you can assume that the constraint is active at a $\max$.

Third, assuming that $N_sP >0$, we see that the constraint gradient is non zero, hence a Lagrange multiplier exists and there is some $\lambda$ such that $a_k (h_k^2 + \lambda) = 0$.

Hence either $a_k = 0$ or $h_k^2 + \lambda = 0$. Since at least one $a_k \neq 0$ we see that there is some $i$ such that $h_i^2+\lambda = 0$. Let $I= \{ j | h_j^2+\lambda =0 \}$. Then at a $\max$ we have $a_k = 0$ for $k \notin I$ and as long as $\sum_{k \in I} a_k^2 = N_sP$ the cost is the same.

Since the cost is given by $N_s P h_i^2$, it is clear that $\lambda = - \max_k h_k^2$ and hence the $\max$ cost is $(\max_k h_k^2) NsP$.

This is not a huge surprise since the problem is essentially an LP of the form $\max\{ \sum_k x_k h_k^2 | \sum_k x_k \le N_s P, x_k \ge 0\}$.