Additional references: Fundamentals of Convex Analysis (Hirriart-Urruty/Lemarechal); and Numerical Methods for Unconstrained Optimization and Nonlinear Equations, by J. E. Dennis, Jr. and Robert B. Schnabel, see chapters 3,4 for lin. alg/calculus background.

• date: Thursday, April 21, 4-6:30PM MC4040
• Outline for final exam mean and median final grades: 71.85, 76

• Course Goals
  • Formulate problems as (convex) optimization problems
  • Develop code for problems of moderate size
  • Characterize optimal solutions (optimality conditions)
• Topics
  • Convex sets, functions, optimization problems
  • Examples and applications
  • Algorithms
• Textbook: Convex Optimization - Boyd and Vandenbergh
  • http://www.stanford.edu/~boyd/cvxbook/
• Software: CVX
  • http://www.stanford.edu/~boyd/cvx/ webpage (for e.g. downloads/manual)
  • file pccvxstartup.m for sample path file for matlab
  • CVX user's guide (pdf file)

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^*={A^Tv | 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 1^Tx=1):
           • No (additional) constraints.
           • Long-only: x ≥ 0.
           • Limit on total short position: 1^T(x_-) ≤ 0.5, where (x_-) _i = max{ -x_i , 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]
        c^max [100; 100; 100; 100; 100]
        p = [ 3; 2; 7; 6]
        p^disc = 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 A² =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.

   • Problems from the text:
     • 9.12, 10.5, 10.8,
     • 11.1, 11.2, 11.3, 11.4
   • feedback on assignment