Optimization

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra kybernetiky

Anotace:

The topic of the subject is the optimization of functions of continuous variables

without and with constraints. Considerable space is devoted to convex

optimization and linear programming (LP). The student will understand the scope,

generality and usefulness of the discipline of optimization and receive

theoretical background and practical skills to formulate optimization problems,

estimate their level of difficulty, and propose ways of solution.

Požadavky:

Linear algebra, Calculus, Probability and statistics, Logic and graph theory

Osnova přednášek:

1. Taxonomy of optimization problems. What belongs and what does not belong to the subject. Motivating examples. Local and global extremes.

2. Algorithms of unconstrained local optimization: bracketing an extreme,

gradient optimization, coordinate optimization, Newton's method.

3. Algorithms of constrained local optimization: Lagrange multipliers,

projected gradient methods.

4. Convex sets and functions.

5. LP1: convex polyhedra and their geometry

6. LP2: simplex method

7. LP3: Farkas lemma, LP duality

8. Application of LP (linear regression in L1 metric etc.)

9. Quadratic programming. Perceptron and Kozinec algorithms.

10. More general tasks of convex optimization: semidefinite programming (SDP), geometric programming. Examples, applications.

11. Lagrange duality.

12. Conjugated gradients.

13. Optimization of nonsmooth functions: subgradients, Shor's theorem.

14. Reserve.

Osnova cvičení:

The labs consist of solving practically motivated problems, which can hardly or

not at all be tackled without using the knowledge acquired at the lectures. This

does not require lengthy coding but will be mathematically nontrivial --

therefore preparation at home is necessary for each lab lesson. The MATLAB

programming language is used.

Cíle studia:

After the course, the students should be able to recognize

optimization problems around them, formulate them

mathematically, estimate their level of difficulty, and

solve easier problems.

Studijní materiály:

Selected parts of the book „Boyd and Vanderberghe: Convex Optimization“ (freely available on www).

Poznámka:

Rozsah výuky v kombinované formě studia: 28p+6c

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Open Informatics - Computer Systems (povinný předmět programu)
• Open Informatics - Computer and Information Science (povinný předmět programu)
• Open Informatics - Software Systems (povinný předmět programu)
• Open Informatics (povinný předmět programu)