how to construct the Lagrangian dual problem?

754 Views Asked by At

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)$?

1

There are 1 best solutions below

2
On BEST ANSWER

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