2.098/15.093J:Recitation 10 Xuan Vinh Doan 2004.11.19 1、凸性寸 凸集 设集合ScR",如果对所有的x,y∈S.有元x+(1-2)y∈S,元∈0，】，则S 为R”上的凸集。 性质 两个凸集的交集仍为凸集。 凸函数 设∫：R"→R,若有 f(x+(1-iy)s if(x)+(1-a)f(y) Vx,yE R",iE[0.1] 则移了为R上的凸函数： 性质 两个凸函数的和仍为凸函数。 若f(x)为凸函数，则gy)=f(Ax+b)也是凸函数。 f为凸函数，ep列f={(x,4)eRIH2f(x)}为R上的凸子集. 如何判定一个凸函数 设函数f二阶可微，即梯度可f(x)和ss1an矩库T2f(x)存在，有 ).r) ol-ga )=)+6-到+-到f-+心非-，当→3 时，R(x)+0, 当且仅当ssian矩阵对所有x华正定时，f(x)为凸函数。 对于实对称矩阵M,下列结论是等价的 1.矩阵AM半正定(PSD) 2.对所有xER",都有x你20
2.098/15.093J：Recitation 10 Xuan Vinh Doan 2004.11.19 1、 凸性∀ 凸集 设集合 S ⊂ Rn ，如果对所有的 x, y ∈ S ,都有 λx + (1− λ) y ∈ S ,λ ∈[0,1] ，则 为 S n R 上的凸集。 性质 两个凸集的交集仍为凸集。 凸函数 设 f R R ,若有 : n → ( ) λ + ( ) 1− λ ≤ λ ( )+ (1− λ) ( ) ∀ , ∈ ,λ ∈[ ] 0,1 n f x y f x f y x y R 则称 f 为 n R 上的凸函数。 性质 两个凸函数的和仍为凸函数。 若 f (x) 为凸函数，则 g( y) := f (Ax + b) 也是凸函数。 f 为凸函数， {( , ) | ( )}为 1 epif x R f x n = ∈ ≥ + µ µ n+1 R 上的凸子集。 如何判定一个凸函数 设函数 f 二阶可微，即梯度∇f (x) 和 Hessian 矩阵 ( ) 存在，有 2 ∇ f x [ ] ( ) ( ) [ ] ( ) ( ) i j ij i i x x f x f x x f x f x ∂ ∂ ∂ ∇ = ∂ ∂ ∇ = 2 2 ，以及 ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) 2 2 2 1 f x f x f x x x x x ∇ f x x − x + R x x − x ′ − + − ′ = + ∇ ， 当 x → x 时， R(x) → 0 。 当且仅当 Hessian 矩阵对所有 x 半正定时， f (x) 为凸函数。 对于实对称矩阵 M ，下列结论是等价的： 1.矩阵 M 半正定(PSD) 2.对所有 ，都有 . n x ∈ R x′Mx ≥ 0 1
3.M的所有特任值套负。 4,M的各阶顺序主子式均事负。 特征 当且仅当f)(x-x)≤f(x)-f)时，)为凸函数. 例如： L,线性函数∫(x)=a'x+b 2二次函数/)=xQ-,Q半正定(PSD) 3对数函数f)=-∑”og6,-arπb 凸最优化 凸最优化问题是求凸函数(x)在凸钓束集F下的极小值问题， 性质 若X是一个凸最优化创题的局部极小点，则X为全具极小点. 2、无钓束最优化 最优性条件 考虑无约束最优化利遥ming(),北中()二阶可微。最优性约束条件为： 1.必要条件： 若x为同部楼小点，则Vf(x)=0且V2f(x)半正定。 2.充分条件： 对所有xeB(元，e),知果有/(=0，且3∈中0：72f(x)率正定，则x为局部极 小点。 对连续可微的凸函数f八)，x为局部极小点的充分必要条件是可f(x)=0。 例愿 求函数fx)=-og1-x一)-logx)-log)的局部极小值，其中 名1+x:元1无00x2◆0 分析：我们知道函数f(名x:)为凸函数，因此只需铃证可八x)=0。 ,11 解方程组)=0，刹到（名）=兮学.即为极小值
3. M 的所有特征值非负。 4. M 的各阶顺序主子式均非负。 特征 当且仅当 f ( ) x ( ) x − x ≤ f (x) − f (x ) ′ ∇ 时， f (x) 为凸函数。 例如： 1.线性函数 f ( ) x = a ′x + b 2.二次函数 f ( ) x = x′Qx − c′x 2 1 ,Q 半正定(PSD) 3.对数函数 f ( ) x (b a x) Ax b m i log i i , π ∑=1 = − − ′ 凸最优化 凸最优化问题是求凸函数 f (x) 在凸约束集 F 下的极小值问题 。 性质 若 是一个凸最优化问题的局部极小点，则 为全局极小点。 * x * x 2、 无约束最优化 最优性条件 考虑无约束最优化问题 min n f (x) ，其中 二阶可微。最优性约束条件为： x∈R f (x) 1. 必要条件： 若 为局部极小点，则 且 半正定。 * x ( ) 0 * ∇f x = ( ) 2 * ∇ f x 2. 充分条件： 对所有 x ∈ B(x,∈) ，如果有∇f (x) = 0 ，且 0 : ( ) 半正定，则 2 ∃ φ∈ ∇ f x x 为局部极 小点。 对连续可微的凸函数 f (x) , 为局部极小点的充分必要条件是 。 * x ( ) 0 * ∇f x = 例题 求函数 ( ) ( ) ( ) ( ) 1 2 1 2 1 2 f x , x = −log 1− x − x − log x − log x 的局部 极小值 ，其中 1 0, 0 x1 + x2 π x1 φ x2 φ 分析：我们知道函数 f (x1, x2 ) 为凸函数，因此只需验证∇f (x) = 0。 ( ) ( ) ( ) ′ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − − − − − ∇ = 1 2 1 1 2 2 1 2 1 1 1 , 1 1 1 , x x x x x x f x x 解方程组∇f (x) = 0，得到 ) 3 1 , 3 1 ( , ) ( x1 x2 = ，即为极小值。 2
梯度法 设f(x)为对维空间的可微函数，点x处引出的方向d计算如下， vr()'d-limf+id-f) 下降方向：如果有Vfx)dx0,则对2中0，无充分小，有fx+2d)元f(x). (generic algorithn elepents)一般算法元素： 1.选代更新：x州=x“+入d 2.下降方向f(x'y'd"0,例如d*=-Df(x).其中DPSD. 3.最住步长龙=arg min(x+d*). 最速下降法的下降方向还需条件D=I,或者d”=-可(x)。步长可由精确线性搜素 成不精确线性瘦家，成其他算法求得
梯度法 设 f (x) 为 n 维空间的可微函数，点 x 处引出的方向 d 计算如下： ( ) ( ( )) λ λ λ f x d f x f x d + − = ′ ∇ →0 lim 下降方向：如果有 f ( ) x d π 0 ，则对 ′ ∇ λ φ 0 ，λ 充分小，有 f (x + λd) π f (x)。 （generic algorithm elements）一般算法元素： 1. 迭代更新： k k k k x = x + λ d +1 2. 下降方向 ( ) π 0 ，例如 ，其中 。 k k ∇f x ′d ( ) k k k d = −D ∇f x D isPSD k 3. 最佳步长 arg min ( ) 。 k k o k λ = λφ f x + λd 最速下降法的下降方向还需条件 D I k = ，或者 。步长可由精确线性搜索 或不精确线性搜索，或其他算法求得。 ( ) k k d = −∇f x 3