第二节 优化基础

一、最优化

（一）最优化问题

在现实社会中，人们经常遇到这样一类问题：判别在一个问题的众多解决方案中什么样的方案最佳，以及如何找出最佳方案。例如，在资源分配中，如何分配有限资源，使得分配方案既能满足各方面的需求，又能获得好的经济效益；在工程设计中，如何选择设计参数，使得设计方案既能满足设计要求，又能降低成本等。这类问题就是在一定的限制条件下使得所关心的指标达到最优。最优化就是为解决这类问题提供理论基础和求解方法的一门数学学科。

在量化求解实际最优化问题时，首先要把实际问题转化为数学问题，建立数学模型。最优化数学模型主要包括三个要素：决策变量和参数、约束或限制条件、目标函数。

连续变量优化模型的数学模型一般形式可以写为：

式中，x=(x1,x2,…,xn)T∈Rn，x即是n维向量，是指需要确定的未知数，在实际问题中也常常把变量x1,x2,…,xn叫决策变量；f(x)，hi(x)(i=1,2,…,m)，gj(x)(j=1,2,…,p)为x的函数，s.t.为英文“subject to”的缩写，表示“受限制于”。

求极小值的函数f(x)称为目标函数，是要求达到极小的目标的衡量。hi(x)(i=1,2,…,m)，和gj(x)(j=1,2,…,p)称为约束函数，其中hi(x)=0称为等式约束，而gj(x)≥0称为不等式约束。

对于求目标函数极大值的问题，由于max f(x)与min[-f(x)]的最优解相同，因而可转化为目标函数的相反数求解极小值：min[-f(x)]。

满足约束条件式（2-35）和式（2-36）的x称为可行解，由全体可行解构成的集合称为可行域，记为D，即

对一般模型（P），最优解具有如下定义：

定义2-1 若存在x∗∈D，使得x≠x∗对任意x∈D，均有f（x∗）≤f（x），则称x∗为最优化问题（P）的整体最优解。

定义2-2 若存在x∗∈D，使得对任意x∈D，均有f（x∗）＜f（x），则称x∗为最优化问题（P）的严格整体最优解。

定义2-3 若存在x∗∈D及x∗的一个邻域Nε（x∗），使得对任意x∈D∩Nε（x∗），均有f（x∗）≤f（x），则称x∗为最优化问题（P）的局部最优解，其中，ε＞0}。

定义2-4 若存在x∗∈D及x∗的一个邻域Nε（x∗），使得对任意x∈D∩Nε（x∗），x≠x∗，均有f（x∗）＜f（x），则称x∗为最优化问题（P）的严格局部最优解。

根据数学模型中有无约束函数分类，最优化问题可分为有约束的最优化问题和无约束的最优化问题。在数学模型中m=0，p=0时，即不存在约束的最优化问题称为无约束最优化问题，否则称为约束最优化问题。

（二）凸集

凸集和凸函数在最优化的理论中十分重要，称为凸优化。

凸优化具有良好的性质，比如局部最优解是全局最优解；凸优化问题是多项式时间可解问题，如线性规划问题。此外，很多非凸优化或NP-Hard问题也可以使用对偶、松弛（扩大可行域，去掉部分约束条件）方法转化成凸优化问题，在SVM算法中，为了对目标函数进行优化，就使用了拉格朗日乘子法、对偶问题、引入松弛因子等。

因此，本节主要介绍凸集的相关定义和性质。

1.凸集

定义2-5 设集合D⊂Rn，若对于任一点x，y∈D及实数α∈[0，1]，都有：

则称集合D为凸集。

凸集的直观几何表示如图2-1所示：左侧为凸集，右侧为非凸集，因为右边的集合中任意两点x和y连线之间的点有时不属于该集合。

凸集具有如下性质（设Di⊂Rn，i=1，2，…，k）：

1）设D1,D2,…,Dk是凸集，则它们的交D=D1∩D2∩…∩Dk是凸集；

2）设D是凸集，β为一实数，则集合βD={y|y=βx,x∈D}是凸集；

3）设D1,D2是凸集，则D1与D2的和D1+D2={y|y=x+z,x∈D1,z∈D2}是凸集。

