CSE 203B, Winter 2022 Convex Optimization

University of California, San Diego

Instructor

• CK Cheng, room CSE2130, email: ckcheng+203B@ucsd.edu, tel: 858 534-6184
• Office hour: TBA

Teaching Assistant

• Holtz, Chester, chholtz@ucsd.edu,
• Liu, Isabella, lal005@ucsd.edu
• Nagola, Ethan, enagola@ucsd.edu
• Paksoy, Oguz, opaksoy@ucsd.edu
• Ravindrakumar, Vaishakh, varavind@ucsd.edu
• Song, Meng, mes050@ucsd.edu
• Office hours: TBA (Piazza)

Class Platform

• Disclose details of any related manuscripts that all authors have under consideration or in press elsewhere. Piazza: http://piazza.com/eng.ucsd/winter2022/cse203bwinter2022, or https://piazza.com/class/kx85xrdgigl5m5.
• Gradescope:
• UCSD Podcast of lectures and discussion sessions

Schedule

• Lectures: 12:30-1:50PM TTH, Centr 101
• Discussion: 9:00-9:50AM F, Centr 101

References

• Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge, 2004 (required textbook).
• Numerical Recipes: The Art of Scientific Computing, Third Edition, W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Cambridge University Press, 2007.
• Matrix Computations, 4th Edition, G.H. Golub and C.F. Van Loan, Johns Hopkins, 2013.
• Convex Optimization by R. Tibshirani, http://www.stat.cmu.edu/~ryantibs/convexopt/
• EE364a: Convex Optimization I, http://stanford.edu/class/ee364a/

Prerequisite

Linear algebra and basic knowledge of numerical methods, or intention of conducting projects related to scientific computation.

Content

We study the formulations and algorithms solving convex optimization problems. The topics include convex sets, functions, optimality conditions, duality concepts. If time permits, we will talk about gradient descent, conjugate gradient, interior-point methods, and applications. The objective of the course is to provide students the background and techniques for scientific computing and system optimization.

Lectures

• Part I: Theory
• Lecture 1 Introduction pptx, pdf.
• Lecture 1 Survey on grading policy: 50% HW, 25% Midterm, 25% project
• Lecture 2 Convex Set, Reading assignment: Chapter 2, Lecture slides pptx, pdf with notes on W2A 1/11 0111.pdf, 0111a.pdf, on W2B 1/13 W2B.pdf, on W3A 1/18 W3A.pdf.
• Lecture 3 Convex Function, Reading assignment: Chapter 3, pptx, pdf, on W3B 1/20 pdf, on W4A 1/25 pdf, on W4B 1/27 pdf, on W5A 2/1 pdf,
• Lecture 4 Formlation, Reading assignment: Chapter 4, pptx, pdf, on W5B 2/3 pdf, on W6A 2/8 pdf,
• Lecture 5 Duality, Reading assignment: Chapter 5, pptx, pdf, on W6B 2/10 pdf, on W7A 2/15 pdf, on W7B 2/17 pdf, on W8A 2/22 pdf, on W8B 2/24 pdf,
• Part II: Algorithms
  • Lecture 9 Unconstrained Minimization pptx, pdf, with notes on W9B pdf, with notes on W10A pdf.
  • Recommended reading on Newton's method: Dauphin, Y., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S. and Bengio, Y., 2014. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. arXiv preprint arXiv:1406.2572.
  • Lecture 10 Equality Constrained Minimization pptx, pdf
  • Lecture 11 Interior Point Methods pptx, pdf, with notes on W9A pdf, with notes on W10B pdf

Lectures (Winter 2021)

• Part I: Theory
• Lecture 1 Introduction pptx, pdf, and slides with notes on W1A pdf.
• Lecture 2 Convex Set pptx, pdf, slides with notes on W1B pdf, slides with notes on W2A1 pdf, slides with notes on W2A2 pdf, notes on W2B pdf.
• Lecture 3 Convex Function pptx, pdf, slides with notes on W3A pdf, slides with notes on W3B pdf, slides with notes on W4A pdf.
• Lecture 4 Formulation pptx, pdf, slides with notes on W4B pdf, slides with notes on W5A pdf.
• Lecture 5 Duality pptx, pdf, slides with notes on W5B pdf, slides with notes on W6A pdf, slides with notes on W6B pdf, slides with notes on W7B pdf, slides with notes on W8A pdf, slides with notes on W8B pdf.
• Part II: Algorithms
  • Lecture 9 Unconstrained Minimization pptx, pdf, slides with notes on W8B pdf, slides with notes on W9A pdf.
  • Lecture 10 Equality Constrained Minimization pptx, pdf, slides with notes on W9B pdf, slides with notes on W10A pdf.
  • Lecture 11 Interior Point Methods pptx, pdf, slides with notes on W10B pdf.

