1
$\begingroup$

While reading a combinatorics paper about packing densities in compositions, I encountered the following optimization problem.

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$$

(See below for written out expressions.)

The authors conclude that $\alpha_5 = 0$ for the optimum with the following motivation:

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

Question: Could someone elaborate a bit on what the authors are referring to and how they apply it in this specific problem? Is this related to linear programming? Polytope theory?


The function written out:

$$\begin{align}f(\alpha_1, \alpha_2, \alpha_3, \alpha_4, \alpha_5)=&\alpha_1\alpha_2\alpha_3 + \alpha_1\alpha_2\alpha_4 + \alpha_1\alpha_2\alpha_5 + \\ &\alpha_1\alpha_3\alpha_4 + \alpha_1\alpha_3\alpha_5 + \alpha_1\alpha_4\alpha_5 + \\ &\alpha_2\alpha_3\alpha_4 + \alpha_2\alpha_3\alpha_5 + \alpha_2\alpha_4\alpha_5 + \\ &\alpha_3\alpha_4\alpha_5 \end{align}$$

And the constraints: $$\alpha_1+2\alpha_2+3\alpha_3+4\alpha_4+5\alpha_5=1$$ $$0 \le \alpha_1, \dots, \alpha_5 \le 1$$


EDIT: Please note that the question is not how to solve the complete optimization problem. This can be done with Lagrange multipliers, or possibly other techniques, about which I will probably ask a question later onI have posted a follow-up question, once the fact that $\alpha_5 = 0$ is established (and, at least numerically, even before that). The question is what techniques the authors use, and how they use them, to conclude $\alpha_5 = 0$.

$\endgroup$
  • $\begingroup$ Your problem is a cubic optimization problem. Unfortunatelly, the literature about cubic problems is scarce. In my opinion, your problem is not related to linear programming. $\endgroup$ – The Pheromone Kid Jun 17 '14 at 8:48
  • $\begingroup$ I think for any $\alpha_k$, the objective function is linear. Given that the constraint is also linear, the optimum lies in some corner point. Since $\alpha_5=1$ violates the constraint, so $\alpha_5=0$. $\endgroup$ – ziyuang Jun 19 '14 at 10:59
  • $\begingroup$ "for any $\alpha_k$, the objective function is linear." This doesn't matter. Your argument applies only if the constraint is linear in all variables. $\endgroup$ – Michael Grant Jun 24 '14 at 15:25
6
+50
$\begingroup$

The sentence you have quoted is wrong. That is an error in their paper. Fortunately, it looks like Innuo's answer looks correct, so they happened upon the truth anyway.

Let me explain what they are trying to do. Consider the problem\begin{array}{ll}\text{minimize} & f(x) \\ \text{subject to} & x\in C\end{array}where $C$ is a closed, bounded, connected set, and $f$ is differentiable on $\mathop{\textrm{int}} C$, the interior of $C$.

If we can find a point $\bar{x}\in\mathop{\textrm{int}} C$ satisfying $\nabla f(\bar{x})=0$, then $\bar{x}$ is a candidate solution to the constrained problem. Of course, we'll usually need some additional conditions too (for instance, $f$ is convex) before we can be sure it is a global optimum, but at least it's a candidate. For example, consider the problem $$\begin{array}{ll}\text{minimize} & f(x)=x^2\\\text{subject to}&-1\leq x\leq 1\end{array}$$In this case, $\nabla f(\bar{x})=0$ at $\bar{x}=0$, which is on the interior of the feasible region $C=[-1,1]$. $f$ is convex, so $\bar{x}$ is the global minimum of $f$, and also the solution to the constrained problem.

On the other hand, if $\nabla f(x)\neq 0$ for all $x\in\mathop{\textrm{int}} C$, then it must be the case that the solution to the problem is on the boundary of $C$. It's a simple logical argument: there are no candidates on $\mathop{\textrm{int}} C$, so the solution must be on $x\in C-\mathop{\textrm{int}} C=\mathop{\textrm{bd}} C$. We need no other conditions to draw this conclusion. So, for example, consider the problem $$\begin{array}{ll}\text{minimize} & f(x)=x^2\\\text{subject to}&1\leq x\leq 2\end{array}$$Now $\bar{x}=0$ is outside of $\mathop{\textrm{int}} C=(1,2)$, so the solution must lie on the boundary $\mathop{\textrm{bd}}C=\{1,2\}$. We can easily verify that $x=1$ is the solution in this case.