2.凸组合

定义2-6 设xi∈Rn，i=1，2，…，k，实数λi≥0，，则称为x1，x2，…，xk的凸组合。

由凸集的定义知，凸集中任意两点的凸组合属于凸集。

3.极点

定义2-7 设D是凸集，若D中的点x不能称为D中任何线段上的内点，则称x为凸集D的极点。

极点的直观几何表示如图2-2所示。

（三）凸函数

明确凸集的概念后，可以进一步介绍凸函数的定义和性质。凸函数具有很好的极值特性，这使它在非线性规划中占有重要的地位。凹函数与凸函数相似，凸函数具有全局极小值，凹函数具有全局极大值，两者之间可以很方便地进行转换。

1.凸函数

定义2-8 设函数f（x）定义在凸集D⊂Rn上。若对于任意的x，y∈D及任意实数α∈[0，1]，都有

则称f(x)为凸集D上的凸函数。

对于一元凸函数，其几何表现如图2-3所示。

在曲线上任取两点，之间的弦位于弧之上。

2.严格凸函数

定义2-9 设函数f（x）定义在凸集D⊂Rn上。若对于任意的x，y∈D，x≠y，及任意实数α∈（0，1），都有

则称f(x)为凸集D上的严格凸函数。

3.凸函数的性质

1）设f（x）是凸集D⊂Rn上的凸函数，实数k≥0，则kf（x）也是D上的凸函数；

2）设f1（x），f2（x）是凸集D⊂Rn上的凸函数，实数λ≥0，μ≥0，则λf1（x）+μf2（x）也是D上的凸函数；

3）设f（x）是凸集D⊂Rn上的凸函数，β为实数，则水平集s(f,β)={x|x∈D，f（x）≤β}是凸集；

4）f（x）是凸集D⊂Rn上的凹函数的充分必要条件是[-f（x）]是凸集D⊂Rn上的凸函数。

4.凸函数的判断

判断一个函数是否为凸函数，最基本的方法是使用其定义。但对于可微函数，下面介绍的两个判定定理可能更为有效。

定理2-1（一阶判别定理） 设在凸集D⊂Rn上f（x）可微，则f（x）在D上为凸函数的一阶充分必要条件是对任意的x，y∈D，有

定理2-2（二阶判别定理） 设在开凸集D⊂Rn内f（x）二阶可微，则

1）f（x）为凸集D内的凸函数的二阶充分必要条件为在D内任何一点x处，f（x）的二阶偏导数组成的矩阵即黑塞矩阵∇2f(x)为半正定矩阵。

2）若在D内∇2f(x)为正定矩阵，则f（x）在凸集D内为严格凸函数。

5.常用凸函数判断方法

下面给出一些常用的快速判别凹、凸函数的方法：

1）指数函数是凸函数；

2）对数函数是凹函数，负对数函数是凸函数；

3）对一个凸函数进行仿射变换，可以理解为线性变换，结果仍为凸函数；

4）二次函数是凸函数（二次项系数为正）；

5）正态分布（又称高斯分布）函数是凹函数；

6）常见的范数函数是凸函数；

7）多个凸函数线性加权，如果权值大于等于零，那么整个加权结果函数为凸函数。

二、无约束最优化问题

这里讨论无约束最优化问题的数学模型

求解无约束最优化问题（P）的基本方法是给定一个初始点x0，依次产生一个点列x1，x2，…，xk，…，记为{xk}，使得或者某个xk恰好是问题的一个最优解，或者该点列{xk}收敛到问题的一个最优解x∗，这就是迭代算法。

在迭代算法中由点xk迭代到xk+1时，要求f(xk+1)≤f(xk)，称这种算法为下降算法，点列{xk}的产生，通常由两步完成。首先在xk点处求一个方向pk，使得f(x)沿方向pk移动时函数值有所下降，一般称这个方向为下降方向或搜索方向。然后以xk为出发点，以pk为方向做射线xk+αpk，其中α>0，在此射线上求一点xk+1=xk+αkpk，使得f(xk+1)<f(xk)，其中αk称为步长。

