Foundations of gauge and perspective duality

Introduction

Sensitivity of the optimal values and solutions of optimization problems, with respect to perturbations in the problem data, is a central concern of Fenchel-Rockafellar duality theory. Lagrange duality can be regarded as a special case of this theory, in which perturbations to the data are introduced in a particular manner. Gauge duality, on the other hand, as introduced in 1987 by Freund , was developed without any reference to sensitivity. It relies instead on a special polarity correspondence that exists for nonnegative, positively homogeneous convex functions that vanish at the origin; these are known as gauge functions. In 2014, Friedlander, Macêdo, and Pong made partial progress towards connecting gauge and Lagrange dualities. In the present work, we show that gauge duality may be regarded as a particular application of Fenchel-Rockafellar duality theory that is different than the one required for Lagrange duality. This connection provides a useful vantage point from which to develop new algorithms for an important class of convex optimization problems. We also describe how gauge duality theory can be extended beyond the optimization of gauge functions to the optimization of all convex functions that are bounded below. We call this extension perspective duality.

A convenient and fully general formulation for our approach is the problem

The formulation Eq. Gp gives rise to two different “dual” problems:

Here $\rho^{\circ}$ and $\kappa^{\circ}$ are the polars of $\rho$ and $\kappa$, which are also gauge functions; see Section 2.1 for a precise definition. In the important case $\sigma=0$, we interpret $\sigma\rho^{\circ}$ as the indicator function of the closure of the domain of $\rho^{\circ}$ (see the discussion in LABEL:sect:assumptions). The first problem Eq. Ld is the standard Lagrangian (or Fenchel-Rockafellar) dual, which is the dual problem typically considered in connection with convex optimization problems. Strong duality, reflected in the equality

and in the attainment of the optimal value of the Lagrange primal-dual pair, holds under mild interiority conditions often referred to as the Slater constraint qualification. The second problem Eq. Gd is the gauge dual and is less well-known. Under interiority conditions similar to those required by Lagrange duality, strong duality holds in the gauge duality setting; this is reflected in the analogous equality

and in the attainment of the optimal value of the gauge primal-dual pair.

This set-up immediately yields the primal-dual pair

Fenchel-Rockafellar duality theory flows from an appropriate choice of $F$. We show that gauge duality fits equally well into this framework under a judicious choice of the perturbation function $F$, thereby putting Fenchel-Rockafellar and gauge duality theories on an equal footing. Strong duality, primal-dual optimality conditions, and an interpretation of the gauge dual solutions as sensitivity measures—i.e., subgradients of the value function—quickly follow; cf. Section 3.2. These results, in particular, answer an open question posed by Freund in his original work , which asked for an interpretation of gauge dual variables for problems with nonlinear constraints. It also completes a partial analysis by Friedlander et al. on the interpretation of gauge dual variables as sensitivity measures.

This viewpoint allows us to prove a striking relationship between optimal solutions of the primal and optimal solutions of the Lagrangian dual of the gauge dual: the two coincide up to scaling by the optimal value (Section 3.5). Consequently, Lagrangian primal-dual methods applied to the gauge dual can be used to recover solutions of the original primal problem. We illustrate this idea in Section 7 with an application of Chambolle and Pock’s primal-dual algorithm to a specific problem instance.

Notation and assumptions

The derivation of our results relies on standard notions from convex analysis. Unless otherwise specified, we generally follow Rockafellar for standard definitions and notation, including domains and epigraphs, relative interiors, convex conjugate functions, subdifferentials, polar sets, etc. In this section we collect less well-known definitions and notation used throughout the paper, and establish blanket assumptions on the problem data.

where $f^{\infty}(x)$ is the recession function of $f$ [20, Theorem 8.5]. A calculus for the perspective transform $f\mapsto f^{\pi}$ is described by Aravkin, Burke, and Friedlander [2, Section 3.3] and, for the infinite-dimensional case, by Combettes , where properties of the perspective transform are described in detail. We often apply more than one transformation to a function, and in such cases, the multiple transformations are applied in the order that they appear; e.g., $f^{\pi\circ}:=(f^{\pi})^{\circ}$.

2 Gauge functions

The following is only a brief description of gauge functions. A complete description is given by Rockafellar [20, Section 15].

which is also a gauge and satisfies $\kappa^{\circ\circ}=\kappa$ when $\kappa$ is closed [20, Theorem 15.1]. For example, if $\kappa$ is a norm then $\kappa^{\circ}$ is the corresponding dual norm. Note the identity

It follows directly from (2.2) and positive homogeneity of a gauge function that its polar can be characterized as the support function to the unit level set, i.e.,

Moreover, $\kappa$ and $\kappa^{\circ}$ satisfy a Hölder-like inequality

which we refer to as the polar-gauge inequality. The zero level set

plays a key role when $\sigma=0$. It is straightforward to show that

whenever $\kappa$ is closed, where $\mathcal{U}_{\kappa}^{\infty}$ is the recession cone for $\mathcal{U}_{\kappa}$ [20, Section 8]. We include proofs of (2.6) in Appendix A.

3 Assumptions on the feasible region

Define the following primal and dual feasible sets:

The nonnegativity of $\rho$ implies that the Slater condition can fail when $\sigma=0$, and thus special attention is required. In this case, we make the replacement

The gauge primal (Gp) and dual (Gd) problems are said to be feasible, respectively, if the following intersections are nonempty:

Similarly, the primal and dual problems are said to be relatively strictly feasible, respectively, if the following intersections are nonempty:

If the intersections above are nonempty, with interior replacing relative interior, then we say that the problems are strictly feasible. We have

which follows from Rockafellar [20, Theorem 7.6] when $\sigma>0$, and from the convention (2.9) when $\sigma=0$.

We assume throughout that $\rho(b)>\sigma$. Otherwise, $\mathcal{F}_{p}$ contains the origin, which is a trivial solution of (Gp). This assumption is consistent with classical applications in signal processing and machine learning, where the corresponding assumption is that the data $b$ does not entirely consist of noise.

Perturbation analysis for gauge duality

