Abstract Duality in Optimization (Part I)

Difficulty: Experts & Advanced Graduate Students

Abstract duality in optimization is often presented using one of two approaches: (i) the Lagrange-multiplier approach, and (ii) the (less-studied) perturbation function approach. In this series of posts, we will attempt to distill the main ideas of the latter approach and its applications to Lagrange multiplier theory. All of the content in this series is elaborated in detail in Ekeland and Témam’s book “Convex Analysis and Variational Problems”, albeit with (possibly) different terminology and notation.

Basic Definitions

Throughout this discussion and future ones in the series, we let $V$ be a topological vector space (t.v.s.), $V^{*}$ be its dual with associated inner product $\langle\cdot,\cdot\rangle_{V}\equiv\langle\cdot,\cdot\rangle$, and $\overline{\mathbb{R}}=\mathbb{R}\cup{-\infty,+\infty}$. The set of proper convex and lower semicontinuous functions on a t.v.s. $Z$ is denoted by $\Gamma_{0}(Z)$. For an arbitrary function $F:V\mapsto\overline{\mathbb{R}}$, the primal problem of $F$ is

We denote $\inf\ {\cal P}$ to be the infimum of problem ${\cal P}$, and every element $\bar{u}\in V$ satisfying $\inf\ {\cal P}=F(\bar{u})$ is called a solution of ${\cal P}$. The problem ${\cal P}$ is said to be nontrivial if there exists $u_{0}\in V$ such that $F(u_{0})<+\infty$.

Given another finite-dimensional t.v.s. $Y$ and its dual $Y^{*}$ with associated inner product $\langle\cdot,\cdot\rangle_{Y}\equiv\langle\cdot,\cdot\rangle$, we say that $\Phi:V\times Y\mapsto\overline{\mathbb{R}}$ is a perturbation function of $F$ if $\Phi(u,0)=F(u)$ for every $u\in{\rm dom}\ F$ and ${\rm dom}\ \Phi(\cdot,0)={\rm dom}\ F$. The conjugate function of $\Phi$ is denoted as $\Phi^{*}:V^{*}\times Y^{*}\mapsto\overline{\mathbb{R}}$.

The dual function of $F$ with respect to $\Phi$ is $-\Phi^{*}(0,p^{*})$ and the dual problem of $F$ with respect to $\Phi$ is

Similarly, we denote $\sup\ {\cal P}$ to be the supremum of problem ${\cal P}^{*}$, and every element $\bar{p}^{*}\in Y^{*}$ satisfying $\sup\ {\cal P}^{*}=-\Phi(0,\bar{p}^{*})$ is called a solution of ${\cal P}^{*}$. The problem $P^{*}$ is said to be nontrivial if there exists $p_{0}^{*}\in Y^{*}$ such that $\Phi(0,p_{0}^{*})<+\infty$.

Weak and Strong Duality

Our first major result presents the relationship between ${\cal P}$ and ${\cal P}^{*}$.

Proposition I.1. (Weak Duality) If ${\cal P}$ is non-trivial, then

If ${\cal P}^{*}$ is non-trivial, then

If both ${\cal P}$ and ${\cal P}^{*}$ are nontrivial, then $\sup\ {\cal P}^{*}$ and $\inf\ {\cal P}$ are both finite, with

Remark I.2. There are various counterexamples in the literature where $\sup\ {\cal P}^{*}<\inf\ {\cal P}$ or $\sup\ {\cal P}^{*}=\inf\ {\cal P}$. When the latter holds, it is called strong duality.

Remark I.3. Much like how $\Phi$ is a perturbation function of the primal function $F$, we can associate the dual function $-\Phi^{*}(0,\cdot)$ with the “natural” perturbation function $-\Phi^{*}(\cdot,\cdot)$ whose dual problem is

where $\Phi^{**}$ is conjugate of $\Phi^{*}$, or the lower semicontinuous regularization of $\Phi$. Now, since $\Phi^{*}$ is closed convex, and hence $\Phi^{*}=\Phi^{***}$, it follows that the dual of ${\cal P^{**}}$is actually

which is precisely ${\cal P^{*}}$. So, if ${\cal P}^{**}\equiv{\cal P}$, i.e., $\Phi^{**}(u,0)=\Phi(u,0)$ for every $u\in V$, then the previous observation implies that the dual of ${\cal P}^{*}$ is actually ${\cal P}^{**}\equiv{\cal P}$ and a sort of symmetry exists between ${\cal P}$ and ${\cal P}^{*}$.

Remark I.4. A sufficient condition for $\Phi^{**}(u,0)=\Phi(u,0)$, and hence ${\cal P}^{**}\equiv{\cal P}$, is that $\Phi\in\Gamma_{0}(V\times Y)$. In the next section, we will examine what additional properties can be derived from the assumption $\Phi\in\Gamma_{0}(V\times Y)$.

Remark I.5. Even if ${\cal P}\equiv{\cal P}^{**}$, we generally do not have $\sup\ {\cal P}^{*}=\inf\ {\cal P}$. In a later post, we will describe what are called constraint qualification conditions that imply $\sup\ {\cal P}^{*}=\inf\ {\cal P}$.

Duality with “Nice” Perturbation Functions

Throughout our discussion, we will suppose that $\Phi\in\Gamma_{0}(V\times Y)$.

In this post, we are concerned with the properties of the function

and how it relates to ${\cal P}$ and ${\cal P^{*}}$.

Remark II.1. It can be shown that $h:Y\mapsto\overline{\mathbb{R}}$ is convex and, in general, $h$ is convex whenever $\Phi$ is convex.

Remark II.2. In general, $h\notin\Gamma_{0}(Y)$.

The negative of the conjugate function of $h$ is called the dual function of ${\cal P}$ and satisfies \(-h^{*}(p^{*})=-\Phi^{*}(0,p^{*})\) and the biconjugate of $h$ satisfies

Remark II.3. Weak duality is equivalent to the well-known inequality $h^{**}(0)\leq h(0)$. Moreover, it can be shown that the set of solutions of ${\cal P}^{*}$ is identical to $\partial h^{**}(0)$.

We now present a regularity condition for strong duality in terms of $h$. For the sake of brevity, we will say ${\cal P}$ is normal with respect to $\Phi$ if $h(0)$ is finite and semicontinuous at $0$.

Proposition II.1. The following conditions are equivalent:

1. ${\cal P}$ is normal

2. ${\cal P}^{*}$ is normal

3. $\inf\ {\cal P}=\sup\ {\cal P}^{*}$ and this number is finite.

Remark II.4. It can be shown that 1 and 3 are equivalent under the condition that $h$ is convex, which holds if $\Phi$ is convex.