CO367/CM442 Winter 2011

Nonlinear Optimization ( Course Information/Syllabus)
Instructor: Henry Wolkowicz (MC6065,x35589)

  • Time: 01:30-02:20MWF
  • Location: MC 4042
  • TA: Heng (Jerry) Ye, two office hours Tues. and Thurs. 2-3PM, MC5147.
  • Office Hours: Henry: Wed. 4-5:30PM, MC6065.
    Also: . extra office hour for Prof. on tuesday april 19,2011 at 4pm.

  • Text - ONLINE: Convex Optimization – Boyd and Vandenberghe
    (UW Davis Reserves (3 hour loan) QA402.5 .B69 2004)
  • Midterm: Wed. Feb 16, 2011, 7-9PM, MC4058 ( covers material up to and including Lecture 15)
  • Final:
  • Marking Scheme: HW 40%; Midterm 20%; Final 40% latest marks (csv file - view as spreadsheet A1; A2; after midterm -->
  • Lectures outlines/supplementary material
  • Structure of Class

    HOMEWORK - due in class, by start of class, 1:30PM. (Late assignments not accepted.) Submit software code/output to Jerry by email (email address available using uwdir command);
    solutions will not be available due to publisher´s request; questions regarding assignments will be answered in class and during office hours.
    (Hand in assignments for remarking possible for two weeks following return of assignments.)

    HW1, HW2, HW3, HW4, HW5,

    1. Homework #1; due in class, by start of class, Fri. Jan 21, 1:30PM.

      • Problems in Section 2, from the text:
          2.1, 2.2, 2.6, 2.9, 2.12, 2.28, and 2.36.
          Hint for 2.28: A symmetric matrix is positive semidefinite if and only if all principal minors (determinants of submatrices obtained by selecting the same subset of rows and columns) are nonnegative.
      • Bonus problem from text: 2.15
      • Reading: Chapters 1 and 2.
      • Feedback on assignment from the marker
      • Hand in assignments for remarking possible till before start of class, Wed, Feb 9.
    2. Homework #2; due in class, by start of class, Fri. Feb 4, 1:30PM.

      • Problems in Sections 3,4, from the text:
          3.3, 3.6, 3.12, 3.16, 4.1, 4.8(a), 4.8(e)
      • Additional problems:
        1. Use CVX to verify the optimal values you obtained (analytically) for Exercise 4.1.
        2. Show that K is a closed convex cone if and only if the second dual K**=K. (Hint: Sufficiency is easy. For necessity, one inclusion is easy. For the second inclusion use the hyperplane separation theorem.)
        3. Show that the dual (nonnegative polar) of the polyhedral cone V={x | A x ≥ 0} can be expressed as

          V*={ATv | v ≥ 0}. (Hint: It is useful to use/prove that a finitely generated cone is closed.)

        4. (Simple portfolio optimization) We consider a portfolio optimization problem as described on pages 155 and 185-186 of the text, with data that can be found in the file simple_portfolio_data.m.
          1. Find minimum-risk portfolios with the same expected return as the uniform portfolio (x=(1/n)1), with risk measured by the portfolio return variance, and the following portfolio constraints (in addition to 1Tx=1):
            • No (additional) constraints.
            • Long-only: x ≥ 0.
            • Limit on total short position: 1T(x-) ≤ 0.5, where (x-) i = max{ -xi , 0}.
            Compare the optimal risk in these portfolios with each other and the uniform portfolio.
          2. Plot the optimal risk-return trade-off curves for the long-only portfolio, and for total short-position limited to 0.5, in the same figure. (The horizontal axes should show the standard deviation of portfolio return, and the vertical axis should show the mean return. See Figure 4.12 in the text.)
      • Feedback on assignment from the marker
      • Hand in assignments for remarking possible till before start of class, Fri, Feb 18.
    3. Homework #3; due any time from Mon. Feb 28 to start of class, Wed. Mar 2, 1:30PM.

      • Problems in Sections 2-5, from the text:
          2.16 (partial sum of convex sets), 2.21 (set of separating hyperplanes), 3.18 (convexity of matrix functions), 4.17 (optimal activity levels), 5.1 (Lagrangian duals), 5.5 (Dual of general LP - use the notion of implicit/hidden constraint), 5.13 (Lagrangian relaxation/Boolean LP), 5.26 (optimality conditions)
      • Additional problems:
        1. Optimal activity levels: Solve the optimal activity level problem described in exercise 4.17 for the instance with problem data (given in MATLAB notation)
          A=[ 1 2 0 1; 0 0 3 1; 0 3 1 1; 2 1 2 5; 1 0 3 2]
          cmax [100; 100; 100; 100; 100]
          p = [ 3; 2; 7; 6]
          pdisc = 2; 1; 4; 2]
          q = [ 4; 10; 5; 10]

          You can do this by forming the LP you found in your solution of exercise 4.17, or more directly, using cvx. Give the optimal activity levels, the revenue generated by each one, and the total revenue generated by the optimal solution. Also, give the average price per unit for each activity level, i.e., the ratio of the revenue associated with an activity, to the activity level. (These numbers should be between the basic and discounted prices for each activity.) Give a very brief story explaining, or at least commenting on, the solution you find.

      • feedback on assignment
    4. Homework #4; due by start of class, Friday, Mar 18, 1:30PM.

      • Problems in Chapter 9, from the text:
        • Exercises 5.27, 5.28
        • Exercise 9.1(b);
        • Exercise 9.8;
      • Additional problems:
        1. link to CVX problem
        2. Suppose that A is a real n by n symmetric matrix and trace A=K and trace A2 =L are given constants.
          1. Write down the problem of finding the maximum of the sum of the largest two eigenvalues based on the given constants $K,L$.
          2. Write down the KKT conditions for this problem.
          3. Solve the KKT conditions explicitly to obtain the optimal solution. Explain any need for a CQ. Explain why this provides an upper bound on the sum of the largest two eigenvalues.
    5. Homework #5; due by start of class, Monday, April 4, 1:30PM.

  • Last Modified:  Thursday 28 April 2011