非线性规划的概念和原理

1、第五章 非线性规划的概念和原理非线性规划的理论是在线性规划的基础上发展起来的。优性条件，为它的发展奠定了基础。以后随着电子计算机的普遍使用，非线性规划的理论和方法有了很大的发展，其应用的领域也越来越广泛，特别是在军事，经济，管理，生产过程自动化，工程设计和产品优化设计等方面都有着重要的应用。一般来说，解非线性规划问题要比求解线性规划问题困难得多，而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法。非线性规划的各种算法大都有自己特定的适用范围。都有一定的局限性，到目前为止还没有适合于各种非线性规划问题的一般算法。这正是需要人们进一步研究的课题。5.1 非线性规划的实例及数学模型例题6

2、.1 投资问题：假定国家的下一个五年计划内用于发展某种工业的总投资为b亿元，可供选择兴建的项目共有几个。已知第j个项目的投资为亿元，可得收益为亿元，问应如何进行投资，才能使盈利率（即单位投资可得到的收益）为最高？ 解：令决策变量为，则应满足条件同时应满足约束条件目标函数是要求盈利率最大。例题6.2 厂址选择问题：设有n个市场，第j个市场位置为，它对某种货物的需要量为。现计划建立m个仓库，第i个仓库的存储容量为。试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。解：设第i个仓库的位置为，第i个仓库到第j个市场的货物供应量为，则第i个仓库到第j个市场的距离为目标函数为约束条件为：（1

3、） 每个仓库向各市场提供的货物量之和不能超过它的存储容量；（2） 每个市场从各仓库得到的货物量之和应等于它的需要量；（3） 运输量不能为负数。因此，问题的数学模型为：s.t. , , ,一般非线性规划的数学模型可表示为：； s.t. , ,式中是n维向量，都是的映射（即自变量是n维向量，因变量是实数的函数关系），且其中至少存在一个非线性映射。与线性规划类似，把满足约束条件的解称为可行解。若记则称为可行域。因此上述模型可简记为 s.t. 当一个非线性规划问题的自变量X没有任何约束，或说可行域即是整个n维向量空间,即，则称这样的非线性规划问题为无约束问题：或有约束问题与无约束问题是非线性规划的两大

4、类问题，它们在处理方法上有明显的不同。5.2 无约束非线性规划问题无约束极值条件对于二阶可微的一元函数，如果是局部极小点，则，并且；反之，如果，则是局部极大点。关于多元函数，也有与此类似的结果，这就是下述的各定理。考虑无约束极值问题：，定理6.1 （必要条件）设是n元可微实函数，如果是以上问题的局部极小解，则。定理6.2 （充分条件）设是n元二次可微实函数，如果是上述问题的局部最小解，则，半正定；反之，如果在点有，正定，则为严格局部最小解。定理6.3 设是n元可微凸函数，如果，则是上述问题的最小解。例题6.3 试求二次函数的极小点。解：由极值存在的必要条件求出稳定点：， ，则由得，再用充分条件

5、进行检验：，则由为正定矩阵得极小点为。无约束极值问题的解法.1梯度法（i） 给定初始点，；（ii） 计算和，若，迭代停止，得近似极小点和近似极小值；否则，进行下一步；（iii） 做一维搜索或取作为近似最佳步长，并计算，令，转向第二步。例题6.4 求解无约束极值问题 解：取，则，故为极值点，极小值为。.2牛顿法对正定二次函数，其中A为n阶方阵，B为n维列向量，c为常数，设为其极小点，则，所以；任给，消去B，得所以 ，这说明，从任意近似点出发，沿方向搜索，步长为1，一步即可达极小点。例题6.5 求解无约束极值问题解：任取，由可知，确实为极小点。牛顿法与梯度法的搜索方向不同，优点是收敛速度快，但有时

