M.petrishchev: Created page with "= Optimization = * '''Course name:''' Optimization * '''Course number:''' R-01 == Prerequisites == == Course characteristics == === Key concepts o..."

2022-07-05T07:57:27Z

Created page with "= Optimization = * <span>'''Course name:'''</span> Optimization * <span>'''Course number:'''</span> R-01 == Prerequisites == == Course characteristics == === Key concepts o..."

New page

= Optimization =

* <span>'''Course name:'''</span> Optimization
* <span>'''Course number:'''</span> R-01
== Prerequisites ==

== Course characteristics ==

=== Key concepts of the class ===

* Optimization of a cost function
* Algorithms to find solution of linear and nonlinear optimization problems

=== What is the purpose of this course? ===

The main purpose of this course to make the student aware of basic notions of mathematical programming and of its importance in the area of engineering.

== Course Objectives Based on Bloom’s Taxonomy ==

==== What should a student remember at the end of the course? ====

By the end of the course, the students should be able to

* explain the goal of an optimization problem
* remind the importance of converge analysis for optimization algorithms
* draft solution codes in Python/Matlab.

==== What should a student be able to understand at the end of the course? ====

By the end of the course, the students should be able to

* formulate a simple optimization problem
* select the appropriate solution algorithm
* find the solution.

==== What should a student be able to apply at the end of the course? ====

By the end of the course, the students should be able to apply:

* the simplex method
* algorithms to solve nonlinear optimization problems.

=== Course evaluation ===

The course has two major forms of evaluations:

<div id="tab:OSCourseGrading">

{| style="border-spacing: 2px; border: 1px solid darkgray;"
|+ '''Course grade breakdown'''
!align="center"| '''Component'''
! '''Points'''
|-
| Labs/seminar classes (weekly evaluations)
|align="center"| 0
|-
| Interim performance assessment (class participation)
|align="center"| 100/0
|-
| Exams
|align="center"| 0/100
|}

A student can take the examination by properly solving three assignments or the final exam, which is composed of three questions on the same arguments of the assignments.

=== Grades range ===

<div id="tab:OSCourseGradingRange">

{| style="border-spacing: 2px; border: 1px solid darkgray;"
|+ Course grading range
|-
| A. Excellent
|align="center"| 86-100
|-
| B. Good
|align="center"| 71-85
|-
| C. Satisfactory
|align="center"| 56-70
|-
| D. Poor
|align="center"| 0-55
|}

=== Resources and reference material ===

* '''Textbook:''' C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
* '''Textbook:''' D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.

== Course Sections ==

The main sections of the course and approximate hour distribution between them is
as follows:

<div id="tab:OSCourseSections">

{| style="border-spacing: 2px; border: 1px solid darkgray;"
|+ Course Sections
!align="center"| '''Section'''
! '''Section Title'''
!align="center"| '''Teaching Hours'''
|-
|align="center"| 1
| Linear programming
|align="center"| 15
|-
|align="center"| 2
| Nonlinear programming
|align="center"| 15
|}

</div>
=== Section 1 ===

==== Section title: Linear programming ====

==== Topics covered in this section ====

* simplex method to solve real linear programs
* cutting-plane and branch-and-bound methods to solve integer linear programs.

==== What forms of evaluation were used to test students’ performance in this section? ====

<div id="tab:OSSectionEval1">

{| style="border-spacing: 2px; border: 1px solid darkgray;"
|''' '''
! '''Yes/No'''
|-
| Development of individual parts of software product code
|align="center"| 0
|-
| Homework and group projects
|align="center"| 0
|-
| Midterm evaluation
|align="center"| 1
|-
| Testing (written or computer based)
|align="center"| 1
|-
| Reports
|align="center"| 0
|-
| Essays
|align="center"| 0
|-
| Oral polls
|align="center"| 0
|-
| Discussions
|align="center"| 0
|}

</div>

==== Typical questions for ongoing performance evaluation within this section ====

# How a convex set and a convex function are defined?
# What is the difference between polyhedron and polytope?
# Why does always a linear program include constraints?

