Convex Optimization Research Notebook

Checklist


1. The Problems.

Each problem must eventually be cast as a feasibility problem. In particular, the feasibility problem must be cast as finding a point in the intersection of an affine set and a cone. Note that the cone, however, may be the cross-product of multiple different cones.

2. + 3. The Algorithms

.

Alternating projections

Dykstra’s

ADMM

Halfspace Eliminating Alternating Projections (memory )

Halfspace Eliminating Alternating Projections (memory )

Halfspace Eliminating Alternating Projections, with momentum

Halfspace Eliminating Alternating Projections, with plane search / momentum

Halfspace Eliminating Alternating Projections, with plane search / momentum and additional problem transformations

4. Theoretical Analyses

Halfspace Eliminating Alternating Projections (free, from Pang)

Halfspace Eliminating Alternating Projections, with plane search

Halfspace Eliminating Alternating Projections, with plane search and additional problem transformations

5. The Test Cases

2D feasibility problems, for intuition’s sake.

Intersection of second-order cone and affine set, randomly generated

Random cone problems of varying sizes.

  • NB: Can use the method described in the long SCS paper to generate these problems. Will need to take generated problem and form the self-dual homogeneous embedding in order to recover the feasibility problem, however.

Open test suite for feasibility problems?

  • To the best of my knowledge, none exist!