Modern treatment of duality in convex optimization is based on an interpretation of multipliers as giving sensitivity information relative to perturbations in the problem data. No such analysis, however, has existed for gauge duality. In this section we show that for a particular kind of perturbation, the gauge dual (Gd) can in fact be derived via such an approach.

is obtained from the general perturbation theory by setting $F(x,u)=f(Ax+u)+g(x)$. In that case, the primal-dual pair takes the familiar form

Under certain conditions, described in the following theorem, strong duality holds, i.e. $p(0)=p^{\star\star}(0)$, and the optimal values are attained.

The inequality $p(0)\geq-q(0)$ always holds.

Optimal solutions are characterized jointly through the conditions

2 A perturbation for gauge duality

We now show that the problems Eq. Gp and Eq. Gd constitute a primal-dual pair under the framework set out by Theorem 3.1. The key is to postulate the correct pairing function $F$. In the derivation below, we show that the gauge primal-dual pair corresponds to the primal and dual value functions

where, as in (Gd), we use the convention described by (2.8) and (2.9). The parameters $u$ and $(t,\theta)$ are perturbations to the primal and dual gauge problems, respectively. This perturbation scheme differs significantly from that used in Fenchel-Rockafellar duality—cf. (3.1)—because of the product $\mu u$.

We begin by observing that $v_{p}(0)$ is equal to the optimal value of the primal Eq. Gp. Because $u$ and $\mu$ appear as a product in this definition, it is convenient to reparametrize the problem by setting $\lambda:=1/\mu$ and $w:=x/\mu$. The positive homogeneity of $\kappa$ and $\rho$ allows us to equivalently phrase the primal value function as

In particular, this reparameterization shows that the value function $v_{p}$ is convex because it is the infimal projection of a convex function, and it is proper when the primal Eq. Gp is feasible.

Observe that the matrix $W$ is nonsingular.

which correspond to the general definitions shown in (1.1). Note that the function $p$ is the reciprocal of $v_{p}$, as formalized in the following lemma (stated without proof).

Equality $v_{p}(u)=-1/p(u)$ holds provided that $v_{p}(u)$ is nonzero and finite. Moreover, $v_{p}(u)=0$ if and only if $p(u)=-\infty$, and $p(u)=0$ if and only if $v_{p}(u)=+\infty$.

We now compute the conjugate of $F$, which is needed to derive the dual value function $q$. By Rockafellar and Wets [23, Theorem 11.23(b)],

The application of Theorem 3.1 asks that we evaluate these conjugates at $(t,\theta)=(0,0)$, which yields the expression

recovers, up to a sign change, the required gauge dual problem (Gd) when $\sigma>0$. When $\sigma=0$, we also recover the gauge dual problem (Gd) by making the appropriate substitutions (2.8) under the convention (2.9).

This discussion justifies the definition of the dual perturbation function $v_{d}(t,\theta):=\inf_{y}\,F^{\star}(t,\theta,y)$, which is equivalent to the expression (3.2b). Note that $v_{d}(0,0)$ is the optimal value of (Gd). In summary, $(-1/v_{p})$ and $v_{d}$, respectively, play the roles of $p$ and $q$ as defined in (3.3). In the application of Theorem 3.1, we identify $x$ with $(w,\lambda)$, and $v$ with $(t,\theta)$.

3 Proof of gauge duality

We now use the perturbation framework from Section 3.2 to prove weak and strong duality results for the gauge duality setting. Theorem 3.5 [15, section 5] is already known, but the proof via perturbation is new.

The following auxiliary result ties the feasibility of the gauge pair (Gp) and (Gd) to the domain of the value function. The proof of this result, which is largely an application of the calculus of relative interiors, is deferred to Appendix B.

The duality relations in the gauge framework follow analogous principles to Lagrange duality, except that instead of an additive relationship between the primal and dual optimal values the relationship is multiplicative. The following theorem summarizes weak and strong duality for gauge optimization.

Set $\nu_{p}:=v_{p}(0)$ and $\nu_{d}:=v_{d}(0,0)$. Then the following relationships hold for the gauge primal-dual pair (Gp) and (Gd).

(Basic Inequalities) It is always the case that

In particular, if $\nu_{p}=0$ (resp. $\nu_{d}=0$), then (Gd) (resp. (Gp)) is infeasible.

(Weak duality) If $x$ and $y$ are primal and dual feasible, then

(Strong duality) If the dual (resp. primal) is feasible and the primal (resp. dual) is relatively strictly feasible, then $\nu_{p}\nu_{d}=1$ and the gauge dual (resp. primal) attains its optimal value.

To simplify notation, in this proof we denote the optimal value of the primal value function by $p_{0}\equiv p(0)$.

Part (a). We begin with the inequality (i). Theorem 3.1 guarantees the inequality

By Lemma 3.3, whenever $\nu_{p}$ is nonzero and finite, equality $p_{0}=-1/\nu_{p}$ holds, which together with (3.4) yields (i). If, on the other hand, $\nu_{p}=+\infty$, then (i) is trivial. Finally, if $\nu_{p}=0$, Lemma 3.3 yields $p_{0}=-\infty$, and hence (3.4) implies $\nu_{d}=+\infty$, and (i) again holds. Thus, (i) holds always. To establish (ii), it suffices to consider the case $\nu_{d}=0$. From (3.4) we conclude $p_{0}\geq 0$, that is either $p_{0}=0$ or $p_{0}=+\infty$. By Lemma 3.3, the first case $p_{0}=0$ implies $\nu_{p}=+\infty$ and therefore (ii) holds. The second case $p_{0}=+\infty$ implies that the primal problem is infeasible, that is $\nu_{p}=+\infty$, and again (ii) holds. Thus (ii) holds always, as required.

Part (b). Because the gauge primal and dual problems are both feasible, $\nu_{p}$ and $\nu_{d}$ are nonzero and finite so the result follows from part (a).

4 Gauge optimality conditions

Our perturbation framework can be harnessed to develop optimality conditions for the gauge pair that relate the primal-dual solutions to subgradients of the corresponding value function. This yields a version of parts (b) and (d) in Theorem 3.1 that are specialized to gauge duality.

The following relationships hold for the gauge primal-dual pair (Gp) and (Gd).

If the primal is relatively strictly feasible and the dual is feasible, then the set of optimal solutions for the dual is nonempty and coincides with

