文档介绍：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 f 0 ( x ) subject to f i ( x ) ≤ b i , i = 1 , . . . , m ? x = ( x 1 , . . . , x n ) : optimization variables ? f 0 : R n → R : objective function ? f i : R n → R , i = 1 , . . . , m : constraint functions optimal solution x ? has smallest value of f 0 among all vectors that satisfy the constraints Introduction 1–2 Examples portfolio optimization ? variables: amounts invested in di?erent assets ? constraints: budget, max./min. investment per asset, mini mum 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 ?tting ? variables: model parameters ? constraints: prior information, parameter limits ? objective: measure of mis?t or prediction error Introduction 1–3 Solving optimization problems general optimization problem ? very di?cult to solve ? methods involve promise, . , very putation time, or not always ?nding the solution exceptions: certain problem classes can be solved e?ciently and reliabl y ? least-squares problems ? linear programming problems ? convex optimization problems Introduction 1–4 Least-squares minimize k Ax ? b k 22 solving least-squares problems ? analytical solution: x ?= ( A T A ) ? 1 A T b ? reliable and e?cient algorithms and software ? computation time proportional to n 2 k ( A ∈ R k × n ); less if structured ? a mature technology using least-squares ? least-squares problems are easy to recognize ? a few standard techniques increase ?exibility ( . , including weights, adding regularization terms) Introduction 1–5 Linear programming m