Course detail

Optimization I

FSI-SOPAcad. year: 2024/2025

The course focuses on fundamental optimization models and methods for solving engineering problems. The principal ideas of mathematical programming are presented in the following steps: 1) formulation and analysis of problems, 2) building of mathematical models, 3) classification of models, possible transformations and assessment of their theoretical properties, 4) selection and modification of solution algorithms, 5) their software implementation, 6) finding, analysis and interpretation of the optimal solutions. The course mainly covers the topics of linear programming (convex and polyhedral sets, simplex method, duality) and nonlinear programming (convex functions, optimality conditions, typical algorithms). The course also includes introductory information on the principles of modification and generalization of basic optimization models (related to integer programs, network flow models, time and randomness modeling, etc.), which are further extended and deepened in the follow-up courses. The content of the course was developed by the author on the basis of his experience with similar courses collected during his stays at foreign universities.

Language of instruction

Czech

Number of ECTS credits

4

Mode of study

Not applicable.

Guarantor

RNDr. Pavel Popela, Ph.D.

Department

Institute of Mathematics (ÚM)

Entry knowledge

Fundamental knowledge of principal concepts of mathematical analysis  and linear algebra within the scope of subjects taught in mathematical engineering is assumed.

 

Rules for evaluation and completion of the course

Credit is awarded on the basis of the student's active participation in the course and his/her significant contribution to group homework projects during the semester. Then, the examination result is based on the results of a written paper including modeling-related, computational and theoretical questions. The written work is then accompanied by an oral discussion with the student.


The attendance at seminars is required as well as active participation in lectures. Passive or missing students are required to work out additional assignments.

 

Aims

The course focuses on introducing students to the fundamental knowledge of optimization - mathematical programming. Emphasis is placed on presenting essential information about models and methods for solving optimization problems. This includes an introduction to the analysis of decision problems, the building of basic (linear and nonlinear) mathematical models, their formal descriptions and analysis of their properties, appropriate transformations of models in terms of their solvability, and the choice and modification of algorithms. The theoretical interpretation of the above mentioned knowledge is supported by illustrative geometrical and numerical examples with the aim to lead students to a deep and applicationally useful understanding of the lectured material.


The course is designed for mathematical engineering students and is useful for students of applied science and selected engineering disciplines. Participating students will gain knowledge of the theoretical foundations of optimization (especially linear and nonlinear programming). They will also learn general principles of modeling and selected algorithms for solving optimization problems, and form a basic idea of the use  of optimization models in typical applications.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Bazaraa et al.: Linear Programming and Network Flows, , Wiley 2011 (EN)
Bazaraa et al.: Nonlinear Programming, , Wiley 2012 (EN)
Dupačová et al.: Lineárne programovanie, Alfa 1990 (CS)
Klapka a kol.: Metody operačního výzkumu, VUT 2001 (CS)

Recommended reading

Dvořák a kol.: Operační analýza, VUT FSI, 2001 (CS)
Charamza a kol.: Modelovací systém GAMS, MFF UK Praha, 1994 (EN)
Klapka a kol.: Metody operačního výzkumu, VUT, 2001 (CS)

Classification of course in study plans

  • Programme B-MAI-P Bachelor's 3 year of study, summer semester, compulsory

  • Programme C-AKR-P Lifelong learning

    specialization CLS , 1 year of study, summer semester, elective

Type of course unit

 

Lecture

26 hod., optionally

Teacher / Lecturer

RNDr. Pavel Popela, Ph.D.

Syllabus

1. Introductory optimization: problem formulation and analysis, model building and classification, basic theory.

2. Visualisation, algorithms, software, postoptimization. Remarks on specialized and general optimization models.

3. Linear programming (LP): Convex and polyhedral sets.

4. LP: Feasible sets, extreme points, extreme directions, representation theorem, optimality conditions.

5. LP: The simplex method - introduction,  derivation, sipmplex tableau.

6. LP: The simplex method - extension themes.

7. LP: Duality, sensitivity and parametric analysis.

8. Nonlinear programming (NLP): Convex functions and their properties.

9. NLP: Unconstrained optimization - theoretical results and applications.

10. NLP: Constrained optimization and optimality conditions (geometric, FJ, KKT).

11. NLP: Unconstrained optimization and related line search and multivariate methods.

13. NLP: Constrained optimization and related numerical  methods.

14. Selected additional topics. 

Computer-assisted exercise

13 hod., compulsory

Teacher / Lecturer

RNDr. Pavel Popela, Ph.D.

Syllabus

Introductory problems (1-3)
Linear problems (4-8)
Nonlinear problems (9-13)

Course participance is obligatory.