优化理论与最优控制

优化理论与最优控制“优化”与“最优化”

优化

“化”—加在名词或形容词后构成动词,表示转变成某种性质或状态。比如：绿化、美化、丑化，自动化，优化…

最优化（值）

指在一定条件影响下所能得到的最佳值。它是一个相对的概念；不同于数学上的极值，但在很多情况下可以用最大值或最小值来表示。最优化问题的控制方程调整（设计、策略、决策）变量

设计变量的数目称为最优化设计的维数。目标函数

在最优化设计中，可将所追求的设计目标（最优指标）用设计变量的函数（解析或隐含）形式表达出来，这一过程称为建立目标函数。约束条件

在很多实际问题中，设计变量的取值范围是有限制的或必须满足一定的条件。以及其他方面的限制。最优化问题的控制方程为：最优化问题的数学模型调整参数：目标函数:约束条件：X=[x1x2x3…xn]T,XDymin或

ymax=f(X)hv(X)=0,v=1,2,…,pgu(X)0,u=1,2,…,m几点说明调整（决策、策略）变量

原则应选择对目标函数影响大且独立的变量；通常情况下，调整变量越多，优化潜力越大，但优化过程也越复杂。目标函数

单目标函数：只有一个目标函数；多目标函数：有多个目标函数。约束条件

{显约束vs

隐约束}、{等式约束vs不等式约束}和{边界约束vs

性态约束}。控制方程的解

调整（设计、策略、决策）变量组合vs

目标函数；最优值的相对性与动态性等。约束条件目标函数取决于调整变量,而在工程实际问题中调整变量的取值范围是有限制的或必须满足一定的条件。

等式约束：对调整变量的约束严格，起着降低设计自由度的作用。

不等式约束

分类线性规划：若都是调整变量

X的线性函数；非线性规划：若它们不全是调整变量X的线

性函数；无约束规划：

若。举例说明（Ⅰ）小朋友算数

1)

2堆苹果，每堆有3个，问2堆加起来一共有几个苹果？若有3堆，1000堆这样的苹果呢？

2）9个苹果，3个小朋友分，问每人分几个苹果？若有18个，3000个苹果呢？观察到什么现象？发现什么问题？得到什么结论？举例说明（Ⅱ）

一简单的仅有两个输入变量x1、x2，一个输出变量y的工业过程，即。在工程中，输入变量即运行（工艺）参数x1、x2一般都有一定的取值范围。不妨设其允许取值范围分别为[a,b]、[c,d]。那么，图中蓝色方框中所有的x1、x2组合都能满足系统正常运行的要求。

简单的工业问题举例说明（Ⅱ）请问在这无穷多个组合中，哪个组合y能取得最大值或最小值呢？无约束目标函数的极值点存在条件1

一元函数

任何一个单值、连续、可微分的不受任何约束的一元函数点处有极值的充分必要条件是：

2

二元函数

若二元函数点的某个领域内有连续二阶偏导数，则在该点存在极值的充分必要条件是：且3

多元函数

n元函数在点M处存在极值的充分必要条件是：①在点M处函数的梯度为零向量：②Hessian矩阵为正定或负定：且当最优化设计的数值计算方法1

解析法—间接最优化方法

利用数学分析的方法,根据目标函数的变化规律与函数极值的关系,求目标函数的极值点.

寻找极值点

需要求解由目标函数的偏导数所组成的方程组或梯度。

然后用Hessian矩阵对所找到的稳定点进行判断，看它是否是最优点。

当目标函数比较简单时，求解上述方程组且用Hessian矩阵进行判断并不困难。但当目标函数比较复杂时，就会遇到麻烦，甚至很难求解各项偏导数所组成的方程组，更不用说对Hessian矩阵进行判断时将遇到的困难。数值计算方法—直接最优化方法

它是根据目标函数的变化规律，以适当的步长沿着能使目标函数值下降的方向，逐步向目标函数值的最优点进行探索，逐步逼近到目标函数的最优点。

