Complex of differentiable manifolds associated with active sets of nonlinear optimization problems

[mkoeppe]

Just like a polytope can be written as the finite disjoint union of relative interiors of its faces, we can write the feasible set of (well-behaved...) nonlinear optimization problems as the finite disjoint union of differentiable manifolds of different dimensions. Their closures are manifolds with corners (#30080...), which together form a CW complex.

In the special case of the simplex method for LP in standard equation form:

• a basic solution is a submanifold of dimension 0 embedding into the affine space defined by the equations
• the nonbasic variables form an adapted chart of that space.

In the more general case of convex quadratic programming:

• an active set determines a submanifold (an affine subspace) of some dimension

CC: @yuan-zhou

Component: manifolds

Issue created by migration from https://trac.sagemath.org/ticket/31376

[mkoeppe]

comment:1

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1,2 +1,10 @@
 Just like a polytope can be written as the finite disjoint union of relative interiors of its faces, we can write the feasible set of (well-behaved...) nonlinear optimization problems as the finite disjoint union of differentiable manifolds of different dimensions. Their closures are manifolds with corners (#30080...), which together form a CW complex.

+In the special case of the simplex method for LP in standard equation form:
+- a basic solution is a submanifold of dimension 0 embedding into the affine space defined by the equations
+- the nonbasic variables form an adapted chart of that space.
+
+In the more general case of convex quadratic programming:
+- an active set determines a submanifold (an affine subspace) of some dimension
+
+