Continuous Optimization - 466/666 - Winter 2001

1. Submit a contour plot of the banana function for variable values between
2. How many function evaluations did the minimization take for: steepest descent; simplex search; Broyden-Fletcher-Golfarb-Shanno; Davidon-Fletcher-Powell; Levenberg-Marquardt? (Please specify the line search you used.)

Note: You can modify the matlab programs. You can see what the matlab routines are doing by looking at the matlab m-files. To do this change directory using: cd /software; cd matlab; cd distribution; cd toolbox; cd optim. In particular, there is an m-file called bandemo.m.

• Chapters 5,6 in the text (pages 100-162)

1. MATLAB
   Use the conjugate gradient algorithm in the matlab program cgtrust.m to find the minimum of the banana function from the initial points: (-2,-3), (0,0), (-1.9,2), (-1.9,20).
   Provide the number of major iterations and the final point to four decimals. Explain the behaviour.
   You will need the files dirdero.m and README. (You can use the default parameter values to start.)
2. Page 133, Problem 5.2, 5.4 Comments on Solutions to Homework 4
3. Homework #5 (NLLS, Nonlinear Equations, Nonlinear Programming)
   Due: Tuesday February 27, 2001 (at start of class)
   Reading
   • Chapters 10,11,12 in the text (pages 250-358)
   Problems
   1. MATLAB (try to use matlab 6)
      
      1. Test out the data fitting demo. This is one of the command line demos in the optimization toolkit. The example demonstrates fitting a nonlinear function to a set of data. Provide the plots of the data points; then provide the plots, number of iterations, function evaluations, and norm of the residual of the fit when using the Gauss-Newton method (with mixed polynomial interpolation) and, also when using sequential quadratic programming. Include the algebraic form of the nonlinear function that is used.
   2. Problems from text:
      1. Page 274, Problem 10.1.
      2. Page 311, Problem 11.7.
      3. Page 358, Problems 12.1,12.2,12.5.
4. Homework #6 (Constrained Nonlinear Programming and Convex Analysis)
   Due: Thursday March 8, 2001 (at start of class)
   Reading
   • Chapter 12 in the text (pages 314-358)
   • For further information on Lagrange Multiplier Theorems and modern proofs see the paper:

             author    = "B.H. POURCIAU",
              title     = "Modern multiplier methods",
              journal   = "American Mathematical Monthly",
              year      = "1980",
              volume    = "87",
              number    = "6",
              pages     = "433-451"}
     

     This paper is available on campus using JSTOR, e.g. try the link http://www.jstor.org/cgi-bin/jstor/listjournal/00029890/di991653?config=jstor&frame=frame&userID=8161a648@uwaterloo.ca/01cc99331a0050473801&dpi=3
   Problems
   1. Constraint Qualifications
      1. Consider the general NLP with both equality and inequality constraints. Define the tangent cones and the linearizing cones at a feasible point x. Then show that the tangent cone is a subset of the linearizing cone.
      2. Consider the NLP:
         
         miniminze f(x,y,z)= e^x + e^-y+z
         subject to:
         g₁(x,y,z)= e^x -1 <= 0
         g₂(x,y,z)= e^-y -1 <= 0
         g₃(x,y,z)= (x -1)² + y² -1 <= 0
         g₄(x,y,z)= x²+y²+e^-z -1 <= 0
         
         1. Verify that the NLP is a convex program.
         2. Use the KKT conditions to test for optimality at the origin (0,0,0)^T.
         3. Use the Pshenichnyi conditions to test for optimality at (0,0,0)^T.
         4. Is there a contradiction between the two tests for optimality? Find the linearizing cone at (0,0,0)^T. Then find a direction in the linearizing cone that is not a tangent direction and use this to explain the discrepency.
   2. MATLAB (try to use matlab 6)
      
      1. Use the constrained optimization function fmincon in the optimization toolbox to solve the above convex program (problem 1.2 above). Can you get high accuracy in the solution?
   3. Problems from text:
      1. Page 359, Problem 12.10
      2. Page 360, Problem 12.17
   4. Homework #7 (Constrained Nonlinear Programming, Convex Analysis, and Linear Programming)
      Due: Thursday March 22, 2001 (at start of class)
      Reading
      • Chapters 13,14 in the text (pages 363-419)
      Problems
      1. Duality
         1. Consider the Trust Region Subproblem, TRS:
            p^*:= minimize q(x)=x^TAx-2b^Tx subject to x^Tx <= a
            Show that:
            1. The KKT conditions, with the added restriction that the Lagrangian function (at the optimal dual variable y) is convex, characterizes optimality. (How does this differ from the usual second order optimality conditions?)
            2. Show that a dual problem is:
               d^*:= maximize g(y):=y a - b^T(A-y I)^-1b
               ---subject to (A- y I) positive definite, y <= 0
         2. Problems from text and MATLAB:
            1. 1. First, try and extend the duality theory for the TRS above to include general constraints of the type: q(x) <= 0 or q(x) = 0, where q is a general quadratic function on Rⁿ.
               2. Then, use the above duality theory and apply it to solving the problems on Page 360, Problems 12.18,12.20,12.21.
               3. Solve the above three problems using the MATLAB: (i) Levenberg-Marguardt algorithm lsqnonlin; (ii) the trust region algorithm in the directory distribution/toolbox/optim/private (file trust.m); and (iii) the trust region method in fmincon.
            2. Page 393, Problems 13.2,13.3
         3. Homework #8 (Penalty and Barrier Methods; Sequential Quadratic Programming)

            The assignment is OPTIONAL. But, we will go over it in class on Thursday. Similar questions may appear on the final exam.

            Due: Thursday March 29, 2001 (at start of class)
            Reading
            • Chapters 17,18 in the text (pages 491-575)
            Problems
            1. Problems from text:
               1. Page 526-527 Problems 17.1,17.2,17.3

            ---

            ---

            
            Mail to: hwolkowicz@uwaterloo.ca
            (C) Copyright Henry Wolkowicz, 2001.
            , by Henry Wolkowicz

            ---