最优化方法考试大纲

1、1. 下降算法一维搜索定义： ，若令 ，则优化问题等价为 。一维搜索的几何意义：在搜索方向上所得最优点处的梯度和该搜索方向正交： 。一维搜索的分类精确一维搜索(函数值下降最多)1) 区间收缩法：用某种分割技术缩小最优解所在的区间(称为搜索区间)。2) 函数逼近法(插值法)：用比较简单函数的极小值点近似代替原函数的极小值点。从几何上看是用比较简单的曲线近似代替原的曲线，用简单曲线的极小值点代替原曲线的极小点。3) 利用数值分析中的求根法。非精确的一维搜索通过计算少量的函数值，得到一步长，使得后续迭代点满足，即使目标函数要“充分”，下降。Goldstein准则Armijo准则Wolfe准则确定初始

2、区间优化算法通常具有局部性质，通常的迭代需要在单峰区间进行操作以保证算法收敛。若一维搜索的最优解 ，则称区间a，b为一维最优化问题的搜索区间；若进一步优化函数在区间严格单调递减，严格单调递增，则称区间a，b为单峰区间，是上的单峰函数。精确一维搜索确定区间的方法进退法己知搜索起点和初始步长；然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向；如果函数值下降，则维持原来的试探方向，并将步长加倍。进退法计算流程：步骤1：选取初始点，初始步长及精度，计算并记 步骤2：令，计算 .步骤3：若搜索成功，转步骤4；否则，搜索失败，转步骤5步骤4：， ， 转步骤2步骤5：反向搜索，若，令，转步骤

3、2；否则停止迭代黄金分割法（0.618法）黄金分割法是一种区间收缩方法(或分割方法)，其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短以逼近极小值点。抛物线法抛物线法是插值方法的一种，其思想是利用多个函数值和导数值构造插值多项式，用多项式的最优值来逼近原函数的最优值。抛物线法属于3点二次插值。抛物线法计算流程：三次插值法三次插值法的思想同样是利用多个函数值和导数值构造插值多项式，用多项式的最优值来逼近原函数的最优值，逼近函数是利用两点的函数值和导数值构造的3次插值多项式。 牛顿法根据最优性条件，一维搜索问题的最优解 应该满足 ，则问题转化为非线性方程求根问题。 牛顿法也

4、可认为是一类函数逼近方法，一点2次插值。 也可以根据函数连续性，用二分法进行非线性方程求根运算精确一维搜索的收敛性为了保证方法的下降性，避免搜索方向和负梯度方向正交的情形，假定 为搜索方向和负梯度方向的夹角。定理:若目标函数梯度存在，且在水平集上一致连续，搜索方向满足夹角条件，线搜索中采用精确搜索技术，则 ，或 或 不精确搜索1) 精确搜索计算量较大，特别是当迭代点远离最优解时，效率很低；而且，很多最优化方法的收敛速度并不依赖于精确一维搜索的过程。2) 自从Armijo(1966), Goldstein(1965)提出了不精确线性搜索方法以后，不精确线性搜索由于计算量小、效率高成了现在流行的线

5、搜索方法。3) 在非精确一维搜索中，通常要求 比下降一定的数量，从而使得达到一个满意水平，此时的 就是可接受步长，并非精确求解一维最优化问题。4) 实践证明：非精确一维搜索方法可大大节省计算量，且总体上有较快的收敛速度。不用寻找单谷区间。Armijo-Goldstein准则Armijo-Goldstein准则计算流程：Wolfe准则Wolfe准则计算流程：不精确一维搜索的收敛性为了保证方法的下降性，避免搜索方向和负梯度方向正交的情形，假定 为搜索方向和负梯度方向的夹角。定理:若目标函数梯度存在，且在水平集上一致连续，搜索方向满足夹角条件，线搜索中采用Goldstein准则，则 ，或 或 定理：

