Following are some corollaries regarding the weak duality theorem.

  1. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$.

    Its dual problem is $\sup_{u \geq 0, v} \theta(u,v)$, where the dual Lagrangian function is defined as $\theta(u,v):= \inf_{x \in X} \, f(x) + u^T g(x) + v^T h(x)$.

    In Bazarra's Nonlinear Programming, on P264:

    Corollary 3 If $\inf \{ f(x): x \in X, g(x) \leq 0, h(x) = 0 \} = -\infty$, then the Lagrangian dual function $\theta(u, v) = -\infty$ for each $u \geq 0$.

    Corollary 4 If $\sup \{\theta(u, v): u \geq 0\} = \infty$, then the primal problem has no feasible solution.

  2. For a linear programming problem, $\min_{x \geq 0} c^T x$ subject to $Ax=b$, its dual problem is $\max_{p} p^Tb$ subject to $p^T A \leq c^T$. In Bertskas's Introduction to Linear Optimization, on P147:

    Corollary 4.1

    (a) If the optimal cost in the primal is $-\infty$, then the dual problem must be infeasible.

    (b) If the optimal cost in the dual is $\infty$, then the primal problem must be infeasible.

My questions:

  1. In Corollary 4 in Bazarra's and Corollary 4.1 in Bertsekas', why when one problem's optimal cost is unbounded, the other one is infeasible, i.e. has empty feasible set, instead of also having the same unbounded optimal cost?
  2. Does Corollary 3 in Bazarra's book say that if the optimal cost in primal problem is $-\infty$, then the optimal cost in the dual must also be $-\infty$?
  3. In the linear programming case, is Corollary 3 in Bazarra's book not consistent with Corollary 4.1(a) in Bertsekas' book, in that the former implies that when the optimal cost in the primal is $-\infty$, then the dual problem has a non-empty feasible set (and has $-\infty$ optimal cost)?

Thanks! Also feel free to suggest to improve this post, e.g., to make it concise and clear.

  • $\begingroup$ Are you sure the primal is always a minimization problem? It could have changed in the course of the text. $\endgroup$ – PrimeNumber Apr 2 '11 at 23:10
  • $\begingroup$ @PEV: I think so. On Bertsekas's p 146, the first sentence on the same section it says the section is talking about the standard form of the primal problem, which is a minimization problem as written in p141 and p145 example 4.3. $\endgroup$ – Tim Apr 2 '11 at 23:16

From Theorem 2.7.3(b) of Bazarra, the following holds: $P$ is unbounded $\implies$ $D$ is infeasible and $D$ is unbounded $\implies$ $P$ is infeasible.

From Corollary 1 on page 85 we have: $D$ is infeasible $\implies$ $P$ is unbounded or infeasible and $P$ infeasible $\implies$ $D$ is unbounded or infeasible.

  • $\begingroup$ Thanks! I was wondering if, in Bazaraa's, Corollary 3 on p264 and Theorem 2.7.3(b) are contrary to each other? How to understand the former? Thanks! $\endgroup$ – Tim Apr 3 '11 at 5:09

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.