3
$\begingroup$

As a followup to this question, I am looking for references for the problem of maximizing $x^TQx$, where $Q$ is positive definite, subject to linear equality and inequality constraints bounding all variables. @prubin explained feasible region is a bounded polytope and that the maximum must occurs at a corner of this polytope. Are there textbooks that develop this theory? I'm specifically wondering about formal definition of "corner" and a proof of his point that "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."

I could have posted this as a comment to the original answer but I see at least one other question dealing with a similar maximization problem (one differene: my feasible region is bounded), so I thought it would be worthwhile to have references stated in a separate answer.

$\endgroup$
3
  • 4
    $\begingroup$ I think any text book that covers the KKT-conditions and the associated 2nd order necessary condition should allow you derive those principles. $\endgroup$ Commented Sep 29, 2021 at 1:05
  • $\begingroup$ en.wikipedia.org/wiki/Bauer_maximum_principle states the result. It is provided and proved as theorem 7.42 in "Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB", by Amir Beck my.siam.org/Store/Product/viewproduct/?ProductId=25906139, which also addresses extreme points. $\endgroup$ Commented Sep 29, 2021 at 11:17
  • $\begingroup$ The Bauer maximum principle doesn't explain why "corners" result in better result than points on hyperfaces. $\endgroup$ Commented Sep 29, 2021 at 12:31

1 Answer 1

4
$\begingroup$

You can find all the necessary theoretical elements (and a lot more) in the book "Convex Analysis" by R. Tyrrell Rockafellar. Fair warning: reading this book is tantamount to a graduate class in convex analysis. I suspect most books on mathematical programming will contain the relevant results, although quite possibly by citing other sources rather than spending the necessary space to develop them from scratch. For instance, the book "Combinatorial Optimization: Algorithms and Complexity" by Papadimitriou and Steiglitz contains a theorem (2.3) that asserts that every convex polytope is the convex hull of its vertices. Rather than including a proof, they cite three sources (including Rockafellar).

If you accept that theorem, the part about the optimum being at a vertex is easy. Let $P$ be the polytope, $f$ a convex function to be maximized over $P$ and $x^*\in P$ any maximizer of $f$. By the theorem, we can write $x^*$ as $$x^*=\sum_{i=1}^n \alpha_i v_i$$where $v_1,\dots,v_n$ are the vertices of $P$ and the $\alpha_i$ are nonnegative weights such that $\sum_i \alpha_i = 1$ (using the definition of a convex combination). Since $f$ is convex, $$f(x^*)=f(\sum_{i=1}^n \alpha_i v_i)\le \sum_{i=1}^n \alpha_i f(v_i)\le \sum_{i=1}^n \alpha_i f(x^*) = f(x^*),$$where the last inequality comes from the assumption that $x^*$ maximizes $f$ over $P$. If none of the vertices with positive weight in the sum are maximizers, that inequality becomes strict and you end up with a contradiction. So at least one vertex is a maximizer.

In general, that does not preclude also having a maximizer that is not a vertex, but since $Q$ is positive definite (rather than positive semidefinite) in the question, $f(x)=x^\prime Q x$ is strictly convex, making the first inequality strict (leading to a contradiction) if more than one of the $\alpha_i$ is positive. If only one of them is positive, it must be 1, and so $x^*$ must be one of the vertices.

$\endgroup$
2
  • $\begingroup$ Thanks--what about your heuristic explanation of a corner being the intersection of $n$ hyperplanes? Is that kind of topological fact also in the same reference? I need this for showing that $n$ of the inequalities are equalities. I think you also mentioned "independence" of the constraints. $\endgroup$
    – sayda
    Commented Sep 30, 2021 at 16:28
  • $\begingroup$ Suppose that you have $n$ variables and $k$ binding constraints (intersecting hyperplanes). The points in that intersection satisfy a system of $k$ linear equations in $n$ unknowns. For that intersection to be a single point (corner), you need to have $n$ equations, and they have to be linearly independent (so the matrix is full rank). $\endgroup$
    – prubin
    Commented Sep 30, 2021 at 17:14

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.