6、若目标函数连续可微有下界，且在水平集上一致连续，搜索方向满足夹角条件，一维搜索中采用Wolfe准则，则 一维搜索方法评述1. 如目标函数能求二阶导数：用Newton法，收敛快。2. 如目标函数能求一阶导数 ：1) 如果导数容易求出，考虑用三次插值法，收敛较快；2) 对分法、收敛速度慢，但可靠；3) 二次插值法如割线法也可选择。3. 只需计算函数值的方法 ：1) 二次插值法, 收敛快，但对函数单峰依赖较强；2) 黄金分割法收敛速度较慢，但实用性强，可靠；4. 减少总体计算时间：非精确一维搜索方法更加有效。最速下降法假设 连续可微，取 , 步长 由精确一维搜索得到。从而得到第 次迭代点，即：负梯度

7、方向是函数值减小最快的方向。最速下降法的计算流程1) 选定某一初始点， 并令 2) 若 ，则 ，否则转（3）；3)4) 由精确一维搜索确定步长，即由一个极小化问题求得最佳步长 ，令， 转（2）.最速下降法的收敛性分析：（收敛性定理）设目标函数 连续可微，且水平集 有界，则最速下降法或者在有限迭代步后终止；或者得到点列 ，它的任何聚点都是的驻点。（推论）在收敛定理的假设下，若为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是的全局最小点。最速下降法的特征：1. 相邻两次迭代的方向互相垂直。1) 最速下降法在两个相邻点之间的搜索方向是正交的。2) 最速下降法向极小值点逼

8、近是曲折前进的，这种现象称为锯齿现象。2. 最速下降法收敛速度慢在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内可能得不到需要的结果。3. 对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点。最速下降法的优缺点：优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅

9、仅是指某点的一个局部性质。一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。最速下降法的改进1) 选择不同初始点2) 采用不精确的一维搜索采用非精确一维搜索求步长, 可使相邻两个迭代点处的梯度不正交，从而改变收敛性。3) 采用加速梯度法负梯度方向和 结合。由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可适时改变搜索方向的正交特性。开始取负梯度方向，每两步用产生新的搜索方向，然后继续使用最速下降方向。两种方向交替使用，实践效果优于单纯使用最速下降方向。可以利用最速下降法初期搜索效率高的特性，首先使用最速下降法，然后使用其它局部收敛

10、速度快的计算方式。Newton法考虑从 到的迭代过程，在点处对函数 Tayloy展开： 略去高阶项令，有若Hesse矩阵正定，则存在，由此求出二次函数的极小点为：以此 作为 的极小点 的一个新的近似。Newton法的几何意义二次函数的等值线为椭圆族。为椭圆中心。椭圆等值线逼近目标函数等值线。Newton法的计算步骤已知目标函数，给定误差 步骤1.选定初始点，计算 ， 步骤2.如果 ，算法停止， ，否则转步骤3.步骤3.计算搜索方向步骤4.令， ，转步骤2.Newton法的优缺点Newton法的优点1) 当初始点离最优解很近时，算法收敛速度快；2) 算法简单，不需要进行一维搜索(确定步长=1)；

11、3) 对正定二次函数，迭代一次就可得到最优解。Newton法的缺点1) 对多数算法不具有全局收敛性，对初值依赖；2) 每次迭代都要计算Hesse矩阵，计算量大；3) 可能不存在或者对应方程组奇异(或病态)；4) 可能非正定， 可能不是下降方向，算法也可能收敛于最大值点或者鞍点。Newton法的改进阻尼Newton法在Newton迭代中，取 ，加入精确一维搜索： 求得最佳步长 ，得到下个迭代点 阻尼Newton法的收敛性设 存在连续二阶偏导数，函数的Hesse矩阵正定。且水平集 有界，则阻尼Newton法或者在有限步迭代后终止；或者得到的无穷点列 有如下性质(1) 为严格单调下降序列；(2) 有

12、唯一聚点 ，它是的最小点。共轭梯度法1) 在下降迭代法中，若取下降方向是共轭方向，所得到的方法我们称为共轭方向法。2) 若能找到一组A共轭向量，则得到结合最速下降法和Newton法优点的算法，这个算法具有二次收敛性。3) 一个算法若能在有限步内求得正定二次函数的极小点，则称该算法具有二次收敛性(又称二次终止性)。4) 共轭方向的选取有很大任意性，而一组不同的共轭方向就对应着不同的共轭方向法。作为一种迭代算法，希望共轭方向能在迭代过程中逐次生成。5) 用迭代点处的负梯度向量为基础产生一组共轭方向的方法叫做共轭梯度法。基本思想共轭梯度法是基于共轭方向的一种算法。针对目标函数为二次函数的问题，其搜索

