• Convex Analysis and Nonlinear Optimization , by J.M. Borwein, and A.S. Lewis, Vol. 3, 2000, CMS Books in Mathematics, Springer Verlag, (extended edition 2006) ( Please send me any typos/comments on the text! on 3 hour reserve call number: QA331.5 .B65 2006 )
• Summary of Notation/Basic Results

1. Homework #1
   • Due: Tuesday, Sept. 29, 2009
   • Reading
     • For your interest only:
       • What is Optimization?
       • NEOS Guide Optimization Tree
   • Problems/Tasks
     • Download and install cvx. (We will experiment with this during the course to solve Disciplined Convex Programming Problems.)
     • Consider the MATLAB file: closest_toeplitz_psd.m. Run this file with the current data. Then, remove the % to uncomment the two lines that generate a random example. Run the file again. Hand in your P,Z matrices and the error for each run.
     • Solve the Supplementary Problems
   • Solns 1; Alternate solution to 1.1;
2. Homework #2
   Due: Tuesday, Oct. 20, 2009
   Reading
   • Text: Related sections.
   • Convex Functions Notes
   Problems/Tasks
   • CVX Problem:
     • consider the SDP relaxation of the max-cut problem discussed in class. Solve the dual of the relaxation using CVX. Let y,X denote the optimum of the dual and primal, respectively.
     • Generate random data as input, i.e. generate random nonnegative weights for the graph and input the Laplacian L as data for the SDP problem.
     • Find an (approximate) solution x for the original max-cut problem and calculate a percentage error.
     • Hand in your cvx program and: L; primal dual optimal y, X; the approximate x; and the percentage error.
     • Perform the above for dimension n=3,5,10
   • Assignment 2 problems pdf file;
3. Homework #3
   Due: Thursday, Nov. 12, 2009
   Reading
   • Text: Related sections.
   • Convex Functions Notes
   Problems/Tasks
   • No CVX Problem for this assign.
   • Assignment 3 problems pdf file; Solutions Assignment 3, pdf file
4. Homework #4
   Due: Thursday, Dec. 3, 2009
   Reading
   • Text: Related sections.
   Problems/Tasks
   • CVX Problem for this assign.
     • Consider the (in the Algorithm part of the wikipedia page) difference map for solving the set intersection problem. (See also Veit Elser's webpage and the Sudoku solver and the Fixed Points in the Midst of Chaos video. ) Program the algorithm using CVX.
     • Use it to solve the closest correlation matrix problem, i.e. generate a random symmetric n by n matrix X (try n=5,10,100) and find a closest matrix in the intersection of: the cone of positive semidefinite matrices and the subspace of symmetric matrices with diagonal all ones.
     • Start with beta +1 or -1. Then, try different values for the parameter beta. What can you say about the convergence rates?
     • Now use the same approach to find a point in the intersection of two circles in R²: The circle of radius 2 centered at the origin (0,0) and the circle of radius 1 centered at (-1,0). (The interesection is the point (-2,0). Note that this is the intersection of two nonconvex sets.)
     • A reference for these projection algorithms in the convex case is: H.H. Bauschke and J.M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38(3), pp. 367-426, 1996. ps.gz, or pdf
   • Assignment 4 problems pdf file; solutions assignment 4 pdf file

CVX Tests/Files

• file cvxtesting.m and the output on Sept 22