2.098/15.093J:Recitation 10 Xuan Vinh Doan 2004.12.01 1、无约束问题的解法 最遮下降法 取选代k次后的第k次选代点为x,且f(x)≠0，取d=-f八x)为搜索方向. 步长a已定，则有f(x)xfx) 对任意初始解线性收效。 牛领法(Net0a法) 求函数八x)在x点附近的二阶泰勒近似展开式的极小值。 Newton方向：d*=-(vf(x)f) 等价的 共无梯度法 以子空圆需原里为基能已知d,-…d。∈R”是与Q共韩的d视d,=0,1卡人，刚≤n函数 )0x+的初始点·则=戈+∑（二），其中d为 d'od min.f(:+∑a,d,)相应的解。如果m=n则上面的解就是mim,f)得最优解. 方向：d=-“+花d,f到为=次方程时来.Y (d)YO,一般方程时 .x" I/x') 以保持其Q共矩性质。 (x)为二次函数时无限收效。 2、约束最优化句题 T必要条件 可行域为K={xER"|g,(x)≤0，点(x)=O),然T必要条件表述如下： x为局富极小点，1=U八g,(x)=0,满足下列条件之一
2.098/15.093J：Recitation 10 Xuan Vinh Doan 2004.12.01 1、无约束问题的解法 最速下降法 取迭代 k 次后的第 k 次迭代点为 xk ，且∇ ( ) ≠ 0 ，取 为搜索方向。 k f x ( ) k k d = −∇f x 步长α 已定，则有 ( ) ( ) 1 f x f x k π + 对任意初始解都线性收敛。 牛顿法（Newton 法） 求函数 f (x) 在 x 点附近的二阶泰勒近似展开式的极小值。 Newton 方向： ( ( )) ( ) 2 1 d f x f x k = − ∇ ∇− 等价的 共轭梯度法 以子空间扩张原理为基础：已知 是与 共轭的 n d1.....d m ∈ R Q di ′Qd j = 0,i ≠ j,m ≤ n 函数 f x = x′Qx + c′x 2 1 ( ) 的初始点 x0 ， 则 ∑= ′ − ∇ ′ = + m i i i i o d Qd f x d x x 1 0 ) ( ) ( ， 其 中 为 相应的解。如果 di min ( ) 1 0 i m i i f x ∑ a d = α + m = n则上面的解就是 min f (x) 得最优解。 x 方向： ， 为二次方程时 k k k k d = −∇f x + λ d + + ( ) 1 1 f (x) k k k k k d Qd f x d ( ) ( ) 1 ′ ∇ ′ = + λ ，一般方程时 2 1 2 || ( ) || || ( ) || k k k f x f x ∇ ∇ = + λ ，以保持其Q 共轭性质。 f (x) 为二次函数时无限收敛。 2、约束最优化问题 KKT 必要条件 可行域为 K = {x ∈ R | g (x) ≤ 0,h (x) = 0}，KKT 必要条件表述如下： j i n x 为局部极小点， I = { j | g (x) = 0} j ，满足下列条件之一： 1
1,钓衷为起作用钓束：所有Vg,(x),je/和Vh,(x)线性独立。 2 slater条件：存在x对所有的，j,有g,(x)r0和h,(x)=0. 3.所有约束均为线性。 则存在这样的鞋和P: )+∑，，g,)+∑h,)=0 4≥0 8)s0,h,()=0 ",g,()=0 T充分条件 设为凸集，了为凸函数，x为一个可行解，如果存在山20和”，使得 ()+∑4，g,()+∑Vh,()=0和，8，()=0对所有的j成立，则x为全局最 优解。 黑T条件在起作用钓束条件下为凸最优化问句题的充分必要条件， 1、内点法 仿射尺度法 初始内点解 下降方向通过求解最优化问题 min c'd SI Ad=0 dx-dsl 得到，其中X=digx):利用黑T条件可得到d的封闭形式(closed form》. 步长的选择可长可短。 障风法 障调函数G(x)为连续函数，当g,(x)→0°时G(x)→。障调法将所有不等式的束乘以 恰当的系数4(“→0)转移到目标函数中，构成障调函数。 原始路径跟察法在每次选代时利用二次近似法计算牛顿方向： 2
1.约束为起作用约束：所有 g x j I ∇ j ( ), ∈ 和 h (x) ∇ i 线性独立。 2.slater 条件：存在 x 对所有的i, j ，有 g j (x) π 0和 hi(x) = 0 。 3.所有约束均为线性。 则存在这样的u 和v ： ∇f ( ) x +∑ u ∇g ( ) x +∑ v ∇h (x) = 0 i i j i j j u ≥0 g j( ) x ≤ 0, hi( ) x = 0 u j g j( ) x = 0 KKT 充分条件 设 K 为凸集 ， 为凸函 数 ， 为 一 个可行解 ，如果存 在 和 ， 使 得 和 f x u ≥ 0 v ∇f (x) + ∑ u ∇g (x) + ∑ v ∇hi (x) = 0 i j i j j u j g j (x) = 0 对所有的 成立，则 为全局最 优解。 j x KKT 条件在起作用约束条件下为凸最优化问题的充分必要条件。 1、内点法 仿射尺度法 初始内点解x0 下降方向通过求解最优化问题 1 . . 0 min 2 ′ ≤ = ′ − d X d st Ad c d 得到，其中 ( ) 。利用 KKT 条件可得到 的封闭形式（closed form）。 0 X = diag x d 步长的选择可长可短。 障碍法 障碍函数G(x) 为连续函数，当 时 → − g j (x) 0 G(x) → ∞ 。障碍法将所有不等式约束乘以 恰当的系数 µ(µ → 0) 转移到目标函数中，构成障碍函数。 原始路径跟踪法 在每次迭代时利用二次近似法计算牛顿方向： 2
minle'-w'x+dxd st.Ad =0 原始对再路径限踪法通过求解方程组F(:)=0计算原始和对偶闩愿的牛顿方向，其中 Ax-b F(:)=Ap+s-c S-提
( ) . . 0 2 1 min 1 2 = ′ − ′ + ′ − − st Ad c µe X d µd X d 原始对偶路径跟踪法通过求解方程组 F(z) = 0 计算原始和对偶问题的牛顿方向，其中 ( ) ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − ′ + − − = XSe e A p s c Ax b F z µ 3