非线性规划求解法

一维最优化方法 　

　　指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。

① 黄金分割法：又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。 ② 切线法：又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。 ③ 插值法：又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。

　　此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。

无约束最优化方法 　

　　指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。

　　无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数,称为解析法。另一类不涉及导数，只用到函数值,称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向,沿这个方向进行一维寻查,得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：

① 梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。 ② 牛顿法：收敛速度快，但不稳定，计算也较困难。 ③ 共轭梯度法：收敛较快，效果较好。 ④ 变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。

　　属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。

约束最优化方法

　　指前述一般非线性规划模型的求解方法。常用的约束最优化方法有四种。

① 拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。 ② 制约函数法：又称系列无约束最小化方法，简称SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。 ③ 可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克－沃尔夫法、投影梯度法和简约梯度法都属于此类算法。 ④ 近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。