13、方向是与二次函数系数矩阵相关的共轭方向。用这类方法求解n元二次正定函数的极小问题，最多进行n次一维搜索。定义：设x，y是n维欧氏空间中两个向量，即，若有 ，就称x与y是两个正交的向量。又设A是一个n阶对称正定矩阵，若有，则称向量x，y关于A共轭正交，简称关于A共轭。共轭方向及其性质1) 在n维空间中与n个线性无关的向量都正交的一定是零向量2) 若中的非零向量,是A共轭向量组，则这m个向量是线性无关的3) 在n维空间中互相共轭的非零向量的个数不超过n4) 若中的非零向量,是A共轭向量组，则这m个向量是线性无关的。FR共轭梯度法的计算步骤步骤1.选定初始点 步骤2.如果 ，算法停止， ，否则转步骤

14、3.步骤3.取 步骤4.精确一维搜索找最佳步长 ，令 步骤5.如果，算法停止， ，否则转步骤6.步骤6.如果k=n，令，算法停止，k=1，转步骤4，否则转步骤7步骤7.计算 ，k=k=1,转步骤4.共轭梯度法的特点1) 对凸函数全局收敛（下降算法）；2) 计算公式简单，不用求Hesse矩阵或者逆矩阵，计算量小，存储量小，每步迭代只需存储若干向量，适用于大规模问题；3) 具有二次收敛性；(对于正定二次函数，至多n次迭代可达最优解）4) 共轭梯度法的收敛速率不坏于最速下降法。如果初始方向不用负梯度方向，则其收敛速率是线性收敛的；5) 共轭梯度法是目前求解无约束优化问题最常用的方法之一;6) 共轭梯

15、度法有多种求解形式，不同的求解公式对于正定二次函数是等价的，对非正定二次函数，有不同的效果。变尺度法变尺度法构造思想最速下降法计算简单，但收敛速度慢；Newton法(阻尼)具有收敛速度快的优点，但需要计算Hesse矩阵的逆，计算量大，实现困难。它们可统一描述为 为减少计算量，用一个n阶对称正定矩阵 近似代替Hesse矩阵的逆，即，从而搜索方向是，由此搜索方向产生的方法称为变尺度法，称为尺度矩阵，这是一种拟Newton法，被认为是无约束优化问题中最有效的方法之一。变尺度法的计算步骤步骤1. 任取初始点，初始尺度矩阵 令k=1.步骤2. 计算步骤3. 利用精确一维搜索找最佳步长，令步骤4. 令，转

16、步骤2。其中称为修正矩阵。修正矩阵选取的不同，对应着不同的变尺度法。DFP算法DFP算法是最先被研究的一种变尺度算法，目前仍在广泛使用。DFP算法的优缺点1) 对n元正定二次函数，DFP算法有二次收敛性。2) 若是可微的严格凸函数，则DFP算法全局收敛；3) 对非二次函数，DFP算法的效果也很好，它比最速下降法和共轭梯度法要有效的多，收敛速度是超线性的；4) DFP算法的计算量、存储量要比共轭梯度法大，因此，对大规模的优化问题，用共轭梯度法更方便；5) 实际运算中，由于舍入误差的存在可能影响算法的稳定性，但BFGS算法受到的影响要小得多。拟牛顿法评述1) 当线性搜索可以精确进行时，拟牛顿法不但

17、生成共轭方向，而且构建了拟海赛阵的近似值。这意味着当收敛到具有正定海赛阵的最小时，类似于牛顿法，具有较快的收敛速度；2) 上述性质不依赖于初始矩阵。因此，拟牛顿法不需要像共轭梯度法那样，周期性地利用最速下降步长重新开始计算；3) 数值算例表明：拟牛顿法对线性搜索的精确度不像共轭梯度法那么敏感；共轭梯度法需要O(n)次计算共轭方向和下个迭代点，拟牛顿法则需要O()次。若对目标函数及梯度的计算量大于或相当于O()次运算量，选择拟牛顿法，否则，选择共轭梯度法。2. 无约束优化最优性条件算法框架结构下降递推法信赖域算法n 线搜索方法是把一个复杂的最优化问题转化成一系列简单的一维寻优问题。方法的核心思想

