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

第24页,共26页，星期六，2024年，5月第25页,共26页，星期六，2024年，5月第26页,共26页，星期六，2024年，5月Page?*Page?*Page?*Page?*最优化理论算法及工程应用第一章预备知识最优化问题方向导数与极值问题泰勒级数问题凸集、凸函数与凸优化问题算法概述第2页,共26页，星期六，2024年，5月1.最优化问题最优化定义:最优化是从所有可能方案中选择最合理方案以达到最优目标的一门学科。最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。最优化方法包括:线性规划、非线性规划、整数规划、动态规划、多目标规划、组合优化等等。第3页,共26页，星期六，2024年，5月1.最优化问题的发展最优化问题可以追溯至17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题(求解多元函数极值的Lagrange乘数法)。19世纪柯西引入了最速下降法求解非线性规划问题。2020世纪三、四十年代线性规划(LP)理论的引入使得优化理论的研究出现了重大进展。1951年库恩和塔克给出了非线性规划(NLP)的最优性条件。随着计算机技术的发展，各种最优化算法应运而生。第4页,共26页，星期六，2024年，5月最优化问题的数学模型一般形式其中（目标函数）（等式约束）（不等式约束）第5页,共26页，星期六，2024年，5月2.n元函数的Taylor公式一元函数的泰勒展开式：设函数在定义域内连续可微，则有凸集、凸函数与凸优化问题其中第6页,共26页，星期六，2024年，5月二元函数的Taylor展式：其中第7页,共26页，星期六，2024年，5月3.函数的方向导数与极值问题目标函数的等值面（线）对于简单的问题，可用等值线或等值面来描述函数的变化趋势，还可以直观地给出极值点的位置。1）目标函数的等值面，其数学表达式为f(x)=c。在这种线或面上所有点的函数值均相等，因此，这种线或面就称为函数的等值线或等值面。当c取一系列不同的常数值时，可以得到一组形态相似的等值线或等值面，称为函数的等值线簇或等值面簇。第8页,共26页，星期六，2024年，5月函数的方向导数与极值问题2）当n=2时，该点集是设计平面中的一条直线或曲线。例1：目标函数f(x)＝一60x1一120x2的等值线族。这是一组相互平行的直线，函数值沿箭头所指方间逐渐下降。如图所示。凸集、凸函数与凸优化问题第9页,共26页，星期六，2024年，5月函数的方向导数与极值问题3）当n=3时，该点集是设计空间中的一个平面或曲面。例2函数的图形(旋转抛物面)，以及用平面f(X)＝c切割该抛物面所得交线在设计空间中的投影。如图所示。4）当n大于3时，该点集是设计空间中的一个超曲面。第10页,共26页，星期六，2024年，5月函数的方向导数与极值问题方向导数讨论函数在一点P沿某一方向的变化率问题。如果函数在点是可微分的，那末函数在该点沿任意方向L的方向导数都存在，且有其中为x轴到方向L的转角第11页,共26页，星期六，2024年，5月函数的方向导数与极值问题梯度函数在一点的梯度是这样一个向量,它的方向与取得最大方向导数的方向一致,而它的模为方向导数的最大值。以的n个偏导数为分量的向量称为在处的梯度，记为梯度也可以称为函数关于向量的一阶导数。第12页,共26页，星期六，2024年，5月Hesse矩阵（其中）第13页,共26页，星期六，2024年，5月函数的方向导数与极值问题梯度与方向导数之间的关系(1)若，则P的方向是函数在点处的下降方向；(2)若，则P的方向是函数在点处的上升方向。方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，升降的速度就越快第14页,共26页，星期六，2024年，5月结论：(1)梯度方向是函数值的最速上升方向；(2)函数在与其梯度正交的方向上变化率为零；(3