Clarification on optimization problem, continued

136 Views Asked by At

Background

This is a follow-up to this question. The problem statement is the same:

Maximize $$f(\alpha_1, \dots, \alpha_5) = \sum_{1 \le i < j < k \le 5} \alpha_i \alpha_j \alpha_k$$ with the constraints $$0 \le \alpha_1, \dots, \alpha_5 \le 1, \quad\sum_{i=1}^5i\alpha_i=1$$

The authors write

Differentiation yields no interior extreme points, so we conclude $\alpha_5 = 0$ for the optimum.

This is apparently a flawed reasoning according to the nice answers given in the previous question.

Question

Now, the authors continue by finding the values for $\alpha_n$, under the (correct) assumption that $\alpha_5 = 0$. Quote from the paper:

(Differentiation yields no interior extreme points, so we conclude $\alpha_5 = 0$ for the optimum.) Differentiating again, and setting the derivatives to zero, we get the equations $$\begin{align} 0 &= \alpha_3+\alpha_2-8\alpha_4\alpha_3-8\alpha_4\alpha_2-8\alpha_3\alpha_2-3\alpha_3^2-2\alpha_2^2\\ 0 &= \alpha_4+\alpha_2-6\alpha_4\alpha_3-8\alpha_4\alpha_2-6\alpha_3\alpha_2-4\alpha_4^2-2\alpha_2^2\\ 0 &= \alpha_4+\alpha_3-8\alpha_4\alpha_3-4\alpha_4\alpha_2-4\alpha_3\alpha_2-4\alpha_4^2-3\alpha_3^2\\ \alpha_1&=1-\left( 5\alpha_5-4\alpha_4-3\alpha_3-2\alpha_2 \right) \end{align}$$

They then use a CAS to derive quartic equations, to which the $\alpha_n$'s are solutions.

The problem can be solved by use of Lagrange multipliers, which I have done, but that method does not give the same equations. Also, the wording "Differentiating again, ..." seems to rule out the use of Lagrange, doesn't it?

To my question: What method do the authors use to get the equation system shown above?

1

There are 1 best solutions below

1
On BEST ANSWER

This answer is here partly because it can't fit in a comment and partly because in theory there could be another mistake in the paper. I'm interested to see if what I have below agrees with the equations you got from using Lagrange multipliers. Can you check?

From what's written, I think the authors eliminate $\alpha_1$ using the equality constraint and then set \begin{equation} \frac{\partial f}{\partial \alpha_2} = \frac{\partial f}{\partial \alpha_3} = \frac{\partial f}{\partial \alpha_4} = 0 \end{equation} to derive a system of four equations in the variables $\alpha_1, \alpha_2, \alpha_3,\alpha_4$ to find optima. This doesn't give the same equations as you've given above, but it sounds like that's what they mean by the phrase "Differentiating again..."

To get the fourth equation, we take the equality constraint (using $\alpha_5 = 0$) and rearrange it to get \begin{equation} \tag{1} \alpha_1 = 1 - 4\alpha_4 - 3\alpha_3 - 2\alpha_2, \end{equation} and if you plug in $\alpha_5 = 0$ in the fourth equation in the list you've given above, this agrees with what's in the paper. I think this equation makes it pretty clear that they are eliminating $\alpha_1$ by using the equality constraint.

We can then compute $\frac{\partial f}{\partial \alpha_2}$ as \begin{equation} \frac{\partial f}{\partial \alpha_2} = \alpha_1\alpha_3 + \alpha_1\alpha_4 + \alpha_3\alpha_4. \end{equation} Setting this equal to $0$ and plugging in Equation $(1)$ gives \begin{equation} 0 = \alpha_4 + \alpha_3 - 6\alpha_4\alpha_3 - 2\alpha_3\alpha_2 - 2\alpha_4\alpha_2 - 4\alpha_4^2 - 3\alpha_3^2. \end{equation} Doing the same for $\frac{\partial f}{\partial \alpha_3}$ gives \begin{equation} \frac{\partial f}{\partial \alpha_3} = \alpha_1\alpha_2 + \alpha_1\alpha_4 + \alpha_2\alpha_4 \end{equation} and then \begin{equation} 0 = \alpha_4 + \alpha_2 - 3\alpha_4\alpha_3 - 5\alpha_4\alpha_2 - 3\alpha_3\alpha_2 - 4\alpha_4^2 - 2\alpha_2^2. \end{equation}

Repeating this procedure for $\frac{\partial f}{\partial \alpha_4}$ gives \begin{equation} \frac{\partial f}{\partial \alpha_4} = \alpha_1\alpha_2 + \alpha_1\alpha_3 + \alpha_2\alpha_3 \end{equation} and finally \begin{equation} 0 = \alpha_3 + \alpha_2 - 4\alpha_4\alpha_2 - 4\alpha_3\alpha_2 - 4\alpha_4\alpha_3 - 3\alpha_3^2 - 2\alpha_2^2. \end{equation}

Do these equations agree with what you got using Lagrange multipliers?