Homework

• Policy for late homework: 10% discount for each day before the solution is released.
• Homework 1: Basic concepts of programming and linear algebra tex, pdf, due 1/12/2022. solution: pdf
• Homework 2: Convex Set tex, pdf, due 1/26/2022. solution: pdf
• Homework 3: Convex Function tex, pdf hw3_signal.txt, was due 2/2/2022. The due date is shifted to 2/9/2022. solution: pdf
• Homework 4: Problem Statement tex, pdf due 2/16/2022. solution: pdf

Homework (Winter 2021)

• Policy for late homework: 10% discount for each day
• Homework 0: Linear Algebra tex, pdf, due 1/18/2021 (problem 2.4 updated on 1/11/2021), solution: pdf
• Homework 1: Convex Set tex, pdf, due 1/25/2021, solution: pdf
• Homework 2: Convex Function tex, pdf, due 2/1/2021, solution: pdf
• Homework 3: Problem Formulation, HW3 tex file tex, figure ellipsoid.png, and data hw3_signal_noise.txt, HW3 pdf, due 2/8/2021, solution: pdf
• Homework 4: Duality tex, pdf, due 2/15/2021

Discussions

• Discussion 1: Math Fundations pptx, pdf.
• Discussion 2: Affine, convex sets and hyperplanes pdf.
• Discussion 3: Qualification & enumeration, dual cone and SVM pptx, pdf.
• Discussion 5: Convex function pdf.
• Discussion 6: Problem formulation pdf.
• Midterm Review pdf.

Discussion (Winter 2021)

• Discussion 1: Linear Algebra Review: pdf. tex.
• Discussion : Convex Sets: pdf
• Discussion : Convex Functions 1: pdf
• Discussion : Convex Functions 2: pdf
• Discussion : Convex Formulation: pdf
• Discussion : Midterm Review: pdf

Exam

• Winter 2022 Midterm Exam: tex. pdf. solution: pdf.

Exam (Winter 2021)

• Winter 2021 Midterm Exam: tex, pdf, and solution: pdf. Take home exam posted on 10AM Tu 2/16, due 10AM Th 2/18. No class lecture on Tu 2/16.
• Fall 2017 Midterm review, pdf file
• Fall 2017 Midterm Rubrics, pdf file
• Winter 2019 Midterm Rubrics, pdf file
• Winter 2020 Midterm, pdf file, tex file.
• Winter 2020 Midterm Solution, pdf file.

Project

• Project Outlines was due 1/28. The due date is shifted to Friday 2/4/2022 pdf, pptx.
Top reports: Award Winning (3 out of 66 reports)
• 17) Towards an Optimization Perspective for Bandits Problem [Authors: Junyan Liu, Sijie Wang] pdf
• 34) An Evaluation of Methods for Instrument Style Transfer [Authors: Ahmed Hussaini, Heidi Cheng, Payal Pandit, Sachinda Edirisooriya] pdf
• 65) Global Alignment of HD Maps and Satellite [Authors: Harish Sethuram, Manoj Kilaru, Srirangan Madhavan] pdf
Prototype reports: Prototyping (4 out of 66 reports)
• 29) Energy-Based Video Frame Interpolation [Authors: Mehak Preet Dhaliwal, Rohan Patil, Uday Varikuti, Wei-Ling Huang] pdf
• 44) A Survey on Convex Image Denoising Methods [Authors: Hao Li, Sihan He, Tianrui Wang, Yi Zhang] pdf
• 49) Efficient Influential Researcher Selection [Authors: Jiongli Zhu, Shijie Sun, Shuangyu Xiong, Tingwei Chen] pdf
• 54) Fine-grained Named Entity Recognition using only Coarse-grained Labels [Authors: Gaurav Kumar, Sudhanshu Ranjan] pdf

Project (Winter 2021)

• Winter 2021: Two Award Winning Projects
  • 1. Optimizing the Administration of COVID-19 Vaccines pdf.
  • 2. Toward More Vibrant Image Colorization pdf.
• Project Outlines due Monday March 1, 2021 pdf, pptx.
• Clarification of the project outlines and report (what are we looking for?) pdf, pptx.
• Outline Sample: Market Forcast docx
• Outline Sample: Spectralization pdf
• Outline Sample: ImageSeg pdf
• Final Presentation Sample pdf
• Final Report Sample: Market Forcast pdf
• Report Sample: Sprectralization pdf
• Report Sample: ImageSeg pdf
• Two award winning teams of the Best Presentation Winter 2019 Award.jpg.