最优化理论算法及工程应用

最优化理论算法及工程应用第1页，共26页，2023年，2月20日，星期五第一章预备知识最优化问题01方向导数与极值问题0304泰勒级数问题02凸集、凸函数与凸优化问题05算法概述第2页，共26页，2023年，2月20日，星期五1.最优化问题最优化定义:最优化是从所有可能方案中选择最合理方案以达到最优目标的一门学科。最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。最优化方法包括:线性规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。第3页，共26页，2023年，2月20日，星期五1.最优化问题的发展

最优化问题可以追溯至17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题(求解多元函数极值的Lagrange乘数法)。19世纪柯西引入了最速下降法求解非线性规划问题。2020世纪三、四十年代线性规划(LP)理论的引入使得优化理论的研究出现了重大进展。

1951年库恩和塔克给出了非线性规划(NLP)的最优性条件。

随着计算机技术的发展，各种最优化算法应运而生。

第4页，共26页，2023年，2月20日，星期五最优化问题的数学模型一般形式其中（目标函数）（等式约束）（不等式约束）第5页，共26页，2023年，2月20日，星期五2.n元函数的Taylor公式一元函数的泰勒展开式：设函数在定义域内连续可微，则有凸集、凸函数与凸优化问题其中第6页，共26页，2023年，2月20日，星期五二元函数的Taylor展式：其中第7页，共26页，2023年，2月20日，星期五3.函数的方向导数与极值问题目标函数的等值面（线）对于简单的问题，可用等值线或等值面来描述函数的变化趋势，还可以直观地给出极值点的位置。

1）目标函数的等值面，其数学表达式为f(x)=c。在这种线或面上所有点的函数值均相等，因此，这种线或面就称为函数的等值线或等值面。当c取一系列不同的常数值时，可以得到一组形态相似的等值线或等值面，称为函数的等值线簇或等值面簇。

第8页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题2）当n=2时，该点集是设计平面中的一条直线或曲线。例1：目标函数f(x)＝一60x1一120x2的等值线族。这是一组相互平行的直线，函数值沿箭头所指方间逐渐下降。如图所示。凸集、凸函数与凸优化问题第9页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题3）当n=3时，该点集是设计空间中的一个平面或曲面。例2函数的图形(旋转抛物面)，以及用平面f(X)＝c切割该抛物面所得交线在设计空间中的投影。如图所示。4）当n大于3时，该点集是设计空间中的一个超曲面。第10页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题方向导数讨论函数在一点P沿某一方向的变化率问题。如果函数在点是可微分的，那末函数在该点沿任意方向L的方向导数都存在，且有

其中为x轴到方向L的转角第11页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题梯度函数在一点的梯度是这样一个向量,它的方向与取得最大方向导数的方向一致,而它的模为方向导数的最大值。以的n个偏导数为分量的向量称为在处的梯度，记为梯度也可以称为函数关于向量的一阶导数。第12页，共26页，2023年，2月20日，星期五Hesse矩阵（其中）第13页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题梯度与方向导数之间的关系(1)若，则P的方向是函数在点处的下降方向；(2)若，则P的方向是函数在点处的上升方向。方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，升降的速度就越快第14页，共26页，2023年，2月20日，星期五结论：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；(4)梯度反方向是函数值的最速下降方向．第15页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题可行方向定义设

是规划（NP）一个可行点,若非零向量

满足：当

时，则称为集处的一个可行方向（feasibledirection）。合

在点

若下降方向关于区域D可行，则称为可行下降方向。第16页，共26页，2023年，2月20日，星期五函数的方向导数与极值问题无约束优化极值问题

定理3.1(一阶必要条件)在一次可微；(2)

为

的局部极值点，则（1）函数定理3.2.(充分条件)（3）Hesse矩阵（）。则为的严格局部极小值点（极大值）

在二次可微；（1）函数（2）第17页，共26页，2023年，2月20日，星期五凸集、凸函数与凸优化问题

凸组合：已知，任取k个点，如果存在常数，使得则称为的凸组合。

凸集：设集合，如果中任意两点的凸组合仍然属于,则称为凸集。第18页，共26页，2023年，2月20日，星期五凸集、凸函数与凸优化问题

设，任取如果有，有则称为上的（严格）凸函数。凸函数凹函数第19页，共26页，2023年，2月20日，星期五凸函数的判断条件（1）一阶导数向量法是凸集上的凸函数的充要条件是，有

(2)二阶导数矩阵法设在凸集X上有二阶连续偏导数，则是凸函数的充要条件是，有半正定。

第20页，共26页，2023年，2月20日，星期五凸规划

设有规划

设P为凸规划，则：当为凸函数时，称规划P为凸规划。（1）规划P的可行解集为为凸集（2）规划P的最优解集为（3）规划P的任何局部极小点都是全局极小值点（全局最优解）