If it is further assumed that the primal is strictly feasible, then the set of optimal solutions to the dual is bounded.

If the dual is relatively strictly feasible and the primal is feasible, then the set of optimal solutions for the primal is nonempty with solutions $x^{*}=w^{*}/\lambda^{*}$, where

If it is further assumed that the dual is strictly feasible, then the set of optimal solutions to the primal is bounded.

We use the sensitivity interpretation given by Theorem 3.7 to develop a set of necessary and sufficient optimality conditions that mirror the more familiar KKT conditions from Lagrange duality. For a primal-dual optimal pair $(x^{*},y^{*})$, the condition $\rho^{\circ}(y^{*})=0$ characterizes a degenerate case when $\sigma>0$ because in that case the primal constraint is inactive at $x^{*}$ (i.e., $\rho(b-Ax^{*})<\sigma$). On the other hand, the dual constraint is always active at optimality because the positive homogeneity of the dual objective and the dual constraint imply $\langle b,y^{*}\rangle-\sigma\rho^{\circ}(y^{*})=1$. The full primal-dual optimality conditions for gauge duality are described in the following theorem.

Suppose both problems of the gauge dual pair Eq. Gp and Eq. Gd are relatively strictly feasible, and the pair $(x^{*},y^{*})$ is primal-dual feasible. Then $(x^{*},y^{*})$ is primal-dual optimal if and only if it satisfies the conditions

First suppose that $(\bar{x},\bar{y})$ satisfies (3.5a)-(3.5d). By Theorem 3.5, to show that $(\bar{x},\bar{y})$ is primal-dual optimal it is sufficient to show that $\kappa(\bar{x})\cdot\kappa^{\circ}(A^{T}\!\bar{y})=1$. Add (3.5c) and (3.5d) to obtain

By combining the above with (3.5b) we obtain $\kappa(\bar{x})\cdot\kappa^{\circ}(A^{T}\!\bar{y})=1$, as desired.

Suppose now that $(x^{*},y^{*})$ is primal-dual optimal. We begin by assuming that $\sigma>0$ and obtain the case $\sigma=0$ by applying the result for the $\sigma>0$ case under the replacement (2.8). By the positive homogeneity of $\kappa^{\circ}$ and the optimality of $y^{*}$, (3.5b) holds. Also note that $\kappa(x^{*})$ and $\kappa^{\circ}(A^{T}\!y^{*})$ are both nonzero and finite because of the strong duality guaranteed by Theorem 3.5.

Define $\lambda^{*}:=1/\kappa(x^{*})$ and $w^{*}:=\lambda^{*}x^{*},$ so that $\kappa(w^{*})=1$. By Theorem 3.1(e) and Theorem 3.7(b), we must have $(0,0,y^{*})\in\partial F(w^{*},\lambda^{*},0)$. Since the primal problem is relatively strictly feasible, we can apply [20, Theorem 23.9] to deduce the characterization

where $\operatorname{\mathcal{N}}_{\mathcal{C}}(\cdot)$ denotes the normal cone to a set $\mathcal{C}$. We now consider two cases. First, suppose $\rho(\lambda^{*}b-Aw^{*})=\lambda^{*}\sigma.$ Then (3.5a) holds, and by straightforward computations involving only (2.4) and the definitions of normal cones and subdifferentials, we have

and $\operatorname{\mathcal{N}}_{\mathcal{U}_{k}}(w^{*})=\set{v}{\kappa^{\circ}(v)\leq\langle v,w^{*}\rangle}$. Substitute these formulas into (3.6) to obtain

We deduce the existence of $z^{*}\in\partial\rho(\lambda^{*}b-Aw^{*})$ and $\mu^{*}\geq 0$ such that

Note that $\mu^{*}=0$ cannot satisfy (3.7b), hence (3.7c), together with the polar-gauge inequality and the fact that $\kappa(w^{*})=1$, implies

Equality must hold in the above, and dividing through by $\lambda^{*}>0$ we see that (3.5c) is satisfied. Finally, we aim to show that (3.5d) holds using the fact that $y^{*}\in\mu^{*}\partial\rho(\lambda^{*}b-Aw^{*})$. From the characterization (2.4) of the polar, we have

In particular, this characterization implies $\langle y^{*}/\mu^{*},\lambda^{*}b-Aw^{*}\rangle\geq\langle 0,\lambda^{*}b-Aw^{*}\rangle=0.$ If $\rho(\lambda^{*}b-Aw^{*})=0$, then by the polar-gauge inequality (2.5) we have

which gives condition (3.5d) after dividing through by $\lambda^{*}$. On the other hand, if $\rho(u)>0$ then the set (3.8) is given by $\set{y}{\rho(u)=\langle y,u\rangle,\,\rho^{\circ}(y)=1}$. Thus when $\rho(\lambda^{*}b-Aw^{*})>0$, we again have $\langle y^{*}/\mu^{*},\lambda^{*}b-Aw^{*}\rangle=\rho^{\circ}(y^{*}/\mu^{*})\cdot\rho(\lambda^{*}b-Aw^{*})$, and multiplying through by $\mu^{*}/\lambda^{*}$ and applying (3.5a) gives (3.5d).

We have shown the forward implication of the theorem when $\rho(\lambda^{*}b-Aw^{*})=\lambda^{*}\sigma.$ The other case we need to consider is when $\rho(\lambda^{*}b-Aw^{*})<\lambda^{*}\sigma,$ or equivalently when $\rho(b-Ax^{*})<\sigma$. An easy argument (e.g., see [12, Proposition 2.14(iv)]) shows

Thus if $(x^{*},y^{*})$ is primal-dual optimal, then (3.5a)-(3.5d) hold, as claimed. This finishes the proof for $\sigma>0$.

Let us now consider the case when $\sigma=0$ and apply what we have just proved to the pair (Gp) and (Gd) under the replacement (2.8). Then $(x^{*},y^{*})$ is primal-dual optimal if and only if the conditions (3.5a)-(3.5d) hold with $(\rho,\sigma)=(\delta_{\mathcal{H}_{\rho}},1)$, i.e.,

