Programming, Numerics and Optimization

Programming, Numerics and Optimization

Spring 2021    (course flyer [pdf])

Course schedule

Tuesday 9:30 a.m., Room S-4 (4th floor), currently online, IPPT PAN
  1. (A-1) Preliminaries, programming basics I (Mar., 2nd)
  2. (A-2) Programming basics II (Mar., 9th)
  3. (A-3) Programming basics III (Mar., 16th)
  4. (B-1) Basics of numerical computations (Mar., 23rd)
  5. (B-2) Numerical integration of ODEs (Mar., 30th)
  6. (A-4) Object-oriented programming (Apr., 6th)
  7. (B-3) Linear systems I (Apr., 13th)
  8. (B-4) Linear systems II (Apr., 20th)
  9. (C-1) Basics of optimization (Apr., 27th)
  10. (C-2) Unconstrained optimization I (May, 4th)
  11. (C-3) Unconstrained optimization I (May, 11th)
  12. (C-4) Constrained optimization (May, 18th)
  13. (C-6) Structural reanalysis in statics (Jun., 1st)
  14. (C-5) Heuristic methods (Jun., 8th)
  15. (B-5) Linear integral equations (Jun., 15th)

Grading and homeworks

Grading [pdf]
Please feel free to contact me, if you have any questions.
  1. HW1 [pdf]: First steps
  2. HW2 [pdf]: Loops and functions
  3. HW3 [pdf]: Arrays and pointers
  4. HW4 [pdf]: Basics of numerics
  5. HW5 [zip], readme [pdf]: Numerical integration of ODEs
  6. HW6 [zip], readme [pdf]: Objects
  7. HW7 [zip], readme [pdf]: LU decomposition
  8. HW8 [pdf]: Regularization and iterative linear solvers
  9. HW9 [pdf]: Linear programming
  10. HW10 [pdf]: Optimization

Lecture notes

A) Programming

  1. Basics I [pdf]
    1. Course preliminaries
    2. Programming paradigms
    3. C/C++ basics
  2. Basics II [pdf]
    1. Types and variables
    2. (Few important) operators
    3. Control flow statements
    4. Functions
  3. Basics III [pdf]
    1. Pointers
    2. Arrays
    3. Data structures
    4. Command line arguments
  4. Object-oriented programming [pdf]
    1. The idea
    2. Objects and classes
    3. Creating and destroying objects
    4. Overloaded operators
    5. STL vector class

B) Numerics

  1. Basics of numerical computations [pdf]
    1. Number representations
    2. Arithmetic errors
    3. Problems and algorithms
    4. Conditioning
    5. Algorithm stability
  2. Numerical integration of ordinary differential equations [pdf]
    1. Explicit one-step methods (Euler, Runge-Kutta, convergence, order and stability of RK, Richardson extrapolation, adaptive stepsize control)
    2. Implicit one-step methods (modified midpoint, predictor-corrector, Adams-Bashforth-Moulton)
    3. Multistep methods
    4. Methods for 2nd order equations
  3. Linear systems I: Direct and iterative methods [pdf]
    1. Basics (basic notions, types of problems, methods of solution)
    2. Existence and uniqueness of solution
    3. Direct methods (special matrices, factorizations and decompositions, Gaussian elimination)
    4. Iterative methods (stationary methods, Krylov subspace methods)
  4. Linear systems II [pdf]
    1. Least-squares problems (normal equations, Gauss-Markov theorem, SVD-based and iterative methods)
    2. Conditioning (vector and matrix norms, conditioning and estimation of accuracy, deconvolution as a common source of ill-conditioning)
    3. Regularization (for direct methods, for iterative methods, regularization parameter)
    4. Large Toeplitz systems
    additional files (.avi)
  5. Linear integral equations [pdf]
    1. Classification
    2. Integral operators
    3. Integral equations of the first kind
    4. Integral equations of the second kind
    5. Selected solution methods

C) Optimization

  1. Basics of optimization (in structural engineering), sensitivity analysis [pdf]
    1. Optimization problems
    2. Objective function, variables, constraints
    3. Sensitivity analysis (Finite Difference Approximations, Direct Differentiation Method, Adjoint Method, Automatic Differentiation)
  2. Unconstrained optimization I [pdf]
    1. Basics (stop conditions, rate/order of convergence)
    2. Line search vs. trust region methods
    3. Line search - search directions (steepest descent, conjugate direction, Newton direction)
    4. Line search - step size (Wolfe, strong Wolfe, Goldstein and Price conditions, Zoutendijk condition)
    5. Univariate optimization
  3. Unconstrained optimization II [pdf]
    1. Zero order methods (coordinate descent, Powell's direction set, Rosenbrock method)
    2. Steepest descent (simplified version: number of iterations and attraction basins of the minima)
    3. Conjugate gradient methods (conjugate directions, linear and nonlinear conjugate gradient)
    4. Newton methods (inexact and modified Newton methods)
    5. Quasi-Newton methods (Hessian approximations, DFP and BFGS, Broyden class and SR1)
    6. Least-squares problems (Gauss-Newton and Levenberg-Marquardt methods)
    additional files (.avi)
    • No of iterations in dependence on step length: BW (12.6 MB), CMYK (13.6 MB)
    • No of iterations, zoom: BW (19 MB), CMYK (18.6 MB)
    • Attraction basins of minima: blue-yellow (8.6 MB)
  4. Constrained optimization [pdf]
    1. Basics
    2. Handling constraints (Lagrangian and KKT conditions, penalty function)
    3. Types of problems
    4. Linear programming (simplex method, interior point methods)
  5. Heuristic methods [pdf]
    1. Coupled local minimizers
    2. Nelder-Mead method
    3. Simulated annealing
    4. Evolutionary (genetic) algorithms
    5. Swarm intelligence (particle swarm, ant colony)
    6. Artificial neural networks
  6. Structural reanalysis in statics [pdf]
    1. Basics (sensitivity analysis vs. reanalysis, reanalysis and SHM, formulation)
    2. Combined approximations (CA)
    3. Virtual distortion method (VDM)
    4. VDM - sensitivity analysis