Optimization Online


Foundations of gauge and perspective duality

A.Y. Aravkin (saravkin***at***uw.edu )
J.V. Burke (jvburke***at***uw.edu )
D. Drusvyatskiy (ddrusv***at***uw.edu)
M.P. Friedlander (mpf***at***cs.ubc.ca )
K. MacPhee (kmacphee***at***uw.edu )

Abstract: Common numerical methods for constrained convex optimization are predicated on efficiently computing nearest points to the feasible region. The presence of a design matrix in the constraints yields feasible regions with more complex geometries. When the functional components are gauges, there is an equivalent optimization problem---the gauge dual-- where the matrix appears only in the objective function and the corresponding feasible region is easy to project onto. We revisit the foundations of gauge duality and show that the paradigm arises from an elementary perturbation perspective. We therefore put gauge duality and Fenchel duality on an equal footing, explain gauge dual variables as sensitivity measures, and show how to recover primal solutions from those of the gauge dual. In particular, we prove that optimal solutions of the Fenchel dual of the gauge dual are precisely the primal solutions rescaled by the optimal value. The gauge duality framework is extended beyond gauges to the setting when the functional components are general nonnegative convex functions, including problems with piecewise linear quadratic functions and constraints that arise from generalized linear models used in regression.

Keywords: convex optimization, gauge duality, nonsmooth optimization, perspective function

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: 2/27/2017

Download: [PDF]

Entry Submitted: 02/27/2017
Entry Accepted: 02/28/2017
Entry Last Modified: 02/28/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society