[拼音]:feixianxing guihua [外文]:nonlinear programming 目标函数是非线性函数或约束条件不全是线性等式(或不等式)的一类数学规划,即在问题 ![]() 中,若ƒ(尣)为非线性的,或Ω不能用线性(不)等式表出,则此规划问题就称为非线性规划问题。由于问题的这种描述过于广泛,使得难于得到任何有深刻意义的结果。同时,对于某些特殊类型的Ω(例如Ω中点的坐标仅限于取某些整数值),需要特殊的方法去处理因而形成了一些独立的分支。非线性规划问题一般取如下的形式: ![]() 这里g(尣)=(g1(尣),g2(尣),…,gm(尣))为一给定的m 维向量实函数,g(尣)≤0表示它的所有分量皆不大于0,G为一给定的凸域,在多数情况下, 算法在ƒ(尣) 和Ω给定时,如何求出一个(或多个)点尣*∈Ω,使得ƒ(尣*)≤ƒ(尣)对所有尣∈Ω成立,是研究非线性规划的主要目的。因此,寻求能找出此尣*的算法便成为非线性规划研究的核心。目前尚未出现可以用来解决所有非线性规划问题的任何算法,算法的研究将是一个长期的课题。一般的算法都是迭代算法。除了某些特殊情况之外,求解的过程是一种无限过程,即逐渐逼近于所求的解。为了要判断一个算法所产生的点或所产生的极限点是否为所给问题的解,从而导致寻求解的充分必要条件。 充分必要条件对一般的约束非线性规划问题: ![]() 设函数ƒ、gi、hj都是一阶可微函数, ![]() 这一组条件称为库恩-塔克尔条件,又称为一阶必要条件。它是由H.W.库恩和A.W.塔克尔于1951年提出的。但是在凸性假设下,它又是充分条件。 库恩-塔克尔条件对于任意一个局部极小点并不一定成立。约束规格,是指约束条件在局部极小点处具有使库恩-塔克尔条件成立的性质。例如上述的“梯度墷gi( ![]() 式中ƒ、gi、hj均为一阶可微函数。F.约翰在1948年提出这个条件,由于他没有考虑约束规格,因此他的条件中,主要参数u0可能为零而使此条件失效。 对于不可微的凸规划,有推广的库恩-塔克尔条件。在推广库恩-塔克尔条件时需要引入次梯度的概念。设ƒ是Rn中的凸函数,若向量ξ满足 ![]() 式中ƒ和gi都是凸函数。设gi满足斯雷特约束规格:存在一点尣0,使得gi(尣0)<0,i=1,2,…,m。则可行点 对偶问题是指根据 (P)中的数据建立起来的一个与所给的问题(P)伴随的问题(P*)。 (P)与(P*)之间有如下的关系: (1)若(P)是求目标函数ƒ(尣)的极小(大)值,则(P*)是求某一目标函数 l(у)的极大(小)值; (2)对于(P)与(P*)的可行解尣与у,常有ƒ(尣)≥l(у)(ƒ(尣)≤l(у)); (3)(P)与(P*)在 x*与у*取最优值的充分必要条件是l(у*)=ƒ(尣*)。 对于所给定的(P),能满足上述三种性质的(P*)一般并不是惟一的。因此就存在构造(P*)的不同途径。目前研究对偶性主要有两条途径。 其一是利用拉格朗日乘子。例如线性规划(P): ![]() 这里,I(I*)中之min(max)只限于就 一般,令 ![]() 其对偶问题为 ![]() 更一般言之,设φ(尣,у)为定义在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.卡鲁什的结果,但可以看作是非线性规划理论工作的先驱。这组条件更合适的名称应该是卡鲁什-库恩-塔克尔条件。
|