# The Heavy Ball Method

The heavy-ball method is a multi-step iterative method that exploits iterates prior to the most recent one. It does so by maintaining the momentum of the previous two iterates. If you imagine each iterate as a point in the trajectory of a falling ball, then the points carry with them a momentum or a velocity. The heavy-ball method exploits that velocity:

where $\alpha, \beta \geq 0$ are parameters. The heavy ball method is one way of guarding against zigzagging trajectories in iterative descent and alternating projection methods. (Scribed from Polyak’s book.)

I can’t find anything about accelerating alternating projections with the heavy-ball method, though Escalante’s book Alternating Projection Methods does describe how to perform a line search when all of the sets are affine (I imagine the technique extends beyond the affine case).

# Experiments for Alternating Projections

Steps:

1. Framework for generating random cone programs, (see extended SCS paper, look for code) generating the KKT matrix and in particular the affine set and the cone whose intersection we wish to probe 1.
2. Base class for the model: feasibility problem.
3. Base class for algorithms: iterative (projection).
4. Inherited classes, descendants of (3), that implement various projection algorithms.

One thing, though: I’d like to, at least initially, use CVXPY in order to implement the more involved acceleration schemes (for example, the plane search along the points in the affine set). Actually, I’d like to use CVXPY for all of my algorithms, because I don’t actually know how to write algorithms to project onto convex sets … (!). // Taking advantage of special cone structures.

Scratch that. I know how to write algorithms to project onto convex sets, or I vaguely know how to (subgradient descent methods, for example). What I don’t know, or don’t yet buy (it is important for me to buy this!), is whether it is often the case that it is easier to project onto $\mathcal{K}$ and $\mathcal{A}$ individually rather than onto $\mathcal{K} \cap \mathcal{A}$ directly.

1. Kind of strange because there’s only (I think) one point in the intersection of the two sets. The solution, if it exists, is unique. But I could be wrong.

# Professor Boyd [10/24/2016]

## Notes from the meeting

Goal: See if projection methods can be accelerated by more intelligent selection of the iterates. In particular, make more use of the information that we collect along the way during projection: supporting hyperplanes and their associated halfspaces, and sequences of iterates upon which to do a line search.

### Projecting onto an affine set and a convex cone is general

Consider starting with an affine set and a convex cone. This is the most general setting – it generalizes to any intersection of cones. To see this, say that we wanted to project a vector $x$ onto $C = C_1 \cap C_2 \cap \ldots \cap C_r$, each $C_i \in \mathbb{R}^n$. Form

Finding a point in $\underset{i}\cap C_i$ is equivalent to finding a point in $\tilde{C} \cap \tilde{A}$. Note that $\tilde{C}$ is a convex cone and that $\tilde{A}$ is an affine set. To project onto $\tilde{A}$ from $\tilde{C}$, we just take the average of each block $x_i$.

### Projections can be cheap, even for extremely high dimensional data

Say we have some variable $x \in \mathbb{R}^{10^7}$ and a fixed $z$ in the same space, and say we want $x$ to be the projection of $z$ onto a polyhedron. Provided that the polyhedron is defined by a small number of halfpsaces, we can compute this projection extremely cheaply. To be more concrete, our optimization problem is of the form

where $F \in \mathbb{R}^{10 \times 10^7}$. That is, $F$ is short and fat. The fact that $F$ is short is precisely what will let us compute the projection of $z$ onto the polyhedron efficiently.

The Lagrangian of the above problem is

Minimizing it in the normal way, we have

Substituting $x = z - F^T\gamma$ into our objective function eliminates both $z$ and $x$:

Note that $FF^T \in \mathbb{R}^{10 \times 10}$! Our minimization problem has become

We can solve the problem easily after paying the overhead to compute $Fz$ and $FF^T$.

### Generating a large, random cone program.

Recall the KKT conditions for the problem in SCS.

Randomly generate $z \in_{\mathcal{R}} \mathbb{R}^n$. Generate $x = \Pi_C(z)$. Then generate $s = z - \Pi(z) = \Pi_{C^*}(z)$. We will have $x^Ts = 0, x \in C, s \in C^{*}$. From there, enough will be specified to generate the data matrix $A$ and the vector $b$. What’s more, you’ll have the solution $x$, too.

### Canonical sources and algorithms to read up on

1. Borwein’s survey on alternating projections
2. On the heavy ball method and momentum
3. “FCM Method,” from the 364B notes? Something about cutting planes with memory=2. I couldn’t find it.

### Ideas on accelerating alternating projections

1. Dumbest, simplest idea (that just might work well enough): project onto the intersection of the supporting halfspaces to form a new iterate.
2. Somewhat smarter: Keep more than 2 halfspaces. (Will this help? Certainly not in $\mathbb{R}^2.$)
3. Somewhat smarter still: Project onto more the halfspaces, but also do a line/plane search of the previous $k$ iterates, $k$ a parameter.

Suggestion (2):

• Say we let $\tilde{F}$ be the supporting hyperplanes we collect for the convex cone.
• And let $F$ be a 0-1 diagonal matrix that whose $i$-th diagonal entry is 1 if and only if we’re picking up the $i$-th equality constraint.
• Then, at each step, we’re solving