If we combine this with primal feasibility, $\rho(b-Ax^{*})=0$, and use the identity (2.9) that $0\cdot\rho^{\circ}=\delta_{\mathcal{H}_{\rho}^{\circ}}$ , then these conditions are equivalent to (3.5a)-(3.5d) for $\sigma=0$, $\rho$, and $\rho^{\circ}$ as written above.

The following corollary describes a variation of the optimality conditions outlined by Theorem 3.9. These conditions assume that a solution $y^{*}$ of the dual problem is available, and gives conditions that can be used to determine a corresponding solution of the primal problem. An application of the following result appears in LABEL:sect:recovery_ex.

Suppose that the primal-dual pair (Gp) and (Gd) are each relatively strictly feasible. If $y^{*}$ is optimal for (Gd), then for any primal feasible $x$ the following conditions are equivalent:

$\langle x,A^{T}\!y^{*}\rangle=\kappa(x)\cdot\kappa^{\circ}(A^{T}\!y^{*})$ and $b-Ax\in\partial(\sigma\rho^{\circ})(y^{*})$;

$A^{T}\!y^{*}\in\kappa^{\circ}(A^{T}\!y^{*})\cdot\partial\kappa(x)$ and $b-Ax\in\partial(\sigma\rho^{\circ})(y^{*})$,

We use the optimality conditions given in Theorem 3.9. As noted before, by the optimality of $y^{*}$ we automatically have equality (3.5b) in the dual constraint.

We first show that (b) implies (a). Suppose (b) holds. Then (3.5c) holds automatically. From the characterization (2.4) of the polar, we have

where the case $\sigma=0$ uses the convention (2.9). Thus, $\partial(\sigma\rho^{\circ})(y^{*})$ is the set of maximizing elements in this supremum. Because $b-Ax\in\partial(\sigma\rho^{\circ})(y^{*})$, it holds that $\rho(b-Ax)\leq\sigma$. If we additionally use the polar-gauge inequality, we deduce that

and therefore the above inequalities are all tight. Thus conditions (3.5a) and (3.5d) hold, and by Theorem 3.9, $(x,y)$ is a primal-dual optimal pair.

We next show that (a) implies (b). Suppose that $x$ is optimal for (Gp). Then the first condition of (b) holds by (3.5c), and (3.5a) and (3.5d) combine to give us

This implies that $z:=b-Ax$ is a maximizing element of the supremum in (3.9), and thus $b-Ax\in\partial(\sigma\rho^{\circ})(y^{*}).$

Finally, to show the equivalence of (b) and (c), note that by the polar-gauge inequality, $\langle x,A^{T}\!y^{*}\rangle=\kappa(x)\cdot\kappa^{\circ}(A^{T}\!y^{*})$ if and only if $x$ minimizes the convex function $\kappa^{\circ}(A^{T}\!y^{*})\,\kappa(\cdot)-\langle\cdot,A^{T}\!y^{*}\rangle.$ This, in turn, is true if and only if $0\in\kappa^{\circ}(A^{T}\!y^{*})\,\partial\kappa(x)-A^{T}\!y^{*}$, or equivalently, $A^{T}\!y^{*}\in\kappa^{\circ}(A^{T}\!y^{*})\cdot\partial\kappa(x)$.

5 The relationship between Lagrange and gauge multipliers

We now use the perturbation framework for duality to establish a relationship between gauge dual and Lagrange dual variables. We begin with an auxiliary result that characterizes the subdifferential of the perspective function (2.1). Combettes [10, Prop. 2.3(v)] also describes an equivalent formula for the subdifferential, though the derivation and subsequent form of the expression are very different. The formula in Lemma 3.13 is more suitable for our purposes.

Using the expression for the subdifferential of a support function, $(z,\gamma)$ achieves the supremum of (3.10) if $z\in\partial g(x/\mu)$ and $-\gamma=g^{\star}(z)$. On the other hand, if $\mu=0$ then

We now state the main result relating the optimal solutions of (Gp) to the optimal solutions of the Lagrange dual of (Gd).

Suppose that the gauge dual (Gd) is relatively strictly feasible and the primal (Gp) is feasible. Let $(L_{p})$ denote the Lagrange dual of (Gd), and let $\nu_{\scriptscriptstyle L}$ denote its optimal value. Then

We first note that $(L_{p})$ can be derived via the framework of Theorem 3.1 through the Lagrangian value function

Here $h$ plays the role of $p$ in Theorem 3.1; cf. [23, Example 11.41]. Strong duality in Theorem 3.5 guarantees that $h(0)$ is nonzero and finite, and by Lemma 3.4,

Thus, it follows from Theorem 3.1 that the optimal points $z^{*}$ for $(L_{p})$ are characterized by $z^{*}\in\partial h(0)$. Note also that $h(0)=\nu_{L}$.

On the other hand, by Theorem 3.7(b) the solutions to (Gp) are precisely the points $w^{*}/\lambda^{*}$ such that $(w^{*},\lambda^{*})\in\partial v_{d}(0,0)$. Thus to relate the solution sets of $(L_{p})$ and (Gp), we must relate $\partial h(0)$ and $\partial v_{d}(0,0)$.

For $\theta$ in a neighborhood of zero and all $t$, by positive homogeneity of $\kappa^{\circ}$ and $\rho^{\circ}$ we have

Thus by Lemma 3.13, $\partial v_{d}(0,0)=\set{(z,-h^{\star}(z))}{z\in\partial h(0)}.$ However, for $z\in\partial h(0)$ the Fenchel-Young equality gives us

Thus we obtain the convenient description

and the set of optimal solutions for (Gp) is precisely $\frac{1}{\nu_{L}}\partial h(0)$.

Perspective duality

The functions $f^{\sharp}$ and $g^{\sharp}$ are the polars of the perspective transforms of $f$ and $g$. This transform is a key operation needed to derive perspective duality. In the next section we describe properties of that transform and its application to the derivation of the perspective-dual pair. Throughout this section, we assume that $\sigma>\inf_{u}g(u)\geq 0$.

An explicit characterization of the perspective-polar transform is given by

This representation can be obtained by applying the definition of the gauge polar (2.2) to the perspective transform as follows:

