ELG7173D Introduction to Convex Optimization (Winter 2018)

(under construction, frequently updated)


Announcements:

 

 

Final exam marks and unofficial final grades are now posted. Official grades will be announced by the university in the regular way.

 

***

Assignment 4 has been posted.

Marks of assignments 1-3 have been posted. Double-check and report any errors within 1 week.

Project topics have been posted.

Project guidelines have been posted – please read and start your project activities (talk to me if you are not sure which topic to select).

1st class: Wed. Jan. 10, 16:00, CBY E015.

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

 

“Is convex optimization really useful and worth of trouble?”        See for yourself.


Office hours:

 

Thursdays, 5-6pm. Outside office hours - by appointment only. No exceptions! You are encouraged to ask questions immediately after lectures (but not before). No questions by email (will not be answered).

Lectures:

 

Lec 1,

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

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

 

 

Assignments:

 

Marks: 1-3

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.


Additional material:

Matlab software for convex programming (CVX) (includes detailed guidelines on installation and use, and many examples, including those from the course textbook), CVX review , CVX User's Guide .

 

Minimax and Convex-Concave Games

 

Convex tools for non-convex problems

 

Additional links:

·       Introduction to Convex Optimization at MIT

·       Optimization of Communication Systems at Princeton

·       Convex Optimization at UofT

·       Convex Optimization at Berkeley

·       Optimization Models and Applications at Berkeley

o   Hyper-Textbook

·       Convex Analysis and Optimization at MIT

·       Optimization Methods at MIT

Recent news: convexity is NP hard.

 

Brief review of matrix theory. Eigenvalues and singular values (in Matlab).

 

On the not-so-distant revolution in optimization:

·       M.H. Wright, "The interior-point revolution in optimization: history, recent developments, and lasting consequences." Bulletin of the American mathematical society, v. 42, no. 1 (2005): pp. 39-56.

·       A. Forsgren, P. E. Gill, M. H. Wright. "Interior methods for nonlinear optimization." SIAM review, v. 44, no. 4 (2002): pp. 525-597.

History of optimization:

·       G. Giorgi, T.H. Kjeldsen, A Historical View of Nonlinear Programming: Traces and Emergence, Springer Basel, 2014.

·       H.W. Kuhn, Being in the Right Place at the Right Time, Operations Research, v. 50, N. 1, pp. 132-134, Jan.-Feb. 2002.

Project Info:


Project guidelines. Sample references. List of project topics.

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:

TBD, Open book.