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

• I think this starts very straight-forward. $f:X_1\times X_2\to I\!\!R$, $f(x_1,x_2)=f_1(x_1)+f_2(x_2)$ etc. Can you tell where it gets so complicated that you have to stop? – Lutz Lehmann Jan 3 '14 at 14:15
• I'm not sure how this relates to the Lagrange dual? What am I missing? Let's say I define such a function, how do I find the Lagrange dual problem? – Curious Jan 3 '14 at 19:10
• Please restate your problem in more correct terms. Is the argument of all the functions the same $x\in\mathbb R^n$? Then the sum of the functions is only defined on the intersection of the convex sets $X_i$. Or is $x$ a big vector in the Cartesian product of all the sets $X_i$? – Lutz Lehmann Jan 3 '14 at 19:13
• The minimization is only on the intersection of the convex sets. All of the convex sets are in the same $R^{n}$. – Curious Jan 3 '14 at 20:54
• My main problem here is what are the constraints? I guess they are related to representing the fact that x is in the intersection of Xi , but as I only know they are convex sets - how do I represent them? Should I use some kind of indicator function? – Curious Jan 3 '14 at 21:51

$$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$$
$$\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.)