18、是先寻找“理想”的下降方向，然后在确定的方向上确定长度。n 信赖域方法是把最优化问题转化为一系列相对简单的局部寻优问题。方法能够对局部的所有方向进行“搜索”，进而同时确定“局部最好”的前进方向及长度。信赖域算法基本思想牛顿法的基本思想是在迭代点 附近用二次函数逼近 并以 的极小点 修正，得到： 以上方法只能保证算法的局部收敛性，为了建立全局收敛性算法，阻尼Newton法采用线搜索技术。但它没有进一步利用导致算法快速收敛的二次函数逼近模型。信赖域方法是另一种新的保证算法全局收敛的方法。在迭代过程中不断利用二次函数模型对目标函数进行逐步逼近。信赖域方法在每次迭代中给出一个小区域，称为信赖域，这个信

19、赖域一般是当前迭代点的一个小邻域。后在这个邻域内求解一个带约束（信赖域约束）优化子问题，得到“局部最优”位移，接着用某一评价函数来决定是否接受该位移以及确定下一次迭代的信赖域。如果试探步长被接受，则： 否则，信赖域算法特点1) 这种方法既具有牛顿法的快速局部收敛性，又具有理想的全局收敛性。2) 不要求目标函数的Hesse阵是正定的。3) 利用了二次模型来求修正步长， 使得目标函数的下降比线性搜索方法更有效。4) 由于步长受到使Taylor展开式有效的信赖域的限制，故方法又称为有限步长法。直接法模式搜索法从几何意义上看,寻找具有较小函数值的“山谷”力图使迭代产生的序列沿“山谷”走向逼近极小点,算

20、法从初始基点开始,包括两种类型的移动-探测移动和模式移动。n 探测移动依次沿n个坐标轴进行,用以确定新的基点和有利于函数值下降的方向n 模式移动沿相邻两个基点连线方向进行.Powell方法基本思想： Powell方法主要由基本搜索、加速搜索和调整搜索方向三个部分组成。基本搜索包括从基点出发沿着已知的n个搜索方向进行一维搜索，确定一个新基点；加速搜索是沿着相邻的两个基点的连线方向进行一维搜索，使函数下降更快；最后用基点连线方向代替已知的n个搜索方向之一，构造新的搜索方向组并进行下一步迭代。也可以认为： Powell方法是把整个计算过程分成若干个阶段,每一阶段(一轮迭代)由n+1次一维搜索组成的直

21、接方法。l 与模式搜索法的异同Powell方法用一维搜索取代模式搜索中的试探方式；Powell方法的加速搜索采用的方式与模式搜索法类似，仅在步长的取法上有一定差异，Powell方法仍然采用一维搜索方法；Powell方法产生新的迭代方向，而模式搜索法迭代方向保持不变或者产生正交迭代方向，与之相比，Powell方法所产生的迭代方向为共轭方向，具有二次收敛性。l 基本 Powell 法存在的问题在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成n维空间，可能求不到极小点。l 改进Powell法在Powell基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中

22、的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。单纯形法基本思想： 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。单纯形： n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是

23、四面体。在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。设当前的单纯形的顶点为X1，X2，X3，且有 3. 约束优化最优性条件约束优化问题的求解困难1) 极小点可能位于约束域中间，也可能位于边界；2) 迭代点处可行方向有限制，不再是任意方向；3) 无约束问题的最优性条件不再适用；约束优化问题的分类等式约束等式约束优化的最优性条件求解方法l 代入法（消元法） l 拉格朗日乘子法 等式约束一阶必要条件定理：考虑等式约束优化问题， 为可行点，f(x)在处可微， (j=1,l)在处连续可微，向量集线性无关。若是等式约束问题的局部最优解，则存在数 使得

24、 拉格朗日函数等式约束二阶必要条件 或者的海塞矩阵关于y在处半正定。定理当然还需要目标函数和约束函数二阶连续可微。等式约束二阶充分条件若目标函数和约束函数二阶连续可微，且满足 或者的关于y的矩阵 在处正定。则是满足约束的局部最小点。不等式约束优化可行域： 其中的元素可行点；设可行解，若，则称不等式约束是在处的积极约束或称紧约束、起用作约束。积极约束指标的全体组成的集合，称为处的积极约束指标集，记为 ，。一阶最优性必要条件定理(一阶必要条件)：考虑一般约束优化问题，为可行点 ， 和在可微，在处连续， 在处连续可微，向量集 线性无关。若是局部最优解，则存在数和 使得 定理中的条件在处连续加强为连续

