# Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and..

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}

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
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^*)$.
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