tailieunhanh - Mathematical optimization

mathematical optimization least-squares and linear programming convex optimization example course goals and topics nonlinear optimization brief history of convex optimization | Convex Optimization — Boyd & Vandenberghe 1. Introduction mathematical optimization • least-squares and linear programming • convex optimization • example • course goals and topics • nonlinear optimization • brief history of convex optimization • 1–1 Mathematical optimization (mathematical) optimization problem minimize f0(x) subject to f (x) b , i = 1, . . . , m i ≤ i x = (x , . . . , x ): optimization variables • 1 n f : Rn R: objective function • 0 → f : Rn R, i = 1, . . . , m: constraint functions • i → ? optimal solution x has smallest value of f0 among all vectors that satisfy the constraints Introduction 1–2 Examples portfolio optimization variables: amounts invested in different assets • constraints: budget, max./min. investment per asset, minimum return • objective: overall risk or return variance • device sizing in electronic circuits variables: device widths and lengths • constraints: manufacturing limits, timing requirements, maximum area • objective: power consumption • data fitting variables: model parameters • constraints: prior information, parameter limits • objective: measure of misfit or prediction error • Introduction 1–3 Solving optimization problems general optimization problem very difficult to solve • methods involve some compromise, ., very long computation time, or • not always finding the solution exceptions: certain problem classes can be solved efficiently and reliably least-squares problems • linear programming problems • convex optimization problems • Introduction 1–4 Least-squares minimize Ax b 2 k − k2 solving least-squares problems analytical solution: x? = (AT A)−1AT b • reliable and efficient algorithms and software • computation time proportional to n2k (A Rk×n); less if structured • ∈ a mature technology • using least-squares least-squares problems are easy to recognize • a few standard techniques increase flexibility (., including weights, • adding regularization terms) Introduction 1–5 Linear programming minimize cT x subject to .