25、可微，则上述结论等价于：当时，可知，自然消失。二阶最优性条件（二阶必要条件）若目标函数和约束函数二阶连续可微， 有 (二阶充分条件) 若目标函数和约束函数二阶连续可微 则为满足约束的严格局部最小值点。可行方向法l 可行方向法是求解约束优化问题的方法之一。通过在可行域内直接搜索最优解求解约束优化问题，它可看作无约束优化下降算法的自然推广。l 基本思想：从可行点出发，沿着下降的可行方向进行搜索，求出使目标函数值下降的新的可行点，直到满足终止条件，得到最优解x*.l 基本的迭代步骤：1) 从可行点 开始迭代，设已得到可行点2) 在处用某种方法确定一可行下降方向3) 沿寻找新的迭代点 使得是可行点且

26、令k = k +1，转2，直到满足终止条件。l .可行方向法的分类可行方向法的核心是选择可行下降搜索方向和确定搜索步长。搜索方向的选择方式不同就形成不同的可行方向法：1) 通过求解一个线性规划来确定，如Zoutendijk(约坦狄克)可行方向法、Frank-Wolfe方法等；2) 利用投影矩阵直接构造，如梯度投影法;3) 利用既约矩阵直接构造，如既约梯度法。Zoutendijk法梯度投影法基本思想：当迭代点在可行域内部时，取该点处的负梯度方向为可行下降方向；当迭代点在可行域边界上时，取该点处负梯度方向在可行域边界上的投影产生一个可行下降方向。既约梯度法基本思想：借鉴求解线性规划的单纯形算法，选

27、择某些变量为基变量，其它的作为非基变量，将基变量用非基变量表示，并从目标函数中消去基变量，得到以非基变量为自变量的简化的目标函数，进而利用此函数的负梯度构造下降可行方向。既约梯度：简化目标函数关于非基变量的梯度罚函数法借助罚函数将约束非线性规划转化为一系列无约束问题，通过求解无约束问题来求解约束非线性规划，所以也称为序列无约束极小化技术。根据约束特点（等式或不等式）构造某种罚函数p(x)，把它加到目标函数中去，将约束非线性规划转化为一系列无约束问题： 罚因子，惩罚函数。这种惩罚策略，对于在无约束的求解过程中企图违反约束的迭代点给予很大的目标函数值，迫使无约束问题的极小点或者无限地向可行域D靠近

28、，或者一直保持在可行域D内移动，直到收敛到原来约束最优化问题的极小点。不改变可行域局部极小值，可以将约束域之外的局部极小值变大。 惩罚函数法分类l 外点法：对违反约束的点在目标函数中加入相应的惩罚，可行点不予惩罚，这种方法的迭代点一般在可行域D的外部移动；l 内点法：对从内部企图穿越可行域D边界的点在目标函数中加入障碍，距边界越近，障碍越大，在边界上给予无穷大的障碍，从而保证迭代点一直在可行域内部移动；l 混合法：将外点法和内点法结合，两种惩罚函数联合使用。外点法l 罚函数p(x)应满足的性质 （1）连续 （2） （3）若是的最优解，且，则也是的最优解。n 一般来说，仅在M充分大时才成立，但在

29、实际计算中，过大的M会造成无约束问题的求解困难，因此取一个递增且趋于的罚因子序列 ，即 然后求解一系列无约束问题n 罚函数p(x)的构造 （1）连续 （2） （3）外点罚函数法算法步骤1) 给定初始点，初始罚因子(可取)，精度2) 以初始点，求解无约束优化问题得到极小点，记为 3) 若，则停止计算，得到近似极小点；否则，令，置，转步骤2，常取 算法收敛性分析引理：对于由外点法产生的点列 总有：（1），（2），（3）外点罚函数法特点1) 初始点可以任选，对等式约束和不等式约束均可适用；2) 初始罚因子要选择得当，否则会影响迭代计算的正常进行，许多计算表明，取常常可以取得满意的效果；按经验公式计算

