Abstract Duality in Optimization (Part II)
Published:
Difficulty: Experts & Advanced Graduate Students
We now look at some conditions that imply at least one of ${\cal P}$ or ${\cal P^{*}}$ has solutions, as well as some nice properties that are a consequence of this fact. Later, we look at the relationship between our previous developments, the classic Lagrangian of ${\cal P}$, and the well-known saddle-point duality.
Existence of Solutions
Throughout our discussion, we will suppose that $\Phi\in\Gamma_{0}(V\times Y)$.
For brevity, we say that ${\cal P}$ is stable if $h(0)$ and $h$ is subdifferentiable at $0$. The next result relates normality, stability, and the existence of solutions.
Proposition III.1. The following conditions are equivalent:
${\cal P}$ and ${\cal P}^{*}$ are normal and have some solutions.
${\cal P}$ and ${\cal P^{*}}$ are stable.
${\cal P}$ is stable and has some solutions.
A sufficient condition for stability is as follows.
Proposition III.2. Suppose (i) $\Phi$ is convex, (ii) $\inf\ {\cal P}$ is finite, and (iii) there exists $u_{0}\in V$ such that $\Phi(u_{0},\cdot)$ is finite and continuous at $0$. Then, ${\cal P}$ is stable.
Remark III.3. Condition (iii) in the above result immediately implies the existence of solutions of ${\cal P}^{*}$ and acts as a sort of constraint qualification for ${\cal P}$.
Extremal Relationships
The following result gives a nice property in the case where ${\cal P}$ and ${\cal P^{*}}$ both have solutions.
Proposition III.4. Suppose ${\cal P}$ and ${\cal P^{*}}$ have solutions, $\inf\ {\cal P}=\sup\ {\cal P}^{*}$, and this number is finite. Then all solutions $\bar{u}$ of ${\cal P}$ and all solutions $\bar{p}^{*}$ of ${\cal P}^{*}$ satisfy the extremality relation
\[\Phi(\bar{u},0)+\Phi^{*}(0,\bar{p}^{*})=0,\]or equivalently,
\[(0,\bar{p}^{*})\in\partial\Phi(\bar{u},0).\]Conversely, if $\bar{u}\in V$ and $\bar{p}^{*}\in Y^{*}$ satisfy the above extremality relation, then $\bar{u}$ is a solution of ${\cal P}$, $\bar{p}^{*}$ is a solution of ${\cal P}^{*}$, $\inf\ {\cal P}=\sup\ {\cal P}^{*}$, and this number is finite.
Remark III.5. The definition of the conjugate function implies that
\[\Phi(u,0)+\Phi^{*}(0,p^{*})\geq\left\langle (u,0),(0,p^{*})\right\rangle =0\]for every $u\in V$ and $p^{*}\in Y^{*}$. It is for this reason that $\Phi(\bar{u},0)+\Phi^{*}(0,\bar{p}^{*})=0$ is called an extremality relation.
Lagrangian of ${\cal P}$
The Lagrangian $L:V\times Y^{*}\mapsto\overline{\mathbb{R}}$ of ${\cal P}$ relative to $\Phi$ is given by
\[-L(u,p^{*}):=\sup_{p\in Y}\left\{ \left\langle p^{*},p\right\rangle -\Phi(u,p)\right\}\]for every $u\in V$ and $p^{*}\in Y^{*}$.
Remark IV.1. For a fixed $u\in V$, let $\Phi_{u}$ be the function $p\mapsto\Phi(u,p)$. It is straightforward to see that $-L(u,p^{*})=\Phi_{u}^{*}(p^{*})$.
The result gives some basic properties of $L$.
Proposition IV.2. For every $u\in V$, the function $p^{*}\mapsto L(u,p^{*})$ is an upper semicontinuous function of $Y^{*}$ into $\overline{\mathbb{R}}$. On the other hand, if $\Phi$ is convex then for every $p^{*}\in Y^{*}$ the function $u\mapsto L(u,p^{*})$ is convex from $V$ into $\overline{\mathbb{R}}$.
Remark IV.3. Unfortunately, we cannot assert that $u\mapsto L(u,p^{*})$ is lower semicontinuous even if $\Phi\in\Gamma_{0}(V\times Y)$.
Remark IV.4. Without any assumptions on $\Phi$, it can be shown that the following relationships hold:
\[\begin{aligned} -\Phi^{*}(0,p^{*}) & =\inf_{u\in V}L(u,p^{*}),\\ {\cal P}^{*} & \equiv\sup_{p^{*}\in Y^{*}}\inf_{u\in V}L(u,p^{*}).\end{aligned}\]Remark IV.5. If $\Phi\in\Gamma_{0}(V\times Y)$, it can be shown that the following relationships hold:
\[\begin{aligned} \Phi(u,0) & =\sup_{p^{*}\in Y^{*}}L(u,p^{*}),\\ {\cal P} & \equiv\inf_{u\in V}\sup_{p^{*}\in Y^{*}}L(u,p^{*}).\end{aligned}\]Saddle-Point Duality
We can see from the previous results that there is a possible min-max saddle-point duality if $\Phi\in\Gamma_{0}(V\times Y)$. In this subsection, we give the precise relationships.
For brevity, let us say that $(\bar{u},p^{*})\in V\times Y^{*}$ is a saddle point of $L$ if
\[L(\bar{u},p^{*})\leq L(\bar{u},\bar{p}^{*})\leq L(u,\bar{p}^{*})\]for every $u\in V$ and $p^{*}\in Y^{*}$.
Proposition IV.6. If $\Phi\in\Gamma_{0}(V\times Y)$ then the following statements are equivalent:
$(\bar{u},\bar{p}^{*})$ is a saddle point of $L$.
$\bar{u}$ is a solution of ${\cal P}$, $\bar{p}^{*}$ is a solution of ${\cal P^{*}}$, and $\inf\ {\cal P}=\sup\ {\cal P}^{*}$.
Proposition IV.7. Suppose $\Phi\in\Gamma_{0}(V\times Y)$ and ${\cal P}$ is stable. Then $\bar{u}\in V$ is a solution of ${\cal P}$ if and only if there exists $\bar{p}^{*}\in Y^{*}$ such that $(\bar{u},\bar{p}^{*})$ is a saddle point of $L$.
Leave a Comment