CO463/663 Fall 2012

Convex Optimization and Analysis

    "The great watershed in optimization is not between linearity and nonlinearity, but convexity and nonconvexity." (Rockafellar, 1993.)

Instructor Henry Wolkowicz (MC6065, x35589)

  • Time: TR 11:30-1:00PM
  • Location: MC 4060
  • Office Hours: Tues. 2-3PM
  • FINAL EXAM: Thursday, Dec. 6, 12:30-3:00PM, RCH 209 (You may bring one 8.5-by-11 sheet of paper with handwritten notes.)
  • Text:
    • J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis, Springer, 2001
      (available at reserve desk; 3 hour reserve) Picture of Hiriart textbook cover
    Further References
  • Latest list of marks
  • HOMEWORK
    Expect 6 assignments - to be submitted at the beginning of the class stated on the assignment.
    HW1; HW2; HW3; HW4; HW5; HW6 ;

    1. Homework #1
    2. Homework #2
      Problems and solutions - , Due: Tuesday, Oct. 9, 2012
    3. Homework #3
      Due: Thursday, Oct. 18, 2012
      • Problems AND Solutions -
      • CVX Problem: (Note: There is a typo in problem 4: $\alpha \geq 0$ is missing.)
        • 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 (or email) 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
    4. Homework #4
      • Problems and solutions, (typo in problem 1; C is convex set) Due: Thursday, Nov. 1, 2012
      • CVX Problem for this assign.
        • Use CVX 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.
        • Try and do the same for finding the nearest symmetric positive semidefinite http://en.wikipedia.org/wiki/Toeplitz_matrix Toeplitz matrix, a symmetric matrix with constant 'diagonals'. Check the accuracy of your solutions, e.g. is the optimum you found positive semidefinite; are the primal and dual optimal values equal?
    5. Homework #5 problems and solutions, Handed out: Tuesday Nov. 6; Due: Thursday, Nov. 15, 2012 (at start of class)
    6. Homework #6 with solutions, Handed out: Tuesday Nov. 20; Due: Thursday, Nov. 29, 2012 (at start of class)
        (Hint for problem 1: Use the following result from Linear Programming: assume that $u,u^1,,\ldots,u^p$ are vectors in $\R^q$ If $u$ is a nonnegative combination of $u^1,\ldots, u^p$, then it must be a nonnegative combination of no more than $q$ of these vectors. (This follows from the definition of BFS in LP, basic feasible solution in Linear Programming)
        (Hint/Outline for problem 7: \begin{enumerate} \item A convex function $f$ has bounded lower level sets if, and only if, it satisfies the growth condition \[ \liminf_{\|x\|\rightarrow \infty} \frac {f(x)}{\|x\|} >0. \] \item Since $f$ is closed, it is bounded below on compact sets. \item Therefore, the above inequality is equivalent to the existence of a minorant of the form $\epsilon \| \cdot \|+k \leq f(\cdot)$ for some constants $\epsilon >0$ and $k$. \item Taking conjugates, shows that this is equivalent to $f^*$ being bounded above on a neighbourhood of $0$, which in turn is equivalent to $f^*$ being continuous at $0$. \end{enumerate}


    • Last Modified:  Monday 3 December 2012
    XHTML CSS W3C-WAI