which yields (4.1) after dividing through by $\lambda$. Rockafellar’s extension [20, p.136] of the polar gauge transform to nonnegative convex functions that vanish at the origin coincides with $f^{\sharp}(z,-1)$.

The following theorem provides an alternative characterization of the perspective-polar transform in terms of the more familiar Fenchel conjugate $f^{\star}$. It also provides an expression for the perspective-polar of $f$ in terms of the Minkowski function generated by the epigraph of the conjugate of $f$, i.e.,

which is a gauge. Nonnegativity of $f$ is not required for the first part of this result.

The following result relates the level sets of the perspective-polar transform to the level sets of the conjugate perspective. This result is useful in deriving the constraint sets for certain perspective-dual problems for which there is no closed form for the perspective polar; cf. Example 5.5.

The following chain of equivalences follows from Theorem 4.1:

Define $\alpha=\inf\set{\lambda>0}{f^{\star\pi}(z,\lambda)\leq-\xi}$.

We first show that $f^{\sharp}(z,\xi)\leq\mu$ implies $0\leq\mu$ and $f^{\star\pi}(z,\mu)\leq-\xi$. By (4.2), $0\leq\alpha\leq\mu$. If $\alpha<\mu$, there exists $\lambda$ with $0<\lambda<\mu$ such that $f^{\star\pi}(z,\lambda)\leq-\xi.$ Because $f$ is nonnegative, $\mu f\geq\lambda f$, and thus $(\mu f)$. In particular,

On the other hand, if $\alpha=\mu$, there exists a sequence $\lambda_{k}\to\mu$ such that $f^{\star\pi}(z,\lambda_{k})\leq-\xi$ for each $k$. Now by the lower semi-continuity of $f^{\star\pi}$, we obtain

This establishes the forward implication of the theorem.

which gives $f^{\sharp}(z,\xi)\leq 0=\mu$ in the limit, since $f^{\sharp}$ is closed.

Two useful calculus rules are now developed that govern the perspective-polar transform when applied to gauge functions and separable sums.

Suppose that $f$ is a closed proper gauge. Then

Use expression (4.1) for this derivation. When $\xi>0$, take $x=0$ in the infimum in (4.1) to deduce that $f^{\sharp}(z,\xi)=+\infty.$ On the other hand, when $\xi\leq 0$, the positive homogeneity of $f$ implies that $f^{\sharp}(z,\xi)=f^{\circ}(z)$. We leave the details to the reader. More generally, if $f$ vanishes at the origin, then $f^{\sharp}(z,\xi)=+\infty$ for all $\xi>0.$

2 Derivation of the perspective dual via lifting

We now derive the relationship between the primal and dual problems (Np) and (Nd) by lifting (Np) to an equivalent gauge optimization problem, and then recognizing (Nd) as its gauge dual.

A point $x^{*}$ is optimal for (Np) if and only if $(x^{*},1)$ is optimal for the gauge problem

where $\rho(z,\mu,\tau):=g^{\pi}(z,\tau)+\delta_{\{0\}}(\mu)$ is a gauge function.

By definition of $f^{\pi}$, $x^{*}$ is optimal for (Np) if and only if the pair $(x^{*},1)$ is optimal for

The following equivalence follows from the definition of $\rho$:

Thus we arrive at the constraint expressed in (4.3).

It follows from the canonical dual pairing (Gp) and (Gd) that the gauge dual of (4.3) is

Because $\rho$ is separable in $(z,\mu)$ and $\beta$, it follows from [15, Proposition 2.4] that

Since $\delta_{\{0\}}^{\circ}(\alpha)$ is identically zero, the result follows.

The next result generalizes the gauge duality result of Theorem 3.5 to the case where $f$ and $g$ are convex and nonnegative but not necessarily gauges. We parallel the construction in (2.7), and for this section only redefine the feasible sets by

Thus, (Np) is relatively strictly feasible if

Similarly, (Nd) is relatively strictly feasible if there exists a triple $(y,\alpha,\mu)$ such that

Let $\nu_{p}$ and $\nu_{d}$, respectively, denote the optimal values of the pair (Np) and (Nd). Then the following relationships hold for the perspective dual pair (Np) and (Nd).

(Basic Inequalities) It is always the case that

Thus, $\nu_{p}=0$ and $\nu_{d}=0$, respectively, imply that (Nd) and (Np) are infeasible.

(Weak duality) If $x$ and $(y,\alpha,\mu)$ are primal and dual feasible, then

(Strong duality) If the dual (resp. primal) is feasible and the primal (resp. dual) is relatively strictly feasible, then $\nu_{p}\nu_{d}=1$ and the perspective dual (resp. primal) attains its optimal value.

Parts (a) and (b) follow immediately from the analogous result in Theorem 3.5, together with Theorem 4.7 and Corollary 4.9.

By [20, Corollary 6.8.1], the above description yields

A similar argument verifies that (Nd) is relatively strictly feasible if and only if (4.4) is relatively strictly feasible. Strong duality then follows from relative interiority, Corollary 4.9, Theorem 4.7, and the analogous strong-duality result in Theorem 3.5.

3 Optimality conditions

The following result generalizes Theorem 3.7 to include the perspective-dual pair.

Suppose (Np) is strictly feasible. Then the tuple $(x^{*},y^{*},\alpha^{*},\mu^{*})$ is perspective primal-dual optimal if and only if

By construction, $x^{*}$ is optimal for (Np) if and only if $(x^{*},1)$ is optimal for its gauge reformulation (4.3). Apply Theorem 3.7 to (4.3) and the corresponding gauge dual (Nd) to obtain the required conditions.

The following result mirrors Corollary 3.11 for the perspective-duality case.

$\langle x,A^{T}\!y^{*}\rangle+\alpha^{*}=f(x)\cdot f^{\sharp}(A^{T}\!y^{*},\alpha^{*})$ and $(b-Ax,1)\in\sigma\partial g^{\sharp}(y^{*},\mu^{*});$

$A^{T}\!y^{*}\in f^{\sharp}(A^{T}\!y^{*},\alpha^{*})\cdot\partial f(x)$ and $(b-Ax,1)\in\sigma\partial g^{\sharp}(y^{*},\mu^{*}).$

