Optimització Matemàtica

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
EIO
S'introduixen el conceptes bàsics d'optimització, els diferents tipus de problemes d'optimització, els algoritmes d'optimització i les seves propietats teòriques. Les sessions de teoria es complementen amb sessions pràctiques on es mostra l'ús de llenguatges de modelització i paquets d'optimització, així com la implementació de mètodes d'optimització. Tot això orientat cap a l'aplicació d'aquestes tècniques a la solució de problemes de data science.

Professorat

Responsable

  • Jordi Castro Pérez (jordi.castro@upc.edu)

Altres

  • F. Javier Heredia Cervera (f.javier.heredia@upc.edu)

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Tècniques

Competències tècniques

  • CE3 - Analitzar fenòmens complexos mitjançant la probabilitat i l'estadística, i plantejar models d'aquests tipus en situacions concretes. Formular i resoldre problemes d'optimització matemàtica.

    • Competències Transversals

    Transversals

  • CT5 [Avaluable] - Ús solvent dels recursos d'informació. Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació en l'àmbit de l'especialitat i valorar de forma crítica els resultats d'aquesta gestió.
  • CT6 [Avaluable] - Aprenentatge autònom. Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement.

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Concebre sistemes computacionals que integren dades de procedències i formes molt diverses, construeixen amb ells models matemàtics, raonen sobre aquests models i actuen en conseqüència, aprenent de l'experiència.
  • CG2 - Elegir i aplicar els mètodes i tècniques més adequats a un problema definit per dades que representin un repte pel seu volum, velocitat, varietat o heterogeneïtat, inclosos mètodes informàtics, matemàtics, estadístics i de processament del senyal.

    • Objectius

    1. Solucionar problemes de ciència de dades prèviament formulats com a problemes d'optimització matemàtica.
      Competències relacionades: CE3, CT5, CT6, CG1, CG2,
    2. Saber què es un problema d'optimització matemàtica, quins tipus de problemes hi ha, i tenir un coneixement bàsic d'algoritmes d'optimització.
      Competències relacionades: CE3, CT5, CG1, CG2,
    3. Modelitzar problemes d'optimització matemàtica i formular-los a través de llenguatges de modelització. Saber escollir el mètode o "solver" més adequat segons el tipus de problema.
      Competències relacionades: CT5, CT6, CG2,

    Continguts

    1. Optimització sense restriccions.
      Modelització de problemes. Condicions d'optimalitat. Convexitat. Direccions de descens. Exploracions lineals. El mètode del gradient o de màxim descens i variants (gradients estocàstics, etc.); velocitat de convergència del mètode del gradient. El mètode de Newton i variants globalment convergents (p.e., Newton modificat); velocitat de convergència del mètode de Newton. Mètodes quasi-Newton. Aplicacions: xarxes neuronals, regressio LASSO, etc.
    2. Optimització amb restriccions.
      Modelització de problemes. Convexitat. Condicions d'optimalitat (condicions Karush-Kuhn-Tucker). Casos particulars: optimització lineal i optimització quadràtica. Mètode del símplex per a optimització lineal. Dualitat en optimització. Dual de problemes lineals i quadràtics. Aplicacions: support vector machines, etc.
    3. Optimització entera.
      Modelització de problemes amb variables binàries i/o enteres. Problemes combinatoris. Propietats dels problemes d'optimització entera i combinatòria. Mètodes de resolució: branch-and-bound, i plans de tall. Aplicacions: clustering, k-median, classificació, etc.

    Activitats

    Activitat Acte avaluatiu


    Desenvolupament del tema "Optimització sense restriccions"


    Objectius: 2 3 1
    Continguts:
    Teoria
    14h
    Problemes
    7h
    Laboratori
    7h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    42h

    Desenvolupament del tema "Optimització amb restriccions"


    Objectius: 2 3 1
    Continguts:
    Teoria
    12h
    Problemes
    6h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    36h

    Desenvolupament del tema "Optimització entera"


    Objectius: 2 3 1
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Metodologia docent

    Sessions teòriques on s'introduiran els conceptes i es faran exercicis que facilitin l'aprenentatge d'aquests conceptes (75%)
    Sessions de problemes i laboratoris (25%).

    Mètode d'avaluació

    Hi haurà 3 notes (cada una en [0,10]):

    Pr: nota de pràctiques de laboratori.
    ExP: nota examen parcial (correspon a la 1a part del curs, i és allliberatori).
    ExF: nota examen final (correspon a la 2a part del curs, i és de fet un 2n parcial). A l'examen final no s'avalua la 1a part del curs.

    La nota final (NF) es calcularà així:

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

    Els estudiants amb NF<5 (suspesos) podran fer un examen de reavaluació de tot el curs. A la reavaluació només es tindrà en compte la nota de l'examen de reavaluació (no es tindran en compte les pràctiques). La nota final de l'assignatura després de la reavaluació serà el màxim entre la nota de la convocatòria ordinària i la nota de l'examen de reavaluació.

    Bibliografia

    Bàsic

    Web links

    Capacitats prèvies

    Coneixements de càlcul i àlgebra lineal. Saber programar en algun llenguatge de programació.