ELG6108 Introduction to Convex Optimization (Winter 2024)

(under construction, frequently updated)


Announcements:

 

 

Assignment 4 has been posted (see below).

 

A very brief shortcut to (almost) entire course (by D. Rosenberg). Keep in mind that this is a good (high-level) overview but not a substitute to the regular studies (attending lectures, reading the textbook, doing assignments and project).

 

 

***

Assignment 3 has been posted. Please study the slides of Lecture 4 (including those not covered in class) and read the relevant sections of Chapter 4 of the course textbook.

 

Project guidelines have been posted (see below). Please read carefully and start your project activities.

 

1st class: Mon. Jan. 8, 4pm, CRX C410.

Please download and print the lecture notes before coming to the class. All the questions will be answered in the class.

 

Course information:

see Lecture 1 for details.

 

“Is convex optimization really useful and worth of trouble?”        See for yourself; (see also citation numbers for this 6-year old paper ; good luck to all of us with getting that many citations in our entire lifetime :)

 

A very brief shortcut to (almost) entire course (by D. Rosenberg). Keep in mind that this is a good (high-level) overview but not a substitute to the regular studies (attending lectures, reading the textbook, doing assignments and project).

 


Office hours:

 

            Wednesday, 5:30-6:30 pm.

Lectures:

 

Lec 1, 3, 4, 5,

I will be using the lecture slides of Prof. Boyd, which can be found at

http://www.stanford.edu/class/ee364a/lectures.html

 

 

Assignments:

 

 

Assignments: 1, 2, 3, 4,

Study Appendix A of the textbook (math background). Consult additional references for more information.

* Please give detailed solutions, not just final answers. Explain all important steps, do not skip them!

* Plagiarism (i.e. “cut-and-paste” from a student to a student, other forms of “borrowing” the material for the assignment) is absolutely unacceptable and will be penalized. Each student is expected to submit his own solutions. If two (or more) identical or almost identical sets of solutions are found, each student involved receives 0 (zero) for that particular assignment. If this happens twice, the students involved receive 0 (zero) for the entire assignment component of the course in the marking scheme and the case will be send to the Dean’s office for further investigation.

Project Info:

 

            Project guidelines

 

            Tips for preparing a presentation:

  • Pointers on giving a talk” by D.G.Messerschmitt (UC Berkeley). Extra advice is here.
  • Number all slides; give a printout to the instructor (4 slides/page).

·         

Course Textbook:

*S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

 

More material is available at the following web pages:

·        http://www.stanford.edu/~boyd/cvxbook/

    • this is the book web page (pdf of the book is available)
    • this is a convex optimization course taught by Prof. Boyd at Stanford
    • there are many useful things at this page, including the videos of lectures.
    • this is an optimization course taught by Prof. Vandenberghe at UCLA.

 

Additional texts:


Additional books (available in the library, some in pdf):

2.   D. G. Luenberger, Linear and Nonlinear Programming, Springer, 2005.
3.   J. Brinkhuis, V. Tikhomirov, Optimization: Insights and Applications, Princeton, 2005.
4.   R. Fletcher, Practical Methods of Optimization, Wiley, 2000.
5.   K. Lange, Optimization, Springer, 2013.
6.   C.L. Byrne, A First Course in Optimization, available at http://faculty.uml.edu/cbyrne/opttext.pdf
7.   M. Aoki, Introduction to Optimization Techniques. Macmillan, 1971.

Some more references (deep but mathematically demanding)

8.   D.P. Bertsekas, Nonlinear Programming, Athena Scientific, 2nd Ed., 2008.
9.   A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, 2001.
10. D. G. Luenberger, Optimization by Vector Space Methods, Wiley-Interscience; 1997.
11. D.P. Bertsekas, A. Nedic, A,E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, 2003.
12. A.G. Suharev, A.B. Timoxov, B.B. Fedorov, A Course of Optimization Methods, FML, Moscow, 2005 (in Russian).
13. B.M. Alekseev, E.M. Galeev, B.M. Tihomirov, Problems in Optimization Theory, FML, Moscow, 2005 (in Russian).
14. B.T. Polayk, Introduction to Optimization, Nauka, Moscow, 1983 (in Russian).).

Matrices/linear algebra

15. A.J. Laub, Matrix Analysis for Scientists and Engineers, SIAM, 2005. -
this is a good introductory book with discussion of basic techniques and results in linear algebra and matrix theory.
16.  F. Zhang, Matrix Theory, Springer, 1999. – this is a more comprehensive textbook of matrix theory, with many end-of-chapter problems.
17. R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press. this and the 2nd volume (next) is a comprehensive book, which treats in detail all important methods and results in matrix theory; it is very well written and end-of-chapter problems are well-selected. Strongly recommended, especially if you use matrix theory in your research.
18.  R.A. Horn, C.R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991. – see the comments for # 14.
19. D.S. Bertstein, Matrix Mathematics, Princeton University Press, 2005. - this is an extensive handbook with many facts and formulas involving matrices, which are well categorized and handy to use (but this is not a textbook - you cannot learn matrix theory from it).
20. Matrix Cookbook - a handbook on matrices, pdf is available.
20a. R. Bronson, Matrix Operations, McGraw Hill, 2011. – a handbook on matrices/linear algebra with many solved problems.

Convex Optimization in Communications/Signal Processing/Networks

21. D. P. Palomar and Y. Jiang, “MIMO transceiver design via majorization theory,” Found. Trends Commun. Inf. Theory, vol. 3, no. 4-5, pp. 331–551, 2006
22. M. Chiang, Geometric Programming for Communication Systems, Foundations and Trends in Communications and Information Theory, Vol. 2, No 1/2 (2005) 1–154.
23. E. Jorswieck, H. Boche, Majorization and Matrix-Monotone Functions in Wireless Communications, Foundations and Trends in Communications and Information Theory, Vol. 3, No. 6 (2006) 553–701.
24. M. Chiang, P. Hande, T. Lan, Power Control in Wireless Cellular Networks, Foundations and Trends in Networking, Vol. 2, No. 4 (2007) 381–533.
25. M. Chiang et al, Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures, Proceedings of the IEEE, Vol. 95, No. 1, January 2007.
26. P.P. Vaidyanathan, S.M. Phoong, Y.P. Lin, Signal Processing and Optimization for Transceiver Systems, Cambridge University Press, 2010.
27. E. Björnson and E. Jorswieck, "Optimal Resource Allocation in Coordinated Multi-Cell Systems," Foundations and Trends in Communications and Information Theory, vol. 9, no. 2–3, pp. 113-381, Jan. 2013.
28. Y. J. Zhang, L. Qian, and J. Huang, "Monotonic Optimization in Communication and Networking Systems," Foundations and Trends in Networking, vol. 7, no. 1, pp. 1-75, Oct. 2013.

Course References: Papers (Selected only)

Sample reference list

Final Exam:

 3h, open book

Extra info:

 * Submodular Optimization,  

 * Online Convex Optimization,

 * Lagrangian Duality and Convex Optimization,

 * Extreme Abridgement of Convex Optimization,