MSc: Optimization

Optimization

• Course name: Optimization
• Code discipline: R-01
• Subject area:

Short Description

This course covers the following concepts: Optimization of a cost function; Algorithms to find solution of linear and nonlinear optimization problems.

Course Topics

Course Sections and Topics

Section	Topics within the section
Linear programming	simplex method to solve real linear programs cutting-plane and branch-and-bound methods to solve integer linear programs.
Nonlinear programming	methods for unconstrained optimization linear and nonlinear least-squares problems methods for constrained optimization

Intended Learning Outcomes (ILOs)

What is the main 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.

ILOs defined at three levels

Level 1: What concepts should a student know/remember/explain?

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.

Level 2: What basic practical skills should a student be able to perform?

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.

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

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

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

Grading

Course grading range

Grade	Range	Description of performance
A. Excellent	86-100	-
B. Good	71-85	-
C. Satisfactory	56-70	-
D. Poor	0-55	-

Course activities and grading breakdown

Activity Type	Percentage of the overall course grade
Labs/seminar classes (weekly evaluations)	0
Interim performance assessment (class participation)	100/0
Exams	0/100

Resources, literature and reference materials

Open access resources

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

Teaching Methodology: Methods, techniques, & activities

Activities and Teaching Methods

Activities within each section

Learning Activities	Section 1	Section 2
Midterm evaluation	1	1
Testing (written or computer based)	1	1

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

Activity Type	Content	Is Graded?
Question	How a convex set and a convex function are defined?	1
Question	What is the difference between polyhedron and polytope?	1
Question	Why does always a linear program include constraints?	1
Question	Consider the problem: ${\displaystyle {\text{minimize }}c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}+c_{4}x_{4}}$ ${\displaystyle {\text{subject to }}x_{1}+x_{2}+x_{3}+x_{4}=2}$ ${\displaystyle 2x_{1}+3x_{3}+4x_{4}=2}$ ${\displaystyle x_{1},x_{2},x_{3},x_{4}\geqslant 0}$ Solve it using simplex method.	0
Question	Consider the problem: ${\displaystyle {\text{minimize }}x_{1}+x_{2}}$ ${\displaystyle {\text{subject to }}-5x_{1}+4x_{2}\leq 0}$ ${\displaystyle 6x_{1}+2x_{2}\ \leq 17}$ ${\displaystyle x_{1},\ x_{2}\geq 0}$ Solve it using cutting-plane and branch-and-bound methods.	0

Section 2

Activity Type	Content	Is Graded?
Question	Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem?	1
Question	What is the goal of a descent algorithm?	1
Question	What does it mean to fit some experimental data points	1
Question	Consider the problem: ${\displaystyle {\text{minimize }}{\frac {1}{2}}\left(x_{1}^{1}+x_{2}^{2}\right)}$ Solve it using the suitable method.	0
Question	Consider the problem: ${\displaystyle {\text{minimize }}-\left(x_{1}-2\right)^{2}}$ ${\displaystyle {\text{subject to }}\ x_{1}+x_{2}^{2}=1}$ ${\displaystyle -1\leq x_{2}\leq 1}$ Solve it using the suitable method.	0

Final assessment

Section 1

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

Section 2

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

The retake exam

Section 1

1. Consider the problem:

${\displaystyle {\text{minimize }}x_{1}+x_{2}}$ ${\displaystyle {\text{subject to }}x_{1}+{2x}_{2}+2x_{3}\leq 20}$ ${\displaystyle 2x_{1}+x_{2}+2x_{3}\leq 20}$ ${\displaystyle 2x_{1}+2x_{2}+x_{3}\leq 20}$ ${\displaystyle x_{1},\ x_{2},\ x_{3}\geq 0}$ Solve it using simplex method.

1. Consider the problem:

${\displaystyle {\text{maximize }}15x_{1}+{12x}_{2}+4x_{3}+2x_{4}}$ ${\displaystyle {\text{subject to }}8x_{1}+5x_{2}+3x_{3}+2x_{4}\leq 10}$ ${\displaystyle x_{i}\in \{0,1\}}$ Solve it using cutting-plane and branch-and-bound methods.

Section 2

1. Consider the problem:

${\displaystyle {\text{minimize }}100\left(x_{2}-x_{1}^{2}\right)^{2}+\left(1-x_{1}\right)^{2}}$ ${\displaystyle {\text{subject to }}x_{1},\ x_{2}\geq 0}$ Solve it using the suitable method.