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.

Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and an optimal solution $(\bar{x},\bar{z})$ of the problem 2 $\min z $ s.t $z\ge f(x)\,, x\in \mathbb{R}^n$ are such that $\bar{z}=f(\bar{x})=f(x^*).$ Provide an example where $x^*\neq \bar{x}$.

The problem with proof structure has been resolved!

Now here is an idea:

Can we prove $x^*$ is global optimal of problem 1?

Hypothesis: There does not exist $(x,z)$ s.t $z\ge f(x),\, z<z^*$ by definition of optimal solution.

Claim: There does not exist $x'\in \mathbb{R}^n$ s.t $f(x')<f(x^*).$ Proof: Suppose there exists $x'\in \mathbb{R}^n$ s.t $f(x')<f(x^*)\le z^*$. Then we could create $z=f(x)$ but then $z<z^*$.

For the example, where $x^*\neq \bar{x}$, here's what I think: \begin{align} \min \,f(x,y)=2x-3y\\ &s.t \,\,\, -2< x < 2\\ & \, \, \,\,\,\,\,\,\,\, 0< y < 4\\ &\,\,\, x,y\in \mathbb{R}\\ \end{align} \begin{align} \min \,z=2x-3y+1\\ &s.t \,\,\, -2< x <2\\ & \, \, \,\,\,\,\,\,\,\, 0< y < 4\\ &\,\,\, x,y\in \mathbb{R}\\ \end{align}

Any comments/suggestions/answers are appreciated.

share|improve this question
1  
Nice of you to take time out of your busy schedule to visit us, Mr. President. It can't be if and only if, because I could pick a random $x$ out of a hat and define $\bar x = x^* = x$ and $\bar z = f(x)$. Certainly these are not the optimal solutions (my hat is not that clever). –  Rahul Sep 6 '12 at 12:15

1 Answer 1

up vote 1 down vote accepted

Let $x^*$ be any optimal solution to (1) and set $z^*=f(x^*)$. Then notice that $(x^*,z^*)$ is feasible in (2) from which we can conclude that any optimal solution $x^*$ to (1) provides an upper bound $(x^*,f(x^*))$ to (2). Conversely, assume that $(\bar{x},\bar{z})$ is any optimal solution to (2). Then $\bar{z}=f(\bar{x})$ since otherwise we could reduce $\bar{z}$. Moreover, $f(\bar{x}) \geq f(x^*)$ since $x^*$ is a minimizer of $f$.

Putting everything together we have $f(x^*) \geq \bar{z} = f(\bar{x}) \geq f(x^*)$ which implies $\bar{z} = f(\bar{x}) = f(x^*)$.

share|improve this answer
    
Thanks. Can you also think of an example where $x^*\neq x$. –  Lyapunov Sep 6 '12 at 15:13
    
Sure. You can do this any time there are multiple optimal solutions to (1). Suppose you minmize $f(s,t)=s$ subject to $s\geq 0, 0 \leq t \leq 2$. Then you can take $x^*=(0,0)$ and $\bar{x}=(0,2,0)$ (here $\bar{z}=0$). Notice that $f(x^*)=0=f(\bar{x})=\bar{z}$. –  shoda Sep 7 '12 at 12:49

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.