  Market equilibrium is a solution concept with many applications such as
digital ad markets, fair division, and resource sharing. For many classes of
utility functions, equilibria can be captured by convex programs. We develop
simple first-order methods suitable for solving these convex programs for
large-scale markets. We focus on three practically-relevant utility classes:
linear, quasilinear, and Leontief utilities. Using structural properties of
market equilibria under each utility class, we show that the corresponding
convex programs can be reformulated as optimization of a structured smooth
convex function over a polyhedral set, for which projected gradient achieves
linear convergence. To do so, we utilize recent linear convergence results
under weakened strong-convexity conditions, and further refine the relevant
constants in existing convergence results. Then, we show that proximal gradient
(a generalization of projected gradient) with a practical linesearch scheme
achieves linear convergence under the Proximal-PL condition, a recently
developed error bound condition for convex composite problems. For quasilinear
utilities, we show that Mirror Descent applied to a new convex program achieves
sublinear last-iterate convergence and yields a form of Proportional Response
dynamics, an elegant, interpretable algorithm for computing market equilibria
originally developed for linear utilities. Numerical experiments show that
Proportional Response dynamics is highly efficient for computing approximate
market equilibria, while projected gradient with linesearch can be much faster
when higher-accuracy solutions are needed.