步骤：①初选一个可能靠近最小点的初始点，从出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到点；②得到新点后再选择一个新的使函数值迅速下降的方向及适当的步长，从点出发再跨出一步，达到点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。

中间过程中每一步的迭代形式为：

式中：

-第k步迭代计算所得到的点；

-第k步迭代计算的步长；

-第k步迭代计算的探索方向。③每向前跨完一步，都应检查所得到的新点能否满足预定的计算精度，即

如满足，则认为为局部最小点；

否则，应以为新的初始点，按上述方法继续跨步探索。几点讨论

迭代过程中探索方向S的选择

①保证沿此方向进行探索时，目标函数值是不断下降的；②应尽可能地使其指向最优点，以缩短探索的路程和时间，提高求优过程的效率。

迭代的收敛性根据任意一个迭代式进行计算，不一定都能得到逼近精确解的近似解。①如果能够计算出逼近精确解的近似解，即近似解序列有极限，则迭代是收敛的。②否则，迭代是发散的。

对于实际工程问题有时很难判断其目标函数的极小值，而只能根据计算中的具体情况来进行判断。

如满足，则认为为局部最小点；

否则，应以为新的初始点，继续跨步探索。

判断是否应终止迭代的依据有三种形式：

①当设计变量在相邻两点之间的移动距离已充分小时，可用相邻两点的向量差的模作为终止迭代的判据：终止迭代的判断依据

或用向量的所有坐标分量之差表示：

②当相邻两点目标函数值之差已达充分小时，即移动该步后目标函数值的下降量已充分小时，可用两次迭代的目标函数值之差作为终止迭代的判据：

上述3种任何一种得到满足，则认为目标函数值收敛于该函数的最小值。

③当迭代点逼近极值点时，目标函数在该点的梯度将变得充分小，故目标函数在迭代点处的梯度达到充分小时，也可作为终止迭代的判据：几点讨论（2种特殊情况）★函数变化剧烈★函数变化缓慢为了防止当函数变化缓慢时，判据②虽已得到满足，而所求得的最优点与真正最优点仍相距较远，往往将判据①、②结合起来使用。

为了防止当函数变化剧烈时，判据①虽已得到满足，而所求得的最优值与真正最优值仍相差较大；无约束最优化方法的特点及应用范围最优化方法特点及应用范围坐标轮换法(变量轮换法或降维法)不需求导数，方法易懂，程序设计容易，但迭代过程较长，收敛速度较慢，且问题的维数n愈多求解效率愈低，适用于n≤10的小型无约束最优化问题，当函数的等值线为圆或为长短轴都平行于坐标轴的椭圆时此法很有效。最速下降法(一阶梯度法)效率高于上法，尤其最初几步迭代函数值下降很快，但愈靠近极值点愈慢。迭代计算简单，占用计算机单元少，对初始点的选择要求低。常与其它方法混用。牛顿法(Newton-Raphson法或二阶梯度法)当初始点选得合适时是目前算法中收敛得最快的一种(尤其对二次函数)，但当初始点选择不当会影响到能否收敛或导致失败。计算较繁且要求Hessian矩阵是非奇异的。计算量和存贮量都以维数n的平方(n2)比例增加，故当函数变量较多和因次较高时不宜采用此法。修正牛顿法(广义牛顿法)即使初始点选择不当，此法亦会成功，其它特点与牛顿法相同。共轭梯度法是对最速下降法在收敛速度上的重大改进，其收敛速度比最速下降法大为加快，而计算又比牛顿法大为简化。计算简单，所需的存储量少，收敛速度快，常用于多变量的最优化设计。共轭方向法及其改进—Powell法

