Exercise numbers refer to the course text, Numerical Optimization (sec-ond edition, 2006).
Some of these questions require knowledge of Appendix A of Numerical Optimization, and the other background material posted on Canvas.
A polyhedron is the intersection of a nite number of linear inequalities. Say which of the following sets are polyhedra. If they are polyhedral, express them in the form fx j Ax b; F x = gg.
(a) S = fx 2 Rn j x 0; Pn xi = 1; Pn aixi = b; Pn a2xi =
i=1 i=1 i=1 i
cg, where a1; a2; : : : ; an; b; c 2 R are given constants.
S = fx 2 Rn j x 0; xT y 1 for all y with kyk2 = 1g.
S = fx 2 Rn j x 0; xT y 1 for all y with kyk1 = 1g.
Exercise 2.6: Prove that all isolated minima are strict. (Hint: One way to do this is to prove that \not strict" ) \not isolated".)
(a) Give an example of a matrix that is not positive de nite despite having all positive entries.
If A is a positive de nite matrix, must its diagonal elements all be positive? Explain.
Exercise 2.1 from the text.
For each value of the scalar , nd the set of all stationary points (that is, the points x for which rf(x) = 0) of the following function:
f(x) = x21 + x22 + x1x2 + x1 + 2x2:
Which of these points is a global minimizer?
Let f be a twice continuously di erentiable function on Rn. Prove that f is convex if and only if r2f(x) 0 for all x. Hint: The following characterization of convexity of a smooth convex function on Rn may
be helpful: f(y) f(x) + rf(x)T (y x) for all x and y.
1
For the following functions of two variables, answer these questions and justify your answers fully using optimality conditions. (A saddle point is a point that is neither a local minimum nor a local maximum.)
(a) Show that f(x1; x2) := (x12
4)2 + x22 has two global minima and
one saddle point.
(b)
Find all local minima of f(x1; x2) =
1
x12
+ x1 cos x2.
2
(c)
Show that f(x1; x2) := (x2
x12)2 x12
has only one stationary
point, which is a saddle point.
2
