ABSTRACT

A new smoothing inexact Newton method is presented for solving the second-order cone programming. At each iteration, the method uses an inexact Newton method to solve the system of equations, which saves computation work of smoothing Newton methods. Under weak assumptions, our method is proved to have global and local quadratic convergence. Numerical experiments indicate that the proposed method is quite effective.

Keywords:Second-Order Cone Programming, Smoothing Inexact Newton Method, Convergence

二阶锥规划的光滑非精确牛顿法

董丽¹，徐思齐²，杨金根¹

¹信阳师范学院数学与信息科学学院，河南 信阳

²信阳师范学院土木工程学院，河南 信阳

Email: dongli9261128@163.com

收稿日期：2015年7月30日；录用日期：2015年8月12日；发布日期：2015年8月18日

摘 要

本文给出了一个新的求解二阶锥规划的光滑非精确牛顿法。在每次迭代时，新方法采用非精确牛顿法去求解一个方程组的解，降低了光滑牛顿法的计算量。在较弱条件下，证明了算法具有全局和局部二阶收敛性质。数值试验表明算法是有效的。

关键词 :二阶锥规划，光滑非精确牛顿法，收敛性

1. 引言

本文考虑如下二阶锥规划：

(P)

其中是变量，和是已知的量。是维的二阶锥，其定义为

其中为向量的欧几里得范数。(P)的对偶规划为

(D)

二阶锥规划作为数学规划领域的一个重要分支，有着非常重要而又广泛的应用背景和实际意义, 其研究问题涉及控制、金融、组合优化、工程技术、神经网络、机器学习等诸多领域[1] 。许多数学规划问题, 如凸二次规划、二次约束的凸二次规划、矩阵分式优化、范数极小化问题、鲁棒最小二乘问题、天线阵列的设计、带损失风险的金融优化问题等均可以转化为二阶锥规划[1] 。因此近年来二阶锥规划成为数学规划领域一个值得关注的方向。

光滑算法是近年来求解二阶锥规划的一种新方法[2] -[6] 。该方法的基本思想是利用一个光滑函数将二阶锥规划等价转化成一个非线性方程组，然后利用牛顿法求解该方程组，从而得到原问题的最优解。由于光滑算法不但在理论上具有好的收敛性质，而且在具体实施中有很好的实际计算效果，因而近年来得到了迅速的发展。注意到，文献[2] -[6] 所研究的光滑算法在每次迭代时，都需要精确求出一个非线性方程组的解。如果要求解的问题规模较大，精确求解此方程组的解往往效率不高，而非精确牛顿法是解决这类问题的一种很好的途径。

本文给出了一个求解二阶锥规划的光滑非精确牛顿法，证明了算法的全局和局部收敛性质。该方法采用非精确牛顿法求解方程组的解，大大提高了光滑算法的效率。数值试验表明算法对求解大规模二阶锥规划是有效的。

2. 预备知识

对任意的，，与二阶锥相伴的约当代数定义为

是一个欧几里得约当代数，其单位元为。

对任意的，定义，其中I为维单位矩阵。

易知。

下面给出与二阶锥相伴的中向量的谱分解。对任意的，它的谱分解为，其中谱值和谱向量分别为

这里是满足的任意向量。利用谱分解，我们可以定义

本文假设原始问题(P)及其对偶问题(D)都严格可行。在此假设条件下，原始问题(P)及其对偶问题(D)都有最优解且最优值相等，并且求解二阶锥规划问题等价于求解其最优性条件：

(1)

3. 算法描述

光滑函数在二阶锥规划光滑算法的设计和收敛性分析中起着非常重要的作用。本文采用著名的Fischer–Burmeister光滑函数，其定义如下：

(2)

由文献[7] 中的命题4.2可知

(3)

记。利用定义函数如下：

(4)

由(1)和(3)可知是的解当且仅当是(P)和(D)的解。

下面给出我们的算法。

算法3.1. (光滑非精确牛顿法)

步骤0: 选取常数。选取初始点。令。选取常数，使得。选取常数，使得。令。

步骤1：如果，则停止迭代。否则，计算

(5)

步骤2：求解如下方程组得搜索方向,