下降法如算法2-1所示：

对于迭代算法，我们还要给出某种终止准则。当某次迭代满足终止准则时，就停止计算，而以这次迭代所得到的点xk或xk+1为最优解x∗的近似解，常用的终止准则有以下几种。

1）‖xk+1-xk‖＜ε或；

2）|f（xk+1）-f（xk）|＜ε或；

3）‖∇f（xk）‖=‖gk‖＜ε；

4）上述三种终止准则的组合。

其中，ε>0是预先给定的适当小的实数。

下面介绍几种常用的优化算法。

（1）一维搜索。

最优化问题有明显的几何意义，往往可以用图解法获得最优解。一维搜索又称一维优化，是指求解一维目标函数的最优解的过程，已知xk，并且求出了xk处的下降方向pk，从xk出发，沿方向pk求目标函数的最优解，即求解问题

或者

称为一维搜索，设其最优解为αk，于是得到一个新点

所以一维搜索是求解一元函数φ(α)的最优化问题（也叫一维最优化问题）。我们把此问题仍表示为

（2）最速下降法。

对于无约束最优化问题考虑下降算法，最速下降法是其他许多算法的基础，它的计算过程就是沿梯度下降的方向求解极小值。在多元函数f(x)中，由泰勒公式有

由于

式中，θ为p与-g(x)的夹角。当θ=0°时，cos θ=1，因此，负梯度方向使目标函数f(x)下降最快，称为最速下降方向。

最速下降法如算法2-2所示：

（3）牛顿法。

最速下降法的本质是用线性函数去近似目标函数，可以考虑对目标函数的高阶逼近得到快速算法，牛顿法就是通过用二次模型近似目标函数得到的。假设f（x）是二阶连续可微函数，设xk为f（x）的极小点x∗的一个近似，将f（x）在xk附近做泰勒展开，有

式中，fk=f（xk），gk=g（xk），Gk=G（xk），若Gk正定，则qk（x）有唯一极小点，将它取为x∗的下一次近似xk+1。由一阶必要条件可知，xk+1应满足

即

令xk+1=xk+pk，其中pk称为牛顿方向，应满足

上述方程组称为牛顿方程，也可以从中解出pk并代入迭代公式，得到

即称为牛顿迭代公式。

根据上面推导，牛顿法如算法2-3所示：

（4）共轭梯度法。

牛顿法每步计算量很大，因此放松要求，认为经过有限次迭代就可得到正定二次函数极小点的算法是比较有效的。共轭梯度法的基本思想是在共轭方向法和最速下降法之间建立某种联系，以求得到一个既有效又有较好收敛性的算法。

对正定二次函数，由初始下降方向取为

确定共轭方向，并且采用精确一维搜索得到的共轭梯度法，在m(m≤n)次迭代后可求得二次函数的极小点，并且对所有i∈{1,2,…,m}，有

然后通过设法消去表达式中的G，使算法便于推广到一般的目标函数。

（5）拟牛顿法。

拟牛顿法不需要二阶导数的信息，有时比牛顿法更为有效。拟牛顿法是一类使每步迭代计算量少而又保持超线性收敛的牛顿型迭代法，条件类似于牛顿法，给出以下迭代公式：

其中，αk为迭代步长。若令，则上式为牛顿迭代公式。拟牛顿法就是利用目标函数值和一阶导数的信息，构造合适的Hk来逼近，使得既不需要计算，算法又收敛得快。为此，Hk的选取应满足以下的条件：

1）Hk是对称正定矩阵。显然，当Hk是对称正定矩阵时，若gk≠0，则

从而pk=-Hkgk为下降方向。

2）Hk+1由Hk经简单形式修正而得Hk+1=Hk+Ek，其中，Ek称为修正矩阵，此式称为修正公式。

我们希望经过对任意初始矩阵H0的逐步修正能得到的一个好的逼近。令

由泰勒公式，有

当Gk+1非奇异时，有，对于二次函数，该式为等式。

因为目标函数在极小点附近的性态与二次函数近似，所以一个合理的想法就是，如果使Hk+1满足

