TransWikia.com

Are basic feasible solutions, vertices, and extreme points equivalent for semidefinite programs (SDPs)?

Mathematics Asked on November 26, 2021

First some definitions. Given a polyhedron (intersection of finitely many halfspaces) $P subseteq mathbb{R}^n$, we say a point $x in P$ is

  • a vertex if there exists $c in mathbb{R}^n$ such that $c^mathsf{T} x < c^mathsf{T} y$ for all $y in P, y ne x$,
  • an extreme point if there do not exists points $u, v ne x$ in $P$ such that $x$ is a convex combination of $u$ and $v$, and
  • a basic feasible solution (BFS) if at least $n$ linearly independent constraints are tight at $x$.

These terms are equivalent for linear programs. The definitions and the proof that they are in fact equivalent for linear programs come from here. I will include how I intuitively understand the proof in the general case since I think this is more important than the formal proof:

  1. Vertex $x$ is also an extreme point. Assume that $x$ isn’t an extreme point, i.e., it can be written as a convex combination of some other points $u,v in P$. But then $x$ isn’t actually a vertex since it lies on a line inside $P$, so there is no way there could exist a hyperplane through $x$ that only intersects $x$ and nothing else in $P$.

  2. Extreme point $x$ is also a BFS. Assume that $< n$ constraints are tight at $x$. Then find a point $y$ in $P$ at which $n$ constraints are tight and these tight constraints include those constraints tight at $x$. Then there exists a line segment entirely in $P$ which goes through $x$. It has $y$ at one end and a point a little bit past $x$ in the opposite direction at the other. (Very informal, but you get the point, haha.)

    Or as an alternative proof, assume the vectors defining (i.e., perpendicular to) the hyperplane constraints tight at $x$ don’t form a basis for $mathbb{R}^n$ (equivalent to assuming $< n$ tight constraints). Then, if you throw these vectors into the rows of a matrix, that matrix will kill some vector $y$. If you make (a scaled version of) $y$ your displacement vector, you can use it to move back and forth a tiny bit from $x$ and still stay in $P$. (Actually following this direction is how you would find $y$ [point at which $n$ constraints are tight with shared constraints] in the first version.)

  3. BFS $x$ is also a vertex. We need to find $c in mathbb{R}^n$ which makes $x$ satisfy the vertex condition. Consider the $n$ vectors defining the hyperplane constraints tight at $x$. Assuming proper signs, the angles between any pair must be between $0$ and $180$ degrees exclusive as otherwise the constraints aren’t linearly independent or the feasible region isn’t convex/nonempty. Then there exists a vector which is strictly within 90 degrees of all of them. Take this as $c$.


Now consider a generic SDP:

Minimize $C bullet X$ such that $A_i bullet X ge b_i$ for all $i in [m]$, and $X succcurlyeq 0$.

Are the three also the same for an SDP? Can we generalize even farther?

Intuitively, I think the answer is that extreme points and vertices are the same, but BFSs are different. I couldn’t find anything on it online.

One Answer

The Positive Semidefinite Cone is a closed pointed cone. Hence its only extreme point is the origin. See section 2.7.2.1 "cone invariance" of Convex Optimization Euclidean Distance Geometry, Jon Dattorro, Mε βoo Publishing

Any SDP having additional constraints rendering the origin infeasible has no extreme points.

On a related note, the rank one matrices in the PSD cone constitute its extreme directions.

Answered by Mark L. Stone on November 26, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP