凸优化理论 课件

1–5
Solving convex optimization problems • no analytical solution • reliable and efficient algorithms • computation time (roughly) proportional to max{n3, n2m, F }, where F is cost of evaluating fi’s and their first and second derivatives • almost a technology
1–7
New applications since 1990
• linear matrix inequality techniques in control • circuit design via geometric programming • support vector machine learning via quadratic programming • semidefinite programming relaxations in combinatorial optimization • applications in structural optimization, statistics, signal processing, communications, image processing, quantum information theory, finance, . . .
Convex Optimization
Stephen Boyd (Stanford University)
Short Course, Harbin Institute of Technology July 13-18, 2012
Convex optimization — HIT 2012
1. Introduction
a a x0 aT x ≥ b
x0 x aT x = b
aT x ≤ b
• a is the normal vector • hyperplanes and halfspaces are convex
2–3
Euclidean balls and ellipsoids
(Euclidean) ball with center xc and radius r {xc + ru | u Ellipsoid with center xc {xc + Au | u with A square and nonsingular
Using convex optimization • often difficult to recognize • many tricks for transforming problems into convex form • surprisingly many problems can be solved via convex optimization
1–9
Nonlinear optimization
traditional techniques for general nonconvex problems involve compromises Local optimization methods (nonlinear programming) • find a point that minimizes f0 among feasible points near it • fast, can handle large problems • require initial guess • provide no information about distance to (global) optimum Global optimization methods • find the (global) solution • worst-case complexity grows exponentially with problem size these algorithms are often based on solving convex subproblems
1
Euclidean norm cone is called secondorder cone
t
0.5
0 1 0
1
x2
0 −1 −1
x1
norm balls and cones are convex
2–5
Polyhedra
solution set of finitely many linear inequalities and equalities Ax ( A ∈ Rm×n , C ∈ R p×n , b, Cx = d
• mathematical optimization • least-squares and linear programming • convex optimization • example • brief history
1–1
Mathematical optimization
minimize f0(x) subject to fi(x) ≤ 0, h i ( x ) = 0, variable x = (x1, . . . , xn) • complexity varies widely, depending on properties of fi, hi • general methods involve compromise (computation time, suboptimality) Exceptions: certain problem classes can be solved efficiently and reliably • least-squares • linear programming • convex optimization problems
Nonlinear convex optimization • around 1990 (Nesterov & Nemirovski): polynomial-time interior-point methods for nonlinear convex programming • since 1990: extensions and high-quality software packages
1–8
Interior-point methods
Linear programming • 1984 (Karmarkar): first practical polynomial-time algorithm • 1984-1990: efficient implementations for large-scale LPs
is componentwise inequality)
a1 a2
a5P a3 a4源自Examples (one convex, two nonconvex sets)
Convex cone x1, x2 ∈ C, θ1 , θ2 ≥ 0 =⇒ θ1 x1 + θ2 x2 ∈ C
2–2
Hyperplanes and halfspaces
Hyperplane: set of the form {x | aT x = b} with a = 0 Halfspace: set of the form {x | aT x ≤ b} with a = 0
1–2
i = 1, . . . , m i = 1, . . . , p
Least-squares
minimize Ax − b
2 2
• analytical solution: x⋆ = (AT A)−1AT b • reliable and efficient algorithms and software • a widely used technology Using least-squares • least-squares problems are easy to recognize • standard techniques increase flexibility (weights, regularization, . . . ) • computation time proportional to n2p (for A ∈ Rp×n); less if structured
1–10
Convex optimization — HIT 2012
2. Convex sets
• definition • some important examples • operations that preserve convexity
2–1
Definition
Convex set: contains line segment between any two points in the set x1, x2 ∈ C, 0≤θ≤1 =⇒ θx1 + (1 − θ)x2 ∈ C
1–6
History
• 1940s: linear programming minimize cT x subject to aT i x ≤ bi , • 1950s: quadratic programming • 1990s: semidefinite programming, second-order cone programming, quadratically constrained quadratic programming, robust optimization, sum-of-squares programming, . . . i = 1, . . . , m
2 2
≤ 1}
≤ 1}
xc
2–4
Norm balls and norm cones