2
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • 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$
    – sayda
    Commented 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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