\documentclass{article}
\begin{document}
{\it
\noindent
Andrej Cherkaev 581-6822\\
cell: 801 403 9500\\
email: cherk@math.utah.edu\\
}

\begin{center}
{\Large \bf Final exam for \\
MATH 5710/MATH 6880 Optimization \\ Fall 2010 \\~
\\}
You may use any academic sources. \\ ~\\
Return at Thursday, December 16, at 9:40.\\~\\

\end{center}
\begin{enumerate}

\item
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 ), \quad F=x_1^2+ x_2 ^2 + x_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.

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

\item

Show that a trust region method can be used for minimization of a  bell-shape function 
$$ f=1-\frac{1}{1+x_1^2+\,x_2 ^2},
$$  starting from the point $x_1=2,~ 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.3,~ x_2 =0.1 $? Explain.


\item
% Simplex method - game with mixed strategies
Consider a two-players  zero sum game with the payoff matrix  
$$M=\pmatrix{1 &2& 4 \cr
      5 &2 &3 \cr}.
      $$
Find optimal mixed strategies for both players, applying simplex method for the corresponding linear program. 
\newpage

\item \label{1}
Find duals for the following optimization problems

a)  Linear programming:
$$
\min_{x_1,x_2,x_3} (x_1+ x_2- 3 x_3) $$
subject to 
$$
x_1-x_2 = 1, \quad
x_3+ x_1 \geq 2, \quad x_1\geq 0, ~x_2\geq 0,~ x_3\geq 0.
$$
b) Quadratic programming:
$$
\min_{x_1,x_2,x_3} (x_1^2+ x_2^2 + x_1 x_3 +x_3^2- x_1x_2) $$
subject to 
$$
x_1-x_2\geq 1, \quad
x_3+ x_1 = 2, \quad x_1\geq 0, ~x_2\geq 0, ~x_3\geq 0.
$$
 \item
(i) For both problems in No \ref{1}, find KKT optimality conditions. Suggest an algorithm for the solutions. Solve.

(ii) Apply an interior points method to the problems in No \ref{1}: Modify the KKT conditions, derive and explain an algorithm.

\item
Consider the problem
$$\min_{x_1,x_2 } (x_1^4+ x_2 ^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.



\item
Plot the 3d graph of a multimodal function
$$
f=3 \sqrt{x_1^2+x_2 ^2}+ \log( 1+ x^4+ 4y^2) \left(1.3+\cos(x_1^2-x_2 ^3) \right), \quad |x_1| \leq 5 , ~| x_2  | \leq 5 .
$$

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



\end{enumerate}

\end{document}