计算加权线性矩阵不等式分析中心使用牛顿法不可行

文摘

我们研究的问题计算加权分析中心系统的线性矩阵不等式约束。可以使用标准的牛顿法来解决问题。然而,这种方法需要一个起点在可行域内点或一个阶段我问题得到解决。我们解决这个问题通过使用不可行的牛顿法应用于马方程组,可以从任何时候开始。我们也使用回溯搜索技术和实现方法研究大重量的影响的方法。我们用数值实验比较不可行牛顿法和牛顿法标准。结果表明,牛顿法不可行措施可行的内部地区往往很快,从任何时候开始。我们建议它作为一个方法来找到一个内点通过设置每个重量是1。似乎要比标准的牛顿法找到权重的加权分析中心没有一个相对于其他权重非常大。然而,我们发现不可行牛顿法更敏感的牛顿法比标准大重量的变化。

1。介绍

我们认为一个系统的线性矩阵不等式约束如下: 在哪里是一个变量和每个是一个对称矩阵。线性矩阵不等式(LMI)约束已经被充分研究过特别领域的半定规划(1,2]。LMI约束应用在各种领域,包括工程、几何和统计数据。我们假设的可行性取决于约束是有界的,非空的内部。这意味着集是线性无关的3]。

在本文中,我们考虑的是计算加权分析中心的lmi使用牛顿法不可行。一个可行的起点不需要启动方法。在特殊情况下的线性约束,加权分析中心已经被广泛的研究在过去的(例如,[4])。中心加权分析lmi延伸中给出的定义(4]在[5,6]。研究加权分析中心本身的兴趣。许多算法利用半定规划是线性规划和基于加权分析中心(2,3,7,8]。

加权线性矩阵不等式分析中心可以找到使用标准的牛顿法通过最小化屏障功能。这种方法的缺点,从可行域的内部必须有。牛顿法也不工作时的一些权重相对相对于其他权重非常大。不可行牛顿方法分析单LMI约束给出中心(9]。我们现在不可行牛顿法寻找加权分析中心,可以从任何时候开始。方法应用于Karush-Kuhn-Tucker(马)方程组加权分析的中心问题。我们也使用回溯搜索技术和实现方法研究大重量的影响的方法。我们用数值实验比较不可行牛顿法和牛顿法标准。

我们发现牛顿法不可行举措很快成可行的内部区域的大部分时间里我们的测试问题。这似乎是一种适当的方法来找到一个内部的系统通过设置每个重量是1。牛顿法效果优于标准如果没有一个权重相对很大的对其他的权重。我们也发现不可行牛顿法对大的变化更敏感比标准牛顿法的权重。对于非常大的权重的变化,我们建议使用牛顿法不可行进入室内,每个重量设置为1,然后切换到标准牛顿法收敛加权分析中心使用原来的重量和从内部开始。

2。中心加权分析线性矩阵不等式

让表示定义的可行域的不平等(1)。鉴于,定义屏障功能通过的加权分析中心对于系统(1)被定义为5,6]

这个定义扩展了(4)线性约束。当,被称为分析中心。加权分析中心内点方法用于线性规划和半定规划(2,3,7,8,10]。半定规划的非中央路径收敛于最优解集的分析中心(11]。

标准牛顿法选择寻找加权分析中心。梯度和黑森的屏障功能是由(6以下:为 标准的牛顿法计算加权分析中心输入:一个内点、宽容集重复(1)计算牛顿方向(2)计算(3)线搜索得到stepsize吗(4)更新(5)更新直到。

线搜索技术,如采用线搜索技术可以用在牛顿法找到加权分析中心(9]。

3所示。不可行牛顿法计算加权分析中心

在本节中,我们描述不可行牛顿法寻找加权分析中心。计算的加权分析中心的问题(3)是一个更一般形式的行列式最大化问题[3]。其双重由以下给出: 的子弹矩阵点积。定理1给出了最优性条件计算加权分析中心。

定理1(见[3])。假设原始问题(3)和对偶问题(5)严格可行的。原始的最优解集和双最优解系统的可行的解决方案吗

最优性条件定理1可以写同样吗现在,在3),让在哪里是栈的地图一个矩阵的列上彼此成一个向量和是逆映射。同时,让然后,系统的(7)成为。牛顿方向系统发现通过求解线性系统: 使用块消除,我们得到的在哪里矩阵是正定的。以下是不可行的牛顿法的迭代。在步骤2的迭代是不对称的。我们使对称在步骤3。

不可行牛顿法的迭代计算加权分析中心

步骤1。计算牛顿方向使用(13)。
这给了。

步骤2。为每一个,确定