(6)

这里，其中并且满足

(7)

步骤3：令是使得下式成立的最小非负整数

(8)

令。

步骤4：令。令。转步骤1。

注：令，则由算法3.1的步骤2可知

即方程组(6)由非精确牛顿法求解。

下面定理给出了的雅可比矩阵及其可逆性，具体证明可参见文献[6] 中的定理3.2。

定理3.1：设由(4)定义，则有下面结论。

(i)在上全局Lipschitz连续且处处强半光滑，并且在任意的处连续可微，其雅可比矩阵为

其中

(ii) 如果矩阵行满秩，则对任意的有可逆。

定理3.2：设矩阵行满秩，则算法3.1有好的定义。

证明：假设对于某个有。因为矩阵行满秩，故由定理3.1知可逆，所以在第步迭代步骤2有好的定义。令为方程组(6)的解，则对任意的，有

(9)

由(9)及定理3.1可知在附近连续可微。对任意的，定义

(10)

则。由(5)和(7)知，，故知

因此，由(6)和(10)可知对任意的，有

因为，所以存在一个常数使得对于任意的，有

，

从而可知步骤3在第步迭代有好的定义，即算法步骤3可以产生一个步长。由(9)可知，因此由数学归纳法可知算法3.1有好的定义。证毕。

引理3.1 设为算法3.1产生的迭代点列，则对任意的有。

证明：由算法3.1的步骤3和步骤4可知点列单调下降，从而由的定义可知点列也是单调下降的。由算法3.1的步骤0可知。假设对于某个有，则由(9)可得

,

进而由数学归纳法可知结论成立。证毕。

4. 算法的收敛性质

定理4.1：如果矩阵行满秩并且是由算法3.1产生的迭代点列，那么的任意聚点都是的解。

证明：不失一般性，我们假设当时，收敛到。因为单调下降并且有下界，所以由的连续性可知收敛到一个非负数。若，则结论成立。假设。因为并且单调下降，故

,

从而由定理3.1可知存在并可逆。因此，存在的一个闭邻域，使得对任意的有并且可逆。因为，故对于充分大的有，进而可知并且可逆。对于充分大的，设是方程组唯一的解。类似于定理3.2的证明，对于充分大的，存在一个非负整数满足，这里，使得

对任意的和都成立。对于充分大的，因为，所以由算法3.1的步骤3和步骤4可得

令并在上式两边取极限，利用，可得。这与矛盾。因此可知。证毕。

定理4.2：假设矩阵行满秩并且是算法3.1产生的迭代点列的任意聚点。如果所有的都是非奇异的，则二次收敛到，即。

证明：由定理4.1可知，故对于充分大的，有并且，进而可知。

因此，类似于文献[2] 中的定理4.3可证得结论成立。在此省略。证毕。

表1. 算法3.1的数值结果

5. 数值试验

为检验算法3.1的实算效果，我们用Matlab7.0.1编程在Windows XP操作系统的电脑上做数值试验。

在所有的试验中，参数选择为，，，，。我们选择，作为初始点。终止准则为。

测试问题是随机生成的二阶锥规划问题。具体步骤为：首先生成随机的行满秩矩阵和随机向量，，，这里，然后令，，则得到的二阶锥规划的原问题和对偶问题都存在最优解且最优值相等。每个算例测试10次，计算结果列于表1，其中表示，AIT表示算法所需的迭代次数的平均值，ACPU表示算法所需的CPU时间(单位：秒)的平均值，MHK表示算法终止时10个算例中的最大值。

由表1可以看出，算法3.1是有效的并且能够求解大规模二阶锥规划问题，它只需要很少的迭代次数和CPU时间就可以得到满足终止条件的解。

基金项目

河南省自然科学基金(142300410437)，河南省高等学校重点科研项目(15A110039)。

文章引用

董丽,徐思齐,杨金根. 二阶锥规划的光滑非精确牛顿法
Smoothing Inexact Newton Method for the Second Order Cone Programming[J]. 应用数学进展, 2015, 04(03): 271-276. http://dx.doi.org/10.12677/AAM.2015.43033

参考文献 (References)