Opened 9 months ago

Last modified 3 months ago

#31376 new enhancement

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.5
Component: manifolds Keywords:
Cc: yzh Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Change History (3)

comment:1 Changed 7 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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.

comment:2 Changed 6 months ago by mkoeppe

  • Cc yzh added
  • Description modified (diff)

comment:3 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.