• Svenska

# FEG3324 Applied Optimization and mathematical Decompositions 10.0 credits

This course provides a deep understanding of the optimization models and its solution algorithms in an applied context. In part 1, standard optimization models will be discussed. This includes LP, convex Quadratic Program (QP), Quadratically Constrained Quadratic program (QCQP), Second Order Cone Program (SOCP), Semi Definite Program (SDP), and convex Dynamic Program (DP). Then in part 2, three special groups of nonconvex optimization models with special mathematical properties will be comprehensively discussed. These are mixed-integer convex programs, quasi convex optimization models, and inside ellipsoid outside sphere models. We will cover comprehensively disjunctive programs, logicbased programs, stochastic programs, and finally multi-level (bilevel, trilevel, and quad level) programs. Complementarity models arise in many real-life applications. Hence, we discuss Linear Complementarity Problems (LCPs) and Mixed Complementarity Problems (MCPs) and their solution algorithms. Having complementarity conditions in an optimization problem lead to Mathematical Programs with Equilibrium Constraints (MPEC) and Equilibrium Problems with Equilibrium Constraints (EPEC). The mathematics of complementarity problems will be discussed in Part 4 of the course. Mathematical decomposition algorithms are very important when it comes to real-life applications. Accordingly, three important and well-known groups of mathematical decomposition techniques will be discussed in Part 5 of the course. In particular, we discuss Benders decomposition and its variants, Lagrange decomposition and its variants, and also hybrid decomposition algorithms. In part 6 of the course, several applications of the mathematical concepts developed and discussed through parts 1 to 5 will be discussed. Part 7 of the course provides the ABC of optimization based modeling process. We discuss and provide a systematic approach to deal with different real-life applications.

Course offerings are missing for current or upcoming semesters.
Headings with content from the Course syllabus FEG3324 (Spring 2023–) are denoted with an asterisk ( )

## Content and learning outcomes

### Course disposition

Lectures (15), guest lectures (3), students seminars (one for each student), and final research paper written by the student

### Course contents

PhD course on:

Applied Optimization and Mathematical Decompositions

Part 1: Convex optimization problems

Linear Program (LP)

• General formulation
• Solution algorithms
• - Simplex method
• - Interior Point method
• Example

• General formulation
• Solution algorithms
• Example

• General formulation
• Solution algorithms
• Example

Second Order Cone Program (SOCP)

• General formulation
• Solution algorithms
• Example

Semi Definite Program (SDP)

• General formulation
• Solution algorithms
• Example

Dynamic Program (DP) and Dynamic Dual Program (DDP)

• General formulation
• Solution algorithms
• Example

Part 2: Nonconvex optimization problems with special properties

• Mixed Integer Linear Program (MILP)
• General formulation
• Solution algorithms
• - Branch and Bound
• - Branch and Cut
• Example
• Generalized Mixed Integer Convex Programs (MICP)

Quasi Convex Optimization Problem

• General formulation
• Solution algorithms
• Example

Inside Ellipsoid Outside Sphere Program (IEOSP)

• General formulation
• Solution algorithms
• Example

Part 3: Selected nonconvex optimization problems

Disjunctive program

• General formulation
• Solution algorithms
• Example

Logic-based program

• General formulation
• Solution algorithms
• Example

Stochastic program

• General formulation
• Solution algorithms
• Example

Bilevel and Trilevel programs

• General formulation
• Solution algorithms
• Example

Part 4: Complementarity problems

Linear Complementarity Problem (LCP)

• General formulation
• Solution algorithms
• Example

Mixed Complementarity Problem (MCP)

• General formulation
• Solution algorithms
• Example

Mathematical Program with Equilibrium Constraints (MPEC)

• General formulation
• Solution algorithms
• Example

Equilibrium Problem with Equilibrium Constraints (EPEC)

• General formulation
• Solution algorithms
• Example

Part 5: Mathematical decompositions

Benders decomposition and its variants

• Basic theory
• Variants
• Examples

Lagrange decomposition and its variants

• Basic theory
• Variants
• Examples

Hybrid decomposition and its variants

• Basic theory
• Variants
• Examples

Part 6: Some Applications in electricity-network optimization

Transmission capacity expansion: LP model

Transmission investment planning: MILP model

Transmission planning with quadratic generation cost function: MIQP

Transmission planning with ohmic loss function: MIQCQP

VPP trading in reserve and intra-day markets: Dynamic program and dual

dynamic program

Transmission investment regulation: Disjunctive program

TSO-DSO operational coordination: Logic-based program

Transmission investment under uncertainty: Stochastic program

Merchant transmission investment: LCP and MCP

Optimal hydropower bidding: MPEC

Nash equilibrium: EPEC

Part 7: The ABC of optimization modeling process

A: Convex model or nonconvex model?

B: For nonconvex models:

• Identify the hidden convex structure
• Convex approximation
• Convex relaxation
• Reformulation to one of the nonconvex models with special properties
• Solve your model using standard off-the-shelf solvers

C: How about original nonconvex structure? New theories and insights …

References:

• Lecture slides and research papers
• R. Baldick, Applied Optimization Formulation and algorithms for Engineering Systems, Cambridge University Press, 2006.

### Intended learning outcomes

After the course, the student should be able to:

• Understand and describe the theory of convex and nonconvex optimization problems,
• Examine and compare practical convex optimization models (LP, QCQP, SOCP, SP, DP),
• Examine and compare practical nonconvex optimization models (MILP, Quasiconvex optimization, IEOSP)
• Investigate and test selected practical nonconvex optimization models (Disjunctive program, Logic-based program, Stochastic program, Bilevel and Trilevel programs),
• Investigate and test applied compelementarity problems (LCP, MCP, MPEC, EPEC),
• Apply different varitions of decomposition algorithms (Benders decomposition, Lagrange decomposition, Hybrid decomposition, and their variants) for solving complex real-life optimization models,
• Understand different applications of the above models and solution algorithms in electricity-network optimization,
• Examine and practice the ABC of the optimization modeling process.

## Literature and preparations

### Specific prerequisites

No specific prerequisite.

### Recommended prerequisites

General familiarity with calculus, probability, and optimization theory is required.

### Equipment

The necessary software packages will be introduced in the beginning of the course.

### Literature

1. Lecture handouts and relevant research papers,
2. R. Baldick, Applied Optimization Formulation and algorithms for Engineering Systems, Cambridge University Press, 2006

## Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

P, F

### Examination

• EXA1 - Examination, 10.0 credits, grading scale: P, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Examination is based on a seminar, several course projects, a research paper, and a final report. Each student should give a seminar presentation of a selected topic relevant to the course. During the course several projects will be defined where students experience different optimization models and software packages. Also, a research paper based on the selected topic will be written by the student. The final examination is based on the final report delivered by the student.

### Other requirements for final grade

A final report which includes seminar presentation, course projects, and research paper.

### Opportunity to complete the requirements via supplementary examination

No information inserted

### Opportunity to raise an approved grade via renewed examination

No information inserted

### Ethical approach

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

## Further information

### Course room in Canvas

Registered students find further information about the implementation of the course in the course room in Canvas. A link to the course room can be found under the tab Studies in the Personal menu at the start of the course.

### Main field of study

This course does not belong to any Main field of study.

### Education cycle

Third cycle

No information inserted