arXiv Analytics

Sign in

arXiv:1702.08649 [math.OC]AbstractReferencesReviewsResources

Foundations of gauge and perspective duality

Alexandre Y. Aravkin, James V. Burke, Dmitriy Drusvyatskiy, Michael P. Friedlander, Kellie MacPhee

Published 2017-02-28Version 1

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. measurements. 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.

Related articles: Most relevant | Search more
arXiv:1308.4191 [math.OC] (Published 2013-08-19)
Projected Subgradient Minimization versus Superiorization
arXiv:2006.01014 [math.OC] (Published 2020-06-01)
Approximate methods for phase retrieval via gauge duality
arXiv:1601.06893 [math.OC] (Published 2016-01-26)
Applications of gauge duality in robust principal component analysis and semidefinite programming