Key question: Can we solve this efficiently? Will the trick above help? Will FA become bigger than A? (No.)

Suggestion (3):

$a_i$ are a finite number of previous iterates that were on the affine set. That is, we’re doing a plane search. Can we solve this cheaply? We don’t have to solve it exactly, just need to do better than projecting the last of the iterates (the most recent one) onto $\mathcal{C}$, because that’s what we do by default. We’re assuming we know how to project onto $\mathcal{C}$. Is the objective function differentiable? Does the cost still go down if we do this? Do this, then do the cutting plane strategy, then project onto affine?

Boyd was under the impression / had the feeling that if we did three “weird” things, things might just work out well. One or two might not suffice, however.

### Papers to bring up:

1. Set Intersection Problems: Supporting Hyperplanes & Quadratic Programming
• Upshot: superlinear convergence in certain cases
• Work to be done: Numerical validations on real test suite
2. SuperMann: Special case –> find point in intersection of (convex) sets

### Approaches to discuss for accelerating alternating projections:

1. Solve QP + over-project? (Note that projecting onto the intersection of two halfspaces is a simple cone projection problem.)
2. What if we just initialize our new iterate at the intersection of the two halfspaces (when finding the intersection of two sets)?
3. Randomness (Mert Pilanci’s work) (choose which halfspaces to use uniformly at random?)

### Questions:

1. Canonical sources?

### Action items:

1. Hooked into / clone the test suite (Mark N…?)
2. Implement vs. theoretical guarantees – what’s the best way to go about getting a feel for how “good” an algorithm is? A bit of both simultaneously?
• prove convergence at the very least …?

# SCS: Conic Optimization

Key Idea: SCS reduces the problem of solving a convex cone program to the problem of finding a nonzero point in the intersection of a subspace and a cone.

Key Idea: Can take many convex problems and convert them into feasibility problems by forming the KKT system (i.e., system of equations and inequalities that constitute the KKT optimality conditions)!

primal-dual pair –> hoomogeneous self-dual embedding = cvx feasability problem –> solve with ADMM

nonzero solution to embedding –> solution to original; else certificate of infeasibility

Homogeneous self-dual embeddings traditionally used in interior-point methods.

### KKT Conditions

The KKT conditions are given by

$Ax^* + s^* = b, \quad s^* \in \mathcal{K},$ $A^Ty^* + c = r^*, \quad r^* = 0, \quad y^* \in \mathcal{K}^*, \quad (y^*)^Ts^* = 0$

The KKT conditions can be embedded into a system of equations and inclusions to obtain a feasibility problem:

subject to

where the last equality implicitly encodes complementary slackness and explicitly enforces the duality gap to be zero.

### Homogeneous Self-Dual Embedding

The above KKT system has no solution if the original problem is either primal or dual infeasible. We can get around this problem by adding two non-negative variables $\tau$ and $\kappa$ to the embedding:

A special feature of this problem is that at most of of $\kappa$ and $\tau$ are nonzero because $(x, y, \tau)^T(r, s, \kappa)$ equals $0$ at every solution (due to skew symmetry), and each component of the inner product is non-negative.

Possible cases:

1. $\tau > 0$: Then the original problem has a solution ($\tau$) is a scaling factor.
2. $\tau = 0, \kappa > 0$: Then the duality gap is negative (primal or dual is infeasible).
3. $\tau = \kappa - 0$ provides us with the least information. The problem can be expressed as

Let $u = \begin{bmatrix} x \\ y \\ \tau \end{bmatrix}$, $v = \begin{bmatrix} r \\ s \\ \kappa \end{bmatrix}$, $Q$ be the big matrix above. Then the modified KKT problem becomes

$\mathcal{C} = \mathbb{R}^n \times \mathcal{K}^* \times \mathbb{R}_{+}$.

Note that the equality constraint can be rewritten as

Written this way, it becomes evident that the SCS problem can be solved with the alternating projections method.

# Change of Basis

A coordinate system is a way from translating from numbers to a vector in Euclidean space.

Say you have a set of basis vectors $b_1, b_2$ which differ from your basis vectors $e_1, e_2$.

A matrix $% $ can be thought of as a transformation that moves $e_1, e_2$ to $b_1, b_2$. B expresses the actual coordinates of a vector expressed in the foreign basis of $b_1, b_2$ (from her language to our language). The inverse $B^{-1}$ takes a vector written in our language to a vector written in her language.

Change of coordinates

Say $x = x_1e_1 + x_2e_2 + \ldots + x_ne_n$. The $x_i$ are the coordinates of $x$ in the standard basis. If $b_1, \ldots, b_n$ is another basis for $\mathbb{R}^n$, then

where $\tilde{x} = B^{-1}x$, and $\tilde{x}_i = (B^{-1})_i^Tx_i$ is the first coordinate of $x$ in the $b_1, \ldots, b_n$ basis. This is apparent because $x = BB^{-1}x = \tilde{x}_1b_1 + \ldots + \tilde{x}_nb_n$.