Dual gauge programs,with applications to quadratic programming and the minimum-norm problem

A gauge functionf(·) is a nonnegative convex function that is positively homogeneous and satisfiesf(0)=0. Norms and pseudonorms are specific instances of a gauge function. This paper presents a gauge duality theory for a gauge program, which is the problem of minimizing the value of a gauge functionf(·) over a convex set. The gauge dual program is also a gauge program, unlike the standard Lagrange dual. We present sufficient conditions onf(·) that ensure the existence of optimal solutions to the gauge program and its dual, with no duality gap. These sufficient conditions are relatively weak and are easy to verify, and are independent of any qualifications on the constraints. The theory is applied to a class of convex quadratic programs, and to the minimuml _p norm problem. The gauge dual program is shown to provide a smaller duality than the standard dual, in a certain sense discussed in the text.