Two duality theorems

83 Views Asked by At

Suppose $X$ is a Hilbert space with norm $||.||$ and $K$ is a weak compact and convex subset of $X$.

The supporting functional: $$h(x^*)=\sup_{x\in K} \langle x^*, x \rangle$$

The indicator function: $$\delta (x|K)=0 \phantom{0}if \phantom{0} x\in K \phantom{0} and \phantom{0}+\infty\phantom{0} if \phantom{0}x\notin K$$

What is the relation between the following two duality theorems? Are they equivalent and 2 implies 1?

  1. $$\delta (x|K)=\sup_{x^*\in X} \langle x^*, x \rangle - h(x^*)$$

  2. $$ \inf_{x'\in K}||x- x' ||= \max_{||x^*||\leq 1} \langle x^*, x \rangle - h(x^*)$$

  3. Will the following claim be true: Fix any $1\leq M< +\infty$,

$x\in K$ if and only if for all $x^*$ satisfying $||x^*||\leq M$, we have

$$ \sup_{||x^*||\leq M} \langle x^*, x \rangle - h(x^*)=0.$$

1

There are 1 best solutions below

1
On

The statement (1) is the observation that $\delta(\cdot|K)$ is the convex conjugate of $h$ (and vice-versa). So (1) is always true under your assumptions. The function $h$ is usually called the support functional of $K$.

The statement (2) states that there is no duality gap between the primal problem $$ \min_{x'\in X} \|x-x'\| + \delta(x'|K) $$ and its dual $$ \max_{x^*\in X}\ \delta(x^*|B) + \langle x^*,x\rangle - h(x^*) $$ with $B$ being the unit ball. Observe that $f^*(x^*)=\delta(x^*|B) + \langle x^*,x\rangle$ is the conjugate of $f(x')=\|x-x'\|$.

Question (3) is related to the primal problem above by a scaling with $M$, $$ \min_{x'\in X}\ M^{-1} \|x-x'\| + \delta(x'|K) $$