Exercise 3.2 (Optimality conditions)

Proof. We demonstrate the validity of both sides of the equivalence.

$⟹$

Suppose that $x$ is optimal. Let $d$ be an arbitrary feasible direction at $x$, i.e, by Definition 3.1 there exists a positive scalar $𝜃$ such that $x+𝜃d\in P$. Denote $y:=x+𝜃d$. By assumption, $c^{\prime }y\ge c^{\prime }x$ and therefore

$$c^{\prime }d=\frac{c^{\prime }y-c^{\prime }x}{𝜃}\ge 0.$$

$⟸$

Now suppose that none of the feasible directions $d$ at $x\in P$ reduces the optimal cost. Then, for any $y\in P$ we have

$$y=x+(y-x),$$

or in other words, defining $d:=y-x$ and $𝜃:=1$,

$$y=x+𝜃d.$$

Since $0\le c^{\prime }d=c^{\prime }y-c^{\prime }x$, we conclude $c^{\prime }y\ge c^{\prime }x$.

Proof.

$⟹$

Suppose that $x$ is a unique optimal solution to our optimization problem, i.e., $c^{\prime }x<c^{\prime }y$ for any other $y\in P$. Using the same argument as in the previous exercise part, we obtain

$$c^{\prime }d=\frac{c^{\prime }y-c^{\prime }x}{𝜃}>0.$$

$⟸$

Similarly, suppose that any other feasible direction $d$ at $x$ increases the cost. If we had another optimal solution $y\in P$ with $c^{\prime }y=c^{\prime }x$, then $d:=y-x$ with $𝜃:=1$ would constitute for a feasible direction which does not increase the cost - a contradiction.