  In optimization the duality gap between the primal and the dual problems is a
measure of the suboptimality of any primal-dual point. In classical mechanics
the equations of motion of a system can be derived from the Hamiltonian
function, which is a quantity that describes the total energy of the system. In
this paper we consider a convex optimization problem consisting of the sum of
two convex functions, sometimes referred to as a composite objective, and we
identify the duality gap to be the 'energy' of the system. In the Hamiltonian
formalism the energy is conserved, so we add a contractive term to the standard
equations of motion so that this energy decreases linearly (i.e.,
geometrically) with time. This yields a continuous-time ordinary differential
equation (ODE) in the primal and dual variables which converges to zero duality
gap, i.e., optimality. This ODE has several useful properties: it induces a
natural operator splitting; at convergence it yields both the primal and dual
solutions; and it is invariant to affine transformation despite only using
first order information. We provide several discretizations of this ODE, some
of which are new algorithms and others correspond to known techniques, such as
the alternating direction method of multipliers (ADMM). We conclude with some
numerical examples that show the promise of our approach. We give an example
where our technique can solve a convex quadratic minimization problem orders of
magnitude faster than several commonly-used gradient methods, including
conjugate gradient, when the conditioning of the problem is poor. Our framework
provides new insights into previously known algorithms in the literature as
well as providing a technique to generate new primal-dual algorithms.
