词条 | 非线性规划 |
释义 | feixianxing guihua 非线性规划(卷名:数学) nonlinear programming 目标函数是非线性函数或约束条件不全是线性等式(或不等式)的一类数学规划,即在问题 ![]() ![]() ![]() 算法 在ƒ(尣) 和Ω给定时,如何求出一个(或多个)点尣*∈Ω,使得ƒ(尣*)≤ƒ(尣)对所有尣∈Ω成立,是研究非线性规划的主要目的。因此,寻求能找出此尣*的算法便成为非线性规划研究的核心。目前尚未出现可以用来解决所有非线性规划问题的任何算法,算法的研究将是一个长期的课题。一般的算法都是迭代算法。除了某些特殊情况之外,求解的过程是一种无限过程,即逐渐逼近于所求的解。为了要判断一个算法所产生的点或所产生的极限点是否为所给问题的解,从而导致寻求解的充分必要条件。 充分必要条件 对一般的约束非线性规划问题: ![]() ![]() ![]() ![]() ![]() ![]() 库恩-塔克尔条件对于任意一个局部极小点并不一定成立。约束规格,是指约束条件在局部极小点处具有使库恩-塔克尔条件成立的性质。例如上述的“梯度墷gi( ![]() ![]() ![]() ![]() 对于不可微的凸规划,有推广的库恩-塔克尔条件。在推广库恩-塔克尔条件时需要引入次梯度的概念。设ƒ是Rn中的凸函数,若向量ξ满足 ![]() ![]() ![]() ![]() ![]() ![]() ![]() 对偶问题 是指根据 (P)中的数据建立起来的一个与所给的问题(P)伴随的问题(P*)。 (P)与(P*)之间有如下的关系: ①若(P)是求目标函数ƒ(尣)的极小(大)值,则(P*)是求某一目标函数 l(у)的极大(小)值;②对于(P)与(P*)的可行解尣与у,常有ƒ(尣)≥l(у)(ƒ(尣)≤l(у));③(P)与(P*)在 x*与у*取最优值的充分必要条件是l(у*)=ƒ(尣*)。 对于所给定的(P),能满足上述三种性质的(P*)一般并不是惟一的。因此就存在构造(P*)的不同途径。目前研究对偶性主要有两条途径。 其一是利用拉格朗日乘子。例如线性规划(P): ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 一般,令 ![]() ![]() ![]() ![]() 更一般言之,设φ(尣,у)为定义在X×Y上的实函数,于此,X吇Rn,Y吇Rm。作 ![]() ![]() ![]() ![]() ![]() ![]() 其二是利用共轭函数。若ƒ(或l)为定义在凸集C吇Rn(D吇Rn)上之凸(凹)函数,则称 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 上述两条途径皆得到了深入的发展,特别是R.T.洛卡费勒基于增广拉格朗日函数发展了一般的对偶理论。 研究对偶理论的目的主要有三:一是某些实际问题,特别是某些经济问题,其中所出现的某些现象用对偶理论容易得到解释;二是可以利用它来帮助求解原问题;三是判定原问题是否有解。例如,有时(P*)比(P)容易得到解决,利用性质③即可得出ƒ(尣)的极值;性质②有助于求ƒ(尣)的下界。这一点在分枝定界法中常用到。对偶问题的出现是相当普遍的。数学规划中的许多分支,例如整数规划,参数规划、模糊规划等皆有类似的问题和不同深度的处理。 稳定性 一个数学规划问题 ![]() 形如 ![]() ![]() 非线性规划是极值理论的一部分。早在17世纪P.de费马提出如下的问题:对于平面上给定的三点,要作一点使其与这三点的距离之和为最小。它的对偶问题:过所给三点作一最大的等边三角形,也早在18世纪初即已提出,并证明了这两问题之间存在对偶关系。 对具有等式约束的非线性规划的解应满足的必要条件的研究,可上溯到L.欧拉和J.-L.拉格朗日时代。W.卡鲁什在1939年开始了对具有不等式约束的非线性规划的类似问题的研究,但由于他的工作没有正式发表,同时由于当时计算机尚未出现,数学规划不能在生产实际中产生影响,这项工作便湮没无闻。非线性规划的发展是由于线性规划的出现而引起的。1951年H.W.库恩和A.W.塔克尔的研究工作,虽是重复了W.卡鲁什的结果,但可以看作是非线性规划理论工作的先驱。这组条件更合适的名称应该是卡鲁什-库恩-塔克尔条件。 参考书目 M.阿弗里耳著,李元熹等译:《非线性规划──分析与方法》,上海科学技术出版社,上海,1979。(M.Avriel,Nonlinear Programming-Analysis and Methods, Prentice-Hall,Englewood Ciffs,New Jersey,1976.) |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。