HOMEWORK, HW1, HW2, HW3, HW4, HW5, bonus,

1. Homework #1 (Revision) (homework pdf file)
   Comments by marker

   due Thur Jan 12, at 10AM.
   • Reading: text Chapter 0, sections 0.1, 0.2, 0.3, 0.4.
   • References (FYI): NEOS Guide Optimization Tree; FAQ on nonlinear programming.
     See also:
     • Portfolio Optimization: A Quadratic Programming Problem, at NEOS and the NEOS Server. Also try help quadprog in matlab and try the matlab file
     • And the Tartaglia problem matlab file

2. Homework #2 (Convex Sets and Functions)
   due: Tues. Jan 24, at 10AM; Comments by marker

   due Thur Jan 12, at 10AM.
   1. Problems
      1. Which number is bigger e^Π or Π^e. Why? (Use min/max of a function.)
      2. Show that a set C in Rⁿ is convex if an only if its intersection with any line is convex; Show that a set C in Rⁿ is affine if an only if its intersection with any line is affine.
      3. Exercises: 1.5, 1.7, 1.8, 1.13, 1.18
         (FYI - definition of p-norms - pdf file)
   2. Reading: Text Chapter 1 - Convex Analysis
   3. References (FYI):
      • Eigenvalues are an important tool in optimization. Eigenvalue Show; this is a matlab file called eigshow.m. This file provides an eigenvalue show that is both entertaining and informative. Other such MATLAB files are available. Here is a local online tutorial on MATLAB.
      • Introduction to Convex Optimization, course notes by Stephen Boyd, including Lagrangian duality, LP duality, interior-point methods, and semidefinite programming; see also Part 3 in the notes by Lieven Vandenberghe
      • Open Problem from Mathematics Web at Elsevier:
        Suppose that f maps the interval [0,1] to Rⁿ, is a continuous function, and maps every subinterval to a convex set.
        Is f([0,1]) a line segment?

3. Homework #3 (Convex Functions and Optimality Conditions)
   due: Thurs. Feb. 9, at 10AM Comments by marker

   1. Problems:
      • Exercises from text: 2.1, 2.3, 2.5, 2.6, 2.7, 2.9
      • Supplementary Exercises to be handed in
   2. Reading: Text Chapter 2, Optimality Conditions
   3. FYI: MATLAB
      1. local MATLAB tutorial (video based)
      2. Matlab appears to be on all the Solaris systems in the undergrad environments, e.g. cpu01.student.math and magnus. You may have to go see Lori Suess in MFCF to set your password properly. (The path is: /.software/local/.admin/bins/bin/matlab The default should now be version matlab-6.5. If not you should try the path software/matlab-6.5/bin/matlab or use "setenv PATH `/bin/showpath matlab-6.5 current`")
         Enter the command matlab to start up the matlab session. Then enter
         help optim
         You will see a list of the optimization functions that are available with the optimization toolkit.
      3. Now try the command
         optdemo
         This will bring up a menu. You can try the four choices. The first choice is a tutorial. This demonstrates several of the optimization functions.
      4. The second choice in the optdemo is the minimization of the banana function or Rosenbrock's function. This is a classical example of a function with a narrow valley that exhibits ``very'' slow convergence for steepest descent type methods. Try out several methods to minimize this function.

4. Homework #4 (Optimality Conditions and Duality )
   due: Thurs. Mar. 9, at 10AM
   Comments by marker

   • Problems:
     • 2.12, 2.15, (and 2.13 as a bonus question!)
     • 3.1, 3.2, 3.3, 3.4,
   • Reading:
     Text Chapter 3, Duality, Sections 3.1 to 3.4.

5. Homework #5 (Algorithms and SDP)
   due: Thurs. Mar. 22, at 10AM Comments by marker

   • Problems:
     1. 4.1, 4.2,
     2. Consider the function
        f(x)=log( e ^x+e ^-x ).
        What is the global minimizer? Perform 5 iterations of Newton's method for minimization with fixed step size 1, starting at the point x⁽⁰⁾=1; and then starting at the point x⁽⁰⁾=1.1. Discuss your results. (Using a MATLAB program is fine. Include the program and the output.)
     3. Do the same as in problem 2. above but for the function:
        f(x)=-log( x) +x.
        and the starting point x⁽⁰⁾=3. Discuss your results.
     4. Suppose that you are given the quadratic function
        q(x)= (1/2) x'Qx + b'x,
        where Q=Q', i.e. it is a symmetric matrix. Prove that:
        • (a) q(x) is bounded below if and only if Q is positive semidefinite and b is in the range of Q.
        • (b) Suppose that the quadratic function q(x) is bounded below. Does Newton's method find the minimum of q(x) in one iteration? Why?
     5. 4.15, 4.16, 4,17, 4.19.
   • Reading:
     Text: Chapter 3, Duality, Section 3.6; Algorithms Chapter 4, Sections 4.1, 4.2, 4.3.3, 4.4, 4.5
   • Semidefinite Programming:
     matlab program to solve SDP Max-Cut Relaxation and a test example.

6. Homework - (Constrained Optimization)
   due: Friday March 31, 2006.

   • Reading: Text Chapter 5, Section 5.1, The Reduced Gradient Method; and Chapter 6, The Interior Point Approach to Nonlinear Optimization, Sections 6.1,6.2,6.3.1,6.3.2 and Examples 6.23, 6.24.
   • BONUS Problems: 5.1, 5.2, 5.4.
   • BONUS Reading: Sections 6.3.3-6.3.6, and Examples 6.23, 6.24.
   • BONUS Problems: 6.1,6.2. Perform iteration 15 in Example 6.23 and carefully explain the steps.