Finding the maxima of a multivariable function using Lagrange's Multipliers

Question

I'm practicing Lagrange Multipliers (LM)$^{[1]}$ with the following self-made question:

Given $a + b + c + d + e = 1$, where $a, b, c, d, e \notin R^-$. Find the maximum value of $ab + bc + cd + de$

I already know that the answer is $1/4^{[2]}$. But, as an exercise, I want to use LM.

---

My Attempt:

Let, $$ f(a, \ ... \ ,e) = ab + bc + cd + de \\ g(a, \ ... \ ,e) = a + b + c + d + e = 1 $$

Then, define: $$ \mathcal{L}(a, \ ... \ ,e, \lambda) = f(a, \ ... \ ,e) - \lambda \cdot [g(a, \ ...\ ,e) - 1] \\ \therefore \mathcal{L}(a, ... ,e, \lambda) = ab + bc + cd + de - \lambda \cdot [a + b + c + d + e - 1] $$

Now, $\nabla\mathcal{L} = 0$ would give maxima / minima. On partial differentiation, we get,

$$ \begin{align} b = \lambda \qquad (from \ \ \frac{\delta\mathcal{L}}{\delta a}) \tag 1\\ d = \lambda \qquad (from \ \ \frac{\delta\mathcal{L}}{\delta e}) \tag 2\\ a + c = \lambda \qquad (from \ \ \frac{\delta\mathcal{L}}{\delta b}) \\ c + e = \lambda \qquad (from \ \ \frac{\delta\mathcal{L}}{\delta d}) \\ b + d = \lambda \qquad (from \ \ \frac{\delta\mathcal{L}}{\delta c}) \tag 3 \end{align}$$

Here, equations $(1)$, $(2)$ and $(3)$ seems contradicting. Why it is so?

---

Note: I tested the same approach with $2$, $3$ and $4$ variables and it gave me correct results. Why so?

References:

_{[1]: Lagrange multipliers, examples - Khan Academy
[2]: If $a,b,c,d,e,f$ are non negative real numbers such that $a+b+c+d+e+f=1$, then find maximum value of $ab+bc+cd+de+ef$}

Answer 1

The KKT conditions cannot be solved because $x^*$ is not the optimal point using the constraints you have implemented in your Lagrangian. If we do not implement the inequality constraints $$ \begin{align} a \geq 0 \\ b \geq 0 \\ c \geq 0 \\ d \geq 0 \\ e \geq 0 \end{align} $$ then we can let $$a = t, b = t, e = -t, d = -t \text{ and } c=1$$ such for all $t$ the constraint $g(a, \dots, e) = 0$ is satisfied and our function $$f(a, \dots, e) = t^2 +t - t + t^2 = 2t^2$$ is unbounded. We can just let $t\rightarrow \infty$ and our function does not permit a solution.

As @Toni says we must implement also the inequality constraints $a, b, c, d, e \geq 0$ in the Lagrangian. This yields $$ \begin{align} \mathcal{L}(a, b, c, d, e, \lambda, \mu_a, \mu_b, \mu_c, \mu_d, \mu_e) &= ab + bc + cd + de \\ &+ \lambda(a+b+c+d+e-1) \\ & + \mu_a a + \mu_b b + \mu_c c + \mu_d d + \mu_e e \end{align} $$ As you say optimality implies $\nabla \mathcal{L} = 0$ $$ \begin{align} a + \lambda + \mu_a = 0\\ a + c + \lambda + \mu_b = 0 \\ b + d + \lambda + \mu_c = 0 \\ c + e + \lambda + \mu_d = 0 \\ e + \lambda + \mu_e = 0 \end{align} $$ This more flexible system can be solved for $a=b= \frac{1}{2}, c=d=e=0$.
$$ \begin{align} a + \lambda = 0\\ a + \lambda = 0 \\ b + \lambda + \mu_c = 0 \\ \lambda + \mu_d = 0 \\ \lambda + \mu_e = 0 \end{align} $$ We find no contradiction. Note that $\mu_a = \mu_b = 0$ as these inequailities are inactive for $a, b > 0$.

Answer 2

This Lagrangian can be solved introducing some slack variables $\epsilon_k$ transforming the inequalities into equations as follows. Calling

$$ f = a b + b c + c d + d e $$

we have

$$ L = f + \lambda(a+b+c+d+e-1) + \mu_1(a-\epsilon_1^2)+\mu_2(b-\epsilon_2^2)+\mu_3(c-\epsilon_3^2)+\mu_4(d-\epsilon_4^2)+\mu_5(e-\epsilon_5^2) $$

so the independent variables are now

$$ \{a,b,c,d,e,\lambda,\mu_1,\cdots,\mu_5,\epsilon_1,\cdots,\epsilon_5\} $$

The stationary conditions are

