Projection onto Convex Sets Definition 5(Projection).The projection x of a given point y onto a convex set is defined as the closest point inside the convex set.Formally, x=IIx[y]A arg minxexllx-yll. Theorem 1 (Pythagoras Theorem).Let C Rd be a convex set,y Rd and x IIxly Then for any zEX we have ly-zl≥Πxy-z Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 11
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 11 Projection onto Convex Sets
Convex Function Definition 6(Convex Function).A function f :R is convex if for any x,y∈X, a∈[0,1，f(1-a)x+ay)≤(1-a)f(x)+af(y). (g,f() (z,f(x)) a convex function Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 12
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 12 Convex Function a convex function
Convex/Concave Function Definition 6(Convex Function).A function f:R is convex if for any x,y∈X, a∈[0,1，f(1-a)x+ay)≤(1-a)f(x)+af(y). Definition 7(Concave Function).A function f:R is concave if for any x,y∈X, a∈0,1，f(1-a)x+ay)≥(1-a)f(x)+af(y). Both definitions have already assume a convex feasible domain. We focus on the"convex"language,since the negative of concave functions are convex. Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 13
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 13 Convex/Concave Function • Both definitions have already assume a convex feasible domain. • We focus on the “convex” language, since the negative of concave functions are convex
Convex Function f(y) l(y)f(x)+Vf(x)(y-x) "(xf(x)) If f is convex and differentiable,then f(x)+(Vf(x),y-x)<f(y)for all x,y∈domf. the first-order Taylor approximation of f near x A commonly used equivalent form:f(x)-f(y)<(Vf(x),x-y). Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 14
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 14 Convex Function
Convex Function How to check whether a function is convex or not? Theorem 2.A function f is convex if and only if dom f is convex and one of the following properties hold,for all x,y∈dom f and a∈[0,1， (i)Zeroth order condition:f((1-a)x+ay)(1-a)f(x)+af(y). (ii)First order condition:f(x)+(Vf(x),y-x)<f(y). (iii)Second order condition:V2f(x)0. Advanced Optimization(Fall 2023) Lecture 2.Convex Optimization Basics 15
Advanced Optimization (Fall 2023) Lecture 2. Convex Optimization Basics 15 Convex Function How to check whether a function is convex or not?