Mathematical Optimization

You are here

Credits
6
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
EIO
Basic concepts of optimization, different types of optimization problems, optimization algorithms and their theoretical properties are introduced. The theory sessions are complemented by practical sessions where the use of modeling languages and optimization packages are shown, as well as the implementation of optimization methods. All this oriented towards the application of these techniques to the solution of data science problems.

Teachers

Person in charge

  • Jordi Castro Pérez ( )

Others

  • F. Javier Heredia Cervera ( )

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0.2
Autonomous learning
5.8

Competences

Technical Competences

Technical competencies

  • CE3 - Analyze complex phenomena through probability and statistics, and propose models of these types in specific situations. Formulate and solve mathematical optimization problems.

Transversal Competences

Transversals

  • CT5 - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
  • CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
  • CT7 - Third language. Know a third language, preferably English, with an adequate oral and written level and in line with the needs of graduates.

Generic Technical Competences

Generic

  • CG1 - To design computer systems that integrate data of provenances and very diverse forms, create with them mathematical models, reason on these models and act accordingly, learning from experience.
  • CG2 - Choose and apply the most appropriate methods and techniques to a problem defined by data that represents a challenge for its volume, speed, variety or heterogeneity, including computer, mathematical, statistical and signal processing methods.

Objectives

  1. To solve data science problems previously formulated as mathematical optimization problems.
    Related competences: CE3, CT7, CG1, CG2,
  2. To know what a mathematical optimization problem is, what types of problems are there, and to have a basic knowledge of optimization algorithms.
    Related competences: CE3, CT5, CG1, CG2,
  3. To model mathematical optimization problems and to formulate them through modeling languages. To know how to choose the best method or "solver" according to the type of problem.
    Related competences: CT5, CT6, CT7, CG2,

Contents

  1. Unconstrained Optimization.
    Problem modeling. Optimality conditions. Convexity. Descent directions. Line search methods. The gradient or steepest descent method, and variants (stochastic gradients, etc.); convergence rate of the gradient method. The Newton method and globally convergent variants (e.g., modified Newton); Newton's convergence rate. Quasi-Newton Methods. Applications: neural networks, LASSO regression, etc.
  2. Constrained Optimization.
    Problem modeling. Convexity. Optimality conditions (Karush-Kuhn-Tucker conditions). Particular cases: linear optimization and quadratic optimization. Simplex method for linear optimization. Duality in optimization. Dual linear and quadratic problems. Applications: support vector machines, etc.
  3. Integer Optimization.
    Modeling of problems with binary and/or integer variables.. Combinatorial problems Properties of integer and combinatorial optimization problems. Solution methods: branch-and-bound, and cutting plans. Applications: clustering, k-median, classification, etc.

Activities

Activity Evaluation act


Development of the topic "Unconstrained Optimization"


Objectives: 2 3 1
Contents:
Theory
14h
Problems
7h
Laboratory
7h
Guided learning
1.4h
Autonomous learning
40.6h

Development of the topic "Constrained Optimization"


Objectives: 2 3 1
Contents:
Theory
12h
Problems
6h
Laboratory
6h
Guided learning
1.2h
Autonomous learning
34.8h

Development of the topic "Integer Optimization"


Objectives: 2 3 1
Theory
4h
Problems
2h
Laboratory
2h
Guided learning
0.4h
Autonomous learning
11.6h

Teaching methodology

Theoretical lectures where the concepts will be introduced, including exercises to fix these concepts (75%)
Problems and lab sessions (25%).

Evaluation methodology

There will be 3 marks (each in [0,10]):

Pr: lab mark.
ExP: midterm exam mark (for the 1st part of the course).
ExF: final exam mark (for the 2nd part of the course). The 1st part of the course is not evaluated in the final exam.

The final grade (NF) will be calculated as follows:

NF= 0.3 * Pr + 0.35 * ExP + 0.35 * ExF

Students with NF<5 will be allowed to do a re-evaluation exam. In the re-evaluation the only mark considered will be that of the re-evaluation exam (i.e., the lab mark is not used).

Bibliography

Basic:

Web links

Previous capacities

A first course on calculus and linear algebra. To implement algorithms in some programming language.