tailieunhanh - Bài giảng Tối ưu hóa nâng cao: Chương 6 - Hoàng Nam Dũng

Bài giảng "Tối ưu hóa nâng cao - Chương 6: Subgradients" cung cấp cho người học các kiến thức: Last time - gradient descent, subgradients, examples of subgradients, monotonicity, examples of non-subdifferentiable functions,. . | Bài giảng Tối ưu hóa nâng cao: Chương 6 - Hoàng Nam Dũng Subgradients Hoàng Nam Dũng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Last time: gradient descent Consider the problem min f (x) x for f convex and differentiable, dom(f ) = Rn . Gradient descent: choose initial x (0) ∈ Rn , repeat x (k) = x (k−1) − tk · ∇f (x (k−1) ), k = 1, 2, 3, . . . Step sizes tk chosen to be fixed and small, or by backtracking line search If ∇f Lipschitz, gradient descent has convergence rate O(1/ε) Downsides: I Requires f differentiable I Can be slow to converge 1 Outline Today: I Subgradients I Examples I Properties I Optimality characterizations 2 Basic inequality Basic inequality recall the basic inequality for differentiable convex functions: Recall that for convex and differentiable f , T T f (y )f≥ (y)f (x) + ∇f ≥ f (x) (x)(x) + ∇f −−x), (y (y x) ∀x, ∀yy∈∈dom dom(f f ). (x, f (x)) ∇f (x) −1 I The first-order approximation of f at x is a global lower • the first-order approximation of f at x is a global lower bound bound. • ∇f (x) defines a non-vertical supporting hyperplane to epi f at (x, f (x)): I ∇f defines a non-vertical supporting hyperplane to epi(f ) at T (x, f (x)) ∇f (x) y − x ≤ 0 ∀(y, t) ∈ epi f −1 y t! f (x)!! x ∇f −1 − ≤ 0, ∀(y , t) ∈ epi(f ). Subgradients t f (x) 4-2 3 Subgradients A subgradient of a convex function f at x is any g ∈ Rn such that f (y ) ≥ f (x) + g T (y − x), ∀y ∈ dom(f ). I Always exists (on the relative interior of dom(f )) I If f differentiable at x, then g = ∇f (x) uniquely I Same definition works for nonconvex f (however, subgradients need not exist). 4 Subgradients A subgradient of a convex function f at x is any g ∈ Rn such that f (y ) ≥ f (x) + g T (y − x), ∀y ∈ dom(f ). I Always exists (on the relative interior of dom(f )) Subgradient I If f differentiable