# Fenchel conjugate with indicator function

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. 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.
• Should the first line have $h^*(u) - g^*(u)$ or am I missing something? – TSF Feb 26 '18 at 16:07
• It doesn't make sense to be taking the max over $u$ if the functions have argument $x$? – TSF Feb 26 '18 at 16:16
• 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$? – TSF Feb 26 '18 at 16:28