不需求导数只需计算函数值，适用于中、小型问题的无约束最优化问题。Powell法是一种求无约束最优化问题较为有效的方法，适用于中小型无约束最优化问题，但对于多维问题收敛速度较慢。无约束最优化方法的特点及应用范围(续表)最优化方法特点及应用范围变尺度法(DFP法及BFGS法)为求解无约束极值问题最有效的算法之一，可以用到维数n≥100的问题。对于高维的大型问题，(n>100)，由于收敛快，效果好，被认为是最好的优化方法之一，但计算A(k)的程序较复杂，且需要较大的存贮量。DFP法也存在数值稳定性不够理想等情况，而BFGS．法则有较好的数值稳定性。单纯形法不需求导数，只需计算函数值。属直接求优法，这类方法甚至适用于未知目标函数的数学表达式而只知道它的具体算法的情况、程序简单、收敛快、效果好，适用于中小型设计问题。Hooke-Jeeves法程序简单，当变量较少时比较有效，适应性较强，收敛速度比坐标轮换法有所改善但仍较慢，不适于高维数的问题。Rosenbrock法可看成是对Hooke-Jeeves法的进一步改善与发展，比坐标轮换法显著地提高了迭代效率和解题效能，同样不适用于高维数的问题。Marquardt法集中了最速下降法及牛顿法的优点，且算法简单，接近极小点时收敛得非常快，不需要一维探索。常用于求函数平方和的极小值的问题。最小二乘法(Gauss-Newton法)常用于求函数平方和的极小值问题，且不必计算二阶偏导数矩阵，为线性收敛速度。单纯形法基本思想：★不需要计算目标函数的导数；★实际的最优化工程中，目标函数的导数往往很难求出甚至根本无法求出。①在n维空间中由n+1个线性独立的点构成一个凸多面体；②求出这些顶点处的目标函数值并加以比较，确定它们当中有最大值的点以及函数值的下降方向，再设法找到一个新的比较好的点替换那个最差点，从而构成新的单纯形；③随着这种取代过程的不断进行，新的单纯形将向着极小点收缩。经过一定次数的迭代，即可得到满足收敛准则的近似解。

设有一个二维目标函数，在平面中为线性独立（不在同一直线上）的三个点，并以它们为顶点构造单纯形（三角形）。计算这三个顶点处的函数值并作比较：若，则说明点最差，最好。故应该抛弃点并形成新的单纯形。算法思路：（3种类型的步骤—反射、扩张和压缩）

为此要找出除以外的所有顶点的形心点，并在和连线的延长线上取一点，使最差点的反射点反射系数，一般取为1.0关于反射点的选取：①若反射点的函数值小于最好点的函数值，即时，则表明所取的探索方向正确，可进一步扩大效果，继续沿向前进行扩张，在更远处取一点，并使扩展系数，大小一般在1.2~2.0之间图示

若，说明扩张有利，就用代替最差点，构造新的单纯形；若不成立，则不能扩张。此时，如果则用反射点替换最差点而形成新的单纯形。

②若下式成立，即则表示点走得太远，应该缩回一些，需要进行压缩，且得到的压缩点应为：压缩系数，常取0.5图示

若则用压缩点代替，形成新的单纯形③若反射点的函数值大于最差点的函数值，即时，应该压缩得更多些，即将新点压缩至与之间，这时所得的压缩点应为：④如果在方向上所有点的函数值都大于，或式（6）不成立，则不能沿此方向探索。这时应使单纯形向最好点进行收缩，即最好点不动，其余各顶点，皆向移近为原距离的一半，由原单纯形收缩成新单纯形

。

从以上各步得到新的单纯形后，再重新开始各步，逐渐缩小单纯形直至满足精度要求为止。0x1x2XhXgXlXcXrXeXsXs’

返回返回单纯形法的计算步骤

设目标函数为n元函数，即X为n维向量，因此单纯形应有n+1个顶点。一般取值范围为0.5~15.0;构成初试单纯形时,h=1.6~1.7.

构造初始单纯形时，先在n维空间中选取初始点（尽量靠近最优点），然后从出发沿各坐标轴方向，以步长h找到其余n个顶点；ei0x1x2XhXgXlXg’Xh’

—表示第k轮探索时的最好点,即并令:

—为第k轮探索的第j顶点,其函数值为;

