where again x ∈ Rn is the optimization variable, c ∈ Rn, d ∈ R, G ∈ Rm×n, h ∈ Rm, A ∈ Rp×n, b ∈ Rp are defined by the problem, but we also have P ∈ Sn+, a symmetric positive semidefinite matrix.
• Quadratically Constrained Quadratic Programming. We say that a convex optimization problem is a quadratically constrained quadratic program (QCQP) if both the objective f and the inequality constraints gi are convex quadratic functions,
minimize 1 2 xTPx+ cTx+ d
subject to 1 2 xTQix+ r
T i x+ si ≤ 0, i = 1, . . . ,m
Ax = b
where, as before, x ∈ Rn is the optimization variable, c ∈ Rn, d ∈ R, A ∈ Rp×n, b ∈ Rp, P ∈ Sn+, but we also have Qi ∈ S
n +, ri ∈ R
n, si ∈ R, for i = 1, . . . ,m.
• Semidefinite Programming. This last example is a bit more complex than the pre- vious ones, so don’t worry if it doesn’t make much sense at first. However, semidefinite programming is become more and more prevalent in many different areas of machine learning research, so you might encounter these at some point, and it is good to have an idea of what they are. We say that a convex optimization problem is a semidefinite program (SDP) if it is of the form
minimize tr(CX) subject to tr(AiX) = bi, i = 1, . . . , p
where the symmetric matrix X ∈ Sn is the optimization variable, the symmetric ma- trices C,A1, . . . , Ap ∈ S
n are defined by the problem, and the constraint X 0 means that we are constraining X to be positive semidefinite. This looks a bit different than the problems we have seen previously, since the optimization variable is now a matrix instead of a vector. If you are curious as to why such a formulation might be useful, you should look into a more advanced course or book on convex optimization.
It should be fairly obvious from the definitions that quadratic programs are more general than linear programs (since a linear program is just a special case of a quadratic program where P = 0), and likewise that quadratically constrained quadratic programs are more general than quadratic programs. However, what is not obvious at all is that semidefinite programs are in fact more general than all the previous types. That is, any quadratically constrained quadratic program (and hence any quadratic program or linear program) can be expressed as a semidefinte program. We won’t discuss this relationship further in this document, but this might give you just a small idea as to why semidefinite programming could be useful.
Homework is assigned each week, and due the following Friday by 5pm. This year we will be using Gradescope, if you registered by the 1st day of the quarter you would have received an email to make a gradescope account. If you are adding the course please use your Stanford email address and the code 9KYX2N to join. Please generate a single pdf document to upload. Keep in mind that large, high resolution images in your pdf may take longer to upload, so plan accordingly when you submit.
You are welcome, even encouraged, to use LaTeX to typeset your homework, but handwritten homework is also OK. You're welcome (but not required) to use the LaTeX templates for EE364b.
All numbered exercises are from the textbook; exercises which start with ‘A’ are from the set of additional exercises posted on the textbook website. Data files for the additional exercises can be found on the textbook page. Access to solutions requires SUNetID (Stanford University Network ID) to log in.
Some Jupyter Notebooks with Convex.jl and cvxpy examples
Homework 8 (last one), due Monday 3/12/18:
A8.12, A6.6, A9.8, A7.20a-d.
Note for A9.8: Python users should avoid using and instead use because matrices with high condition numbers may be encountered.
Homework 8 Solutions