Mathematical Optimization

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

Others

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
6

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 [Avaluable] - 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 [Avaluable] - 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.

    • 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, CT5, CT6, 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, 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
    0h
    Autonomous learning
    42h

    Development of the topic "Constrained Optimization"


    Objectives: 2 3 1
    Contents:
    Theory
    12h
    Problems
    6h
    Laboratory
    6h
    Guided learning
    0h
    Autonomous learning
    36h

    Development of the topic "Integer Optimization"


    Objectives: 2 3 1
    Theory
    4h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    12h

    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). The final mark of the subject after the re-evaluation will be the maximum between the mark of the ordinary exam and the mark of the re-evaluation exam.

    Bibliography

    Basic

    Web links

    Previous capacities

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