By construction, $x$ is optimal for (Np) if and only if $(x,1)$ is optimal for its gauge reformulation (4.3). Apply Corollary 3.11 to (4.3) and its gauge dual (Nd) to obtain the equivalence of (a) and (b). To show the equivalence of (b) and (c), note that by the polar-gauge inequality, $\langle(x,1),(A^{T}\!y^{*},\alpha^{*})\rangle\leq f^{\pi}(x,1)\cdot f^{\sharp}(A^{T}\!y^{*},\alpha^{*})$ for all $x$, or equivalently,

The inequality is tight for a fixed $x$ if and only if $x$ minimizes the function $h:=f^{\sharp}(A^{T}\!y^{*},\alpha^{*})f(\cdot)-\langle\cdot,A^{T}\!y^{*}\rangle-\alpha^{*}.$ This in turn is equivalent to $0\in\partial h(x)$, or

This shows the equivalence of (b) and (c) and completes the proof.

Section 6 illustrates an application of Corollary 4.15 for recovering primal optimal solutions from perspective-dual optimal solutions.

4 Reformulations of the perspective dual

Two reformulations of the perspective dual (Nd) may be useful depending on the functions $f$ and $g$ involved in (Np). First, an important simplification of the perspective dual occurs when one or both of these functions are gauges.

If $f$ is a gauge, then a triple $(y^{*},\alpha^{*},\mu^{*})$ is optimal for (Nd) if and only if $\alpha^{*}\leq 0$ and $(y^{*},\mu^{*})$ is optimal for

If, in addition, $g$ is a gauge, then a triple $(y^{*},\alpha^{*},\mu^{*})$ is optimal for (Nd) if and only if $\alpha^{*}\leq 0$, $\mu^{*}\leq 0$, and $y^{*}$ solves (Gd).

Follows from the formulas for $f^{\sharp}$ and $g^{\sharp}$ established in Section 4.1.1.

Theorem 4.3 also allows us to express the level sets of $g^{\sharp}$ in terms of its conjugate polar as in the following corollary.

The point $(y^{*},\alpha^{*},\mu^{*})$ is optimal for (Nd) if and only if there exists a scalar $\xi^{*}$ such that $(y^{*},\alpha^{*},\mu^{*},\xi^{*})$ is optimal for the problem

By introducing the variable $\xi:=(\langle b,y\rangle+\alpha+\mu-1)/\sigma$ in (Nd), the result follows from Theorem 4.3.

Examples: piecewise linear-quadratic and GLM constraints

From a computational standpoint, the perspective-dual formulation may be an attractive alternative to the original primal problem. The efficiency of this approach requires that the dual constraints are in some sense more tractable than those of the primal. For example, we may consider the dual feasible set “easy” if it admits an efficient procedure for projecting onto that set. In this section, we examine two special cases that admit tractable dual problems in this sense. The first case is the family of piecewise linear quadratic (PLQ) functions, introduced by Rockafellar and subsequently examined by Rockafellar and Wets [23, p.440], and Aravkin, Burke, and Pillonetto . The second case is when $g$ is a Bregman divergence arising from a maximum likelihood estimation problem over a family of exponentially distributed random variables.

For this section only, we will assume for the sake of simplicity that the objective $f$ is a gauge, so that the perspective dual in each of this cases simplifies as in Corollary 4.17. The more general case still applies.

The family of PLQ functions is a large class of convex functions that includes such commonly used penalties as the Huber function, the Vapnik $\epsilon$-loss, and the hinge loss. The last two are used in support-vector regression and classification . PLQ functions take the form

The conjugate representation of $g$, given by

where $W_{1}^{T},\ldots,W_{k}^{T}$ are the rows of $W$ that define $\mathcal{U}$ in (5.1).

Because $\mathcal{U}$ is polyhedral, we can make the explicit description

This follows from considering cases on the signs of the $W_{i}^{T}\!y$, and noting that $w\geq 0$ because $\mathcal{U}$ contains the origin. Combining the above results, the theorem is proved.

The next example illustrates how Theorem 5.1 can be applied to compute the perspective-polar transform of the Huber function.

The Huber function , which is a smooth approximation to the absolute value function, is also its Moreau envelope of order $\eta$. Thus it can be stated in conjugate form as

which reveals $h_{\eta}^{\star}(y)=\delta_{[-\eta,\eta]}(y)+(\eta/2)y^{2}$. We then apply Theorem 4.1 to obtain

Note that this can easily be extended beyond the univariate case to a separable sum by applying the result of Example 4.6.

We can now write down an explicit formulation of the perspective dual problem (Nd) when the primal problem (Np) has a PLQ-constrained feasible region (i.e., $g$ is PLQ) and a gauge objective (i.e., $f$ is a closed gauge). The constraint set of (Nd) simplifies significantly so that, for example, a first-order projection method might be applied to solve the problem. Apply Theorem 5.1 and introduce a scalar variable $\xi$ to rephrase the dual problem (Nd) as

We can further simplify the constraint set using the fact that

Thus, projecting a point $\overline{y}$ onto the feasible set of (5.2) is equivalent to solving a second-order cone program (SOCP). In many important cases, the operator $L$ is extremely sparse. For example, when $g$ is a sum of separable Huber functions, we have $L=\sqrt{\eta}I$. Hence in many practical cases, particularly when $m\ll n$ and the dual variables are low-dimensional, this projection problem could be solved efficiently using SOCP solvers that take advantage of sparsity, e.g., Gurobi .

2 Generalized linear models and the Bregman divergence

In applications that impose an a priori distribution on the parameters, the goal is to find an approximation to the MLE estimate that penalizes a regularization function $f$ (a surrogate for the prior). We assume a linear dependence between the parameters and feature vectors, and thus set $\theta=Ax$, where the matrix $A$ has rows $a_{i}$. A regularized MLE estimate could be obtained by solving the constrained problem

where $d_{\phi}(v;w):=\phi(v)-\phi(w)-\langle\nabla\phi(w),v-w\rangle$ is the Bregman divergence function, and $\sigma$ is a positive parameter that controls the divergence between the linear model $Ax$ and the first-moment $\nabla\phi(b)$ relative to the density defined by $\phi$ .

