# Formulation Fenchel Duality for Convex problem

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?

• Define $\tilde{f}(x) = f(x)$ if the constraints are satisfied and $+\infty$ otherwise? – copper.hat Jul 2 '18 at 20:08
• @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 ? – Red shoes Jul 3 '18 at 0:04
• 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. – copper.hat Jul 3 '18 at 16:36
• did you appreciate my answer? – LinAlg Jul 26 '18 at 19:07
• @LinAlg Yes but that wasn't what I was looking for. – Red shoes Jul 27 '18 at 21:40

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$.
• 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 ;) – LinAlg Jul 3 '18 at 0:35
• I suspect a missing minus signs somewhere, since the equality constraint should appear as $\mu^T (Ax-b)$. – copper.hat Jul 3 '18 at 14:47