6、不好用而需采取改进措施，当维数较高时，的计算量很大。5.3 约束非线性规划问题前面我们介绍了无约束问题的最优化方法，但实际问题中，大多数都是有约束条件的问题。求解带有约束条件的问题比起无约束问题要困难得多，也复杂得多。在每次迭代时，不仅要使目标函数值有所下降，而且要使迭代点都落在可行域内（个别算法除外）。求解带有约束的极值问题常用方法是：将约束问题化为一个或一系列的无约束极值问题；将非线性规划化为近似的线性规划；将复杂问题变为较简单问题等等。凸规划问题约束问题的情况较为复杂，先讨论其中的一种较为特殊的情况，即凸规划问题。一般来说，非线性规划的局部最优解和全局最优解是不同的，但是，对凸规划问题，

7、局部最优解就是全局最优解。定义6.1设为定义在非空凸集上的实值函数，如果对于任意的两点，和任意实数，恒有则称为S上的凸函数。定理6.4 设S是n维欧氏空间上的一个开凸集，是定义在S上的具有二阶连续导数的函数，那么，在S上为凸函数的充要条件是：对所有，海赛矩阵都是半正定的；如果对所有的，都是正定的，则在S上为严格凸函数。定义6.2 非线性规划问题：，s.t. 中，如果和（）为x的凸函数，（）为X的线性函数，则称此问题为一凸规划问题。凸规划具有两个重要性质：1 凸规划的可行集是凸集证：设凸规划的可行集为S，即其中（）为X的凸函数，（）为X的线性函数。 对于任意的，和任意实数，利用（）的凸性，对，有

8、但，所以同理因此，故S为凸集。2 凸规划的局部最小解就是它的全局最小解证：用反证法。设是凸规划的一个局部最小解，是它的全局最小解，但。因为 ，所以，由为凸函数得，因为是一个全局最小解，所以此式对一切都成立。当时，则，即在的邻域内还有比小的值，与为局部极小解的假设矛盾。因此，凸规划的局部最小解就是它的全局最小解。例题6.6 验证下述非线性规划为凸规划，并求出最优解。s.t. 解：第1，3，4三个约束条件为线性函数，因此也是凸函数； 第2个约束条件应写成，因此海赛矩阵为，半正定，为凸函数同理，正定，也为凸函数。所以，该非线性规划为凸规划。用图解法得为其唯一极小点，其它类型的约束非线性规划问题考虑只

9、含不等式约束条件下求极小值问题的数学模型：， s.t. 或写成其中可行域。定义6.3对于上述问题，设，若有，则称不等式约束为点处的起作用约束；若有，则称不等式约束为点处的不起作用约束。定义6.4对于上述非线性规划问题，如果可行点处，各起作用约束的梯度向量线性无关，则称是约束条件的一个正则点。库恩塔克条件是非线性规划领域中的重要理论成果之一，是确定某点为局部最优解的一阶必要条件，只要是最优点就必满足这个条件。但一般来说它不是充分条件，即满足这个条件的点不一定是最优点。但对于凸规划，库恩塔克条件既是必要条件，也是充分条件。对于只含有不等式约束的非线性规划问题，有定理如下：定理6.5 设是非线性规划

10、问题 的极小点，若起作用约束的梯度线性无关（即是一个正则点），则，使下式成立对同时含有等式与不等式约束的问题；s.t. , ,为了利用以上定理，将，用来代替。这样即可得到同时含有等式与不等式约束条件的库恩塔克条件如下：设为上述问题的极小点，若起作用约束的梯度和线性无关，则和，使下式成立例题6.7 求下列非线性规划问题的K-T点：s.t. 解：将上述问题的约束条件改写为的形式：设K-T点为，有，由定理得 求解上述方程组，即可求出，,，则可得到满足K-T条件的点。上述方程组是非线性方程组，求解时一般都要利用松紧条件（即上述方程组中的第3，4个方程），其实质是分析点处，哪些是不起作用约束，以便得到，这样分情况讨论求解较为容易：（1） 假设两个约束均是点处的不起作用约束，即有 ，则有 解得 但将该点代入约束条件，不满足，因此该点不是可行点。（2） 若是起作用约束，是不起作用约束，则有，则解得 代入原问题约束条件中检验，可知该点是可行点，且满足K-T定理的条件，又是一个正则点，故它是一个K-T点。因为是起作用约束，此时，可以是，也可以是，若也成立，则结果同（1），已知求出的解不是可行点。（3） 若是不起作