3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ – Lutz Lehmann Jan 3 '14 at 14:15
  • $\begingroup$ 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? $\endgroup$ – Curious Jan 3 '14 at 19:10
  • 1
    $\begingroup$ 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$? $\endgroup$ – Lutz Lehmann Jan 3 '14 at 19:13
  • $\begingroup$ The minimization is only on the intersection of the convex sets. All of the convex sets are in the same $R^{n}$. $\endgroup$ – Curious Jan 3 '14 at 20:54
  • 1
    $\begingroup$ 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? $\endgroup$ – Curious Jan 3 '14 at 21:51
0
$\begingroup$

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

$\endgroup$

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.