CSE 291E, Spring 2024 Topics on Numerical Methods for Engineering

University of California, San Diego

Instructor

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

Teaching Assistant

• Tatsuki Koga, tkoga@ucsd.edu
• Office hours: TBA

Discussion Forum

• TBA

Schedule

• Lectures: 12:30-1:50PM TTH, Room: CSE2154

References

• Nonlinear Programming, Third Edition, D.P. Bertsekas, Athena Scientific, 2016.
• Numerical Optimization, J. Nocedal and S.J. Wright, Second Edition, Springer, 2006.
• An Introduction to Optimization on Smooth Manifolds, N. Boumal, Cambridge, 2023.
• Electronic Circuit and System Simulation Methods, T.L. Pillage, R.A. Rohrer, C. Visweswariah, McGraw-Hill, 1998
• Convex Optimization Algorithms, D.P. Bertsekas, Athena Scientific, 2015.
• Matrix Mathematics, A Scond Course in Linear Algebra, Second Edition, S.R. Garcia, and R. A. Horn, Cambridge, 2023.
• Matrix Computations, G.H. Golub and C.F. Van Loan, Fouth Edition, Johns Hopkins, 2013
• 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.
• Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge, 2004

Prerequisite

Basic knowledge of linear algebra, numerical methods, convex optimization, or intention of conducting projects related to scientific computation.

Content

The class covers topics on numerical methods for engineering. Students are encouraged to carry out the state of the art projects with team members. We intend to cover two parts according to the progress of the class. For part I, we talk about the dynamic system to model the system in high dimensional space with temporal behavior. The techniques of matrix solvers, integration methods, and sensitivity will be discussed. For part II, we study the optimization methods of convex problems. The algorithms of gradient/subgradient descent, approximation, and proximal approaches will be reviewed.

Lecture Notes, Part I: Dynamic Systems

• 1. Introduction pptx.
• 1.1. Motivation ppt.
• 2. Formulation ppt.
• 3. Matrix Solvers:
• (1) Sparse direct method by Xiaoye Sherry Li, ppt
• (2) Steepest descent methods ppt,
• Conjugate gradient tutorial by CK Cheng pdf,
• Nesterov Method: Differential Equation by Su, Boyd and Candes. pdf,
• Nesterov Method: Gradient and Mirror descent by Zhu and Orecchia pdf,
• Graident descent survey by S. Ruder: https://arxiv.org/pdf/1609.04747.pdf
• (3) Krylov subspace methods and multigrid methods ppt.
• 4. Integration:
• (1) One step methods pptx,
• (2) Multistep methods pptx.
• 5. Sensitivity: pptx,
• 6. Koopman Operator: pdf file, Notes on Koopman Operator Theory, S.L. Brunton, Universitat von Washington, 2019.

Lecture Notes, Part II: Nonlinear Programming (lecture notes by D.P. Bertsekas, Term of Use: http://ocw.mit.edu/terms.)

Slides pdf

Lecture Notes, Part III: Convex Optimization Methods (lecture notes by D.P. Bertsekas, Term of Use: http://ocw.mit.edu/terms.)

• 1. Introduction pdf
• 2. Overall view pdf
• 3. Subgradient methods
• I pdf
• II pdf
• 4. Approximation methods pdf
• 5. Proximal methods
• I. pdf
• II pdf
• ADMM by R. Tibshirani pdf
• III pdf
• 6. Advanced Approaches
• Extension of gradient projection methods I pdf
• Extension of gradient projection methods II pdf
• Extension of incremental methods pdf
• Extension of proximal methods pdf
• Distributed asynchronous methods pdf

Integer Programming

• Integer Programming by Larrosa, Oliveras, and Rodriguez-Carbonell, pdf
• Integer Programming by Kolter and Shah, pdf
• Integer Programming by Cornuejols, Trick and Saltzman, pdf

Standard Cell Design using SAT Packages

• Standard Cell Library Analsys and Synthesis, CK Cheng talk, pdf
• The Scope and Challenges of Scaling in Advanced Technologies, CK Cheng talk, 2023, pdf

Papers

• Nesterov's Fast Gradient Method
  • Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights, W. Su et al. Journal of Machine Learning Researech, 2016, pdf file.
  • Understanding the Accelerated Phenomenon via High-Resolution Differential Equations, B. Shi, et al., Mathematical Programming, 2022, pdf file.
  • Fast Iterative Shrinkage-Thresholding Algorithm for Lineare Inverse Problems, A. Beck, and M. Teboulle, SIAM J. Imageing Sciences, 2009, pdf file,
• Koopman Operator
• Notes on Koopman Operator Theory, S.L. Brunton, pdf file,
• Modern Koopman Theory for Dynamical Systems, S.L. Brunton, et al., Learnining for Robust Dynamic Decomposition: Linear and Nonlinear Disambiguatoin Optimization, P.J. Baddoo, et al., Proceedings Royal Society, 2021. pdf file,
• Kernel Learnining for Robust Dynamic Decomposition: Linear and Nonlinear Disambiguatoin Optimization, P.J. Baddoo, et al., Proceedings Royal Society, 2021. pdf file,
• Matrix Calculus (Sensitivity)
• Matrix Calculus, Lecture Note of A. Edelman and S.G. Johnson scribed by P. Bright, MIT, 2023, pdf file,
• Adjoint Network in Time, Circuit Theory of Time Domain Adjoint Sensitivity, J. Li, D. Ahsanullah, Z. Gao, R. Rohrer, IEEE Trans. on Computer-Aided Design, 2023, pdf file,
• Quasi-Newton Methods
• Two classes of multisecant methods for nonlinear acceleration, Numerical Linear Algebra with Applications, H. Fang and Y. Saad, 2009, 16:197-221, pdf file,
• Quasi-Newton optimization origin of the BFGS update, lecture note of S.G. Johnson updated 5/3/2021. pdf file,
• BFGS in a nutshell: an introduction to quasi-Neweton methods, A. Lam, Towards Data Science, 12/25/2020. pdf file,
• Optimization on Stiefel Manifolds
• Sequential subspace methods on Stiefel manifold optimization problems, P. Chen, C.K. Cheng, and C. Holtz, arXiv, 4/2024. pdf file,
• Optimization algorithms exploiting unitary constraints, J.H. Manton, IEEE Trans. on Signal Processing, 3/2002. pdf file,
• Notes on optimization on Stiefel manifolds, H.D. Tagare, 1/24/2011. pdf file,
• Random Algorithms
• On Variants of the Johnson-Lindenstrauss Lemma, J. Matousek, Wiley InterScience, 2008, pdf file,
• Why Are Big Data Matrices Approximately Low Rank?, M. Udell and A. Townsend, SIAM J. Math. Data Sci. 2019, pdf file,
• Fast and Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems, Y. Nakatsukasa and J.A. Tropp, arxiv.org, 2021, pdf file,
• A Fast Randomized Algorithm for the Approximation of Matrices, F. Woolfe, E. Liberty, V. Rokhlin, M. Tygert, Appl. Comput. Harmon, Anal, 2008, pdf file,
• Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, J.A> Tropp, and R.J. Webber, arxiv.org, 2023 pdf file,
• Baysian Learning via Stochastic Gradient Langevin Dynamics, M. Welling and Y.W. Teh, Int. Conf. on Machine Learning, 2011. pdf file,
• Physical Layout
• Initial Analytical Placement by P. Chen, CK Cheng, A. Chern, C. Holtz, A. Li, and Y. Wang, ISPD, 2023, pdf file,

Project

• Project Outlines (what are we looking for?) pdf, pptx.