Optimization Techniques

The main objective of the course is to introduce its participants to the theory and solution methods for optimization problems in science and technology. The students will be able to: understand various theoretical and computational aspects of a wide range of optimization methods, realize the capabilities offered by various optimization methods, use of optimization toolboxes.

The main objective of the course is to introduce its participants to the theory and solution methods for optimization problems in science and technology. The students will be able to: understand various theoretical and computational aspects of a wide range of optimization methods, realize the capabilities offered by various optimization methods, use of optimization toolboxes.

Lecture contents
Concepts and models of mathematical programming (4h): the concept of a
mathematical model, modeling languages, types of problems of
mathematical programming (optimization); examples of applications in
engineering design, parameter identification, computer graphics;
examples of mathematical model building; continuous and discrete
optimization.

Linear programming (6h): standard form of linear programs, plyhedral
set, vertices; basis matrix, basic solutions; geometry of the simplex
method, simplex tableau, algorithms of the simplex method; two-phase
simplex method; computational algorithms of the simplex method, revised
simplex method, product form algorithms, degeneracy issues; optimality
conditions and duality theory, dual simplex method, sensitivity
analysis; nonsimplex algorithms.

Basic concepts and algorithms for (nonlinear) unconstrained
optimization (4h): optimality conditions of the first and second order
for differentiable unconstrained optimization; quadratic functions and
quadratic local approximation; general algorithmic scheme with line
search, convergence issues, review of linesearch methods; steepest
descent; conjugate directions, quasi-Newton methods; direct
(nongradient) search methods.

Theory of constrained optimization (4h): active constraints, feasible
directions, polar cones, Farkas lemma, Karush-Kuhn-Tucker (KKT)
conditions; linear case, convex problems, regularity conditions, saddle
points of Lagrange function, duality theory.

Algorithms of nonlinear (constrained) programming (4h): methods of
feasible directions, Zoutendijk algorithm; external and barrier penalty
functions, Fiacco-McCormick method, multiplier methods based the
augmented Lagrange function; elements of global optimization.

Discrete optimization (5h): review of typical mixed integer programming
(MIP) and combinatorial optimization problems, use of integer variables
to model logical relations, special structures in MIP problems;
complexity of problems; variants of exact solutions methods, basic
branch and bound methods, dynamic programming; approximation methods,
sample heuristics and basic metaheuristics.

Multicriteria optimization (3h): concept of efficient solution,
generation techniques, interactive methods.


Similar Courses

• H.P. Williams, Model Building in Mathematical Programming, 5th
  Ed, Wiley 2013.


• M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and
  Network Flows, 4th Ed, Wiley, 2010.


• M.S. Bazaraa, H.D. Sherali, C.M. Shetty, Nonlinear Programming,
  Wiley, 2006.


• A.P. Ruszczyński, Nonlinear Optimization, Princeton Univ. Press,
  2006.


• I.Maros, Computational Techniques of the Simplex Method, Kluwer,
  2003.


• M.Ehrgott, Multicriteria Optimization, Springer, Berlin 2005.


• A.Kasperski, Discrete Optimization and Network Flows, Wroclaw Univ. of Technology, 2011.

The students will be able to:

• Understand different theoretical and computational aspects of a wide range of optimization methods,
• Realize the possibilities offered by the different optimization methods,
• Use of optimization toolbox.

Theoretical knowledge is validated by means of an exam, scheduled for 2
hours and giving up to 60 points. Laborarories are assessed by
laboratory tutors, giving up to 40 points. All points are summed up to
produce a final mark:

A 91-110 points

B+ 81-90 points

B 71-80 points

C+ 61-70 points

C 51-60 points

D 0-50 points