This assignment replaces two days of lectures that the instructor is missing. Be prepared to turn in solutions to problems 4-10 below on Friday, November 2. The due date for previously assigned homework is being pushed back. In this assignment, you will watch a video and work some problems involving duality. There is also a quiz to take. Follow the instructions below.
Download Boyd's slides on duality (Chapter 5) It can be helpful to follow the video in the PDF slides on your own computer (especially if you have two computer screens: one for slides and one for the video).
Watch Boyd's Lecture 8 You can watch from the beginning or you can watch starting at 25 minutes 18 seconds (25:18). The full video is 76 minutes. The part I am asking you to watch is 51 minutes. I have already lectured on the first 25 minutes of this material. I hope that you find Professor Boyd as engaging as I do.
After watching the video lecture, take the self-directed quiz. If you are confused about any of the correct answers, bring questions to class next Friday.
For the linear program (LP) posed on slide 5-12, write down the Lagrangian function and derive the dual function. Justify each of the steps. Write down the dual problem.
For the quadratic program (QP) posed on slide 5-13, write down the Lagrangian function and derive the dual function. Justify each of the steps. Write down the dual problem.
For the quadratically constrained quadratic program (QCQP) posed on slide 5-14, write down the Lagrangian function and derive the dual function. Justify each of the steps. Write down the dual problem. Then derive the equivalent semidefinite program (SDP) shown at the bottom of slide 5-14. Study Appendix A.5.5 (pages 650-651) in the textbook and other pages in the text that discuss Schur complements (see the index) as well as pages 170 and 202 (problem 4.40) as examples.
Work out the water-filling example on slide 5-20. Start by writing down the KKT equations and then work out the solution.
Work out the dual problem of the normal approximation problem on slide 5-26. Justify each of the steps.
Work out the dual problem of the box constrained LP problem at the top of slide 5-27. Justify each of the steps. Then derive the simpler dual problem at the bottom of slide 5-27 starting with the implicitly constrained LP problem in the middle of slide 5-27. Hint: Note that is equivalent to and recall that the 1-norm is the dual of the -norm. It will help to study Appendix A.1.6 on the dual norm (page 637).
For the semidefinite program (SDP) posed on slide 5-30, write down the Lagrangian function and derive the dual function. Justify each the steps. Write down the dual problem. Where does the constraint come from?