Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Are you sure the primal is always a minimization problem? It could have changed in the course of the text. –  PEV Apr 2 '11 at 23:10
    
@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. –  Tim Apr 2 '11 at 23:16

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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! –  Tim Apr 3 '11 at 5:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.