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$ Commented Apr 2, 2011 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
    Commented Apr 2, 2011 at 23:16

1 Answer 1


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
    Commented Apr 3, 2011 at 5:09

You must log in to answer this question.

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