Introduction to Optimization Theory

Course Information

Instructor: Jian-Jia Weng

Time: Tuesdays and Thursdays, 8:45-10:00

Location: R101, Innovation Building

Office Hour: Upon Request

Teaching Method: Chalkboard Teaching with Video Recording Supplementary

Textbook: E. K. P. Chong, W.-S. Lu, and S. H. Zak, An Introduction to Optimization with Applications to Machine Learning (5ed) https://www.engr.colostate.edu/~echong/book5/

Grade Evaluation: 4 Homeworks (each 10%) + Midterm Exam (25%) + Final Exam (25%) + Notes&In-Class Participation (10%) 

Contact Information

Office: R428, Innovation Building  (please make an appointment before coming)

Campus Internal Phone Number：33528

Email: jjweng AT ccu.edu.tw

If you have any questions regarding the course, you can email me from your school email account with:  

• Subject: [OPT 2024] Inquiry - Your name and Student ID number (example: [OPT 2024] Inquiry - 周杰倫 1234567)

• Contents: (1) topics you want to discuss and (2) your preferred time to meet in person (please specify at least 3 time slots)

for a special accommodation. I should reply to your email within 24hours; if not, please send the email again.

Tentative Schedule

• Week 1 (02/20, 02/22): Section 1

  1. Introduction to Optimization

  2. Basic Logic and Methods of Proof

• Week 2 (02/27, 02/29): Section 2-3

  1. Vector Spaces and Matrices

  2. Inner Product and Norms

  3. Basis and Linear Transformations

  4. Eigenvalues and Eigenvectors

• Week 3 (03/05, 03/07): Section 3-4

  1. Orthogonal Projections

  2. Quadratic Forms

  3. Matrix Norms

  4. Concepts from Geometry (Line Segments, Hyperplanes, and Linear Varieties)

  5. Neighborhoods

  6. Polytopes and Polyhedra

• Week 4 (03/12, 03/14): Section 5

  1. Sequence and Limits

  2. Differentiability

  3. The Derivative Matrix (a.k.a. Jacobian Matrix)

  4. Differentiation Rules

  5. Level Sets and Gradients

• Week 5 (03/19, 03/21): Sections 5-6

  1. Taylor Series

  2. Basics of Set-Constrained and Unconstrained Optimization

  3. Conditions for Local Minimizers (First and Second Order Necessary Conditions)

  4. Introduction to One-dimensional Search Methods

  5. Golden Section Search

• Week 6 (03/26, 03/28): Section 7, 8.1-8.2

  1. Fibonacci Method

  2. Bisection Method

  3. Newton's Method

  4. Secant Method

  5. Bracketing

  6. Gradient Descent Algorithm

  7. Steepest Descent Method

• Week 7 (04/02, 04/04): Sections 9.1, 9.3, 10

  1. Introduction to Newton Method

  2. Levenberg-Marqudrdt Modification

  3. Introduction to Conjugate Direction Methods

  4. Basic Conjugate Diection Algorithm

• Week 8 (04/09, 04/11): Sections 10, 11, Official Midterm Exam Week

  1. Conjugate Gradient Algorithm

  2. Introduction to Quasi-Newton Methods

  3. Approximating the Inverse Hessian

  4. Rank One Correction Formula

  5. DFP and BFGS Algorithms

• Week 9 (04/16, 04/18): Section 15

  1. Introduction to Linear Program

  2. Basic and Feasible Solutions 

  3. Simplex Method

• Week 10 (04/23, 04/25): Section 16

  1. Matrix Form of Simplex Method

  2. Two-Phase Simplex Method

  3. Revised Simplex Method

• Week 11 (04/30, 05/02): Sections 17, 20

  1. Duality for Linear Program

  2. Introduction to Problems with Equality Constraints

• Week 12 (05/07, 05/09): Section 20

  1. Tangent and Normal Spaces

  2. Lagrange Condition

  3. Second Order Conditions

  4. Minimizing Qudratics subject to Linear Constraints

• Week 13 (05/14, 05/16): Section 21

  1. Introduction to Problems with Inequality Constraints

  2. Karush-Kuhn-Tucker (KKT) Condition

  3. Second Order Conditions

• Week 14 (05/21, 05/23): Sections 22.1-22.3 

  1. Introduction to Convex Optimization

  2. Optimality Conditions

• Week 15 (05/28, 05/30): Sections 23.1-23.4

  1. Introduction to Lagrangian Duality

  2. Primal-Dual Pair

  3. General Duality Properties

• Week 16 (06/04, 06/06): Section 23.4-23.5, Official Final Exam Week

  1. Minimax Inequality Chain

  2. Optimality of Saddle Point

  3. Weak Duality and Duality Gap

  4. Strong Duality

  5. Introduction to Algorithms for Constrained Optimization

• Week 17 (06/11, 06/13): Section 24 & Final Exam

  1. Project Gradient Methods with Linear Constraints

  2. Lagrangian Algorithm

  3. Penalty Methods

• Week 18 (01/03): No Class

Selected Homework Problems

You need to submit your answers to homework problems on eCourse2, although they are not marked anyway. You are encouraged to work them together with your friends. Discussion is a good way for learning a new subject.   

• 1.4, 1.7, 1.11 

• 2.3, 2.9, 2.10, 2.11 

• 3.1, 3.3, 3.6, 3.15, 3.18, 3.21 

• 4.1, 4.8, 4.11, 4.12

• 5.4, 5.5, 5.7, 5.11 (read 5.8-5.9 and solve them if you like) 

• 6.1, 6.8, 6.9, 6.11, 6.18, 6.20, 6.29 (read 6.3-6.4, 6.7, 6.33 and solve them if you like)

• 7.4, 7.8, 7.9 

• 8.1, 8.8, 8.12, 8.15, 8.16, 8.18, 8.24 

• 9.1, 9.4, 9.8 

• 10.1, 10.2 10.4, 10.6, 10.10 

• 11.1, 11.3

• 15.1, 15.2, 15.3, 15.4, 15.10 

• 16.2, 16.4, 16.6, 16.18, 16.19 

• 17.1, 17.2, 17.3, 17.7, 17.12, 17.21, 17.24

• 20.1, 20.2, 20.3, 20.17, 20.18 

• 21.1, 21.2, 21.6, 21.10, 21.12, 21.14, 21.21 

• 22.1, 22.2, 22.8, 22.12, 22.18

Reading Assignments

References