==== Typical questions for seminar classes (labs) within this section ====
#Consider the problem:
#:<math> \text{minimize } c_1 x_1 + c_2 x_2 + c_3 x_3 + c_4 x_4 </math>
#:<math> \text{subject to } x_1 + x_2 +x_3 + x_4 = 2 </math>
#:<math> 2x_1 +3 x_3 + 4x_4 = 2 </math>
#:<math> x_1, x_2, x_3, x_4 \geqslant 0 </math>
#:Solve it using simplex method.
# Consider the problem:
#:<math> \text{minimize } x_1 + x_2 </math>
#:<math> \text{subject to } -5x_1+4x_2\le0 </math>
#:<math> 6x_1+2x_2\ \le17 </math>
#:<math>x_1,\ x_2\geq0 </math>
#:Solve it using cutting-plane and branch-and-bound methods.

==== Typical questions for midterm within this section ====
# Consider the problem:
#: <math> \text{minimize } x_1+x_2 </math>
#: <math> \text{subject to } x_1+{2x}_2+2x_3\le20 </math>
#: <math> 2x_1+x_2+2x_3\le20 </math>
#: <math> 2x_1+2x_2+x_3\le20 </math>
#: <math> x_1,\ x_2,\ x_3\geq0 </math>
#: Solve it using simplex method.
# Consider the problem:
#: <math> \text{maximize } 15x_1+{12x}_2+4x_3+2x_4</math>
#: <math> \text{subject to } 8x_1+5x_2+3x_3+2x_4\le10 </math>
#: <math> x_i\in \{0,1\} </math>
#: Solve it using cutting-plane and branch-and-bound methods.

==== Test questions for final assessment in this section ====

# Why does the simplex method require to be initialized with a correct basic feasible solution?
# How one can test absence of solutions to a linear program?
# How one can test unbounded solutions to a linear program?
# How can the computational complexity of an optimization algorithm can be defined?

=== Section 2 ===

==== Section title: Nonlinear programming ====

==== Topics covered in this section ====

* methods for unconstrained optimization
* linear and nonlinear least-squares problems
* methods for constrained optimization

==== What forms of evaluation were used to test students’ performance in this section? ====

<div id="tab:OSSectionEval2">

{| style="border-spacing: 2px; border: 1px solid darkgray;"
|''' '''
! '''Yes/No'''
|-
| Development of individual parts of software product code
|align="center"| 0
|-
| Homework and group projects
|align="center"| 0
|-
| Midterm evaluation
|align="center"| 1
|-
| Testing (written or computer based)
|align="center"| 1
|-
| Reports
|align="center"| 0
|-
| Essays
|align="center"| 0
|-
| Oral polls
|align="center"| 0
|-
| Discussions
|align="center"| 0
|}

</div>

==== Typical questions for ongoing performance evaluation within this section ====

# Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem?
# What is the goal of a descent algorithm?
# What does it mean to fit some experimental data points

==== Typical questions for seminar classes (labs) within this section ====
# Consider the problem:
#: <math> \text{minimize } \frac{1}{2}\left(x_1^1+x_2^2\right) </math>
#: Solve it using the suitable method.
# Consider the problem:
#: <math> \text{minimize } -\left(x_1-2\right)^2 </math>
#: <math> \text{subject to } \ x_1+x_2^2=1 </math>
#: <math> -1\le x_2\le1 </math>
#: Solve it using the suitable method.

==== Typical questions for midterm within this section ====
# Consider the problem:
#: <math> \text{minimize } 100\left(x_2-x_1^2\right)^2+\left(1-x_1\right)^2 </math>
#: <math> \text{subject to } x_1,\ x_2\geq0 </math>
#: Solve it using the suitable method.

==== Test questions for final assessment in this section ====

# How is it possible to compute the Lagrange multiplier of a constrained optimization problem?
# Which are the convergence conditions of the steepest descent method?
# Which are the convergence conditions of the Newton’s method?
# How can one “penalize” a constraint?

MSc: Optimization.previous version - Revision history

M.petrishchev: Created page with "= Optimization = * '''Course name:''' Optimization * '''Course number:''' R-01 == Prerequisites == == Course characteristics == === Key concepts o..."