文摘
摘要总constraint-shifting同伦方法求解一般的非凸非线性规划。聚合是只有不等式约束函数。没有任何锥条件约束函数,全局收敛解的存在性和收敛K-K-T系统得到可行和不可行的起点在更弱的条件下。
1。介绍
在,让 , ,和表示 - - - - - -维欧几里得空间,负的象限和积极的象限 ,分别。本文以下一般的非凸非线性规划将被认为是: 在哪里 和 , ,和 三个连续可微的函数。表示 , ,和 。
众所周知,优化问题的解决可以通过解决凸K-K-T系统非线性问题,但对于非凸非线性问题,我们只能获得K-K-T系统问题的解决方案(1)。
重视同伦方法作为一种重要的全局收敛的计算方法在寻找解决各种非线性问题,因为它被引入和研究了凯洛格等。1,斯梅尔2),和食物等。3]。然而,最初的同伦只是单一同伦和解决非线性问题时需要多强大的假设。在1990年代,一个组合同伦内点(芯片)方法在求解非凸规划首先提出由冯法锥条件下,于(4]。从那时起,各种芯片的方法,作为一个有效的可实现的算法,被广泛使用,在求解一般的非凸规划新建,不动点问题,互补问题、变分不等式,等等,看,例如,(5- - - - - -20.]。
2001年,为减少系统的维数数值跟踪过程中产生和削弱收敛条件,Yu et al。21)提出了一个总体约束同伦方法(ACH法)对凸编程使用所谓的聚合函数的约束。2018年,一个新的ACH法与不等式和等式约束的非线性规划问题,提出了在22]。然而,ACH法仍然属于芯片,因为它要求初始点也是在原始可行集。2006年,为了避免芯片的缺点必须选择可行的初始点集,一个constraint-shifting组合同伦不可行内点法的初始点可以选择在这两个可行和不可行集的求解非线性规划提出了只有不等式约束Yu和商(23,24]。2012年,延长constraint-shifting组合同伦方法解决一般非线性规划,另一个新组合同伦不可行内点法求解非凸规划提出了不等式和等式约束(25),只有不等式约束需要满足法锥条件。从那以后,更多constraint-shifting同伦方程构建和扩展求解非线性规划,委托代理问题,不动点问题,等等,看,例如,(26- - - - - -30.]。然而,这些组合同伦方法通常需要一些证明强收敛锥条件存在的光滑的同伦路径。
上面引用的启蒙运动,没有任何锥条件下,一个聚合约束组合同伦不可行内点法求解非凸非线性规划与不等式和等式约束构造,和全局收敛性弱得多的条件下获得。
本文的其余部分组织如下。节2构造同伦方程,介绍了微分拓扑的一些前题。节3、主要结果将和一个平滑的路径的存在性和收敛的任何点的不可行集K-K-T系统的解决方案。节4,数值算法。
2。预赛
将使用以下假设:(A1) 是一个有界和连接, 。(A2) ,矩阵 是正的线性无关 ,也就是说,
由(21),聚合函数 ,我们有
我们构建以下转移聚合约束函数只与不等式约束函数: 在哪里 是一个参数,是凸和三个连续可微的函数。因此,我们有 和
很明显, 也三个连续可微的函数;让 , , ,和 。
引理1(见[21])。如果假设(A1)和(A2),然后存在 ,为 ,和
引理2(见[27])。如果假设(A1)和(A2),存在 ,为 ,我们有这是一个有界和连接设置,非空的是。
引理3。如果假设(A1)和(A2),存在 ,对于任何给定的可行点 ,和 ,矩阵 是正的线性无关的。
证明。证明了矛盾。为 和任何可行的观点 ,存在 和 属于实部,同时不等于零,这样 让 和 ;两边的8) ,也就是说, 当 , ;让 ,作为 ,我们有 与假设(A2),这是一个矛盾 ,对于任何 ,矩阵 是正的线性无关的。
定义 。自非空的,对吗 , ,和 ,让 ,我们构造同伦方程如下: 在哪里 , ,和 。
当 ,同伦方程(11)转向K-K-T系统
当 ,同伦方程(11), ,有一个独特的简单的解决方案
下面的前题从微分拓扑将在下一节中使用。首先,让 是一个开集,让 是一个 映射;我们说 是一个常规的价值如果
引理4(见[31日])。让 开放组,让 是一个映射, 。如果 是一个常规的价值 ,然后几乎所有 ,0是一个常规的价值 。
引理5(见[31日])。让 是 。如果0是一个常规的价值 ,然后包括一些 - - - - - -维集合管。
引理6(见[31日])。一维光滑流形是diffeomorphic单位圆或一个单位时间间隔。
3所示。主要结果
对于一个给定的 ,重写 在同伦方程(11),
零点的一组 是
引理7。如果假设(A1)和(A2), ,如果存在一个平滑的曲线从 在 ,然后它必须是有界的。
证明。如果
是无限的,有吗
,和
。
从第二个方程(11),我们有
由方程(17),
,
,和
,通过引理2,也是有限的,所以呢是一个有界序列。因此,必须存在一个收敛的子序列也表示是哪一个
。让
和
作为
。表示
,由(17),
;因此,我们获得
从第一个方程(11),我们有
(我)当
,从第三个方程(11),我们有
作为
,这意味着是有界的。因此,
和
。如果
,不失一般性,假设
,然后
为
从第二个方程(11)。限制在(19),我们有
但
是一个凸函数;这是不可能的。如果
,讨论下面的案例(ii)是一样的。(2)当
,不失一般性,假设
与
和
为
。通过方程的两边同时除以(19)和限制,
这与引理3。(3)当
,不失一般性,假设
与
和
,为
。通过方程的两边同时除以(19)
和限制,
这与引理3。
总之,从上面的讨论,我们得到是一个有界曲线
。
定理1。假设假设(A1)和(A2),几乎所有 ,同伦方程的零点集(11)包含一个平滑的曲线 从 ,终止或超平面的方法 。如果 是一个极限点的 ,然后 K-K-T系统问题的解决方案(11)。
证明。让
是一样的地图
但作为变量。考虑下面的雅可比矩阵的子矩阵
:
对所有
和任何
,从
和
,我们得到
非奇异的,这意味着
是满秩。
因此,矩阵
满行秩。也就是说,0是一个常规的价值
。由引理4我们有,几乎所有
,0是一个常规的价值
。
请注意,这个矩阵
是满秩。从引理5,如果0是一个常规的价值
,
非奇异的,事实吗
,
必须包含一个平滑的曲线呢从
和要
。然后,从引理6曲线,
必须diffeomorphic单位圆或单位时间
。
我们有不是diffeomorphic单位圆。也就是说,是diffeomorphic
。让
的极限点
;只可能有以下5个案例:
自
只有一个方程的解决方案
和
是满秩的,例(我)是不可能的。从引理7、案例(ii)也是不可能的。
从
,我们有
和
,也就是说,
,对于一些
,不能同时发生。因此,例(3)是不可能的。如果乘数
和同伦参数
,从
,我们可以得到
,这意味着这种情况下(iv)也是不可能的。
作为一个结论,(v)是唯一可能的情况。也就是说,曲线必须终止或超平面的方法吗
。因此,
K-K-T系统问题的解决方案(1)。
4所示。数值算法
由定理1同伦方程(11)生成一个平滑的曲线几乎所有 作为 ,和一个同伦方程可以找到一个解决方案(11)。让的弧长 ,我们可以参数化关于 ,也就是说,
通过区分(26),我们可以得到 在哪里的导数是 。
如何跟踪同伦路径数字,我们可以使用标准的预估过程;更多细节,请参阅[32,33]。在本文中,我们的贡献只有理论结果对该算法只要求任何可以选择初始点移位的可行集,但不一定在原始可行集。相对同伦算法和数值模拟对该算法的性能可以实现为(34]。
数据可用性
没有数据被用来支持本研究。
的利益冲突
作者宣称没有利益冲突。
作者的贡献
两位作者的贡献同样本文和阅读和批准最后的手稿。
确认
健脾温朱是吉林省教育部门基金(批准号JJKH20190742SK)和高级人才研究辽宁大学的基金。Yeong-Cheng Liou部分支持的大多数109 - 2410 h - 037 - 010和108 - 2410 h - 037 - 020和高雄医学大学研究基金会(批准号KMU-M108002)。