URL study guide
https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2MMD10&collegejaar=2026&taal=enDescription
Unconstrained continuous optimization:
Linear least squares, normal equations, regularization, Tikhonov, nonlinear optimization, Newton, steepest descent, line search, Armijo, nonlinear least squares, Gauss-Newton, Levenberg-Marquardt, inexact Newton, quasi-Newton, BFGS, trust region.
Convexity:
Positive definite matrices and functions. Convex sets, convex functions. Applications of convexity. Useful inequalities
The role of convexity:
Unconstrained optimization; lagrangian approach, Karush Kuhn Tucker conditions for constrained optimization. Lagrangian duality; lagrangian duality for convex programs; duality theorems examples (including discrete ones). Solving convex programs by the barrier method.
Intractability:
Recall: problems, instances and size, algorithms and running time. NP and co-NP certificates.
P vs NP; reductions; NP-hardness; central examples of NP-hard optimization problems.
Approximation:
Basic constant factor approximation algorithms; Integrality gap; basic Approximation schemes
Objectives
- Knowledge and understanding of some iterative methods in unconstrained continuous optimization and some ability to apply them in a practical setting.
- Ability to construct and recognize convex sets and convex functions
- Understanding of the definition of linear-, quadratic and positive semidefinite optimization; ability to recognize a positive semidefinite matrix;
- Ability to construct the Lagrange dual of a constrained optimization problem.
- Knowing the concept of a mixed integer program (MIP) and some understanding of why large MIPs may be difficult (timeconsuming) to solve in practice. Some ability to model a practical problem as a MIP.
- Understanding the concept of NP-completeness and polynomial reductions, being able to make a reduction from a known NP-complete problem to a given similar problem.
- Understanding the concept of a constant factor approximation algorithm, and being able to construct an simple constant factor approximation algorithm.