We use Corollary 4.19 to derive the perspective dual, which requires the computation of the conjugate of $g(z):=d_{\phi\conj}(z;\nabla\phi(b))$:

where we simplify the expression using the inverse relationship between the gradients of $\phi$ and its conjugate. Assume for simplicity that $f$ is a gauge, which is typical when it serves as a regularization function. In that case, the perspective dual reduces to

As a first example, consider the case where the $b_{i}$ are distributed as independent Gaussian variables with unit variance. In this case, $\phi:={\textstyle{\frac{1}{2}}}\|\cdot\|^{2}$ and the above constraints specialize to

This is an example of a PLQ constraint, which falls into the category of problems described in Section 5.1.

Consider the case where the observations $b_{i}$ are independent Poisson observations, which corresponds to $\phi(\theta)=\theta\log\theta-\theta$ and $\phi^{\star}(y)=e^{y}$. Straightforward calculations show that the perspective dual constraints for the Poisson case reduce to

where $\beta=\sum_{i=1}^{m}(b_{i}+b_{i}\log b_{i})$ is a constant. By introducing new variables, this can be further simplified to require only affine constraints and $m$ relative-entropy constraints. To solve projection subproblems onto a constraint set of this form, we note that

is a self-concordant barrier for the set $\set{(x,y,r)}{y>0,\ y\log(y/x)\leq r},$ which is the epigraph of the relative entropy function; see Nesterov and Nemirovski [19, Proposition 5.1.4] and Boyd and Vandenberghe [5, Example 9.8]. Standard interior methods can therefore be used to project onto the constraint set.

When the observations $b_{i}$ are independent Bernoulli observations, which corresponds to $\phi(\theta)=\theta\log\theta+(1-\theta)\log(1-\theta)$ and $\phi^{\star}(y)=\log(1+e^{y})$, the perspective dual constraints in (5.4) reduce to

where $\beta=\sum_{i=1}^{m}(b_{i}\log b_{i}+(1-b_{i})\log(1-b_{i}))$ is a constant. By introducing new variables, this can be rewritten with only affine constraints and $2m$ relative-entropy constraints. Thus the projection subproblems can be solved as in the Poisson case.

Examples: recovering primal solutions

Once we have solved the gauge or perspective dual problems, we have two available approaches for recovering a corresponding primal optimal solution. If we applied a (Lagrange) primal-dual algorithm (e.g., the algorithm of Chambolle and Pock ) to solve the dual, then Theorem 3.15 gives a direct recipe for constructing a primal solution from the algorithm’s output. On the other hand, if we applied a primal-only algorithm to solve the dual, we must instead rely on Corollary 3.11 or Corollary 4.15 to recover a primal solution. Interestingly, the alignment conditions in these theorems can provide insight into the structure of the primal optimal solution, as illustrated by the following examples.

Our first example illustrates how Corollary 3.11 can be used to recover primal optimal solutions from dual optimal solutions for a simple gauge problem. Consider the gauge dual pair

which corresponds to the basis pursuit denoising problem. The 1-norm in the primal objective encourages sparsity in $x$, while the constraint enforces a maximum deviation between a forward model $Ax$ and observations $b$.

Let $y^{*}$ be optimal for the dual problem (6.1b), and set $z=A^{T}\!y^{*}$. Define the active set

(Note that $y^{*}\neq 0$, otherwise the primal problem is infeasible.) The efficiency of this least-squares solve depends on the number of elements in $I(z)$. For many applications of basis pursuit denoising, for example, we expect the support to be small relative to the length of $x$, and in that case, the least-squares recovery problem is expected to be a relatively inexpensive subproblem. We may interpret the role of the dual problem as that of determining the optimal support of the primal, and the role of the above least-squares problem as recovering the actual values of the support.

2 Sparse recovery with Huber misfit

For an example where the constraint is not a gauge function, consider the variant of (6.1a)

where $h_{\eta}$ is the Huber function; cf. Example 5.3. This problem corresponds to (Np) with $f(x)=\|x\|_{1}$ and $g=h$. Suppose that the tuple $(y,\alpha,\mu)$, with $\mu<0$, is optimal for the perspective dual, and that (Np) attains its optimal value. Because $f$ is a gauge, Corollary 4.17 asserts that $\alpha=0$, and thus Corollary 4.15(b) reduces to the conditions

As we did for the related example in Section 6.1, we use (6.3a) to deduce the support of the optimal primal solution. It follows from Theorem 5.1 that because $g$ is PLQ,

In particular, because $h$ is a separable sum of Huber functions, $W=[I\ {-}I]^{T}$, $w$ is the constant vector of all ones, and $L=\sqrt{\eta}I.$ Since $\mu<0$, it follows that

For the set $\set{v_{1},\ldots,\,v_{2m+1}}:=\left\{y_{1},\ldots,y_{m},-y_{1},\ldots,-y_{m},-\frac{\eta}{2\mu}\|y\|^{2}\right\},$ let $J(y,\mu):=\set{j}{|v_{j}|=\max_{i=1,\ldots,2m+1}|v_{i}|}$ be the set of maximizing indices. Then

where conv denotes the convex hull operation. More concretely, precisely the following terms are contained in the convex hull above:

$\left({-}\frac{\eta}{\mu}y,\,\frac{\eta}{2\mu^{2}}\|y\|_{2}^{2}\right)$ if ${-}\frac{\eta}{2\mu}\|y\|^{2}\geq\|y\|_{\infty}$;

where $e_{i}$ is the $i$th standard basis vector. Note that if an optimal solution to (Np) exists, then LABEL:thm:perrecovery tells us that $({-}(\eta/\mu)y,\,(\eta/2\mu^{2})\|y\|^{2})$ must be included in this convex hull, otherwise it is impossible to have $(b-Ax,1)\in\partial h^{\sharp}(y,\mu).$

In summary, Corollary 4.15 tells us that to find an optimal solution $x$ for (Np), we need to solve a linear program to ensure that $(b-Ax,1)\in{\mbox{conv}\,}\set{\nabla v_{j}}{j\in J(y,\mu)}$ subject to the optimal support of $x$, as determined by (6.3a). In cases where the size of the support is expected to be small (as might be expected with a 1-norm objective), this required linear program can be solved efficiently.

