版像 NJUAT 南京大学 人工智能学院 SCHODL OF ARTIFICIAL INTELUGENCE,NANJING UNIVERSITY Lecture 2.Convex Optimization Basics Advanced Optimization(Fall 2023) Peng Zhao zhaop@lamda.nju.edu.cn Nanjing University
Lecture 2. Convex Optimization Basics Peng Zhao zhaop@lamda.nju.edu.cn Nanjing University Advanced Optimization (Fall 2023)
(Constrained)Optimization Problem We adopt a minimization language min f(x) s.t.x∈X optimization variable x e Rd objective function:f:RdR feasible domain:C Rd Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 2
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 2 (Constrained) Optimization Problem • We adopt a minimization language
Unconstrained Optimization The optimization variable is feasible over the whole Ra-space. min f(x) s.t.x∈Rd It is one of the most basic forms of mathematical optimization and serves as the foundations. ---"any optimization problem can be regarded as an unconstrained one" min :f(x) min h(x)f(x)+6x(x) s.t.x∈X s.t.x∈Rd barrier/indicator function 0, 6x(x)= x∈X, 00, x生X. Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 3
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 3 Unconstrained Optimization • • It is one of the most basic forms of mathematical optimization and serves as the foundations. --- “any optimization problem can be regarded as an unconstrained one” barrier/indicator function
Convex Optimization This lecture focuses on the following simplified setting: Language:minimization problem Objective function:continuous and convex Feasible domain:a convex subset of Euclidean space ·What is a convex set? What is a convex function? ·How to minimize? Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 4
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 4 Convex Optimization • This lecture focuses on the following simplified setting: • Language: minimization problem • Objective function: continuous and convex • Feasible domain: a convex subset of Euclidean space • What is a convex set? • What is a convex function? • How to minimize?
Outline Convex Set and Convex Function Convex Optimization Problem Optimality Condition ·Function Properties Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 5
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 5 Outline • Convex Set and Convex Function • Convex Optimization Problem • Optimality Condition • Function Properties
Part 1.Convex Set and Convex Function 。Definition ·Ball and Ellipsoid Convex Hull and Projection Convex/Concave Function Zeroth,First and Second-order Condition Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 6
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 6 Part 1. Convex Set and Convex Function • Definition • Ball and Ellipsoid • Convex Hull and Projection • Convex/Concave Function • Zeroth, First and Second-order Condition
Convex Set Definition 1(Convex Set).A set Y is convex if for any x,y e,all the points on the line segment connecting x and y also belong to t,i.e., a∈0,1，ax+(1-a)y∈X. convex sets? X X Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 7
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 7 Convex Set convex sets?
Examples .A line segment is convex. ·Aray,which has the form{xo+fv|θ≥O},where v≠0，is convex. Any subspace is convex. Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 8
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 8 Examples
Convex Set Definition 2(Ball).A(Euclidean)ball (or just ball)in Rd has the form B(xc;r)={xc+ruull2 <1}. Definition 3(Ellipsoids).A ellipsoid in Rd has the form E(xe,A)={xe+Au|Iu‖2≤1}， where A is assumed to be symmetric and positive definite. Au Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 9
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 9 Convex Set
Convex Set Definition 4(Convex Hull).The convex hull of a set t,denoted conv t,is the set of all convex combinations of points in A: conv={0x1+…+0xkx:∈X,0:≥0，i∈[k],01+…+0=1. Examples: Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 10
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 10 Convex Set Examples: