1

Consider following optimization problem: \begin{equation} \label{eqn:primal} \begin{aligned} \min_{x\in \mathcal{X}} f_p(x)\\ \text{s.t.}~g(x)\leq 0\\ h(x) = 0 \end{aligned} \end{equation} with non-empty domain $\mathcal{X}$ and finite optimal value $p^*$. The Lagrange dual problem as \begin{equation} \label{eqn:dual} \begin{aligned} \max_{\lambda,\eta} f_d(\lambda,\eta)\\ \text{s.t.}~\lambda\geq 0\\ \end{aligned} \end{equation} where \begin{equation} f_d(\lambda,\eta) := \inf_{x\in\mathcal{X}} f_p(x) + \lambda^{\top} g(x) + \eta^{\top} h(x). \end{equation} If functions $f_p(x)$, $g(x)$ and $h(x)$ are all convex, there exists a vector $\tilde{x}\in\mathrm{relint}(\mathcal{X})$, which makes the inequality constraints strictly feasible (Slater's Condition), such that \begin{equation*} g(\tilde{x}) < 0\qquad \text{and} \qquad h(\tilde{x}) = 0. \end{equation*}

Since the Strong Duality holds, I am able to prove that dual optimal $\lambda^*\in\Re^m$ is bounded using the Slater's Condition, such that \begin{equation*} 0\leq \sum_{k=1}^m \lambda^*_k \leq \frac{d^* - f_p(\tilde{x})}{\max_{1\leq k\leq m} g_k(\tilde{x}) } \leq \infty, \end{equation*} where $d^*$ is the dual optimal value.

My Question is: Is it possible to prove that dual optimal $\eta^*\in\Re^n$ is bounded?

Stephen Ge
  • 149
  • Your proof for $\lambda$ is not valid: what if $g_k(\tilde{x})=0$? Is there a reason you write 'max' instead of 'sup' for the dual? – LinAlg Jan 30 '21 at 03:18
  • Slater condition holds, so g(tilde(x))<0 – Stephen Ge Jan 30 '21 at 03:51
  • Slater condition says something about a feasible point, but nothing about the optimal solution – LinAlg Jan 30 '21 at 14:25
  • How would you show for $\lambda$ and what prevents this proof from being extended to $\eta$? – iarbel84 Jan 30 '21 at 17:03
  • \begin{equation} d^ = \inf_{x\in\mathcal{X}} f_p(x) + \lambda^{\top} g(x) + \eta^{\top} h(x) \leq f_p(\tilde{x}) + \lambda^{\top} g(\tilde{x}) \leq f_p(\tilde{x}) + \alpha \sum_{k=1}^m \lambda_k^, \end{equation} where \begin{equation} \alpha := \max_{1\leq k\leq m} g_k(\tilde{x}) < 0. \end{equation} Therefore, dual feasibility ensures that \begin{equation} 0\leq \sum_{k=1}^m \lambda^_k \leq \frac{d^ - f_p(\tilde{x})}{\alpha} \leq \infty. \end{equation*} – Stephen Ge Feb 01 '21 at 00:54

0 Answers0