Solved-Homework 1 -Solution

Description

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.

1. 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 Rⁿ j x 0; ^Pn x_i = 1; ^Pn a_ix_i = b; ^Pn a²x_i =

i=1 i=1 i=1 i

cg, where a₁; a₂; : : : ; a_n; b; c 2 R are given constants.

1. 2. S = fx 2 Rⁿ j x 0; x^T y 1 for all y with kyk₂ = 1g.

1. 2. S = fx 2 Rⁿ j x 0; x^T y 1 for all y with kyk₁ = 1g.

2. Exercise 2.6: Prove that all isolated minima are strict. (Hint: One way to do this is to prove that \not strict” ) \not isolated”.)

2. (a) Give an example of a matrix that is not positive de nite despite having all positive entries.

2. 2. If A is a positive de nite matrix, must its diagonal elements all be positive? Explain.

2. Exercise 2.1 from the text.

2. 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) = x²₁ + x²₂ + x₁x₂ + x₁ + 2x₂:

Which of these points is a global minimizer?

6. Let f be a twice continuously di erentiable function on Rⁿ. Prove that f is convex if and only if r²f(x) 0 for all x. Hint: The following characterization of convexity of a smooth convex function on Rⁿ may

be helpful: f(y) f(x) + rf(x)^T (y x) for all x and y.

7. 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