How to show the following: Let $C$ be a compact set in some Hilbert space $H$ and $I_C(x)$ the indicator function (i.e. $0$ for $x\in C$ and $\infty$ otherwise). Consider the following optimization problem,

$$\min\limits_{x\in H} f(x) + I_C(x)$$

Show that the dual of this problem is,

$$\max\limits_{u\in H} -f^*(u) - I^*_C(-u)$$

where the $*$ denotes the Fenchel Conjugate / Dual (See Fenchel's Duality Theorem). I understand how to find the dual problem when there are inequality or equality constraints but how do you handle "set constraints"?

Edit: Here is a complete solution based off the accepted answer. Using the definition of the conjugate, $g^*(u) = \sup\limits_{x\in H}\langle x, u\rangle -g(x)$, we have the following,

$$\min\limits_{x\in H} f(x) + I_C(x) = -(f + I_C)^* (0)$$

Now, the conjugate of a sum of functions is the infimal convolutions of the conjugates. The infimal convolution, denoted $f\,\square \,g$, is defined to be,

$$(f\,\square\, g)(u) = \inf\limits_{v \in H}\left(f(u-v) + g(v)\right)$$

Applying this to our problem we get,

$$-(f+I_C)^*(0) =-(f^* \,\square \,I_C^*)(0)= -\inf\limits_{v \in H}\left(f^*(0-v) + I_C^*(v)\right)$$

And then renaming $-v$ to be $u$, which doesn't matter because the $\inf$ is over the whole space, we get,

$$\min\limits_{x\in H} f(x) + I_C(x)= \max\limits_{u\in H}-f^*(u) - I_C^*(-u)$$


Let $g$ be a convex function, and $h$ be a concave function. By Fenchel's duality theorem: $$\min_{x \in H} g(x)-h(x) = \max_{u \in H} h_*(u)-g^*(u)$$ Taking $h(x) = 0$ gives: $$\min_{x \in H} g(x) = -g^*(0)$$ Taking $g(x) = f(x) + I_C(x)$ and using the well known theorem that the conjugate of the sum is the infimum convolution gives the desired result.

  • $\begingroup$ Should the first line have $h^*(u) - g^*(u)$ or am I missing something? $\endgroup$ – TSF Feb 26 '18 at 16:07
  • $\begingroup$ It doesn't make sense to be taking the max over $u$ if the functions have argument $x$? $\endgroup$ – TSF Feb 26 '18 at 16:16
  • $\begingroup$ The max in the last line is unnecessary right, you only wrote it because of the Fenchel Duality theorem? Because $-g^*(0)$ does not depend on $u$? $\endgroup$ – TSF Feb 26 '18 at 16:28
  • 1
    $\begingroup$ I provided a basic proof here. As for the perturbation view, what would you perturb in this example? $\endgroup$ – LinAlg Feb 26 '18 at 23:31
  • 1
    $\begingroup$ @jjjjjj I filled in some details in the question based on the answer of LinAlg if that helps you. $\endgroup$ – TSF Feb 27 '18 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.