Convex Optimization Research Notebook

First results for alternating projection acceleration

  1. Plane search does not obey fejer monotonicity
  2. Surprisingly, initial evidence implies that the heavy ball method only hurts. This is of course not a conclusion, but rather an anecdotal observation.
  3. QP (mem == 2) + overprojection seems to work decently well. Is the QP projection cheap? Probably. Closed form? Maybe.

The baseline algorithms:

  1. Alternating projections
  2. Alternating projections with heavy-ball momentum

The state-of-the-art:

  1. Dykstra

What did I try?

Problem set-up:

  • 1500-dimensional variable
  • Affine constraint with random matrix \in , 1% sparsity.
  • , constrained to be in the second-order cone.

(1) A plane search:

are a finite number of previous iterates that were on the affine set, the convex cone. It turns out that performing this plane search produces sequences that are not Fejer monotonic!

(2) Halfpsace Outer Approximation (HOA)

I used the most recent halfspaces generated by projecting onto the convex sets, and obtained the next iterate by projecting onto the intersection of these sets. This works “fairly well.” It works “better” than Dykstra’s if we only look at the number of iterations. Of course, the number of iterations isn’t a “good” metric, but it’s a start. Even small () works well.

(3) HOA with randomly accepting new hyperplanes.

I don’t understand this well yet, but I suspect there is something interesting here.

(4) HOA with momentum

Anecdotally, momentum “helps” with respect to the number of iterations. Over-projecting seems to be more useful than interpolating between the previous velocity and the current one. Again, very anecdotal evidence.

Future work and experiments

(0) Write-up what I’ve done and learned this quarter and send it to Prof. Boyd.

(1) Anneal the momentum (say by a factor of , the # of iterations)?

(2) Flip a p-biased coin to decide whether or not to oveproject

(3) Flip a p-biased coin and overproject by a lot

(4) Take advantage of short-and-fat matrix structure, if it arises

(5) Project onto random subsets of equality constraints

(6) Test on the homogeneous self-dual embedding of a cone program (SCS).

Questions for Professor Boyd

(1) Does a closed-form projector onto the intersection of two halfspaces exist, and/or can it be computed cheaply by some means?

(2) Why is the optimal value returned by CVXPY inaccurate? (roughly 10e-2 precision.)

(3) Lots of stuff I want to try empirically. If anything stands out, will go forward with theoretical analysis. HOA + momentum seems the most promising right now. Does that sound good?

(4) Logistics for continuing the work next quarter? Is an independent study still possible? I think I have sufficient momentum now to carry me forward. Will you be reachable by email? (If not, that’s totally understandable!)

(5) I’m still very much interested in TA-ing convex in the spring, if the offer still stands.