Exercise 3.7 (Optimality conditions)

Proof. This exercise boils down to combining two key results we have proven earlier in the lecture: Exercise 3.2 and Exercise 3.3.

$\text{⟸}$

Suppose that the cost change minimization problem has an optimal solution $0$. First, notice that the polyhedron $P=\{d\in {\Re }^n\mid \mathrm{Ad}=0,d_i=0\text{ for }i\in Z\}$ defining the feasible vectors for cost change minimization problem includes all of the feasible directions $d$ at $x$ (direct result of Exercise 3.3). In other words, every feasible direction at $x$ gives us a non-negative cost change. Secondly, if the cost change is nonnegative $c^{\prime }d\ge 0$ for every feasible direction $d$ at $x$, then $x$ is optimal (direct result of Exercise 3.2). This proves the reverse direction.

$\text{⟹}$

Suppose that $x$ is optimal. Notice that $0$ is feasible for the cost change minimization problem; thus, the minimum is at most $c^{\prime }0=0$. Suppose for the sake of contradiction that the optimal value is even lower, i.e., there is a feasible vector $d$ such that $c^{\prime }d<0$. But $d$ is a feasible direction at $x$ (direct result of Exercise 3.3). That way we have found a feasible direction at the optimal solution which reduced the overall cost - a contradiction to the Exercise 3.2.