步骤3。使对称。
取代通过。

步骤4。线搜索得到stepsize吗。

第5步。更新迭代

任何时候可以作为一个起点。然后,对于选择上述重复迭代,直到,在那里是剩余,是一个给定的公差。一行可以使用回溯搜索(9)或其他技术来获取stepsize。

4所示。数值实验

在本节中,我们给出数值实验比较不可行牛顿法与标准的牛顿法。我们也调查大重量的影响的两种方法。

表1描述了35个随机测试问题用于我们的数值实验。第二列的表1给出了尺寸环境空间和第三列的数字的约束。维度第四列矩阵给出的。对于每一个随机的问题,,,和LMI给出随机生成如下:是一个对角矩阵与对角项选择。每一个()是一个随机的对称与近似稀疏矩阵非零项使用MATLAB命令生成的。每个问题都有一个非空的内部。


LMI测试问题

1	2	2	2、1
2	3	4	3、4、1、2
3	2	2	2、2
4	5	3	4、1、3
5	4	3	5、4、3
6	4	5	4、3、1、1、4
7	3	3	4、2、3
8	3	4	4、2、2、5
9	5	3	4、1、1
10	3	5	5、3、5、1,4
11	2	7	2、5、3、5、2、5、1
12	5	6	5、1、3、4、1、4
13	14	5	5、1,3,4,2
14	20.	5	5、2、5、1、5
15	3	8	5、4、1、5、3、5、1、3
16	9	7	1、4、2、4、4、2、2
17	6	5	4、4、2、1,4
18	10	2	3、5
19	15	9	2、5、3、1、2、3、3、1、2
20.	8	2	4、5
21	19	7	5、2、2、2、5、5、5
22	9	10	3、4、1、1,3,5,5,4,5,2
23	3	4	2、3、2,5
24	8	2	5、1
25	2	8	5、2、1、1、1、5、3、3
26	13	8	4、1、4、2、3、1、2、1
27	24	10	5、4、5、1,4,2,3,5,5,2
28	5	6	4、1、4、2、1,3
29日	16	3	2、2、3
30.	2	2	4、5
31日	2	4	1、5、5、5
32	4	4	5、1、4、5
33	4	4	1、2、3、5
34	17	9	1、5、2、1、2、5、1、4、3
35	20.	5	5、2、5、1、5

我们的代码是用MATLAB编写,跑在880年戴尔商用台式机电脑。不可行牛顿法和牛顿法标准实施使用公差和最多500次迭代。的起点是随机的,它的每个组件从一个正态分布均值为0,方差。我们使用回溯行搜索技术的两种方法。表2比较不可行牛顿法与标准牛顿法不同的权重。在1 - 15的每一个问题,一个是重量,这是一个很高的值相对于别人。问题35,没有权重相对很大。在表2、第三和第四列给所需的迭代次数和时间发现第一点在可行域的内部由牛顿法不可行(职责)。第四和第五列给找到所需的迭代次数和时间加权分析中心(职责)从第一个内陆点。第六个和第七列在表中2给找到所需的迭代次数和时间加权分析中心通过标准的牛顿法(职责)。标准的牛顿法是开始从相同的内部点如牛顿法不可行。牛顿法不可行牛顿法和标准比较表3与重量。


问题	权重	牛顿正无穷。 1有限元分析。点 iter。	牛顿正无穷。 1有限元分析。点时间(秒)	牛顿正无穷。 iter。	牛顿正无穷。时间(秒)	圣牛顿 iter。	圣牛顿时间(秒)

