Lagrange dual of a sum of convex functions Given a set of convex functions $f_i(x)$ and convex sets $X_i$ in $\mathbb R^n$
I need to find the Lagrange dual problem for the problem $\min \sum{f_i(x)} , x \in X_i \forall i$.
There is of course no closed form solution as $f_i$ are unknown but I need to describe the resulting Lagrange dual problem in the terms of the original one.
Thank you.
My thoughts until now are to define an indicator function $g_i(x)$ for each convex set, that will be infinite outside the set. Thus the equivalent optimization will problem will be $min(\sum(f_i(x) + g_i(x)))$. But how to I proceed to derive a Lagrange dual? Can I use the conjugate function of the indicator functions?
I'm confused...
 A: As you suggested, you can define indicator functions for the sets:
$$
g_i(x) = \begin{cases} 0 & \ x \in X_i \\ +\infty & \ x \notin X_i \end{cases}
$$
These are dual to the support functions of those sets:
$$
g_i^*(\lambda) = \sup_{x \in X_i} x^T\lambda
$$
Now you can formulate the problem like a consensus optimization problem:
$$
\begin{gathered}
\inf_{x_i,y_i,z} \sum_i f_i(x_i) + g_i(y_i)\\
\text{s.t.:} \ x_i = z,\ y_i = z
\end{gathered}
$$
Let's form the Lagrangian for this constrained problem and minimize over the "local" variables $x_i,y_i$ to get an expression in terms of the convex conjugates:
$$
\inf_{x_i,y_i,z} \sum_i f_i(x_i) + g_i(y_i) + u_i^T(z-x_i) + v_i^T(z-y_i) 
\\= \inf_{z} \sum_i -f_i^*(u_i) - g_i^*(v_i) + (u_i+v_i)^T z
$$
Minimizing over the "consensus" variable $z$ gives an implicit equality constraint. The dual problem is thus:
$$
\begin{gathered}
\sup_{u_i,v_i} \sum_i -f_i^*(u_i) - g_i^*(v_i)\\
\text{s.t.:} \ \sum_i u_i + v_i = 0
\end{gathered}
$$
Some caveats: this formulation is only really useful if the sets $X_i$ admit simple support functions $g_i^*$. Also, while this always gives a lower bound of the optimal value of the original problem, to get strong duality there are some technical conditions you need. (See the hypotheses of Fenchel's duality theorem in a convex analysis text.)
