Selected Optimization Methods and Algorithms

Course Description

Complexity classes of algorithms, O-notation. Fundamental calculus results (differentials, Directional derivative, Taylor's formula, Increasing and decreasing functions, Extrema), Convexity and concavity of a function. Nonconstrained optimization: Optimization in one dimension, Gradient Methods, Stopping Criteria, The Newton's Method, Quasi-Newton Methods, Conjugate Gradient Methods, Nelder-Mead Simplex Algorithm, Trusted-Region Methods. Constrained optimization: Karush-Kuhn-Tucker optimality conditions, Lagrangian multipliers, Augmented Lagrangian method. Selected heuristical methods (Simulated Annealing, Particle Swarm, Ant Colony, genetic algorithms). Multiobjective Optimization.

Learning Outcomes

  1. recognize and analyze the problem as an optimization one
  2. relate the specified problem to the one of the same kind or a similar known and already solved problem
  3. select the best method for a known problem
  4. adjust methods and algorithms for similar problems so that they become suitable for a given one
  5. design one’s own solution for an unknown problem
  6. assess the validity of one’s own solution, in the sense of algorithm convergence and complexity
  7. compare and contrast own solution to possible alternatives
  8. recommend the algorithm for an unknown problem on the basis of analysis of alternatives

Forms of Teaching

Lectures

Lecturer's exposition and further clarifications based on students' questions.

Independent assignments

Each student will theoretically and practically solve an optimization problem on his/her own choice.

Work with mentor

Assistance to students with their chosen optimization problems.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Seminar/Project 0 % 80 % 0 % 0 %
Final Exam: Oral 20 %
Exam: Written 0 % 80 %
Exam: Oral 20 %

Week by Week Schedule

  1. Constant, logarithmic, linear, quadratic, and exponential complexity classes
  2. Tangent and normal lines to the graph of function; Increasing and decreasing functions
  3. Directional derivative; Derivative of implicit function; Theorem of implicit function, Extrema; Local extrema
  4. Second differential and quadratic forms, Taylor's formula
  5. Convexity and concavity of a function; Finding extrema of a function, necessary and sufficient conditions, Optimization in one dimension (golden section search, successive parabolic interpolation, Newton's method)
  6. Direct Search Algorithms (the Hooke-Jeeves method); Gradient Methods (the steepest descent); , The Newton's Method; The Secant Method, Stopping Criteria
  7. Conjugate Gradient Methods, Quasi-Newton Methods
  8. Midterm exam
  9. Trust-Region Methods
  10. Extrema of a function subject to constraints; Lagrange mutliplier, Augmented Lagrangian Method
  11. Convex optimization problems
  12. Duality; The Lagrange function; Perturbation and sensitivity analysis
  13. Deterministic and heuristic approaches
  14. Meta-heuristics: simulated annealing, tabu search, evolutionary strategies, ant colony optimization, bee mating optimization, and greedy randomized adaptive search procedures (GRASP)
  15. Final exam

Study Programmes

University graduate
Audio Technologies and Electroacoustics (profile)
Free Elective Courses (2. semester)
Communication and Space Technologies (profile)
Free Elective Courses (2. semester)
Computational Modelling in Engineering (profile)
Free Elective Courses (2. semester)
Computer Engineering (profile)
Free Elective Courses (2. semester)
Computer Science (profile)
Free Elective Courses (2. semester)
Control Systems and Robotics (profile)
Free Elective Courses (2. semester)
Data Science (profile)
Free Elective Courses (2. semester)
Electrical Power Engineering (profile)
Free Elective Courses (2. semester)
Electric Machines, Drives and Automation (profile)
Free Elective Courses (2. semester)
Electronic and Computer Engineering (profile)
Free Elective Courses (2. semester)
Electronics (profile)
Free Elective Courses (2. semester)
Information and Communication Engineering (profile)
Free Elective Courses (2. semester)
Network Science (profile)
Free Elective Courses (2. semester)
Software Engineering and Information Systems (profile)
Elective Course of the profile (2. semester)

Literature

E.K.P. Chong, S.H. Żak (2013.), An Introduction to Optimization, 4th Edition, Wiley
Jorge Nocedal, Stephen J. Wright (2006.), Numerical Optimization, 2nd Edition, Springer
Omid Bozorg-Haddad, Mohammad Solgi, Hugo A. Loáiciga (2017.), Meta-heuristic and Evolutionary Algorithms for Engineering Optimization, Wiley
Carl D. Meyer (2000.), Matrix Analysis and Applied Linear Algebra, SIAM
G.A.F. Seber, A.J. Lee (2003.), Linear Regression Analysis, 2nd edition, Wiley
G.A.F. Seber and C. J. Wild (2005.), Nonlinear Regression, Wiley

For students

General

ID 222557
  Summer semester
5 ECTS
L1 English Level
L1 e-Learning
45 Lectures
15 Laboratory exercises

Grading System

90 Excellent
75 Very Good
60 Good
50 Acceptable