2-优化方法的数学基础2.ppt

18 五月 20232 优化方法的数学基础优化方法的数学基础2例如例如 等式约束优化问题的极值条件等式约束优化问题的极值条件(二)、拉格朗日乘子法v拉格朗日乘子法是求解等式约束优化问题的另一种拉格朗日乘子法是求解等式约束优化问题的另一种经典方法，它是经典方法，它是通过增加变量将等式约束优化问题通过增加变量将等式约束优化问题变成无约束优化问题变成无约束优化问题。所以又称作所以又称作升维法升维法。二二.有约束问题最优点的几种情况有约束问题最优点的几种情况2.2.有适时约束有适时约束 目标函数是凸函数目标函数是凸函数,可行域是凸可行域是凸集，则目标函数等值线与适时约集，则目标函数等值线与适时约束曲面的切点为最优点，而且是束曲面的切点为最优点，而且是全局最优点。全局最优点。1.1.无适时约束无适时约束 目标函数是凸函数，可行域是凸集，目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问则最优点是内点。相当于无约束问题的最优点。题的最优点。X*f(x)x*3.3.有适时约束有适时约束 目标函数是非凸函数（图目标函数是非凸函数（图 a a），或可行域是非凸集（图），或可行域是非凸集（图 b b）：）：则目标函数等值线与适时约束曲面可能存在多个切点，是则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。局部极值点，其中只有一个点是全局最优点。二二.有约束问题最优点的几种情况有约束问题最优点的几种情况pQQp三、无约束优化问题的极值条件三、无约束优化问题的极值条件 1.F(x)在在 处取得极值，其必要条件是处取得极值，其必要条件是:即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量。维零向量。l例：例：在在 处梯度为处梯度为l但但 只是双曲抛物面的鞍点，而不是极小点。只是双曲抛物面的鞍点，而不是极小点。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。则称则称 为为f的的驻点驻点驻点驻点。定义：设定义：设 是是D的内点，若的内点，若l根据函数在根据函数在 点处的泰勒展开式，考虑上述点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。极值必要条件，可得相应的充分条件。为了判断从上述必要条件求得的为了判断从上述必要条件求得的 是否是极是否是极值点，需建立极值的充分条件。值点，需建立极值的充分条件。2.处取得极值充分条件处取得极值充分条件l海色（海色（Hessian）矩阵）矩阵 正定正定正定正定，即各阶主，即各阶主子式均大于零，则子式均大于零，则X*为为极小点极小点极小点极小点。l海色（海色（Hessian）矩阵）矩阵 负定负定负定负定，即各阶主，即各阶主子式负、正相间，则子式负、正相间，则X*为为极大点极大点极大点极大点。2-5 2-5 有约束优化问题的极值条件有约束优化问题的极值条件 不等式约束的多元函数极值的必要条件是著名的库恩不等式约束的多元函数极值的必要条件是著名的库恩-塔克（塔克（Kuhn-Tucker）条件，它是非线性优化问题的重要理论）条件，它是非线性优化问题的重要理论（1）库恩）库恩塔克条件塔克条件(K-T条件）条件）对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：一、多元函数不等式约束优化问题一、多元函数不等式约束优化问题二、同时具有等式和不等式约束的优化问题二、同时具有等式和不等式约束的优化问题 利用利用KT条件求极值点往往是很繁琐的，需要确定需要条件求极值点往往是很繁琐的，需要确定需要确定哪些约束在极值点处起作用。确定哪些约束在极值点处起作用。库思库思塔克条件塔克条件也可以叙述为在极值点处目标函数的也可以叙述为在极值点处目标函数的负梯度一定能够表示成所有起作用的各约束函数在该点梯度负梯度一定能够表示成所有起作用的各约束函数在该点梯度（法向量）的非负线性组合，即（法向量）的非负线性组合，即(222)K-T条件Ox1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)0起作用约束：库库恩恩塔塔克克条条件件的的几几何何意意义义是是:在在约约束束极极小小值值点点处处，函函数数的的负负梯梯度度一一定定能能表表示示成成所所有有起起使使用用约约束束在在该该点点梯梯度度（法法向向量量）的的非非负负线线性性组组合合。x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)F F(x xk k)xk可行域点xk处的切平面x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)F F(x xk k)xk可行域点xk处的切平面(a)(b)同时具有等式和不等式约束的优化问题同时具有等式和不等式约束的优化问题:lK-T条件：条件：K-TK-T条件条件是多元函数取得约束极值的是多元函数取得约束极值的必要条件必要条件,以用来作以用来作为约束极值的判断条件，又可以来直接求解较简单的约束为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。优化问题。对于目标函数和约束函数都是凸函数对于目标函数和约束函数都是凸函数的情况，的情况，符合符合K-TK-T条件的点一定是全局最条件的点一定是全局最优点。优点。这种情况这种情况K-TK-T条件即为多元函数取条件即为多元函数取得约束极值的充分必要条件。得约束极值的充分必要条件。K-T K-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,以用来作为约束极值以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。的判断条件，又可以来直接求解较简单的约束优化问题。例库恩例库恩塔克（塔克（K-TK-T）条件应用举例）条件应用举例 ls.tl判断判断1 0T是否为约束最优点。是否为约束最优点。(1)当前点当前点 为可行点，因满足约束条件为可行点，因满足约束条件(3)各函数的梯度：各函数的梯度：（2）在）在 起作用约束为起作用约束为g1和和g2,因因 （4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足是一个局部最优点，因为它满足K-T条件。条件。ls.t三、优化设计问题的基本解法三、优化设计问题的基本解法1、解析解法：解析解法：根据函数极值的必要条件和充分条件求得其根据函数极值的必要条件和充分条件求得其最优解析解的求解方法，适用于目标函数比较简单的情况。最优解析解的求解方法，适用于目标函数比较简单的情况。2数值的近似解法：数值的近似解法：又称为数值迭代方法，它是根据目标又称为数值迭代方法，它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点或直至达到最优点。数值解法是优化到目标函数的最优点或直至达到最优点。数值解法是优化设计问题的基本解法，设计问题的基本解法，其中也可能用到解析解法其中也可能用到解析解法。数值解法更能适应计算机的工作特点：数值解法更能适应计算机的工作特点：1）数值计算而不是数学分析；）数值计算而不是数学分析；2）具有简单逻辑结构并能进行反复的同样的算术计算；）具有简单逻辑结构并能进行反复的同样的算术计算；3）最后得到的是逼近精确解的近似解。）最后得到的是逼近精确解的近似解。数值迭代法的基本思路：数值迭代法的基本思路：搜索、迭代、逼近搜索、迭代、逼近即进行反复数值计算，寻求目标函数值不断下降的可行计即进行反复数值计算，寻求目标函数值不断下降的可行计算点，知道最后获得足够精度的最优点。该方法的求优过算点，知道最后获得足够精度的最优点。该方法的求优过程可归纳为以下步骤：程可归纳为以下步骤：1 1）首先初选一个尽可能靠近最小点的初始点）首先初选一个尽可能靠近最小点的初始点X X(0)(0)，从初始，从初始点出发按照一定的原则寻找可行方向和初始步长，向前点出发按照一定的原则寻找可行方向和初始步长，向前跨出一步，达到跨出一步，达到X X(1)(1)；2 2）得到新点）得到新点X1X1后再选择一个新的使函数值迅速下降的方后再选择一个新的使函数值迅速下降的方向及适当步长，从向及适当步长，从X X(1)(1)点出发再跨出一步，达到点出发再跨出一步，达到X X(2)(2)点。点。以此类推，一步一步地向前探索并重复数值计算，最终以此类推，一步一步地向前探索并重复数值计算，最终达到目标的最优点。达到目标的最优点。优化设计的两类方法：优化准则法，数学规划法优化设计的两类方法：优化准则法，数学规划法数值迭代法的迭代格式数值迭代法的迭代格式-第第k步迭代计算所得到的点。称步迭代计算所得到的点。称为第为第k步迭代点，亦第步迭代点，亦第k步设计方案。步设计方案。其中：其中：-第第k步迭代计算的搜索方向。步迭代计算的搜索方向。-第第k次迭代计算的步长。次迭代计算的步长。每次迭代所得新点的目标函数值应满足函数值下降的要求：每次迭代所得新点的目标函数值应满足函数值下降的要求：收敛：收敛：数值迭代法关键要解决的问题：数值迭代法关键要解决的问题：1 1）怎样确定搜索方向）怎样确定搜索方向2 2）如何确定迭代步长）如何确定迭代步长3 3）如何判断是否找到最优点，以终止迭代）如何判断是否找到最优点，以终止迭代迭代计算的终止准则迭代计算的终止准则1）点距准则）点距准则2）函数值下降量准则）函数值下降量准则3）梯度准则）梯度准则即即或或-绝对下降量绝对下降量-相对对下降量相对对下降量采用哪种收敛准则，可视具体问题而定。可取采用哪种收敛准则，可视具体问题而定。可取 上述准则都在一定程度上反映上述准则都在一定程度上反映了逼近最优点的程度，但都有一了逼近最优点的程度，但都有一定的局限性。在实际应用中，可定的局限性。在实际应用中，可取其中一种或多种同时满足来进取其中一种或多种同时满足来进行判定。行判定。优化设计的一般流程优化设计的一般流程