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.

My questions are regarding a constrained problem, $$\min_{x \in X \subseteq \mathbb{R}^n} f(x),$$ subject to $g(x) \leq 0 \in \mathbb{R}^m, h(x) =0 \in \mathbb{R}^k$. Its dual problem is $$\sup_{u \geq 0 \in \mathbb{R}^m,v \in \mathbb{R}^k} \theta(u,v),$$ where $\theta(u,v):= \inf_{x \in X} \, f(x) + u^T g(x) + v^T h(x)$.

Suppose $x^*$ is primal feasible, and $(u^*,v^*)$ is dual feasible i.e. $u^* \geq 0, v^* \in \mathbb{R}^k$. Define:

Proposition $P$: $f(x^*) = \theta(u^*, v^*)$,

Proposition $Q$: $x^*$ optimizes the primal problem, and $(u^*,v^*)$ optimizes the dual problem.

I was wondering:

  1. Bazaraa's p263 Corollary 2 says: $P \longrightarrow Q$. Is $Q \longrightarrow P$ also true, or when?
  2. When $P$ is true, will $x^*$ solve the inner subproblem of the dual problem when $(u,v)$ is fixed at $(u^*, v^*)$, i.e., $$ f(x^*) + u^{*T} g(x^*) + v^{*T} h(x^*) = \inf_{x \in X} \, f(x) + u^{*T} g(x) + v^{*T} h(x)?$$
  3. When $Q$ is true, will $x^*$ solve the inner subproblem of the dual problem when $(u,v)$ is fixed at $(u^*, v^*)$? If not always, possible to tell when this will happen?

Thanks and regards!

share|improve this question
    
Did you forget to state convexity assumptions? Is $f$ convex? Is $g$ concave? Is $h$ linear? –  Dominique Nov 1 '11 at 22:59
    
@Dominique: I think I was talking about the general case, and there is no such assumption on f, g and h. See the Bazaraa's book link. –  Tim Nov 1 '11 at 23:07

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.