The primal optimization problem is, \begin{align*}\min_x\;&f_0(x)\\ \text{s.t.}\;&f_i(x)\le0\\ &h_j(x)=0\end{align*}, to construct the dual problem, I form the Lagrangian, $$L(x,\lambda,\upsilon)=f_0(x)+\sum_i\lambda_if_i(x)+\sum_j\upsilon_jh_j(x)$$. Here comes my problem, let $x\in D$ be the feasible domain of the primal problem, I found different definition of dual function on the web, here they are, in this tutorial, $$g(\lambda,\upsilon)=\inf_{x\in D}L(x,\lambda,\upsilon)\;\;\;(1)$$, but in this one (at the bottom of page-3), $$g(\lambda,\upsilon)=\inf_{x\in R^n}L(x,\lambda,\upsilon)\;\;\;(2)$$, well, they define dual function over different domains.

This really confuses me, but something confuses me further is that, to derive $g(\lambda,\upsilon)$, both of the two tutorials do the same, compute $x^*$ from $\nabla_xL=0$, and then substitute $x^*$ into $L(x,\lambda,\upsilon)$ which result in $g(\lambda,\upsilon)$. Again, I wonder if equation (1) is right, which means $x\in D$, then how could it be guaranteed that $x^*\in D$ in the derivation of $g(\lambda,\upsilon)$?


It is usually understood that $f_0(x)=+\infty$ for $x\notin D$. This would make both definitions equivalent.

  • $\begingroup$ Do you mean, for those $x'\not\in D$, $L(x',\lambda,\upsilon)$ will always greater than $L(x,\lambda,\upsilon)$ for which $x\in D$? $\endgroup$ – avocado Dec 18 '13 at 1:38
  • $\begingroup$ Yes, so they are automatically excluded from the consideration, even if they are formally included. $\endgroup$ – LutzL Dec 18 '13 at 6:58

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.