# optimizing quadratic form over bounded polytope

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.

• I think any text book that covers the KKT-conditions and the associated 2nd order necessary condition should allow you derive those principles. Commented Sep 29, 2021 at 1:05
• 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. Commented Sep 29, 2021 at 11:17
• The Bauer maximum principle doesn't explain why "corners" result in better result than points on hyperfaces. Commented Sep 29, 2021 at 12:31

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.
• 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. Commented Sep 30, 2021 at 16:28
• 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).