Introduction to Optimization Theory

Announcements

★★★ 2026/03/20 ★★★ Your Pi Day artwork has been uploaded to this webpage. Please scroll to the bottom of the page to find your creation :)

★★★ 2026/03/10 ★★★ Homework Assignment 1 has been announced (see below or eCourse2); please submit your work before due date and late submission is not allowed! 

★★★ 2026/02/12 ★★★ This course will be delivered as an EMI (English-medium instruction) course, in line with the government’s bilingual education policy. This offering will focus specifically on Convex Optimization (different from the previous years)! For undergraduates: if you are taking this course with the intention of applying for credit exemption at other top-tier universities, please note that our depth and coverage may not fully match theirs, so credit exemption may not be possible. 

Course Information

Instructor: Jian-Jia Weng

Time: Tuesdays and Thursdays, 10:15-11:30

Location: R103, Innovation Building

Office Hour: Upon Request

Teaching Method: Chalkboard Teaching with Video Recording Supplementary

Textbook: Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2024.

You can download the textbook and other materials here. Prof. Boyd also provides full lecture videos on YouTube (2023 version), which makes self-study feasible. That said, I strongly encourage you to attend class: convex optimization is an advanced subject and requires a solid foundation, and the in-person lectures will help you build the key concepts and avoid common pitfalls.

 Grade Evaluation: 4 Homework Assignments (each 10%) + Midterm Exam (20%) + Final Exam (20%) + Notes&In-Class Participation (20%) 

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 2026] Inquiry - Your name and Student ID number (example: [OPT 2026] 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 (To be updated)

• Week 1 (02/24, 02/26): Section 1

  1. Mathematical Definition of Optimization Problems

  2. Six Applications (Communications, Control System, Patter Recognition, etc) 

• Week 2 (03/03, 03/05): Section 2.1-2.2

  1. Affine and Convex Sets and Cone

  2. Affine, Convex, Conice Combinations

  3. Affine, Convex, and Conic Hulls

  4. Hyperplane and Half Spaces

  5. Norm Balls, Ellipsoids, and Norm Cone

• Week 3 (03/10, 03/12): No classes

• Week 4 (03/17, 03/19): Section 2.3-2.4

  1. Polyhedra (Simplexes)

  2. Positive Semidefinite Cone

  3. Operations Preserving Convexity

  4. Perspective and Linear-Fractional Functions

  5. Proper Cone and Genearlized Inequalities

• Week 5 (03/24, 03/26):

  1. 
     

Selected Homework Problems

You need to submit your answers 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.   

• HW1: 2.2, 2.7, 2.8, 2.10, 2.12, 2.15, 2.17, 2.25, 2.28, 2.29 (Due: 3/30, 9PM)

References

1. E. K. P. Chong, W.-S. Lu, and S. H. Zak, An Introduction to Optimization with Applications to Machine Learning (5ed) 

2. D. G. Luenberger, Optimization by Vector Space Methods. Available here

3. S. Bubeck, Convex Optimization: Algorithms and Complexity. Available: arXiv1405.4980v2

Additional Materials

1. Polytope and Polyhedron [Wiki]; also see this lecture note from Cornell Univ. and this one from Illinois. 

In certain fields of mathematics, the terms "polytope" and "polyhedron" are used in a different sense: a polyhedron is the generic object in any dimension (referred to as polytope in this article) and polytope means a bounded polyhedron. This terminology is typically confined to polytopes and polyhedra that are convex. With this terminology, a convex polyhedron is the intersection of a finite number of halfspaces and is defined by its sides while a convex polytope is the convex hull of a finite number of points and is defined by its vertices.

2. A Reference for Differentiability in Higher Dimension

3. A Reference for Orthogonally Diagonalizable

4. Change-of-Basis [Wiki]

5. Jonathan Richard Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain Edition 1 1/4, 1994.

Numerical Linear Algebra

As we saw in class an equivalence between solving Ax=b and minimizing 1/2 x^TAx - b^Tx, many iterative algorithms developed to solve linear systems can be transformed into procedures to find the minimizers of the quadratic function. The following materials covers fundamental results on how to solve Ax=b numerically, particularly the Krylov subspace methods. Such methods are highly related to the conjugate gradient (CG) methods in Section 10 of our textbook.  

1. Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press, Cambridge, 2003. 

2. R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. Van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, SIAM, Philadelphia, PA, 1994.

3. T. Sogabe, Krylov Subspace Methods for Linear Systems: Principles of Algorithms, Springer, 2022 

4. Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd Edition, SIAM, 2003.

5. W. Hackbusch, Iterative Solution of Large Sparse Systems of Equations, Springer, 2016.

6. Krylov Subspaces and Conjugate Gradients from MIT

7. A Brief Introduction to Krylov Space Methods for Solving Linear Systems from ETHZ

8. Gerand Sleijpen, A Course on Numerical Linear Algebra

9. Marc Bonnet, Lecture Notes in Numerical Linear Algebra

Fun Readings

1. G. Foschini, R. Gitlin and S. Weinstein, "Optimization of two-dimensional signal constellations in the presence of Gaussian noise," IEEE Trans. Commun., vol. 22, no. 1, pp. 28-38, Jan. 1974, doi: 10.1109/TCOM.1974.1092061.

2. M. Beko and R. Dinis, "Designing good multi-dimensional constellations," IEEE Wireless Commun. Lett., vol. 1, no. 3, pp. 221-224, Jun. 2012, doi: 10.1109/WCL.2012.032312.120203

3. J. Feldman, M. J. Wainwright and D. R. Karger, "Using linear programming to Decode Binary linear codes," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 954-972, March 2005, doi: 10.1109/TIT.2004.842696.

4. T. Cui, T. Ho and C. Tellambura, "Linear Programming Detection and Decoding for MIMO Systems," in Proc. IEEE ISIT, Seattle, WA, USA, 2006, pp. 1783-1787, doi: 10.1109/ISIT.2006.261741.

5. T. Wadayama and M. Hagiwara, "LP-Decodable Permutation Codes Based on Linearly Constrained Permutation Matrices," IEEE Trans. on Inf. Theory, vol. 58, no. 8, pp. 5454-5470, Aug. 2012, doi: 10.1109/TIT.2012.2196253.