1	,10	2	0.0185	4	0.0096	2	0.0056
2	、100、100、1	3	17.2562			3	0.0161
3	,1000年	51	0.3771	46	0.1690	41	0.1042
4	10 1	20.	10.8898			9	0.0687
5	1,10	2	8.8548			4	0.0215
6	1,1 100
7	100年10	129年	9.5582			33	0.1810
8	1,1000,,10
9	、1000、1000	1	8.5943			4	0.0278
10	,1000,100,1000,100	6	25.3801			2	0.0158
11	,100,1000,1000,100
12	1,100,10日,10	3	17.5497			5	0.0701
13	1000年,、1000、100、100
14	1,1000,,1000年1
15	1,1,1,100,、100、100、10
16	10、1、10、1000、1000、10、1	24	0.2885	3	0.0234	5	0.2108
17	100、100、1000	3	0.0508	4	0.0252	3	0.0534
18	1000	2	0.0286	6	0.0182	4	0.0579
19	100,1000,1000,100,100,1000,10	10	0.2117	7	0.0749	8	0.9943
20.	1000年,1000年	1	0.0180	4	0.0125	7	0.0664
21	1、10、1,100,10日,1	21	0.3301	3	0.0342	3	0.4761
22	1、1000、100、1000,1,100年,100年,100年,1	7	0.2006	3	0.0491	3	0.2011
23	100、10、1 1	4	0.0609	5	0.0231	6	0.0297
24	1000年,1	12	0.0564	2	0.0052	3	0.0348
25	1、10、1000、1、1、10	8	0.1360	3	0.0280	3	0.0224
26	100,100,1,1,1,1,1	20.	0.2815	2	0.0208	3	0.3256
27	1 1,1,1,10日,10日,1,100,1,10	8	0.3212	4	0.0945	6	2.1028
28	100年10日,10日,1,1,1	7	0.0986	3	0.0246	4	0.0718
29日	1,1,10	1	0.0092
30.	10、1	2	0.0268	4	0.0149	3	0.0121
31日	1、10、1 1	1	0.0444	4	0.0326	4	0.0270
32	100年,1,10日,1	8	0.0994	4	0.0278	4	0.0444
33	100、100、1、10	6	0.0612	3	0.0168	3	0.0318
34	1 100年1 1 1,10日,100年,100年,10	7	0.1870	3	0.0426	5	0.9478
35	1,100,1,1	31日	0.3678	2	0.0175	2	0.3845


问题	牛顿正无穷。 1有限元分析。点 iter。	牛顿正无穷。 1有限元分析。点时间(秒)	正,牛顿iter。	牛顿正无穷。时间(秒)	圣牛顿 iter。	圣牛顿时间(秒)

1	1	0.0115	3	0.0068	3	0.0059
2	2	0.0327	4	0.0188	3	0.0177
3	1	0.0318	9	0.0271	10	0.0180
4	2	0.0230	3	0.0114	3	0.0249
5	1	0.0250	4	0.0180	4	0.0239
6	1	0.0348	4	0.0248	4	0.0355
7	1	0.0271	5	0.0206	7	0.0247
8	1	0.0284	4	0.0202	3	0.0170
9	1	0.0215	4	0.0145	3	0.0224
10	1	0.0641	6	0.0532	8	0.0520
11	1	0.0451	3	0.0311	3	0.0207
12	2	0.0460	3	0.0237	3	0.0461
13	2	0.0555	4	0.0268	6	0.3949
14	13	0.1481	4	0.0302	6	0.8056
15	1	0.0805	5	0.0629	3	0.0330
16	2	0.0599	4	0.0339	7	0.2742
17	2	0.0370	3	0.0185	3	0.0508
18	2	0.0184	3	0.0088	4	0.0569
19	3	0.0933	4	0.0390	3	0.4423
20.	1	0.0196	4	0.0134	7	0.0665
21	12	0.2080	4	0.0463	5	0.7110
22	2	0.1079	4	0.0659	3	0.2002
23	1	0.0276	4	0.0196	3	0.0164
24	4	0.0281	4	0.0123	6	0.0616
25	2	0.0553	3	0.0286	3	0.0217
26	13	0.1980	3	0.0303	3	0.3295
27	3	0.1791	2	0.0902	2	1.6525
28	3	0.0612	3	0.0262	3	0.0567
29日	1	0.0102
30.	2	0.0275	4	0.0157	3	0.0140
31日	1	0.0359	3	0.0231	3	0.0210
32	2	0.0431	3	0.0212	2	0.0264
33	4	0.0573	4	0.0240	6	0.0543
34	2	0.0992	4	0.0550	4	0.7863
35	13	0.1795	4	0.0367	6	0.8997

图1显示不可行的牛顿法的迭代收敛问题3。很明显的图不可行牛顿法收敛之前大幅放缓加权分析中心。另一方面,见图2,该方法快速聚合。图3显示了如何规范梯度随迭代次数的两个值的权重。在表2,入口意味着不可行牛顿法未能收敛后的最大数量500次迭代问题2,4,5,6,7,8,9,10,11,12、13、14、15日和29日。然而,它设法找到一个内点(1)问题2,4,5,7,9,10,12,29岁。从表中我们可以看到,这两种方法可能不适合在一些权重相对比其他的权重。结果还表明,牛顿法标准执行比牛顿法不可行。在牛顿法不可行,剩余函数的雅可比矩阵变得越来越病态的边界附近的系统(8)和(9由于矩阵)和体重增加之间的变化。观察到不可行牛顿法未能在8收敛问题,即使它找到了一个可行域的内部点(1)。标准的牛顿法聚合(500次迭代的极限内)为每个8的问题除了问题29。标准的牛顿法聚合29 536次迭代后的问题。

在表3,入口29日表明,牛顿法不可行问题未能收敛分析中心经过500次迭代的最大数量。然而,它设法找到一个内点(11)迭代。问题29显示不可行的牛顿法和牛顿法的标准可能无法收敛(500次迭代)即使权重都是平等的和一个内点。我们看到从表3,不可行的牛顿法的迭代次数少12个35的问题,而标准的牛顿法迭代次数少了9个35的问题。牛顿法不可行了更少的时间在23个35的问题和标准牛顿法花更少的时间在11个35的问题。从表中有趣的是不可行的牛顿法发现的内部点(1)在1 - 3的迭代的测试问题。

结果表2和3表明,如果没有一个权重相对很大,不可行的牛顿法是一种更好的方法比标准牛顿法找到加权分析中心。当一个重量相对非常大,一个可以用牛顿法不可行找到一个内部点,然后切换到标准的牛顿法使用原来的重量和从内部点。

5。结论

我们提出不可行牛顿法计算加权分析中心系统的线性矩阵不等式,并与标准的牛顿法。

我们发现不可行牛顿法很快找到一个点在内陆点,从任何时候开始,尤其是当没有权重相对很大。当没有权重相对很大,不可行的牛顿法似乎比标准牛顿法找到加权分析中心。然而,牛顿法不可行不工作时的一些权重非常大相对于他人,但它仍然经常在内部找到一个点,从任何时候开始。我们发现不可行牛顿法适用于找到一个内部的系统通过设置每个重量是1。我们建议,当一些权重相对很大,每个人都应该使用牛顿法不可行在内部找到一个点找到一个内部点,然后切换到标准的牛顿法使用原来的重量和从内部点。

提高效率的不可行牛顿法寻找加权分析中心,这将是有用的利用block-diagonal矩阵的结构,,在未来实现。我们想调查方法如何处理重量,一些相对比另一个更大的权重。此外,它将感兴趣的研究不可行的牛顿法的应用加权分析中心SDP-CUT半定规划的算法,提出了(8]。实现不可行牛顿法加权分析中心使用不同的搜索方向是目前正在接受调查。加权分析问题的中心是一个行列式最大化问题和算法可以解决这些问题。这将是比较感兴趣的这些算法的性能的方法。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

作者要感谢朱拜勒在沙特阿拉伯大学提供一个家,2014 - 2015年公休假。本研究工作在这离开。

引用

f . Alizadeh“半定规划的内点方法与应用程序组合优化,“暹罗杂志上优化,5卷,不。1,13-51,1995页。视图:出版商的网站|谷歌学术搜索
l . Vandenberghe s·博伊德,“半定规划。”暹罗审查,38卷,不。1,49 - 95年,1996页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
l . Vandenberghe s·博伊德,S.-P。吴”,行列式具有线性矩阵不等式约束的最大化。”暹罗《矩阵分析和应用程序,19卷,不。2、499 - 533年,1998页。视图:出版商的网站|谷歌学术搜索
d·s·阿特金森和p . m . Vaidya“缩放技术寻找加权分析中心的多面体,”数学规划卷,57号1,第192 - 163页,1992。视图:出版商的网站|谷歌学术搜索
即美国记者和美国Jibrin加权线性矩阵不等式分析中心”,不平等在纯和应用数学杂志》上,卷2,不。3、第二十九条,2002年。视图:谷歌学术搜索
美国Jibrin和j·w·斯威夫特的边界加权线性矩阵不等式分析中心,“不平等在纯和应用数学杂志》上,5卷,不。1,第十四条,2004。视图:谷歌学术搜索
j . Renegar”,一个多项式时间算法,基于牛顿法,线性规划,“数学规划,40卷,不。1 - 3,59 - 93年,1988页。视图:出版商的网站|谷歌学术搜索
j·s . Jibrin,“一个内点方法求解半定规划使用降低飞机和加权分析中心,“应用数学学报ID 946893条,卷。2012年,21页,2012。视图:出版商的网站|谷歌学术搜索
l . Vandenberghe和s·博伊德,凸优化,剑桥大学出版社,纽约,纽约,美国,2004年。
f . Alizadeh j。答:一、m . l . Overton”半定规划内点方法:收敛速度,稳定性和数值结果,“暹罗杂志上优化,8卷,不。3、746 - 768年,1998页。视图:出版商的网站|谷歌学术搜索
Z.-Q。罗、j . f . Sturm和美国,“超线性收敛的对称半正定规划路径跟踪算法,”暹罗杂志上优化,8卷,不。1,59 - 81年,1998页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学

数学杂志

文摘