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$
3
  • $\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$ Commented Jun 17, 2014 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$
    – Ziyuan
    Commented Jun 19, 2014 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$ Commented Jun 24, 2014 at 15:25

2 Answers 2

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.

$\endgroup$
3
  • $\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
    Commented Jun 25, 2014 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$ Commented Jun 25, 2014 at 15:34
  • $\begingroup$ Oops, have a little min/max mixup in here. Fixing... $\endgroup$ Commented Jun 25, 2014 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.

$\endgroup$
4
  • $\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$ Commented Jun 24, 2014 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
    Commented Jun 24, 2014 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$ Commented Jun 24, 2014 at 17:45
  • $\begingroup$ Thanks Innuo, this is very helpful. $\endgroup$
    – Daniel R
    Commented Jun 25, 2014 at 14:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .