Andrej Cherkaev email: cherk@math.utah.edu

Final exam for

MATH 5710/MATH 6880 Optimization Fall 2011

You may use any academic sources.

Return at Monday, December 12, before 2:00 pm by email to cherk@math.utah.edu

1. Apply the conjugate gradient method for minimization of a quadratic function

min_{x_{1},x_{2},x_{3}} F (x_{1}, x_{2}, x_{3}), F = x_{1}^{2} + 4x_{2}^{2} + 2x_{3}^{2} + (x_{1} + x_{3}) x_{2} − x_{1} x_{3} − x_{1}

Initial point is x_{1} = 2, x_{2} = 0, x_{3} = 0. Show that a solution is achieved in a finite number of iterations. Justify the number of iterations.

2. Apply the quasi-Newton method (any modification) to the same problem. Perform one step.

3. Show that a trust region method can be used for minimization of a bellshape function

f(x_{1}, x_{2}) = 1 − \frac{1}{1 + x_{1}^{2} + 4x_{2}^{2} + x_{1}x_{2}} ,

starting from the point x_{1} = 3, x_{2} = 2. Compute the first iteration.

Is a conjugate gradient method applicable to this problem?

What minimization methods can be used, if the starting point is x_{1} = 0.1, x_{2} = 0.1? Explain.

4. Consider a two-players zero sum game with the payoff matrix

P = ( \begin{matrix}0 & 4 & 3 \\ 4 & 1 & 3 \end{matrix} ) .

Find optimal mixed strategies for both players, applying simplex method for the corresponding linear program.

5. Find duals for the following optimization problems

a) Linear programming:

min_{x_{1},x_{2},x_{3}}(x_{1} − 2x_{2} + x_{3})

subject to

x_{1} + x_{2} = 1, 2x_{3} + x_{1} ≥ 2, x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0.

b) Quadratic programming:

min_{x_{1},x_{2},x_{3}}(3x_{1}^{2} + x_{2}^{2} + x_{1}x_{3} + x_{3}^{2} − x_{1}x_{2} − x_{2})

subject to

x_{1} − x_{2} ≥ 1, x_{3} + x_{1} = 2, x_{1} ≥ 0, x_{2} ≥ 0, x_{3} ≥ 0.

6. (i) For both problems in No 5, find KKT optimality conditions. Suggest an algorithm for the solutions. Solve.

(ii) Apply an interior points method to the problems in No 5: Modify the KKT conditions, derive and explain an algorithm.

7. Consider the problem

min_{x_{1},x_{2}}(x_{1}^{4} + x_{2}^{2} + x_{1} x_{2} − x_{2})

subject to constraint x_{1} = x_{2}^{2} − 1. Applying the augmented Lagrangian method, write an algorithm for iterative solution and updating the Lagrange multiplier.

8. Plot the 3d graph of a multimodal function

f = 3\sqrt{x_{1}^{2} + x_{2}^{2}}+log(1+x^{4}+4y^{4}) (1.25 + cos(4x_{1}^{2} + x_{2}^{3})) , |x_{1}| ≤ 5, |x_{2}| ≤ 5.

What methods can be used for finding its minimum? Suggest an algorithm and discuss.