I am maximizing a convex function (a positive definite quadratic form, if it makes a difference) subject to $0\le x_1\le \ldots \le x_n\le 1$ and a linear constraint $a^\top x+b=0$. Can I conclude that the maximum occurs where some of those inequalities are equalities, or something of the sort?
1 Answer
Yes. Your feasible region is a convex (bounded) polytope, which means that every point in the feasible region can be written as a convex combination of extreme points. Let's say that your function is $f()$, the maximum occurs at $\bar{x}\in [0,1]^n$, and $\bar{x} = \sum_{i=1}^k \alpha_i x^{(i)}$, where the $x^{(i)}\in [0,1]^n$ are extreme points of the feasible region and the $\alpha_i$ are nonnegative weights with $\sum_{i=1}^k \alpha_i = 1$. By the convexity of $f()$, $$f(\bar{x}) \le \sum_{i=1}^k \alpha_i f(x^{(i)}),$$so for $\bar{x}$ to maximize $f()$ over the feasible region every $x^{(i)}$ in the sum with $\alpha_i >0$ must maximize $f()$.
An extreme point (corner) of a polytope is the intersection of a bunch of linearly independent bounding hyperplanes (binding constraints), so there will be at least one maximizer of $f()$ where $n$ of the constraints are binding.
-
1$\begingroup$ When you say at least $n$ of the constraints are binding at the corner, $n$ is the number of hyperplanes/constraints that intersect to make up that corner of the polytope? $\endgroup$– saydaCommented Sep 10, 2021 at 2:15
-
$\begingroup$ Yes. In two dimensions, the hyperplanes are lines, and you need two (not parallel to each other) intersecting to get a point (corner). In three dimensions, hyperplanes are planes, and you need three with linearly independent normals intersecting to get a corner, etc. $\endgroup$– prubin ♦Commented Sep 10, 2021 at 17:24