1. Consider the optimization problem

(P1)    min

xRn- s.t.

1

|x x x0 |2(2)  > 1

eT x = 1,

where n 之 2, x = (x1 , x2 , . . . , xn)T  | nn , x0 = ( , . . . , )T  | nn  and e = (1, 1, . . . , 1)T  | nn .

(i) Show that the problem (P1) is a convex optimization problem.

(ii) Using the Karush-Kuhn-Tucker optimality conditions, find the global minimizer of (P1).

2. Consider the following non-convex quadratic minimization problem

(P2 )

min

xRn-

s.t.

xT Ax + 2bT x + c

|x|2(2) x r > 0,

where A is a symmetric (n < n) constant matrix, b is a constant n < 1 vector, c is a scalar, |x|2 = ′xT x and r > 0 is a scalar. You are given that x*  | nn , λ*  | n and the following conditions hold:

(A + λ I)x** + b = 0,    |x* |2(2) x r > 0,   λ* (|x* |2(2) x r) = 0,    (A + λ* I) e 0,   λ*  之 0,

where I is the (n < n) identity matrix and (A + λ* I) e 0 means that the matrix (A + λ* I) is a positive semi-definite matrix. Note that the matrix A is not assumed to be positive semi-definite. Prove that x* is a global minimizer of (P2).

Hint: Show first that the Lagrangian function L(x, λ* ) of (P2) is a convex function on nn .

3. Minimum Cost Pizza Problem. Using only the items given in the tables below, formulate an optimization problem in standard form to create a minimum cost pizza which satisfies both the nutritional requirements of Table 1 and bounds on item quantities given in Table 2. Use the nutritional data of Table

3 and the cost data of Table 4 in your model.

Use the MATLAB linear optimization routines linprog to solve the problem. Interpret your results.

Table 1

Table 2

UPPER AND LOWER BOUNDS ON PIZZA ITEMS

* Amount in hundreds of grams.