0
$\begingroup$

Consider an optimization problem with sign constraints on the variables: $$ \begin{align} \min_{x\in\mathbb{R}^n}&\quad f(x) \\ \text{s.t.}&\quad g_i(x)\le 0,\quad i=1,...,m \\ &\quad h_j(x)=0,\quad j=1,....,\ell \\ &\quad x\le 0. \end{align} $$ When forming the Lagrangian for this problem, I wonder if it is necessary to assign dual variables to the constraint $x\le 0$?

To be more specific, I know for certain that I can treat $x\le 0$ as general inequality constraints, which yields the Lagrangian $$ L(x,\lambda,\mu,\nu)=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{j=1}^{\ell}\mu_jh_j(x)+\sum_{i=1}^n\nu_ix_i $$ and the dual function $$ d(\lambda,\mu,\nu)=\inf_{x\in\mathbb{R}^n}L(x,\lambda,\mu,\nu),\quad\forall\,(\lambda,\mu,\nu)\in\mathbb{R}^m_+\times\mathbb{R}^{\ell}\times\mathbb{R}^n_+, $$ so the dual problem is $$ \begin{align} (D)\quad\max&\quad d(\lambda,\mu,\nu) \\ \text{s.t.}&\quad \lambda\ge 0,\quad\nu\ge 0. \end{align} $$

What if I do not assign dual variables to the constraints $x\le 0$? That is, let $$ \widetilde{L}(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_ig_i(x)+\sum_{j=1}^{\ell}\mu_jh_j(x) $$ and, when forming the dual function, perform minimization over $x\le0$ instead of $x\in\mathbb{R}^n$, which gives $$ \widetilde{d}(\lambda,\mu)=\inf_{x\le 0}L(x,\lambda,\mu),\quad\forall\,(\lambda,\mu)\in\mathbb{R}^m_+\times\mathbb{R}^{\ell}. $$ This yields $$ \begin{align} (\widetilde{D})\quad\max&\quad \widetilde{d}(\lambda,\mu) \\ \text{s.t.}&\quad \lambda\ge 0. \end{align} $$ Are $(D)$ and $(\widetilde{D})$ equivalent?

$\endgroup$

1 Answer 1

1
$\begingroup$

It turns out that $(D)$ and $(\widetilde{D})$ are not equivalent. As an example, let $n=m=\ell=1$, $g_1(x)=h_1(x)=0$, and $f(x)=-x^3$. Then $(D)$ is given by $$ \begin{align} (D)\quad\max_{\lambda,\mu,\nu}&\quad\min_{x\in\mathbb{R}}(-x^3+\nu x)=-\infty\\ \text{s.t.}&\quad\lambda,\nu\ge 0, \end{align} $$ and has optimal value $-\infty$. In contrast, $(\widetilde{D})$ is $$ \begin{align} (\widetilde{D})\quad\max_{\lambda,\mu}&\quad\min_{x\le 0}(-x^3)=0 \\ \text{s.t.}&\quad\lambda\ge 0 \end{align} $$ and has optimal value $0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .