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
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
To solve data science problems previously formulated as mathematical optimization problems.
Related competences:
CT5,
CT6,
CE3,
CG1,
CG2,
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:
CT5,
CE3,
CG1,
CG2,
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:
CT6,
CG2,
CT5,
Contents
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.
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.
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
ActivityEvaluation act
Development of the topic "Unconstrained Optimization"
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.