Difference between revisions of "MSc: Optimization"

From IU
Jump to navigation Jump to search
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
  +
 
= 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.
   
* <span>'''Course name:'''</span> Optimization
 
* <span>'''Course number:'''</span> R-01
 
 
== Prerequisites ==
 
== Prerequisites ==
   
  +
=== Prerequisite subjects ===
== Course characteristics ==
 
   
=== Key concepts of the class ===
 
   
  +
=== Prerequisite topics ===
* Optimization of a cost function
 
* Algorithms to find solution of linear and nonlinear optimization problems
 
   
=== What is the purpose of this course? ===
 
   
  +
== Course Topics ==
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.
 
  +
{| class="wikitable"
  +
|+ 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? ===
== Course Objectives Based on Bloom’s Taxonomy ==
 
  +
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.
 
==== What should a student remember at the end of the course? ====
 
   
  +
=== ILOs defined at three levels ===
By the end of the course, the students should be able to
 
   
  +
==== 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
 
* explain the goal of an optimization problem
 
* remind the importance of converge analysis for optimization algorithms
 
* remind the importance of converge analysis for optimization algorithms
 
* draft solution codes in Python/Matlab.
 
* draft solution codes in Python/Matlab.
   
==== What should a student be able to understand at the end of the course? ====
+
==== 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 ...
 
By the end of the course, the students should be able to
 
 
 
* formulate a simple optimization problem
 
* formulate a simple optimization problem
 
* select the appropriate solution algorithm
 
* select the appropriate solution algorithm
 
* find the solution.
 
* find the solution.
   
==== What should a student be able to apply at the end of the course? ====
+
==== 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 ...
 
By the end of the course, the students should be able to apply:
 
 
 
* the simplex method
 
* the simplex method
* algorithms to solve nonlinear optimization problems.
+
* algorithms to solve nonlinear optimization problems.
  +
== Grading ==
 
=== Course evaluation ===
 
 
The course has two major forms of evaluations:
 
 
<div id="tab:OSCourseGrading">
 
   
  +
=== Course grading range ===
{| style="border-spacing: 2px; border: 1px solid darkgray;"
 
  +
{| class="wikitable"
|+ '''Course grade breakdown'''
 
  +
|+
!align="center"| '''Component'''
 
! '''Points'''
 
 
|-
 
|-
  +
! Grade !! Range !! Description of performance
| Labs/seminar classes (weekly evaluations)
 
|align="center"| 0
 
 
|-
 
|-
  +
| A. Excellent || 86-100 || -
| Interim performance assessment (class participation)
 
|align="center"| 100/0
 
 
|-
 
|-
  +
| B. Good || 71-85 || -
| Exams
 
  +
|-
|align="center"| 0/100
 
  +
| C. Satisfactory || 56-70 || -
  +
|-
  +
| D. Poor || 0-55 || -
 
|}
 
|}
</div>
 
 
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">
 
   
  +
=== Course activities and grading breakdown ===
{| style="border-spacing: 2px; border: 1px solid darkgray;"
 
  +
{| class="wikitable"
|+ Course grading range
 
  +
|+
 
|-
 
|-
  +
! Activity Type !! Percentage of the overall course grade
| A. Excellent
 
|align="center"| 86-100
 
 
|-
 
|-
  +
| Labs/seminar classes (weekly evaluations) || 0
| B. Good
 
|align="center"| 71-85
 
 
|-
 
|-
  +
| Interim performance assessment (class participation) || 100/0
| C. Satisfactory
 
|align="center"| 56-70
 
 
|-
 
|-
  +
| Exams || 0/100
| D. Poor
 
|align="center"| 0-55
 
 
|}
 
|}
</div>
 
   
  +
=== Recommendations for students on how to succeed in the course ===
=== Resources and reference material ===
 
   
* '''Textbook:''' C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
 
* '''Textbook:''' D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
 
   
  +
== Resources, literature and reference materials ==
== Course Sections ==
 
   
  +
=== Open access resources ===
The main sections of the course and approximate hour distribution between them is
 
  +
* Textbook: C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization, Dover, New York, 1982.
as follows:
 
  +
* Textbook: D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
   
  +
=== Closed access resources ===
<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? ====
 
   
  +
=== Software and tools used within the course ===
<div id="tab:OSSectionEval1">
 
  +
  +
= Teaching Methodology: Methods, techniques, & activities =
   
  +
== Activities and Teaching Methods ==
{| style="border-spacing: 2px; border: 1px solid darkgray;"
 
  +
{| class="wikitable"
|''' '''
 
  +
|+ Activities within each section
! '''Yes/No'''
 
 
|-
 
|-
  +
! Learning Activities !! Section 1 !! Section 2
| Development of individual parts of software product code
 
|align="center"| 0
 
 
|-
 
|-
  +
| Midterm evaluation || 1 || 1
| Homework and group projects
 
|align="center"| 0
 
 
|-
 
|-
  +
| Testing (written or computer based) || 1 || 1
| Midterm evaluation
 
  +
|}
|align="center"| 1
 
  +
== Formative Assessment and Course Activities ==
  +
  +
=== Ongoing performance assessment ===
  +
  +
==== Section 1 ====
  +
{| class="wikitable"
  +
|+
 
|-
 
|-
  +
! Activity Type !! Content !! Is Graded?
| Testing (written or computer based)
 
|align="center"| 1
 
 
|-
 
|-
  +
| Question || How a convex set and a convex function are defined? || 1
| Reports
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || What is the difference between polyhedron and polytope? || 1
| Essays
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || Why does always a linear program include constraints? || 1
| Oral polls
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}c_{1}x_{1}+c_{2}x_{2}+c_{3}x_{3}+c_{4}x_{4}}</math> <br><math>{\displaystyle {\text{subject to }}x_{1}+x_{2}+x_{3}+x_{4}=2}</math> <br><math>{\displaystyle 2x_{1}+3x_{3}+4x_{4}=2}</math> <br><math>{\displaystyle x_{1},x_{2},x_{3},x_{4}\geqslant 0}</math> <br>Solve it using simplex method. || 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'''
 
 
|-
 
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}x_{1}+x_{2}}</math> <br><math>{\displaystyle {\text{subject to }}-5x_{1}+4x_{2}\leq 0}</math> <br><math>{\displaystyle 6x_{1}+2x_{2}\ \leq 17}</math> <br><math>{\displaystyle x_{1},\ x_{2}\geq 0}</math> <br>Solve it using cutting-plane and branch-and-bound methods. || 0
| Development of individual parts of software product code
 
  +
|}
|align="center"| 0
 
  +
==== Section 2 ====
  +
{| class="wikitable"
  +
|+
 
|-
 
|-
  +
! Activity Type !! Content !! Is Graded?
| Homework and group projects
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || Which are the necessary and sufficient conditions of optimality of a generic minimization/maximization problem? || 1
| Midterm evaluation
 
|align="center"| 1
 
 
|-
 
|-
  +
| Question || What is the goal of a descent algorithm? || 1
| Testing (written or computer based)
 
|align="center"| 1
 
 
|-
 
|-
  +
| Question || What does it mean to fit some experimental data points || 1
| Reports
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}{\frac {1}{2}}\left(x_{1}^{1}+x_{2}^{2}\right)}</math> <br>Solve it using the suitable method. || 0
| Essays
 
|align="center"| 0
 
 
|-
 
|-
  +
| Question || Consider the problem:<br><math>{\displaystyle {\text{minimize }}-\left(x_{1}-2\right)^{2}}</math> <br><math>{\displaystyle {\text{subject to }}\ x_{1}+x_{2}^{2}=1}</math> <br><math>{\displaystyle -1\leq x_{2}\leq 1}</math> <br>Solve it using the suitable method. || 0
| Oral polls
 
  +
|}
|align="center"| 0
 
  +
=== Final assessment ===
|-
 
  +
'''Section 1'''
| Discussions
 
  +
# Why does the simplex method require to be initialized with a correct basic feasible solution?
|align="center"| 0
 
  +
# 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'''
  +
# 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?
   
  +
=== The retake exam ===
 
  +
'''Section 1'''
</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:
 
# Consider the problem:
#: <math> \text{minimize } \frac{1}{2}\left(x_1^1+x_2^2\right) </math>
+
<math>{\displaystyle {\text{minimize }}x_{1}+x_{2}}</math>
  +
<math>{\displaystyle {\text{subject to }}x_{1}+{2x}_{2}+2x_{3}\leq 20}</math>
#: Solve it using the suitable method.
 
  +
<math>{\displaystyle 2x_{1}+x_{2}+2x_{3}\leq 20}</math>
  +
<math>{\displaystyle 2x_{1}+2x_{2}+x_{3}\leq 20}</math>
  +
<math>{\displaystyle x_{1},\ x_{2},\ x_{3}\geq 0}</math>
  +
Solve it using simplex method.
 
# Consider the problem:
 
# Consider the problem:
#: <math> \text{minimize } -\left(x_1-2\right)^2 </math>
+
<math>{\displaystyle {\text{maximize }}15x_{1}+{12x}_{2}+4x_{3}+2x_{4}}</math>
#: <math> \text{subject to } \ x_1+x_2^2=1 </math>
+
<math>{\displaystyle {\text{subject to }}8x_{1}+5x_{2}+3x_{3}+2x_{4}\leq 10}</math>
#: <math> -1\le x_2\le1 </math>
+
<math>{\displaystyle x_{i}\in \{0,1\}}</math>
#: Solve it using the suitable method.
+
Solve it using cutting-plane and branch-and-bound methods.
   
  +
'''Section 2'''
==== Typical questions for midterm within this section ====
 
 
# Consider the problem:
 
# Consider the problem:
#: <math> \text{minimize } 100\left(x_2-x_1^2\right)^2+\left(1-x_1\right)^2 </math>
+
<math>{\displaystyle {\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>
+
<math>{\displaystyle {\text{subject to }}x_{1},\ x_{2}\geq 0}</math>
#: Solve it using the suitable method.
+
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?
 

Latest revision as of 14:09, 10 November 2022

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.

Prerequisites

Prerequisite subjects

Prerequisite topics

Course Topics

Course Sections and Topics
Section Topics within the section
Linear programming
  1. simplex method to solve real linear programs
  2. cutting-plane and branch-and-bound methods to solve integer linear programs.
Nonlinear programming
  1. methods for unconstrained optimization
  2. linear and nonlinear least-squares problems
  3. 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

Recommendations for students on how to succeed in the course

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.

Closed access resources

Software and tools used within the course

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:




Solve it using simplex method.
0
Question Consider the problem:




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:

Solve it using the suitable method.
0
Question Consider the problem:



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:

Solve it using simplex method.

  1. Consider the problem:

Solve it using cutting-plane and branch-and-bound methods.

Section 2

  1. Consider the problem:

Solve it using the suitable method.