Numerical experiment: sparse robust regression

To illustrate the usefulness of the primal-from-dual recovery procedure implied by Theorem 3.15, we continue to examine the sparse robust regression problem (6.2), considered by Aravkin et al. . The aim is to find a sparse signal (e.g., a spike train) from measurements contaminated by outliers. These experiments have been performed with the following data: $m=120,$ $n=512,$ $\sigma=0.2$, $\eta=1$, and $A$ is a Gaussian matrix. The true solution $\overline{x}\in\{-1,0,1\}$ is a spike train which has been constructed to have 20 nonzero entries, and the true noise $b-A\overline{x}$ has been constructed to have 5 outliers.

We compare two approaches for solving problem (6.2). In both, we use Chambolle and Pock’s (CP) algorithm , which is primal-dual (in the sense of Lagrange duality) and can be adapted to solve both the primal problem (6.2) and its perspective dual (5.2). Other numerical methods could certainly be applied to either of these problems, such as Shefi and Teboulle’s dual moving-ball method . We note that a primal-only method, for example, applied to (5.2), would require us to use the methods of Section 6 rather than Theorem 3.15 for the recovery of a primal solution.

The CP method applied to problem (3.1) at each iteration $k$ computes

Fig. 7.1 compares the outcomes of running CP on the primal and perspective dual problems. This experiment exhibited similar behavior when run 500 times with different realizations of the random data, and so here we report on a single problem instance. Note that performing an iteration of CP on the perspective dual is significantly faster than performing an iteration of CP on the primal because $\Pi_{\mathcal{Q}}$ can be computed much more efficiently than $\Pi_{f}$ (see the discussion in Section 5.1). This also appears to make convergence of CP on the perspective dual more stable, as seen in Fig. 7.1(a). Fig. 7.1(c)-(d) illustrate the sparsity patterns of the iterates $x_{k}$ relative to those $\overline{x}$. Notably, we recover the correct sparsity patterns using Theorem 3.15. The recovery procedure outlined in LABEL:ex:one_huber also recovers the correct sparsity pattern, when applied to the final perspective dual iterate.

Discussion

Gauge duality is fascinating in part because it shares many symmetric properties with Lagrange duality, and yet Freund’s 1987 development of the concept flows from an entirely different principle based on polarity of the sets that define the gauge functions. On the other hand, Lagrange duality proceeds from a perturbation argument, which yields as one of its hallmarks a sensitivity interpretation of the dual variables. The discussion in Section 3 reveals that both duality notions can be derived from the same Fenchel-Rockafellar perturbation framework. The derivation of gauge duality using this framework appears to be its first application to a perturbation that does not lead to Lagrange duality. This new link between gauge duality and the perturbation framework establishes a sensitivity interpretation for gauge dual variables, which has not been available until now.

One motivation for this work is to explore alternative formulations of optimization problems that might be computationally advantageous for certain problem classes. The phase-retrieval problem, based on an SDP formulation, was a first application of ideas from gauge duality for developing large-scale solvers . That approach, however, was limited in its flexibility because it required gauge functions. The discussions of Section 4 pave the way to new extensions, such as different models of the measurement process, as described in Section 5.2.

Another implication of this work is that it establishes the foundation for exploring a new breed of primal-dual algorithms based on perspective duality. Our own application of Chambolle and Pock’s primal-dual algorithm to the perspective-dual problem, together with a procedure for extracting a primal estimate, is a first exploratory step towards developing variations of such methods. Future directions of research include the development of such algorithms, along with their attendant convergence properties and an understanding of the classes of problems for which they are practicable.

Acknowledgments

We are grateful to Patrick Combettes for pointing us to recent comprehensive work on properties of the perspective function and its applications . Our sincere thanks to two anonymous referees who provided an extensive list of corrections and suggestions that helped us to arrive at several strengthened results and to streamline our presentation.

References

Appendix A Proof of (2.6)

($\mathcal{U}_{\kappa}^{\circ}=\mathcal{U}_{\kappa^{\circ}}$). By definition of the polar gauge and the polar cone, we have $y\in\mathcal{U}_{\kappa^{\circ}}$ if and only if

($\mathcal{U}_{\kappa}^{\infty}=\mathcal{H}_{\kappa}$). Suppose $x\in\mathcal{H}_{\kappa}$. Then for any $u\in\mathcal{U}_{\kappa}$ and $\lambda>0$, by sublinearity of $\kappa$ we have $\kappa(u+\lambda x)\leq\kappa(u)+\lambda\kappa(x)\leq 1+\lambda\cdot 0=1.$ Thus $x\in\mathcal{U}_{\kappa}^{\infty}$, and $\mathcal{H}_{\kappa}\subseteq\mathcal{U}_{\kappa}^{\infty}$. Suppose now that $y\in\mathcal{U}_{\kappa}^{\infty}\setminus\mathcal{H}_{\kappa}$. Then in particular, $\kappa\left(y/\kappa(y)+\lambda y\right)\leq 1$ for all $\lambda>0$. But then by positive homogeneity, $\left(1/\kappa(y)+\lambda\right)\kappa(y)\leq 1$, for all $\lambda>0$. This is a contradiction since $\kappa(y)>0$, so we conclude that $\mathcal{H}_{\kappa}=\mathcal{U}_{\kappa}^{\infty}$.

Appendix B Proof of Lemma 3.4

With no loss in generality, we can assume that $\sigma>0$, because if $\sigma=0$, we use the convention (2.8) and its implication (2.9).

First suppose that the primal (Gp) is relatively strictly feasible. A point $u$ lies in the domain of $p$ if and only if the system

Next, suppose that the gauge dual (Gd) is strictly feasible. By definition of $F^{\star},$ the tuple $(w,\lambda)$ lies in the domain of $v_{d}$ if and only if

where $L^{\prime}$ is the linear subspace $L^{\prime}:=\{(a,b,c)\mid b=0\}$. However, by [20, Lemma 7.3], relative strict feasibility of the dual (Gd) amounts to the inclusion

Finally, the exact same arguments, but with relative interiors replaced by interiors, will prove the claims relating strict feasibility and interiority. This concludes the proof.