NO EXISTEN CAMBIOS
La guía de la asignatura ha sido actualizada con los cambios que aquí se mencionan.
NOMBRE DE LA ASIGNATURA |
OPTIMIZACIÓN CONVEXA EN CIENCIA DE DATOS |
CÓDIGO |
21520086 |
CURSO ACADÉMICO |
2022/2023 |
TÍTULOS DE MASTER EN QUE SE IMPARTE |
MÁSTER UNIVERSITARIO EN MATEMÁTICAS AVANZADAS
|
TIPO |
CONTENIDOS |
Nº ECTS |
7,5 |
HORAS |
187,5 |
PERIODO |
SEMESTRE 1
|
IDIOMAS EN QUE SE IMPARTE |
CASTELLANO |
Aunque el término << ciencia de datos >> no empezó a emplearse hasta la década de los ochenta del siglo pasado, veinte años antes el matemático John Tukey había expuesto en su artículo fundacional The Future of Data Analysis una descripción de la disciplina, que incluiría, << entre otras cosas: procedimientos para analizar datos, técnicas para interpretar los resultados de tales procedimientos, formas de planificar la recopilación de datos para hacer su análisis más fácil, más preciso o más exacto, y toda la maquinaria y los resultados de la estadística (matemática) que se aplican al analizar datos >>
Si añadimos la disponibilidad de ingentes cantidades de datos, el enorme aumento de la potencia computacional y las prácticamente ilimitadas capacidades para la transferencia y almacenamiento que se han producido en los últimos cincuenta años, podremos hacernos una idea de lo que significa << ciencia de datos >>.
En el mencionado artículo, Tukey dedica un apartado a responder a la pregunta << ¿Por qué la optimización?>> (el apartado anterior se titula << Los peligros de la optimización >>, pero nos interesa bastante menos comentarlo, si queremos dar valor al contenido de esta asignatura). Es natural y deseable, dice, que un matemático optimice: así, centra la atención en un pequeño subconjunto de todas las posibilidades que, a menudo, conducen a principios generales y alienta a afinar los conceptos, particularmente cuando los óptimos intuitivamente erróneos se consideran como razones para reexaminar conceptos y criterios. Para Tukey, el peligro solo aparece cuando los resultados se toman demasiado en serio. La solución de un problema de optimización sería más una guía que una respuesta.
Entendiendo así la importancia de la optimización, sin tomar sus resultados demasiado en serio, ¿por qué poner el énfasis en la optimización convexa (la que tiene función objetivo y restricciones convexas, en nuestro caso, siempre en dimensión finita)? Tenemos razones intrínsecas (como la elegancia de los resultados matemáticos), extrínsecas (por ejemplo, muchos problemas de aprendizaje automático requieren la minimización de funciones convexas, como pueden ser las normas) o, lo que es más importante, razones puramente prácticas (aunque no encontraremos normalmente soluciones cerradas, como en el ajuste por mínimos cuadrados, existen algoritmos eficientes para resolver la gran mayoría de los problemas convexos).
En este último sentido, sería como aquel que busca alrededor de una farola sus llaves perdidas cuando se acerca un vecino a ayudarle y, al no hallarlas, le pregunta si está seguro de haberlas perdida ahí, a lo que le responde el primero que no, que las ha perdido en el parque, pero que las busca bajo la farola porque ahí hay luz y en el parque no. Lo que ocurre es que, en nuestro caso, la calle parece estar plagada de pequeñas linternas, que podemos encontrar gracias a la luz de la farola y con las que podremos ir a buscar las llaves al parque. Es decir, no podemos olvidar el papel que pueden desempeñar los métodos de la optimización convexa en los problemas no convexos, bien aplicados localmente, en combinación con otros procedimientos o bien para hallar soluciones heurísticas o acotaciones de las soluciones.
Para hacernos una idea del tipo de problemas que se tratan en esta asignatura, supongamos que queremos diseñar un algoritmo que permita distinguir fotografías de perros de fotografías de gatos. Un enfoque simple e ingenuo, hasta cierto punto, consistiría en considerar cada fotografía como una matriz (bidimensional, si es en escala de grises o de más dimensiones, si la fotografía es a color); extraeríamos, un poco a ciegas, N características de cada una de esas matrices correspondientes a una gran cantidad de fotos, ya clasificadas como de perros o de gatos (por decir algo, pensemos en la media de los valores de sus celdas, las medias de los valores de sus columnas, la desviación típica de esos valores, etc.). De esa manera, obtendríamos de cada foto un vector de un espacio N dimensional. Si encontramos un hiperplano de ese espacio N dimensional (a fin de cuentas, un vector N dimensional) que separe los puntos correspondientes a perros de los puntos correspondientes a gatos, tendremos un procedimiento muy eficiente para clasificar una nueva fotografía: se convierte en vector N dimensional la nueva fotografía y se introduce en la ecuación del hiperplano (solo sumas y multiplicaciones), de manera que el resultado positivo corresponderá a << perro >> y el negativo, a << gato >>.
Simplificando mucho, el proceso de cálculo del hiperplano sería el aprendizaje y se puede formular como un problema de optimización convexa.
La asignatura de Optimización Convexa en Ciencia de datos puede resultar interesante para los graduados en Matemáticas que, queriendo profundizar en sus conocimientos de análisis convexo, se sientan inclinados hacia la matemática aplicada (por ejemplo, para analistas de datos). Pero también, resultará muy útil para los ingenieros y graduados en otras diciplinas científico-tecnológicas que trabajen o deseen trabajar en analítica de datos y no se conformen con implementar paquetes informáticos preprogramados sin comprender lo que hacen, sus posibilidades y limitaciones.
De todo lo anterior se deduce que Optimización Convexa en Ciencia de datos desempeña un papel básico en la especialidad Matemática Aplicada del Máster en Matemáticas Avanzadas. Aunque podemos hallar vínculos con todas las asignaturas de la especialidad, la dependencia más robusta se da con las dos asignaturas que mejor la complementan Optimización en Espacios de Banach e Introducción Métodos Numéricos en Problemas Variacionales, ambas asignaturas de optimización no lineal en dimensión infinita.
Además de la adquisición de unos conocimientos básicos de análisis convexo, se pretende que, al completar el curso, el estudiante sea capaz de seguir mejorando su competencia matemática de forma autónoma y continuada, consultando, tanto textos escritos, como bases de datos en línea. Se procurará generar en los alumnos una actitud positiva hacia la mejora e innovación de los métodos matemáticos que se aplican en la investigación aplicada y en el ejercicio profesional.
Para la correcta asimilación de los contenidos de la asignatura, se requieren los conocimientos en álgebra lineal y análisis matemático que se adquieren habitualmente en los dos primeros ciclos de la enseñanza universitaria de las carreras de ciencias e ingenierías. En particular, es necesaria cierta soltura con los siguientes conceptos:
1. Espacio real n-dimensional
1.1. Producto interior, norma euclidea, ángulos.
1.2. Otras normas.
2. Análisis Matemático:
2.1. Conceptos topológicos elementales.
2.2. Funciones. Continuidad.
2.3. Funciones vectoriales de varias variables.
2.4. Derivadas parciales, gradiente.
2.5. Regla de la cadena.
2.6. Matriz hessiana
3. Álgebra lineal:
3.1. Aplicaciones lineales y matrices; rango y núcleo
3.2. Autovalores. Diagonalización de matrices.
3.3. Matrices definidas y semidefinidas positivas
4. Estadística y probabilidad básicas.
5. Ajuste por mínimos cuadrados.
6. Programación lineal.
7. Comprensión de textos científico-técnicos escritos en inglés.
Horario
Las consultas pueden realizarse, preferentemente, los jueves de 10 a 14h, para el profesor Juan Perán Mazón o bien los martes de 10 a 14h, para la profesora Elvira Hernández García. Téngase en cuenta que durante las semanas de exámenes el equipo docente de la asignatura puede estar en comisión de servicios en alguno de los tribunales, por lo que no sería posible la atención a los alumnos durantes estos periodos.
Procedimiento
Para consultas con contenido matemático, por orden de preferencia:
- Foros del curso virtual
- Correo electrónico: jperan@ind.uned.es (Juan Perán Mazón) o ehernandez@ind.uned.es (Elvira Hernández García)
- Entrevista. Despacho 2.51 (Juan Perán Mazón) o 2.37 (Elvira Hernández García) de la Escuela de Ingenieros Industriales de la UNED. Se ruega concertar cita telefónicamente.
- Teléfono: 91 398 7915 (Juan Perán Mazón) o 913987992 (Elvira Hernández García) La llamada puede ser desviada a un buzón de voz. Por favor, deje su nombre, asignatura, asunto que quiere tratar y número de teléfono donde puede ser localizado.
Para otras consultas (programa, evaluación, orientaciones metodológicas, bibliografía, etc.), por orden de preferencia:
- Entrevista personal o por videoconferencia. Se ruega concertar cita telefónicamente o por correo electrónico.
- Correo electrónico.
- Teléfono.
Dirección postal
Departamento de Matemática Aplicada
Escuela Técnica Superior de Ingenieros Industriales.
C/ Juan del Rosal, 12.
28040 Madrid
COMPETENCIAS BÁSICAS
CB6 - Poseer y comprender conocimientos que aporten una base u oportunidad de ser originales en el desarrollo y/o aplicación de ideas, a menudo en un contexto de investigación.
CB7 - Que los estudiantes sepan aplicar los conocimientos adquiridos y su capacidad de resolución de problemas en entornos nuevos o poco conocidos dentro de contextos más amplios (o multidisciplinares) relacionados con su área de estudio.
CB8 - Que los estudiantes sean capaces de integrar conocimientos y enfrentarse a la complejidad de formular juicios a partir de una información que, siendo incompleta o limitada, incluya reflexiones sobre las responsabilidades sociales y éticas vinculadas a la aplicación de sus conocimientos y juicios.
CB9 - Que los estudiantes sepan comunicar sus conclusiones y los conocimientos y razones últimas que las sustentan a públicos especializados y no especializados de un modo claro y sin ambigüedades.
CB10 - Que los estudiantes posean las habilidades de aprendizaje que les permitan continuar estudiando de un modo que habrá de ser en gran medida autodirigido o autónomo.
COMPETENCIAS GENERALES
CG1 - Adquirir conocimientos generales avanzados en tres de las principales áreas de las matemáticas.
CG2 - Conocer algunas de las líneas de investigación dentro de las áreas cubiertas por el Máster.
CG3 - Adquirir la metodología de la investigación en matemáticas.
CG4 - Aprender a redactar resultados matemáticos.
COMPETENCIAS ESPECÍFICAS
CE1 - Saber abstraer las propiedades estructurales de los objetos matemáticos, distinguiéndolas de aquellas puramente ocasionales. Ser capaz de utilizar un objeto matemático en diferentes contextos.
CE2 - Conocer los problemas centrales, la relación entre ellos, las técnicas más adecuadas en los distintos campos de estudio, y las demostraciones rigurosas de los resultados relevantes.
Conocimientos.
- Conocer los conceptos básicos del análisis convexo (conjuntos convexos, funciones y problemas de optimización).
- Entender las técnicas básicas de optimización convexa: mínimos cuadrados, programas lineales y cuadráticos, programación semidefinida.
- Conocer la teoría básica sobre condiciones de optimalidad, teoría de la dualidad, teoremas de alternativa y aplicaciones.
- Saber cómo funcionan los algoritmos de resolución de problemas convexos
Destrezas y habilidades.
- Reconocer los problemas de optimización convexa que surgen en las aplicaciones.
- Modelar problemas o reformularlos como problemas convexos, cuando sea posible.
- Implementar informáticamente los algoritmos estudiados e interpretar correctamente los resultados numéricos obtenidos.
- Ser capaz de adaptar los métodos estudiados en otros campos de investigación o en aplicaciones.
Tema 0. Repaso de matemáticas
- Normas en Rn
- Producto interior, norma euclidea, ángulos.
- Normas y distancias.
- Equivalencia de normas,
- Norma de un operador lineal.
- Abiertos y cerrados.
- Supremo e ínfimo.
- Funciones. funciones continuas y cerradas.
- Derivadas, gradiente, regla de la cadena, hessiana.
- Rango y espacio nulo.
- Diagonalización de una forma cuadrática
- Complementos de álgebra lineal.
Tema 1. Introducción y motivación
1. Optimización matemática.
2. Mínimos cuadrados y programación lineal.
3. Optimización convexa.
4. Optimización no-lineal.
5. Notación.
Tema 2. Conjuntos convexos.
1. Conjuntos afines y convexos. Ejemplos importantes.
2. Operaciones que preservan la convexidad.
3. Desigualdades generalizadas.
4. Separación por hiperplanos e hiperplanos soporte.
5. Conos duales y desigualdades generalizadas.
Tema 3. Funciones convexas.
1. Propiedades básicas y ejemplos.
2. Operaciones con funciones que preservan la convexidad.
3. Función conjugada.
4. Funciones cuasi-convexas.
5. Funciones log-cóncavas y log-convexas.
6. Convexidad respecto de desigualdades generalizadas.
Tema 4. Problemas de optimización convexa
1. Problemas de optimización.
2. Problemas convexos.
3. Problemas de optimización lineal.
4. Problemas cuadráticos.
5. Programación geométrica.
6. Restricciones por desigualdades generalizadas.
7. Optimización vectorial.
Tema 5. Dualidad
1. Función dual de Lagrange
2. Problema dual de Lagrange.
3. Interpretación geométrica.
4. Condiciones optimalidad.
5. Perturbaciones y análisis de sensibilidad.
6. Desigualdades generalizadas.
Tema 6. Aplicaciones. Aproximación y ajuste.
- Aproximación en norma.
- Soluciones de sistemas lineales con norma mínima.
- Aproximación regularizadora.
- Aproximación robusta.
- Ajuste de funciones e interpolación.
Tema 7. Aplicaciones. Inferencia estadística.
- Estimación paramétrica.
- Estimación no paramétrica.
- Detector óptimo y contraste de hipótesis.
- Cotas de Chebychev y Chernoff.
- Diseño de experimentos.
Tema 8. Aplicaciones. Problemas geométricos.
- Proyección sobre un conjunto.
- Distancia entre conjuntos.
- Problemas con distancias euclideas y ángulos,
- Elipsoides de volumen extremal.
- Centrado
- Clasificación.
- Colocación y ubicación.
- Floor planning
Tema 9. Algoritmos.
Optimización sin restricciones.
- Métodos de descenso.
- Método de descenso del gradiente.
- Método del descenso rápido o de la máxima pendiente.
- Método de Newton.
Optimización con restricciones .
- Restricciones de igualdad.
- Método de Newton con restricciones de igualdad
- Restricciones mediante inecuaciones.
- Métodos del punto interior.
La asignatura se imparte con la metodología de la enseñanza a distancia propia de la UNED. Las principales herramientas son el texto-base y el curso virtual, en particular, sus foros de contenidos, en los que el alumno deberá consignar regularmente sus avances y dificultades. La metodología es, por lo tanto, individualizada, de manera que el alumno y el profesor deben conversar en los foros al menos una vez a la semana. El papel del profesor será tanto de instructor, como de controlador del ritmo de avance. Así mismo, se esforzará en animar a los alumnos para evitar la desmoralización que amenaza al estudiante que estudia solo.
Se pedirá a los alumnos que vayan completando, según avance su estudio, una agenda de trabajo (dentro del curso virtual) en la que anotarán todas y cada una de las sesiones que hayan dedicado al estudio, concretando su duración, dificultades y metas alcanzadas.
La metodología de trabajo es muy sencilla: hay que dedicar aproximadamente una hora seguida a la lectura de cada epígrafe (2.1, 2.2, etc., no se incluyen en esta estimación los epígrafes de la introducción, que son mucho más breves); después, durante otra hora, más o menos, hay que hacer tres o cuatro ejercicios de los propuestos para esa materia.
TIPO DE PRUEBA PRESENCIAL
|
Tipo de examen |
Tipo de examen |
No hay prueba presencial |
CARACTERÍSTICAS DE LA PRUEBA PRESENCIAL Y/O LOS TRABAJOS |
CARACTERÍSTICAS DE LA PRUEBA PRESENCIAL Y/O LOS TRABAJOS
|
Requiere Presencialidad |
Requiere Presencialidad |
No |
Descripción |
Descripción |
En esta asignatura no se contempla examen presencial. En su lugar, el estudiante elaborará un proyecto o trabajo científico que deberá defender ante el equipo docente y sus compañeros mediante videoconferencia.
Se permitirá una amplia opcionalidad en el tema y la metodología. En general, se distinguen dos tipos de trabajos
- Ampliaciones de la teoría (por ejemplo, a espacios de dimensión infinita),
- Implementaciones informáticas de problemas concretos de analítica de datos, en los que se apliquen los contenidos del curso. En este último caso, se empleará CVX sobre MATLAB o CVXPY sobre Phyton.
El trabajo constará de una memoria escrita (elaborada en LaTex) y una presentación (Beamer o similar) que servirá de apoyo a la exposición oral.
La memoria escrita tendrá una extensión de veinte páginas, como mínimo. La exposición oral durará entre quince y veinte minutos. La sesión de defensa concluirá con un breve debate entre el estudiante el equipo docente sobre el contenido del trabajo.
Podrán consultar sus dudas al respecto en el curso virtual.
|
Criterios de evaluación |
Criterios de evaluación |
- Originalidad, relevancia y dificultad del tema elegido.
- Calidad, rigor y precisión de la exposición matemática (enunciados, demostraciones, algoritmos, etc.)
- Calidad de presentación de la memoria escrita (tipografía, normas gramaticales y ortográficas, etc.)
- Orden y claridad en la estructura de la memoria escrita y en la presentación oral.
- Habilidad comunicativa en la defensa del trabajo mediante videoconferencia
- Capacidad para debatir y argumentar.
|
Ponderación de la prueba presencial y/o los trabajos en la nota final |
Ponderación de la prueba presencial y/o los trabajos en la nota final |
El trabajo final representa entre un 50% y un 70% de la nota final, como se detalla en los siguientes apartados. |
Fecha aproximada de entrega |
Fecha aproximada de entrega |
15 de febrero / 15 de septiembre |
Comentarios y observaciones |
Comentarios y observaciones |
Fechas de entrega aproximadas:
- Segunda quincena de febrero, para la convocatoria ordinaria.
- Segunda quincena de septiembre, para la convocatoria extraordinaria.
|
PRUEBAS DE EVALUACIÓN CONTINUA (PEC) |
PRUEBAS DE EVALUACIÓN CONTINUA (PEC)
|
¿Hay PEC? |
¿Hay PEC? |
Si,PEC no presencial |
Descripción |
Descripción |
Hay dos pruebas de evaluación continua, según se describe en el PLAN DE TRABAJO.
Ambas pruebas consistirán en la resolución de un ejercicio de cada tema del bloque correspondiente, para lo que se dispondrá de cuatro horas contadas desde el momento en el que se descargue el enunciado. El estudiante podrá elegir el momento de inicio de la prueba, dentro del plazo de cuatro días establecido por el equipo docente (se incluirá un fin de semana en esos cuatro días). Se podrá emplear todo tipo de material, pero no se podrá consultar con nadie durante la realización de la prueba. Las cuatro horas de la prueba deben transcurrir sin interrupción.
|
Criterios de evaluación |
Criterios de evaluación |
Los indicadores de evaluación se publicarán en el curso virtual.
La rúbrica incluirá el nivel de conocimientos del contenido, así como la calidad de la presentación.
El rigor utilizado y los argumentos considerados serán parte fundamental en los criterios de evaluación de todas las actividades evaluables.
|
Ponderación de la PEC en la nota final |
Ponderación de la PEC en la nota final |
La primera PEC tiene un peso del 20% y la segunda, del 30% |
Fecha aproximada de entrega |
Fecha aproximada de entrega |
PEC1: octubre o noviembre / PEC2: diciembre |
Comentarios y observaciones |
Comentarios y observaciones |
Las fechas aproximadas, el formato y el contenido de las pruebas de evaluación continua a distancia (PEC) están desarrolladas en el PLAN DE TRABAJO y se ampliarán en el curso virtual.
|
OTRAS ACTIVIDADES EVALUABLES
|
¿Hay otra/s actividad/es evaluable/s? |
¿Hay otra/s actividad/es evaluable/s? |
Si,no presencial |
Descripción |
Descripción |
La entrega de los tres informes de estudio señalados en el Plan de Trabajo se valorará con una nota global comprendida entre 0 y 1 punto, que se añadirá al resultado de la evaluación de las pruebas de evaluación continua y del trabajo final.
|
Criterios de evaluación |
Criterios de evaluación |
Oiginalidad de los comentarios del informe, así como la calidad y la puntualidad en su presentación.
|
Ponderación en la nota final |
Ponderación en la nota final |
La nota de esta actividad se añade; no se aplica ninguna media ponderada. Por lo tanto, solo puede incrementar la calificación, nunca reducirla. |
Fecha aproximada de entrega |
Fecha aproximada de entrega |
Informe 1: octubre. Informe 2: noviembre. Informe 3: diciembre, |
Comentarios y observaciones |
Comentarios y observaciones |
|
¿Cómo se obtiene la nota final?
|
Nota final en la convocatoria ordinaria de febrero = Mín(10, 0.2 PEC1 + 0.3 PEC2 + 0.5 TFF + IF),
Nota final en la convocatoria extraordinaria de septiembre = Mín(10, 0.12 PEC1 + 0.18 PEC2 + 0.7 TFS + IF),
en donde
- PEC1, en el intervalo [0,10], es la nota de la primera PEC. El mismo valor en las convocatorias de febrero y septiembre.
- PEC2, en el intervalo [0,10], es la nota de la segunda PEC. El mismo valor en las convocatorias de febrero y septiembre.
- TFF, en el intervalo [0,10], es la nota del trabajo final presentado en la convocatoria ordinaria de febrero.
- TFS en el intervalo [0,10], es la nota del trabajo final presentado en la convocatoria extraordinaria de septiembre.
- IF, en el intervalo [0,1], es la nota global de los tres informes. El mismo valor en las convocatorias de febrero y septiembre.
No hay ninguna actividad obligatoria. Las actividades que no se realicen se evalúan con cero puntos para aplicar la fórmula anterior. Es necesario que la nota final alcance los 5 puntos para superar la asignatura.
|
Se trata de un manual escrito, en lengua inglesa, para servir como libro de texto para posgraduados en áreas cientifíco-técnicas. El autor ha procurado limitar al máximo los prerrequisitos matemáticos, de manera que el texto sea accesible para estudiantes sin una formación avanzada en matemáticas. Los conceptos matemáticos que pudieran no haberse estudiado en los programas habituales de los graduados en ingeniería o en ciencias no matemáticas se incluyen en el texto como anexos.
En el momento de redactar esta guía, se puede acceder libremente al texto vía web en la dirección:
http://www.ee.ucla.edu/~vandenbe/cvxbook/
El equipo docente agradece a los autores su generosidad al propocionar gratuitamente el acceso a su libro.
- Hiriart-Urruty, J.-B.; C. Lemaréchal: Fundamentals of Convex Analysis. Ed. Springer-Verlag. 2001. ISBN(10) 3-540-42205-6 ISBN(13) 978-3-540-42205-1
Se trata de una de las introducciones al Análisis convexo escritas con mayor claridad; sin embargo, cubre temas más avanzados que los propuestos para la asignatura.
- Rockafellar, R.T.. Convex Analysis . Ed. Princeton University Press. 1997
Es la referencia canónica en Análisis Convexo. No obstante, se trata de un libro más difícil de leer que los de Boyd y Vandenberghe o Hiriart-Urruty y Lemaréchal.
- Stephen Boyd, Lieven Vandenberghe: Introduction to Applied Linear Algebra. Vectors, Matrices, and Least Squares 2018 Cambridge University Press. ISBN: 9781316518960.
Este magnífico libro podría usarse como texto para un primer curso de álgebra lineal aplicada a la ciencia de datos.
Curso virtual
Tal y como se detalla bajo el epígrafe de Plan de trabajo, el curso virtual desempeña un papel esencial en la docencia de esta asignatura. La herramienta que más utilizaremos será la de los foros, en donde los alumnos podrán plantear sus dudas e intervenir en los hilos iniciados por otros compañeros al plantear sus dudas.
Videoconferencia
Según cómo se vaya desarrollando el curso, los alumnos podrán plantear la posibilidad de realizar videoconferencias.
Otros
En el momento de redactar esta guía, se podían encontrar en la dirección
http://www.stanford.edu/class/ee364a/videos.html
los vídeos de las clases del profesor Stephen Boyd en la Universidad de Stanford.
Entrega de actividades.
Todos los documentos que se entreguen deberán elaborarse en LaTex. Más detalles en el curso virtual.
Software para prácticas.
Se utilizará CVX sobre MATLAB o CVXPY sobre Phyton para resolver ejericicios de optimización convexa. En el curso virtual se procurará aportar referencias de consulta.