那么Hk+1就可以较好地近似。上式称为拟牛顿方程，如果修正公式满足拟牛顿方程，则相应算法称为拟牛顿法。显然Hk+1yk=sk中有(n2+n)/2个未知数，n个方程，所以一般有无穷多个解，故由拟牛顿方程确定的是一族算法，称为拟牛顿法。

三、约束最优化问题

在解决实际问题时，经常会遇到约束最优化问题，这类优化问题要比无约束最优化问题困难得多，也复杂得多。而由于约束最优化问题的应用极其广泛，所以人们一直在努力寻找它的求解方法，目前已出现很多种有效的求解方法。

本节主要研究一般性的约束最优化问题：

的计算方法。

其中，问题（P1）的可行域为D={x|ci（x）=0,i=1,2,…,l,ci(x)≥0,i=l+1,l+2,…,m}。

（一）约束优化问题的最优性条件

约束优化问题的最优性条件是指最优化问题的目标函数与约束函数在最优解处应满足的充分条件、必要条件和充要条件，是最优化理论的重要组成部分，对最优化算法的构造及算法的理论分析都是至关重要的。

对一般性优化问题（P1），可给出部分库恩-塔克必要定理的内容：

定理2-3（库恩-塔克必要条件） 若

1）x∗为局部最优解，其有效集I∗={i|ci（x∗）=0,i∈I}；

2）f（x），ci（x）(i=1,2,…,m)在点x∗可微；

3）对所有i∈E∪I∗，∇ci（x∗）线性无关，则存在向量使得

通常称式（2-69）为库恩-塔克条件或KT条件，满足式（2-69）的点x∗称为KT点。

m+n维函数

称为问题（P1）的拉格朗日函数，于是式（2-69）中的即为∇xL（x∗，λ∗）=0，其中λ∗称为拉格朗日乘子向量，矩阵

称为拉格朗日函数在处的黑塞矩阵，记为ω∗，即。

定理2-4（二阶充分条件） 设f（x）和ci（x）(i∈E∪I)是二阶连续可微函数，若存在x∗∈Rn，x∗为一般约束优化问题（P1）的可行点，且满足：

1）为KT对，且严格互补松弛条件成立；

2）对子空间中的任意d≠0，有dTω∗d＞0，则x∗为问题（P1）的严格局部最优解。

（二）罚函数法与乘子法

目前已有许多种求解无约束最优化问题的有效的算法，所以一种自然的想法就是设法将约束问题的求解转化为无约束问题的求解。具体说就是根据约束的特点，构造某种“惩罚”函数，然后把它加到目标函数中，将约束问题的求解转化为一系列无约束问题的求解。这种“惩罚”策略将使得一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直至迭代点列收敛到原约束问题的最优解。这类算法主要有三种：外罚函数法、内罚函数法和乘子法。

1.外罚函数法

外罚函数法的惩罚策略是对于在无约束问题的求解过程中企图违反约束的那些迭代点给予很大的目标函数值，迫使这一系列无约束问题的极小点（迭代点）无限向容许集靠近。

对一般约束最优化问题

可行域为D={x|ci(x)=0,i=1,2,…,l,ci(x)≥0,i=l+1,l+2,…,m}；

构造如下罚函数：

其中

显然有

函数p（x,σ）称为约束问题（P1）的增广目标函数，称为问题的罚函数，参数σ>0称为罚因子。

于是求解约束问题（P1）就转化为求增广目标函数p（x,σ）的系列无约束极小min p（x,σk），即求解

其中 {σk}为正的数列，且σk→+∞。

那么如何通过来求解约束最优化问题（P1）呢？首先给出一个定理：

定理2-5 对于某个给定σk，若是无约束问题的极小点，则是约束问题（P1）的极小点的充要条件是是约束问题（P1）的可行点。

证明：

1）必要性：因为极小点必定是可行点，所以必要性显然成立。

2）充分性：设，这里的D是约束问题（P1）的可行域，那么对于∀x∈D，总有：

所以是约束问题（P1）的极小点。

