
264 Introduction to Linear Optimization and Extensions with MATLAB
R
Proof:
Since x
∗
is a local minimum, by Corollary 7.9 ∇f (x
∗
) = 0. Now suppose
that H(x
∗
) is not positive semidefinite. This implies that there is a vector d
such that d
T
H(x
∗
)d < 0.
Now f (x) is twice differentiable, so
f(x
∗
+ αd) = f(x
∗
) + α∇f(x
∗
)
T
(d) + 1/2α
2
d
T
H(x
∗
)d + α
2
kdk
2
o(x
∗
, αd)
= f(x
∗
) +
1
2
α
2
d
T
H(x
∗
)d + α
2
kdk
2
o(x
∗
, αd)
where lim
α→0
o(x
∗
, αd) = 0. Then,
f(x
∗
+αd)−f(x
∗
)
α
2
=
1
2
d
T
H(x
∗
)d + kdk
2
o(x
∗
, αd).
Since d
T
H(x
∗
)d < 0, then for all α > 0 sufficiently small f(x
∗
+
αd) − f(x
∗
) < 0, which implies that d is a descent direction for f(x) at
x
∗
contradicting that x
∗
is local minimum.
The second-order ...