—表示第k轮探索时所有顶点中函数值最大的顶点,即最差点:

—为次差点,即比小,但比其余各顶点的函数值都大;

—为除最差点外,其余所有顶点的形心,其坐标可以按下式计算:式中，i=1,2,

,n为各坐标方向的序号；j为顶点号，或构成初始单纯形后，即可进行以下步骤：①计算各顶点的函数值并进行比较，找出最好点，最差点，次差点，以及除最差点以外其余各顶点的形心。求对形心的反射点：②比较和，如果反射点比最好点还要好，即时，则进行扩张，得扩张点为（按式（2））：③将反射点与次差点比较，若，则用代替最差点，并转入步骤⑤；若，则用代替后进行压缩,否则直接进行压缩，得压缩点为：

得到扩张点后，如果，则用代替后转入⑤。否则用

代替转入⑤。

若，即反射点比最好点差，则转下一步。⑤进行收敛性检验.若则停止迭代并输出及,否则后转第①步。④将压缩点与最差点比较，若，则用代替最差点以后转入下一步;否则使单纯形向最好点收缩,收缩后的单纯形顶点为:逐渐缩小单纯形直至满足精度要求为止。单纯形程序框图复合形法

★复合形法是求解约束非线性最优化问题的一种重要的直接方法。★它来源于用于求解约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。

初始复合形的产生方法：

设在可行域内先给定复合形的一个初始顶点，则其余个n顶点由下式确定：

—调整变量的解域或上下界；其中:

—为复合形顶点的标号;

—为调整变量的标号；

—为区间内服从均匀分布的伪随机数。这样产生的顶点虽能满足调整变量的边界约束条件，但不一定就能满足性能约束条件。假定其中等q个点满足全部约束条件，而其余点不满足，为了使它们也能满足，则可先求出所有满足点的形心点：然后将这些不满足约束条件的点向形心点靠拢，得新点：只要系数选择得当（一般取），总可以使新点满足全部约束条件，即这样就可求得另外n-q+1个满足全部约束条件的初始顶点。取得n+1个顶点后便可构成一个有n+1顶点的多面体—复合形。然后如下进行迭代计算：①计算复合形各顶点的目标函数值，找出其中的最差点：找出次差点:

找出最好点:②计算除最差点外其它各顶点的形心:

或

检查点的可行性。③如果点在可行域内，则沿方向求反射点:

式中，可取，若为非可行点，则应将值减半，继续计算，直至满足全部约束条件为止。④如果点不在可行域内，为了将点移进可行域内，可在以点和点为界，重新利用伪随机数产生n+1个新的顶点，构成新的复合形。此时变量的上下界改为：若，则取

否则相反。重复步骤①、②，直至点进入可行域为止。⑤计算点的目标函数值，如果时，则用反射点替换最差点组成新的复合形，完成一次迭代并转入步骤①，否则转入步骤⑥。

⑥如果则将值减半，重新计算反射点，这时若且为可行点，则转向步骤⑤；否则应再将值减半，如此反复。如果经过若干次减半值的计算并使值已缩小到给定的一个很小的正数（例如）以下仍无效，则可使复合形向最好点收缩，还可在三点所决定的平面中，将点绕点旋转某一角度，并向最好点靠拢，得到新的点后构成新的复合形并转入步骤②，重新进行迭代计算，直到满足计算精度为止。

⑦若同时满足收敛准则Ⅰ、Ⅱ时，则停止迭代，并取复合形的最小函数值的顶点作为最优解。复合形程序框图复合形程序框图Ⅱ多目标函数的最优化方法★前面介绍的最优化方法，可直接用于仅含一个目标函数的所谓“单目标函数的最优化设计问题”。★但在许多实际工程设计问题中，常常期望同时有几项设计指标都达到最优值，这就是所谓“多目标函数的最优化问题”，其数学模型的一般表达式为:★各个目标f1(X)，f2(X)，…，fn(X)的优化往往是互相矛盾的，即不能期望同时达到它们的最优解；★甚至有时还会产生完全对立的情况，即对一个目标函数是优点，对另一目标函数却是劣点。☆这就需要在各个目标的最优解之间进行协调，相互间作出适当“让步”，以便取得整体最优方案。由此也可以看出多目标函数的最优化问题要比单目标函数的最优化问题复杂得多，求解难度也较大。统一目标法统一目标法的实质就是将控制方程中的各个目标函数(或称分目标函数)