定理2-5说明，若由无约束问题解出的极小点是约束问题（P1）的可行点，那就是约束问题（P1）的极小点。此时只需求解一次无约束问题即可，但在实际中，这种情况很少发生，即一般不属于可行域D，那么这时求得的一定不是约束问题（P1）的极小点，需要再进一步增大σk，重新求解无约束问题，新的极小点会进一步向可行域靠近，也就是进一步向式（2-69）的极小点靠近。

构建外罚函数法的求解算法如算法2-4所示：

对已知一般性约束优化问题（P1）：

2.内罚函数法

为使迭代点总是可行点，使迭代点始终保持在可行域内移动，可以使用这样的“惩罚”策略，即在可行域的边界上竖起一道趋向于无穷大的“围墙”，把迭代点挡在可行域内，直到收敛到约束问题的极小点。不过这种策略只适用于不等式约束问题，并且要求可行域内点集非空，否则每个可行点都是边界点，都加上无穷大的惩罚，惩罚方法也就失去了意义。

对不等式约束问题

当x从可行域D={x∈Rn|ci(x)≥0,i=1,2,…,m}的内部趋近于边界时，则至少有一个ci(x)趋于零，因此，可构造如下增广目标函数：

其中或称为内罚函数或障碍函数，参数r>0仍称为罚因子，我们取正的数列{rk}且rk→0，则求解不等式约束优化问题转化为求解系列无约束问题，即

这种从可行域内部逼近最优解的方法称为内罚函数法或SUMT内点法。

内罚函数法的算法如下：

已知不等式约束问题，且其可行域的内点集D0≠∅，取控制误差ε＞0和罚因子的缩小系数0＜c＜1（比如可取ε=10-4，c=0.1）。

求解算法如算法2-5所示：

无约束优化问题的解法目前已有许多很有效的算法，所以在求解约束优化问题时，技术人员一般乐于采用罚函数法。内点法适合解仅含不等式的约束问题，且每次迭代的点都是可行点，但要求初始点为可行域的内点需耗费大量工作量，且不能处理等式约束。外点法能够解决一般约束优化问题，欲使无约束问题的解接近于原约束问题的解，应选取很大的σ，但为减轻求解无约束问题的困难，又应选取较小的σ，否则增广目标函数趋于病态。这些是罚函数法的固有弱点，限制其应用。

3.乘子法

罚函数法虽然易于操作，但是也存在缺点，比如由罚因子σk→∞（或rk→0）引起的增广目标函数病态性质。那么能否克服这个缺点呢？回答是肯定的。将拉格朗日函数与外罚函数结合起来，函数称为增广拉格朗日函数，通过求解增广拉格朗日函数的系列无约束问题的解来获得原约束问题的解，可以克服上述缺点，这就是下面要介绍的乘子法。

一般性约束问题（P1）的乘子法：

对一般约束优化问题（P1）：

有增广拉格朗日函数为

乘子的修正公式为：

令，则终止准则为ψk≤ε。

据此，Rockafellar在PH算法的基础上提出了一般约束问题的乘子——PHR算法，如算法2-6所示：

（三）可行方向法

可行方向法是一类直接求解约束优化问题的重要方法，这类方法的基本思想为：从给定的一个可行点xk出发，在可行域内沿一个可行下降方向pk进行搜索，求出使目标函数值下降的新可行点xk+1=xk+αkpk，如果xk+1仍不是问题的最优解，则可重复上述步骤，直到得到最优解为止。选择可行方向pk的策略不同，则形成不同的方法，此处不做过多介绍。

（四）投影梯度法

投影梯度法就是利用投影矩阵来产生可行下降方向的方法。它是从一个基本可行解开始，由约束条件确定出凸约束集边界上梯度的投影，以便求出下次的搜索方向和步长，每次搜索后都要进行检验，直到满足精度要求为止。

定义2-10 设n阶方阵p满足p=pT且pp=p，则称p为投影矩阵。

投影梯度法的算法如算法2-7所示：

（五）简约梯度法——RG法

简约梯度法的基本思想是利用线性约束条件，将问题的某些变量用一组独立变量表示，来降低问题的维数，利用简约梯度构造下降可行方向进行线性搜索，逐步逼近问题的最优解，如算法2-8所示：