$$ \nabla L = \left\{ \begin{array}{rcl} b+\lambda +\mu _1&=&0 \\ a+c+\lambda +\mu _2&=&0 \\ b+d+\lambda +\mu _3&=&0 \\ c+e+\lambda +\mu _4&=&0 \\ d+\lambda +\mu _5&=&0 \\ a-\epsilon _1^2&=&0 \\ b-\epsilon _2^2&=&0 \\ c-\epsilon _3^2&=&0 \\ d-\epsilon _4^2&=&0 \\ e-\epsilon _5^2&=&0 \\ \epsilon _1 \mu _1&=&0 \\ \epsilon _2 \mu _2&=&0 \\ \epsilon _3 \mu _3&=&0 \\ \epsilon _4 \mu _4&=&0 \\ \epsilon _5 \mu _5&=&0 \\ a+b+c+d+e-1&=&0 \\ \end{array} \right. $$

and after solving and choosing, the feasible solutions are

$$ \left[ \begin{array}{ccccccccccccccccc} f & a & b & c & d & e & \mu_1 & \mu_2 & \mu_3 & \mu_4 & \mu_5 & \epsilon_1^2 & \epsilon_2^2 & \epsilon_3^4&\epsilon_4^2&\epsilon_5^2&\lambda \\ \frac{1}{8} & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & 0 & 0 & -\frac{1}{4} & 0 & 0 & \frac{1}{4} & \frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{4} & -\frac{1}{4} \\ \frac{1}{4} & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{4} & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 & -\frac{1}{2} \\ \frac{1}{4} & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & -\frac{1}{2} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & -\frac{1}{2} \\ \end{array} \right] $$

NOTE

The slack variables when null indicates that the corresponding restriction is active. Now it is necessary proceed with the stationary points qualification.

Answer 3

$\color{brown}{\textbf{Task transformations.}}$

Let $$p=a+c,\quad q=e+c,\tag1$$ then the task is to maximize the function $$f(b,p,d,q\,|\,c) = bp+dq\tag2$$ under the conditions \begin{cases} b+p+d+q = 1+c\\ c\in[0,1],\quad b\in[0,1-c],\quad d\in[0,1-c]\\ p\in[c,1],\quad q\in[c,1],\tag3 \end{cases}

Denote $$g(c) = \max\limits_{b,p,d,q} f(b,p,d,q\,|\,c),\tag4$$ then $$\max\limits_{a,b,c,d,e} ab+bc+cd+de = \max g(c).\tag5$$

$\color{brown}{\textbf{Parametric maximum among the trivial cases.}}$

Taking in account the symmetry of the task (the pair $(b,p)$ is symmetric to the pair $(d,q)$), it suffices to consider the next cases.

$\mathbf{1.\quad f(0,p,d,q\,|\,c) = dq.}$

The nesessary conditions of the parametric maximum are $$p=c,\quad d+q=1,\quad d\in[0,1-c],\quad q\in[c,1],$$ then $$\max f(0,p,d,q\,|\,c) = \max f(0,c,d,q\,|\,c) = \max\limits_{q\in[c,1]} q(1-q) = c(1-c).\tag6$$

$\mathbf{2.\quad f(b,c,d,q\,|\,c) = bc+dq.}$

The nesessary conditions of the parametric maximum are $$b+d+q=1,\quad b\in[0,1-c],\quad d\in[0,1-c],\quad q\in[c,1].$$ Since $$\max f(1-c,c,0,c\,|\,c) = c(1-c),$$ $$\max f(0,c,d,q\,|\,c) = \max\limits_{q\in[c,1]} q(1-q) = c(1-c),$$ $$\max f(b,c,1-b-q,q\,|\,c) = bc+\max\limits_{q\in[c,1-b]} q(1-b-q) = bc+c(1-b-c)=c(1-c),$$ then the least value of $(2)$ among the trivial cases is $$g_v(c) = c(1-c).\tag7$$

$\color{brown}{\textbf{Parametric conditional maximum.}}$

In accordance with the LM method, the stationary points of the function $(2)$ under the condition $(3.1)$ can be defined via the function $$F(\lambda,b,p,d,q\,|\,c) = bp+dq + \lambda(b+p+d+q-1-c)$$ from the system of the conditions $F'_\lambda = F'_b = F'_p = F'_d = F'_q = 0,$ or \begin{cases} b+p+d+q=1+c\\ p+\lambda = b+\lambda = d+\lambda = q+\lambda = 0, \end{cases} with the solution $$b=p=d=q = \dfrac{1+c}4,\quad\text{if}\quad c\in\left[0,\dfrac13\right],$$ $$g_s(c) = f\left(\dfrac{1+c}4,\dfrac{1+c}4,\dfrac{1+c}4,\dfrac{1+c}4\,\Big|\ c\right) = \dfrac{(1+c)^2}8,\quad c\in\left[0,\dfrac13\right].\tag8$$

$\color{brown}{\textbf{The global maximum.}}$

Taking in account $(7),(3),(8),(5),$ one can get $$G_v = \max\limits_{c\in[0,1]} g_v(c) = \dfrac14,$$ $$G_s = \max\limits_{c\in[0,\,^1/_3]} g_s(c) = \dfrac{(1+\,^1/_3)^2}8 = \dfrac29,$$ $$\color{brown}{\mathbf{\max\limits_{a+b+c+d+e = 1} ab+bc+cd+de = \dfrac14.}}$$