# 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 (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.
• 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