2

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?

Community
  • 1
Daniel R
  • 3,199
  • I think that the argument was correct, just a little too brief. When a function has no interior extrema, the extreme values happen on the boundary, which means some of the $a_i$'s is $0$.

    Now, if say a_1=0, the constrain becomes $2a_2+\cdots+5a_5=1$. We can then replace $a_5$ by $a_1'$ and get the constrain $a_1'+2a_2+3a_3+4a_4=1$, which is the case $a_5=0$ but with smaller $f$.

    I believe the author thought that the idea was simple and skipped it.

     – Quang Hoang Aug 01 '14 at 15:01
  • @QuangHoang Your comment is better suited for my previous question, which has an answer that elaborates what you write to some extent. Please comment there if you have anything to add, it would be very much appreciated. – Daniel R Aug 01 '14 at 16:16

1 Answers1

1

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?

yoknapatawpha
  • 4,009
  • Thanks! The equations do not agree with mine, since the use of Lagrange multipliers introduces another variable. Thanks to your response I understand what the authors are doing, although there might be some typos here and there... The bounty is yours! – Daniel R Aug 12 '14 at 11:15