Computational Mathematics for Learning and Data Analysis - AA 2024/25

Section outline

• Select section General Information

  General Information

  Collapse all Expand all

  Schedule

  Held in the first semester, September to December 2024. 72-hour, 9-CFU course.

  • Wed 16:00 - 18:00, Room Fib C1;
  • Thu 11:00 - 13:00, Room Fib C;
  • Fri 11:00 - 13:00, Room Fib M1.

  Organisation

  The course contains two modules:

  • Optimization, taught by Antonio Frangioni: office hours Tuesday 9:00 - 11:00 also on this Team (code yh6612v)

  • Numerical Linear Algebra, taught by Federico Poloni: office hours by appointment

  However, the course is one and the same: one project, one exam, and both lecturers must always be contacted at the same time for any communication.

  Online resources

  • MS Team for online lectures and communication (access with code "0yqe9wv")
  • Lectures log

  Aims of the course

  The course aims at providing the mathematical foundations for some of the main computational approaches to Learning, Data Analysis and Artificial Intelligence. These comprise  techniques and methods for the numerical solution of systems of linear and nonlinear equations and related problems (e.g., computation of eigenvalues), as well as methods for the solution of constrained and unconstrained optimization problems. This requires the understanding of the connections between techniques of numerical analysis and optimization algorithms. The course focuses on presenting the main algorithmic approaches and the underlying mathematical concepts, with attention to the implementation aspects. Hence, use of typical mathematical environments (e.g., Matlab and Octave) and available solvers/libraries is discussed throughout the course.

  Programme

  •  Linear algebra and calculus background
  •  Unconstrained optimization and systems of equations
  •  Direct and iterative methods for linear systems and least-squares
  •  Numerical methods for unconstrained optimization
  •  Iterative methods for computing eigenvalues
  •  Constrained optimization and systems of equations
  •  Duality (Lagrangian, linear, quadratic, conic, Fenchel's, ...)
  •  Numerical methods for constrained optimization
  •  Software tools for numerical computations (Matlab, Octave, ...)
  •  Sparse hints to AI/ML applications

  Bibliography

  • Slides and software by the lecturers available to students on this page
  • Lecture notes for the optimization part are being prepared, the current partial form is distributed below

  Useful books (referenced within the slides):

  • L. N. Trefethen, D. Bau, Numerical Linear Algebra, SIAM, 1997
  • J. Demmel, Applied Numerical Linear Algebra, SIAM, 1996
  • L. Eldén, Matrix Methods in Data Mining and Pattern Recognition, 2007 (freely accessible from the Unipisa network)
  • S. Boyd, L. Vandenberghe, Convex optimization, Cambridge University Press, 2008
  • M.J. Kochenderfer, T.A. Wheeler Algorithms for Optimization, MIT Press, 2019 
  • M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear programming: theory and algorithms, Wiley & Sons, 2006
  • D.G. Luenberger, Y. Ye, Linear and Nonlinear Programming, Springer International Series in Operations Research & Management Science, 2008
  • J. Nocedal, S. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2006
  • H.C. Pinkham. Analysis, Convexity, and Optimization, Draft of September 4, 2014 (available below, downloaded from here)
  • Appunti di Ricerca Operativa (in Italian)

  Other material (pointers to web resources) is suggested in the slides.

   

  Exam

  The course requires a project, typically made in groups of two students, followed by an oral exam. Please check the "Projects" section for detailed information about the projects.

  Students are advised to submit the project incrementally to the lecturers, so that early problems can be spotted and weed out before a significant amount of work is wasted. There is no timeline for the projects: (partial) submissions can happen at any time. Once the project is completed and accepted, the date for the oral exam is freely chosen (with everyone's agreement). Please disregard any "appelli" you see in esami.unipi.it; they need be set (we have asked this to be avoided, but so far with no luck), but they are meaningless. All the students of a group are expected to take the oral exam in the same moment, although well-motivated exceptions are possible.

  • Select activity Annunci

    

    Annunci Forum
  • Select activity Analysis, Convexity, and Optimization (Pinkham, 2014)

    

    Analysis, Convexity, and Optimization (Pinkham, 2014) File
• Select section Slides: Numerical Linear Algebra

  Slides: Numerical Linear Algebra

  • Select activity 0-information

    

    0-information File
  • Select activity 1-linalg

    

    1-linalg File
  • Select activity 2-orthogonality

    

    2-orthogonality File
  • Select activity 3-intro-leastsquares

    

    3-intro-leastsquares File
  • Select activity 4-leastsquares-normal

    

    4-leastsquares-normal File
  • Select activity 5-CG

    

    5-CG File
  • Select activity 6 - SVD

    

    6 - SVD File
  • Select activity 7-matrixnorm

    

    7-matrixnorm File
  • Select activity 8-lab-SVD

    

    8-lab-SVD File
  • Select activity 9-QR

    

    9-QR File
  • Select activity 10-leastsquares-QR

    

    10-leastsquares-QR File
  • Select activity 11-leastsquares-SVD

    

    11-leastsquares-SVD File
  • Select activity 12-conditioning

    

    12-conditioning File
  • Select activity 13-conditioning-least-squares

    

    13-conditioning-least-squares File
  • Select activity 14-stability

    

    14-stability File
  • Select activity 15-stability-and-residual

    

    15-stability-and-residual File
  • Select activity 16-stability-least-squares

    

    16-stability-least-squares File
  • Select activity 17-arnoldi

    

    17-arnoldi File
  • Select activity 18-GMRES

    

    18-GMRES File
  • Select activity 19-lu

    

    19-lu File
  • Select activity 20-chol

    

    20-chol File
  • Select activity 21-largescale-examples

    

    21-largescale-examples File
• Select section Slides: Optimization

  Slides: Optimization

  • Select activity 0- Introduction to the course, motivation, mindset

    

    0- Introduction to the course, motivation, mindset File
  • Select activity 1 - Simple optimization problems

    

    1 - Simple optimization problems File
  • Select activity 2 - Univariate Optimization

    

    2 - Univariate Optimization File
  • Select activity 3 - Unconstraned Multivariate Optimality and Convexity

    

    3 - Unconstraned Multivariate Optimality and Convexity File
  • Select activity 4 - Smoot Unconstrained Optimization

    

    4 - Smoot Unconstrained Optimization File
  • Select activity 5 - Nonsmooth Unconstrained Optimization

    

    5 - Nonsmooth Unconstrained Optimization File
  • Select activity 6 - Constrained Optimality and Duality

    

    6 - Constrained Optimality and Duality File
  • Select activity 7 - Constrained Optimization

    

    7 - Constrained Optimization File
• Select section Optimization & Learning Lecture Notes

  Optimization & Learning Lecture Notes

  These lecture notes are still partial and under active preparation. Reload often. Reports of errors, typos, omissions and suggestions for improvement are highly welcome.

  Part I: A Gentle Introduction

  1 Simple Optimization Problems

  1.2 (Outrageously) Simple (Univariate) Optimization
  1.3 (Not always) Simple Multivariate Optimization 
  1.4 Multivariate Quadratic optimization: Gradient Method .
  1.5 The Conjugate Gradient Method 
  1.6 Multivariate Quadratic optimization: a Direct Method
  1.7 Ex-post motivation: Polynomial Interpolation
  1.8 Wrapup
  1.9 Solutions

  Part II: Unconstrained Optimization

  2 Univariate Optimization

  2.1 General Univariate Optimization Problems
  2.2 Lipschitz (Global) Optimization
  2.3 Local optimization 
  2.4 First local optimization algorithms 
  2.5 Towards faster local optimization algorithms 
  2.6 Dichotomic Search 
  2.7 Newton's method
  2.8 A Fleeting Glimpse to Global Optimization 
  2.9 Wrapup
  2.10 Solutions 

  3 Unconstrained Multivariate Optimality and Convexity

  3.1 Unconstrained Multivariate Optimization
  3.2 Gradients, Jacobians,and Hessians
  3.3 Optimality conditions
  3.4 A Quick Look to Convex Functions
  3.5 Ex-postMotivation: (Artificial, Deep) Neural Networks 
  3.6 Solutions

  4 Smooth Unconstrained Optimization

  5 Nonsmooth Unconstrained Optimization

  Part III: Constrained Optimization

  6 Constrained Optimality and Duality

  7 Constrained Optimization

  Part IV: Combinatorial Optimization

  8 A Fleeting Glimpse to Combinatorial Optimization

  Part V: Supplementary Material

  References

  A Miscellaneous Mathematical Background

  A.1 Infima, suprema and R
  A.2 Vector space, scalar product
  A.3 Matrices, transpose, symmetry, products
  A.4 Eigenvalues and the determinant, in practice 
  A.5 Limits and optimization 
  A.6 Continuity
  A.7 (Univariate) Derivatives 
  A.8 Topology and limit in Rⁿ 
  A.9 Gradients, Jacobians and Hessians
  A.10 Topology and feasibility

  • Select activity Optimization & Learnng Lecture Notes

    

    Optimization & Learnng Lecture Notes File
• Select section Lecture Recordings: Numerical Linear Algebra

  Lecture Recordings: Numerical Linear Algebra

  • Select activity 2024-09-19: Recap of linear algebra: linear combinations, matrix products, coordinates

    

    2024-09-19: Recap of linear algebra: linear combinations, matrix products, coordinates File
  • Select activity l1

    

    l1 File
  • Select activity 2024-09-20: Orthogonality, eigenvectors, positive definiteness and semidefiniteness

    

    2024-09-20: Orthogonality, eigenvectors, positive definiteness and semidefiniteness File
  • Select activity l2

    

    l2 File
  • Select activity 2024-09-27: introduction to least squares problems. Some applications: linear estimation, polynomial fitting. Uniqueness of solution. Method of normal equations. Pseudoinverse.

    

    2024-09-27: introduction to least squares problems. Some applications: linear estimation, polynomial fitting. Uniqueness of solution. Method of normal equations. Pseudoinverse. File
  • Select activity l3

    

    l3 File
  • Select activity 2024-10-02: Singular value decomposition. Matrix norms. Eckhart-Young theorem (statement)

    

    2024-10-02: Singular value decomposition. Matrix norms. Eckhart-Young theorem (statement) File
  • Select activity l4

    

    l4 File
  • Select activity 2024-10-04: sparse matrices. Conjugate gradient: introduction, subspace optimality properties. Krylov subspaces and their relation to gradient-type methods.

    

    2024-10-04: sparse matrices. Conjugate gradient: introduction, subspace optimality properties. Krylov subspaces and their relation to gradient-type methods. File
  • Select activity l5

    

    l5 File
  • Select activity 2024-10-16: Q-norm; orthogonality and convergence properties of CG (convergence in terms of polynomial approximation, worst-case bound, both without proof)

    

    2024-10-16: Q-norm; orthogonality and convergence properties of CG (convergence in terms of polynomial approximation, worst-case bound, both without proof) File
  • Select activity l6

    

    l6 File
  • Select activity 2024-10-18: convergence of CG and polynomial approximation. Data analysis with the SVD: images, student scores, text (latent semantic analysis)

    

    2024-10-18: convergence of CG and polynomial approximation. Data analysis with the SVD: images, student scores, text (latent semantic analysis) File
  • Select activity l7

    

    l7 File
  • Select activity 2024-10-25: dimensionality reduction with PCA; PCA of the Yale faces dataset, used also for image recognition

    

    2024-10-25: dimensionality reduction with PCA; PCA of the Yale faces dataset, used also for image recognition File
  • Select activity l8

    

    l8 File
  • Select activity 2024-10-30: Householder reflectors. QR factorization. Different ways to handle Q: thin QR, returning the Householder vectors.

    

    2024-10-30: Householder reflectors. QR factorization. Different ways to handle Q: thin QR, returning the Householder vectors. File
  • Select activity l9

    

    l9 File
  • Select activity 2024-11-08: solving least-squares problems with the QR factorization and with the SVD. Singular least squares problems. The effect of noise; regularization via truncated SVD.

    

    2024-11-08: solving least-squares problems with the QR factorization and with the SVD. Singular least squares problems. The effect of noise; regularization via truncated SVD. File
  • Select activity l10

    

    l10 File
  • Select activity 2024-11-13: Tikhonov regularization. Condition number. The condition number of solving linear equations and least-squares problems.

    

    2024-11-13: Tikhonov regularization. Condition number. The condition number of solving linear equations and least-squares problems. File
  • Select activity l11

    

    l11 File
  • Select activity 2024-11-15: stability of floating point computations. Backward stability, with an example. A posteriori stability tests for linear systems and LS problems.

    

    2024-11-15: stability of floating point computations. Backward stability, with an example. A posteriori stability tests for linear systems and LS problems. File
  • Select activity l12

    

    l12 File
  • Select activity 2024-11-22: backward stability of QR factorization. Backward stability properties of algorithms to solve LS problems and their comparison. Introduction to the Arnoldi algorithm.

    

    2024-11-22: backward stability of QR factorization. Backward stability properties of algorithms to solve LS problems and their comparison. Introduction to the Arnoldi algorithm. File
  • Select activity l13

    

    l13 File
  • Select activity 2024-11-27: Arnoldi algorithm, GMRES. Convergence, computational and implementation remarks. The symmetric version: MINRES.

    

    2024-11-27: Arnoldi algorithm, GMRES. Convergence, computational and implementation remarks. The symmetric version: MINRES. File
  • Select activity l14

    

    l14 File
  • Select activity 2024-12-06: overview of direct methods for linear systems: LU, LDL, Cholesky, remarks about sparsity

    

    2024-12-06: overview of direct methods for linear systems: LU, LDL, Cholesky, remarks about sparsity File
  • Select activity l15

    

    l15 File
  • Select activity 2024-12-16: examples of solutions of large-scale linear systems. Reordering in direct methods. A quick introduction to preconditioners for iterative methods.

    

    2024-12-16: examples of solutions of large-scale linear systems. Reordering in direct methods. A quick introduction to preconditioners for iterative methods. File
  • Select activity l16

    

    l16 File
• Select section Lectures Recordings: Optimization

  Lectures Recordings: Optimization

  • Select activity Lecture 1.1 - introduction to the course

    

    Lecture 1.1 - introduction to the course File
  • Select activity Lecture 1.2 - motivation for the course: four examples

    

    Lecture 1.2 - motivation for the course: four examples File
  • Select activity Lecture 2.1: general notions of optimization

    

    Lecture 2.1: general notions of optimization File
  • Select activity Lecture 2.2: starting very very easy and very slowly ramping up

    

    Lecture 2.2: starting very very easy and very slowly ramping up File
  • Select activity Lecture 3.1: multivariate optimization: initial concepts, easy functions

    

    Lecture 3.1: multivariate optimization: initial concepts, easy functions File
  • Select activity Lecture 3.2: "real" quadratic functions and how they work

    

    Lecture 3.2: "real" quadratic functions and how they work File
  • Select activity Lecture 4.1: quadratic optimization: from optimality conditions to the gradient method

    

    Lecture 4.1: quadratic optimization: from optimality conditions to the gradient method File
  • Select activity Lecture 4.2: the gradient method for quadratic functions, practice

    

    Lecture 4.2: the gradient method for quadratic functions, practice File
  • Select activity Lecture 5.1: convergence rates: from the gradient method to the world

    

    Lecture 5.1: convergence rates: from the gradient method to the world File
  • Select activity Lecture 5.2: sublinear convergence and where this leads us

    

    Lecture 5.2: sublinear convergence and where this leads us File
  • Select activity Lecture 6.1: optimizing more general functions, but univariate ones

    

    Lecture 6.1: optimizing more general functions, but univariate ones File
  • Select activity Lecture 6.2: first steps with local optimization: the role of derivatives

    

    Lecture 6.2: first steps with local optimization: the role of derivatives File
  • Select activity Lecture 7.1: dichotomic search, from naive to model-based

    

    Lecture 7.1: dichotomic search, from naive to model-based File
  • Select activity Lecture 7.2: faster local optimization and the role of models

    

    Lecture 7.2: faster local optimization and the role of models File
  • Select activity Lecture 8.1: closing thoughts of univariate optimization, a fleeting glimpse to the global case

    

    Lecture 8.1: closing thoughts of univariate optimization, a fleeting glimpse to the global case File
  • Select activity Lecture 8.2: theory of gradients and Hessians towards optimality conditions

    

    Lecture 8.2: theory of gradients and Hessians towards optimality conditions File
  • Select activity Lecture 9.1: local first- and second-order optimality conditions (necessary and sufficient), convexity in \R^n

    

    Lecture 9.1: local first- and second-order optimality conditions (necessary and sufficient), convexity in \R^n File
  • Select activity Lecture 10.1: the gradient method with "exact" line search

    

    Lecture 10.1: the gradient method with "exact" line search File
  • Select activity Lecture 10.2: inexact line search, the Armijo-Wolfe conditions

    

    Lecture 10.2: inexact line search, the Armijo-Wolfe conditions File
  • Select activity Lecture 11.1: convergence with the A-W LS, theory

    

    Lecture 11.1: convergence with the A-W LS, theory File
  • Select activity Lecture 11.2: the A-W LS in practice

    

    Lecture 11.2: the A-W LS in practice File
  • Select activity Lecture 12.1: "extremely inexact LS": fixed stepsize

    

    Lecture 12.1: "extremely inexact LS": fixed stepsize File
  • Select activity Lecture 12.2: gradient twisting approaches at their best: Newton's method

    

    Lecture 12.2: gradient twisting approaches at their best: Newton's method File
  • Select activity Lecture 13.1: all around Newton's method

    

    Lecture 13.1: all around Newton's method File
  • Select activity Lecture 13.2: towards the very-large-scale, quasi-Newton methods

    

    Lecture 13.2: towards the very-large-scale, quasi-Newton methods File
  • Select activity Lecture 14.1: deflected gradient methods I - Conjugate Gradient

    

    Lecture 14.1: deflected gradient methods I - Conjugate Gradient File
  • Select activity Lecture 14.2: deflected gradient methods II - Heavy Ball

    

    Lecture 14.2: deflected gradient methods II - Heavy Ball File
  • Select activity Lecture 15.1: the scary world of nondifferentiable optimization

    

    Lecture 15.1: the scary world of nondifferentiable optimization File
  • Select activity Lecture 15.2: (convex) nondifferentiable optimization, converging against all odds

    

    Lecture 15.2: (convex) nondifferentiable optimization, converging against all odds File
  • Select activity Lecture 16.1: better nondifferentiable approachess, as far as they can go

    

    Lecture 16.1: better nondifferentiable approachess, as far as they can go File
  • Select activity Lecture 16.2: first steps on constrained optimization

    

    Lecture 16.2: first steps on constrained optimization File
  • Select activity Lecture 17.1: algebraic representation of feasible sets, i.e., constraints

    

    Lecture 17.1: algebraic representation of feasible sets, i.e., constraints File
  • Select activity Lecture 17.2: from the KKT conditions to duality

    

    Lecture 17.2: from the KKT conditions to duality File
  • Select activity Lecture 18.1: first step in constrained optimization

    

    Lecture 18.1: first step in constrained optimization File
  • Select activity Lecture 18.2: more (projected gradient) steps in constrained optimization

    

    Lecture 18.2: more (projected gradient) steps in constrained optimization File
  • Select activity Lecture 19.1: from Frank-Wolfe to the dual method

    

    Lecture 19.1: from Frank-Wolfe to the dual method File
  • Select activity Lecture 19.2: ending with a bang: the (primal-dual) interior-point method

    

    Lecture 19.2: ending with a bang: the (primal-dual) interior-point method File
• Select section Software and Data: Numerical Analysis

  Software and Data: Numerical Analysis

  • Select activity NBA salaries dataset

    

    NBA salaries dataset File
  • Select activity Yale "eigenfaces" dataset + supporting scripts

    

    Yale "eigenfaces" dataset + supporting scripts File
• Select section Software and Data: Optimization

  Software and Data: Optimization

  • Select activity A small utlity to generate "interesting" quadratic functions

    

    A small utlity to generate "interesting" quadratic functions File
  • Select activity A small utility to plot a quadratic function

    

    A small utility to plot a quadratic function File
  • Select activity A small utlity to compute the optimal value of a quadratic function

    

    A small utlity to compute the optimal value of a quadratic function File
  • Select activity The Gradient Method for Quadratic Functions

    

    The Gradient Method for Quadratic Functions File
  • Select activity Some one-dimensional test functions

    

    Some one-dimensional test functions File
  • Select activity The Dichotomic Search Method for univariate optimization

    

    The Dichotomic Search Method for univariate optimization File
  • Select activity Newton's Method for univariate optimization

    

    Newton's Method for univariate optimization File
  • Select activity Some multivariate test functions

    

    Some multivariate test functions File
  • Select activity The Steepest Descent (Gradient) method for general nonlinear functions

    

    The Steepest Descent (Gradient) method for general nonlinear functions File
  • Select activity Newton's Method

    

    Newton's Method File
  • Select activity The BFGS quasi-Newton Method

    

    The BFGS quasi-Newton Method File
  • Select activity The Nonlinear Conjugate Gradient Method(s)

    

    The Nonlinear Conjugate Gradient Method(s) File
  • Select activity The Heavy Ball Method

    

    The Heavy Ball Method File
  • Select activity The Subgradient Method

    

    The Subgradient Method File
  • Select activity The Proximal Bundle method

    

    The Proximal Bundle method File
  • Select activity A small utility to create box-constrained quadratic programs

    

    A small utility to create box-constrained quadratic programs File
  • Select activity An off-the-shelf solver for box-constrained quadratic programs

    

    An off-the-shelf solver for box-constrained quadratic programs File
  • Select activity The Active-Set Method for box-constrained quadratic programs

    

    The Active-Set Method for box-constrained quadratic programs File
  • Select activity The Projected Gradient Method for box-constrained quadratic programs

    

    The Projected Gradient Method for box-constrained quadratic programs File
  • Select activity Frank-Wolfe's Method for box-constrained quadratic programs

    

    Frank-Wolfe's Method for box-constrained quadratic programs File
  • Select activity The Dual Method for box-constrained quadratic programs

    

    The Dual Method for box-constrained quadratic programs File
  • Select activity The Primal-Dual Interior-Point Method for box-constrained quadratic programs

    

    The Primal-Dual Interior-Point Method for box-constrained quadratic programs File
• Select section Projects

  Projects

  Please read carefully the guidelines for the projects in the file below.

  A list of possible proposals for didactic projects will be provided in due time (but remember that wildcard projects are always possible and welcome).

  Timeline

  Forming groups for the first assignment:November 1, 2024

  Subdividing available projects among the groups (first assignment): November 15, 2024

   

  After the first assignment has been completed, further groups can be formed at any time, and they can choose projects among those that are still available or propose wildcard projects.

  • Select activity Information about didactic projects

    

    Information about didactic projects File
  • Select activity Project tracks

    

    Project tracks File