That's what the authors of this paper are going for here. Unfortuantely, they have made a mistake. The feasible region is $$C=\big\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5)\,\big|\,0\leq \alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5\leq 1,\,\textstyle\sum_i i\alpha_i=1\big\}$$ This feasible region has an empty interior---that is, $\mathop{\textrm{int}}C=\emptyset$! So of course the solution must lie on the boundary of the feasible region, because $\mathop{\textrm{bd}} C\equiv C$. It's tautological, and not very helpful. In particular, it does not follow from this that $\alpha_5\in\{0,1\}$, because there are plenty of points satisfying $0<\alpha_5<1$ on the boundary of $C$.

Perhaps they were thinking about the relative interior, which is $$\mathop{\textrm{relint}} C=\big\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5)\,\big|\,0<\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5<1,\,\textstyle\sum_i i\alpha_i=1\big\}$$ But the derivative test I describe above, and which they applied in their paper, cannot be applied without modification to the relative interior. It only applies to the true interior of $C$.

One way to "save" the derivative test here is to eliminate the equality constraint and a single variable, say $\alpha_5$. If we do this, then we get the new objective $$\begin{aligned} f(x) &= \alpha_1\alpha_2\alpha_3+\alpha_1\alpha_2\alpha_4+\alpha_2\alpha_3\alpha_4\\&\qquad+\tfrac{1}{5}(\alpha_1\alpha_2+\alpha_2\alpha_3+\alpha_3\alpha_4)(1-\alpha_1-2\alpha_2-3\alpha_3-4\alpha_4)\end{aligned}$$ And the feasible region becomes $$C=\big\{(\alpha_1,\alpha_2,\alpha_3,\alpha_4)\,\big|\,0\leq\alpha_1,\alpha_2,\alpha_3,\alpha_4\leq 1,\,0\leq 1-\alpha_1-2\alpha_2-3\alpha_3-4\alpha_4\leq 5\big\}$$ This feasible region has a non-empty interior, so the derivative test could be applied to this modified $f(x)$. Another way to save it would be to look at the equality-constrained problem \begin{array}{ll} \text{maximize} & \textstyle \sum_{1\leq i<j<k\leq 5} \alpha_i\alpha_j\alpha_k \\ \text{subject to} & \textstyle \sum_i i \alpha_i = 1 \end{array} and conclude that the Lagrangian of this problem $$L(\alpha,\lambda ) = - \textstyle \sum_{1\leq i<j<k\leq 5} \alpha_i\alpha_j\alpha_k - \lambda \left( \textstyle \sum_i i \alpha_i - 1 \right)$$ has no critical points satisfying $\nabla L(\alpha,\lambda)=0$ on the interior of the inequality constraints $$0<\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_4<1$$ I have no idea if that's feasible. But what I know you can't do is just look at $f(x)$ by itself.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Many thanks, this is exactly what I wanted. I will need some time to digest it though, but the bounty is yours! :) $\endgroup$ – Daniel R Jun 25 '14 at 14:06
  • $\begingroup$ I wish you could have split the bounty somehow. I know that you were looking for more of an explanation of the author's thinking, so technically my answer is closer to what you asked for. But I think Innuo's answer is exactly the kind of insight the authors should have used! Regardless, thank you! $\endgroup$ – Michael Grant Jun 25 '14 at 15:34
  • $\begingroup$ Oops, have a little min/max mixup in here. Fixing... $\endgroup$ – Michael Grant Jun 25 '14 at 17:11
6
$\begingroup$

Note that the constraints imply that $\alpha_4 \leq \frac{1}{4}$ and $\alpha_5 \leq \frac{1}{5}$ for any feasible point.

Now consider the objective value at a feasible point $(\alpha_1, \alpha_2, \alpha_3, \alpha_4, \alpha_5)$. If $\alpha_5 > 0$, then the objective is strictly larger at the point $ (\alpha_1, \alpha_2, \alpha_3, \alpha_4 + \frac{5 \alpha_5}{4}, 0)$, which can checked to be feasible also.

I don't see why the fact that the interior has no extremum even matters.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You've done the authors of this paper a favor: their confusion that $\alpha_5=0$ is right, as you have shown; but their reasoning is wrong! $\endgroup$ – Michael Grant Jun 24 '14 at 16:08
  • $\begingroup$ I missed the fact that the interior is empty. Thanks for checking. I wonder if the authors gave a hand-wavy argument once they found that for all examples they tried $\alpha_5$ happened to be $0$. $\endgroup$ – Innuo Jun 24 '14 at 16:18
  • $\begingroup$ Yes, that's exactly my guess. I mean, it's a common argument to make, that the solution is on the boundary of the feasible set. Kind of a formulaic thing to do, really. They just got sloppy. $\endgroup$ – Michael Grant Jun 24 '14 at 17:45
  • $\begingroup$ Thanks Innuo, this is very helpful. $\endgroup$ – Daniel R Jun 25 '14 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.