30、值 3) 罚因子递增()，,递增系数c, c>1通常取。4) 每个近似解 往往不是可行解，这是某些实际问题所无法接受的。内罚函数法可解决5) 外点法中要求而太大将造成增广目标函数 的Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解。 乘子法可解决6) 如果在可行域外目标函数f(x)的性质复杂或者没有定义时，外点法不适用了。内点罚函数法n 迭代点在可行域的内部移动，并对接近可行域边界的点施加惩罚(加入障碍)，距边界越近障碍越大，相当于在可行域边界上筑起一道很高的“围墙”，阻止迭代点穿越边界，从而将最优解“挡”在可行域内。n 内点罚函数法又称为障碍函数法。n 内点

31、法要求迭代点在可行域内部移动，初始点必须是内点，可行域的内部必须是非空的，内点法只能处理不等式约束。n 惩罚函数的有效区域是约束的可行域，目标函数在可行域内的所有点都受到惩罚，越靠近边界惩罚越多。n 不同的惩罚因子对应不同的惩罚函数，惩罚因子越小，惩罚函数的极小点越接近与边界处的最优点。n 当惩罚因子趋近与零时，惩罚函数的极小点就是原约束问题的最优点。内点罚函数构造 B(x)满足下面的条件：1) B(x)在可行域D的内部 int D连续；2) ；3) 当x趋向可行域的边界时 n 从形式上看，内点法对应的问题仍是一个约束优化问题；但从计算的观点看，是一个无约束优化问题。n 在可行域的边界附近，问

32、题的目标函数值趋于，只要从可行域D的任何一个内点开始迭代，并注意控制一维搜索的步长，就可使得迭代点不越过可行域，因此不必直接地与约束问题打交道。n 若原问题的解位于边界，越小，障碍项所起的作用越小，越接近真解。内点罚函数法算法步骤1) 给定初始点 ，初始罚因子 (可取)，精度 2) 以初始点，求解无约束优化问题得到极小点，记为，其中3) 若，则停止计算，得到近似极小点；否则，令，置，转步骤2，常取 收敛性分析引理：对于由内点罚函数法产生的点列 总有：（1），（2），（3）收敛性定理：设可行域D的内点集非空， 在D上存在极小点 ，对严格单减正数列 ，则由内点法产生的点列 的任何聚点是约束问题的最

33、优解。一般的最优解很难用解析法求出，须采用无约束最优化方法。内点罚函数法几点说明1) 初始点的选取使用内点法时，初始点应选择一个离约束边界较远的可行点。如果太靠近某一约束边界，求解无约束优化问题时可能会发生困难。2) 初始罚因子的选取惩罚因子的初值应适当，否则会影响迭代计算的正常进行，太大将增加迭代次数；太小会使惩罚函数的性态变坏，甚至难以收敛到极值点。对于不同的问题，都要经过多次试算，才能决定一个适当。3) 罚因子的缩减系数c的选取，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。4) 由于无约束优化问题的解法目前已经有许多很有效的算法，如DFP算法，BFGS法等，所

34、以在求解复杂的约束优化问题时，工程技术人员一般乐于采用罚函数法。简单、易懂。5) 为求解约束优化问题，需要求解一系列的无约束优化问题，计算量大，且罚因子的选取方法对收敛速度的影响比较大。并且罚因子的增大（外点法）与缩小（内点法）使得问题的求解变得很困难。常常会使增广目标函数趋于病态。这是罚函数法固有的弱点，使其使用受到限制。这正是乘子法所要解决的问题。混合罚函数法n 内点法适于解仅含不等式约束问题，并且每次迭代的点都是可行点。这是设计员所希望的。但要求初始点为可行域的内点，需要浪费相当的工作量；n 外点法适用于求解一般约束问题，且初始值任意选取但求解结果常为不可行解，有时无法使用；n 结合外点法的优缺点，将内点法和外点法结合起来使用，得到混合罚函数法。对于一般约束问题，引进增广目标函数 其中：， n 在计算过程中，对迭代点求积极约束，不断更新集合 结束准则： ，乘子法考虑等式约束问题