f1(X)，f2(X)，…，fn(X)

统一到一个总的“统一目标函数”

f(X)中，即令的型式，把多目标函数的最优化问题转变为单目标函数的最优化问题来求解。在极小化“统一目标函数”

f(X)的过程中，为了使各个分目标函数能均匀一致地趋向各自的最优值，可采用如下的一些方法：加权组合法目标规划法功效系数法乘除法加权组合法又称线性组合法或加权因子法，即在将各个分目标函数组合为总的“统一目标函数”的过程中，引入加权因子，以考虑各个分目标函数在相对重要程度方面的差异及在量级和量纲上的差异。如第i项分目标函数fi(X)的加权因子，是一个大于零的数。在将各个分目标函数加权组合成总的统一目标函数的过程中，加权组合法又分为:直接加权法①直接加权法采用直接加权法来建立总的统一目标函数时，其加权因子wi的选取方法如下：若已知某分目标函数fi(X)的变动范围为①直接加权法;②转化设计指标法。则称为该指标的的容限，于是可取该项指标的加权因子为这种取法是基于要求在统一目标函数中的各项指标(分目标函数)趋于在数量级上达到统一平衡，因此，当某项设计指标的数值变化范围愈宽时，其目标的容限就愈大，加权因子就取较小值；而数值变化范围愈窄时，目标的容限就愈小，加权因子就取大值，以达到平衡各分目标函数量级的作用。另一种直接加权方法是把加权因子分为两部分，即第i项设计指标的加权因子wi为式中

wi1—反映第i项目标(设计指标)相对重要性的加权因子，称作本征权因子；

wi2—第i项目标的校正权因子，用于调整各目标间在量级差别方面的影响、并在迭代过程中逐步加以校正的加权因子。若用梯度来反映各个分目标函数fi(X)随设计变量变化而有不同函数值的情况，则其校正权因子可取即：

fi(X)的函数值变化愈快，加权值愈应取小些；反之则应取大些。这样就可使变化快慢不等的目标一起调整好。②转化设计指标法先将各项设计指标都转化为统一的无量纲值，并且将量级也限于某一规定范围之内，使目标规格化，然后再根据各个目标(设计指标)的重要性用加权因子来组合“统一目标函数”。例如，若能预计各项设计指标的变动范围，即已知★则可用右下图所示的正弦函数将各项设计指标(分目标函数)都转换到在0~1的范围内取值，使各目标规格化。当然也可以用其它合适的函数作为转换函数。★转换函数中自变量的上下界应与原设计指标的上下界相对应。即0与2π应分别对应于αi及βi，则相应于fi(X)值转换函数的自变量值为★令设计指标fi(X)在转化后为fiT(X)

，则

因此，“统一目标函数”为

式中的加权因子wi(i=1,2,…,q)，是根据该项(第i项)设计指标在最优化设计中所占的重要程度来确定。★通过上述换算，可使各项设计指标都转化为无量纲且等量级的一个数。(2)目标规划法先分别求出各个分目标函数的最优值fi(X*)，然后根据多目标函数最优化设计的总体要求，作适当调整，制定出理想的最优值fi(o)

。则统一目标函数可按如下的平方和法来构成：这意味着当各项分目标函数分别达到各自的理想最优值时，统一目标函数f(X)

为最小。此法的关键在于选择恰当的fi(o)

(i=1,2,…,q)值。(3)功效系数法如果每个分目标函数fi(X)

都用一个称为功效系数ηi

(i=1,2,…,q)并定义于0≤ηi≤1间的函数来表示该项设计指标的好坏(当ηi=1时