0
$\begingroup$

What is the Fenchel dual problem for a general convex problem with constraints?

Precisely assume slater condition holds in following convex problem

$$\begin{matrix} \min & f(x) \\ s.t& g(x) \leq 0 \\ &Ax =b \end{matrix}$$

What would be the dual problem.

From Wikipedia I only see that Fenchel duality only works for convex unconstrained problems or at most with affine constraint. How can I incorporated nonlinear constrains into the dual problem?

$\endgroup$
  • $\begingroup$ Define $\tilde{f}(x) = f(x)$ if the constraints are satisfied and $+\infty$ otherwise? $\endgroup$ – copper.hat Jul 2 '18 at 20:08
  • $\begingroup$ @copper.hat Then to Find conjugate of $\tilde{f}(x)$ we need to solve an optimization problem with same constraints , so what's the point of duality ? $\endgroup$ – Red shoes Jul 3 '18 at 0:04
  • $\begingroup$ What do you mean by the Fenchel dual of a constrained problem? A Fenchel dual usually applies to a nominally unconstrained problem of the form $\inf (f-g)$. Without an explicit form of $g$, it is hard to see how you would obtain a useful form of the dual. $\endgroup$ – copper.hat Jul 3 '18 at 16:36
  • $\begingroup$ did you appreciate my answer? $\endgroup$ – LinAlg Jul 26 '18 at 19:07
  • $\begingroup$ @LinAlg Yes but that wasn't what I was looking for. $\endgroup$ – Red shoes Jul 27 '18 at 21:40
1
$\begingroup$

By definition, the Fenchel dual is $$\begin{align} &\mu^T b + \inf_x (f+\lambda g - \mu^T A)(x)\\ = \; &\mu^Tb-\sup_x (0^Tx-f-\lambda g + \mu^T A)(x) \\ = \; &\mu^Tb-(f+\lambda g - \mu^T A)^*(0)\end{align}$$ To compute the conjugate of this sum, use the rules $$(f+\lambda g - \mu^T A)^*(y) = \inf_{y_1,y_2 : y_1 + y_2 + y_3 = y}f^*(y_1)+(\lambda g)^*(y_2) + (-\mu^TA)^*(y_3),$$ $$(\lambda g)^*(y_2)=\lambda g^*(y_2/\lambda)\text{, and}$$ $$(-\mu^TA)^*(y_3)=0 \text{ if } -A^T\mu=y_3.$$ After you substitute these last two formulas into the second one, you obtain the dual with variables $y_i$, $\lambda$ and $\mu$.

$\endgroup$
  • $\begingroup$ What's the source of this definition ? and that infimum looks like a mess . $\endgroup$ – Red shoes Jul 3 '18 at 0:08
  • $\begingroup$ Just the definition of the conjugate: $\mu^Tb-\sup_x (0^Tx-f-\lambda g - \mu^T A)(x) = \inf_x (f+\lambda g + \mu^T A)(x)$. A mess? You wanted the dual ;) $\endgroup$ – LinAlg Jul 3 '18 at 0:35
  • $\begingroup$ definition of the conjugate of what function? $\endgroup$ – Red shoes Jul 3 '18 at 2:42
  • $\begingroup$ I have updated the answer $\endgroup$ – LinAlg Jul 3 '18 at 11:51
  • $\begingroup$ I suspect a missing minus signs somewhere, since the equality constraint should appear as $\mu^T (Ax-b)$. $\endgroup$ – copper.hat Jul 3 '18 at 14:47

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.