ABSTRACT

Based on the Fischer-Burmeister function, a new Newton method is proposed for solving the Second-order cone programming. This algorithm adapts a new smoothing value function and proposes a Newton equation with disturbance to gain the search direction. Under suitable assumptions, we prove that the proposed new method is globally and locally quadratically convergent.

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

二阶锥规划基于新价值函数的新光滑牛顿算法

梁晓娟

广西大学数学与信息科学学院，广西 南宁

收稿日期：2019年7月15日；录用日期：2019年7月30日；发布日期：2019年8月6日

摘 要

本文在Fischer-Burmeister (FB)函数的基础上，提出一种求解二阶锥规划(SOCP)问题的新光滑牛顿函数，并采用一种新的价值函数。同时用一个带扰动的牛顿方程组去获得搜索方向，在适当假设下，证明新算法具有全局收敛和局部二次收敛。

关键词 :二阶锥规划，光滑牛顿法，全局收敛，局部二次收敛

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文主要考虑以下线性二阶锥规划问题:

$\min \left\{c^{\text{T}}x|Ax=b,x\in K\right\}$ (1.1)

其对偶问题：

$\max \left\{b^{\text{T}}y|A^{\text{T}}y+s=c,s\in K,y\in R^m\right\}$ (1.2)

二阶锥规划是凸规划问题的一个重要分支，它是在仿射空间与有限个二阶锥的笛卡尔积的交集上极小化或极大化一个线性函数。在现实生活中有着广泛的应用：图论优化(文 [1] )，力学(文 [2] )，投资组合(文 [3] )等都可以转化为二阶锥规划问题求解。此外，许多数学问题也可转化为二阶锥问题求解：线性规划，二次规划，范数极小化(文 [4] )，因而研究二阶锥规划具有重要的理论与现实意义。本文在向量值FB函数的基础上进行改进得到一个新的光滑函数，并采用一个新的价值函数，给出求解二阶锥问题的一个光滑牛顿法，并证明算法是全局收敛和局部二次收敛。

2. 基础知识

为了更好地研究二阶锥规划，介绍一些与二阶锥相伴的欧几里得若当代数的基本概念以及二阶锥规划的最优性条件等。先介绍一些记号，其中U表示反射矩阵， $E_{n-1}$ 表示 $\left(n-1\right)$ 阶单位阵， $Arw\left(x\right)$ 表示一个箭形矩阵，本文用相应的大写字母表示箭形矩阵，比如 $X=Arw\left(x\right)$， $S=Arw\left(s\right)$， $W=Arw\left(w\right)$， $A^i=Arw\left(a^i\right)$。

对于 $\forall x=\left(x_1;x_2\right)\in R\times R^{n-1},s=\left(s_1;s_2\right)\in R\times R^{n-1}$，定义如下若当积：

$x\circ s\triangleq \left(\begin{array}{c}{x}^{\text{T}}s\\ x_1{s}_2+s_1{x}_2\end{array}\right)=Arw\left(x\right)s=Arw\left(x\right)Arw\left(s\right)e=XSe$

记 $x^2\triangleq x\circ x$， $x+y$ 表示通常的向量的加法。

定理2.1 (谱分解定理) (文 [5] )

对向量x我们定义与二阶锥有关的谱分解为： $x={\lambda }_1{c}_1+{\lambda }_2{c}_2$，其中x的谱值 ${\lambda }_i$ 和与之对应的谱向量 $c_i$ 如下：

${\lambda }_i=x_1+{\left(-1\right)}^{i+1}\Vert x_2\Vert ,i=1,2$

$$， $\omega \in R^{n-1}$ 是满足 $\Vert \omega \Vert =1$ 的任意向量。

定理2.2 (最优性条件) (文 [6] )如果(1.1)和(1.2)都有严格可行解，则 $\left(x,\left(y,s\right)\right)$ 是(1.1)和(1.2)的最优解对当且仅当

$\{\begin{array}{l}Ax=b,x\in K,\\ A^{\text{T}}y+s=c,s\in K,\\ x\circ s=0.\end{array}$ (2.1)

对二阶锥规划，其二阶锥互补函数定义如下：

定义2.1 (文 [7] )如果向量值函数 ${\varphi }^{soc}:R^n\times R^n\to R^n$ 满足

${\varphi }^{soc}\left(x,s\right)=0\iff x\circ s=0,x\in K,s\in K$ (2.2)

则称 ${\varphi }^{soc}$ 为二阶锥互补函数。

对任意 $z=\left(\mu ,x,y\right)\in R_{+}\times R^n\times R^m$，定义函数 $H\left(z\right):R^{1+n+m}\to R^{1+m+n}$ 如下：

$H\left(z\right)=\left(\begin{array}{c}\mu \\ b-Ax\\ \varphi \left(\mu ,x,c-A^{\text{T}}y\right)\end{array}\right)$ (2.3)

令

$\Psi \left(z\right)=\left(\begin{array}{c}b-Ax\\ \varphi \left(\mu ,x,c-A^{\text{T}}y\right)\end{array}\right)$ (2.4)

其中 $\varphi \left(\mu ,x,c-A^{\text{T}}y\right)$ 是任意的二阶锥互补函数。易见 $H\left(x,y,s\right)=0$ 是与最优性条件等价的方程组，由此可知， $\left({\mu }^{*},x^{*},y^{*}\right)$ 是 $H\left(\mu ,x,y\right)=0$ 的解当且仅当 $\left(x^{*},y^{*},c-A^{\text{T}}y\right)$ 满足最优性条件，是问题(1.1)和(1.2)的最优解对。由上易知，求解此方程组的关键在于构造合适的二阶锥互补函数。由于常见的二阶锥互补函数：向量值最小函数，向量值FB函数在 $\left(0,0\right)$ 点不可微(即非光滑)，不能直接用牛顿法求解，为了进一步研究，先给出光滑化的概念。

定义2.2 (文 [8] )对于不可微函数 $h:R^n\to R^m$，考虑带有参数 $\mu >0$ 的函数 $h_{\mu }:R^n\to R^m$，如果它具备如下性质：

(1) 对于任意的 $\mu >0$， $h_{\mu }$ 是光滑的；

(2) $\underset{\mu \to 0}{\lim }{h}_{\mu }\left(x\right)=h\left(x\right),\forall x\in R^n$ ；

则称 $h_{\mu }$ 是h的光滑函数。

3. 一个新的光滑函数及其性质

光滑函数在二阶锥规划算法研究中起着重要作用。由于向量值最小函数，向量值FB函数并不处处连续可微，大大影响了其实际应用。本文在FB函数的基础上通过光滑对称扰动，得到一个新的向量值函数 $\varphi \left(\mu ,x,s\right):R_{+}\times R^n\times R^n\to R^n$ ：

$\varphi \left(\mu ,x,s\right)=\left(e^{\mu }+\mu \right)\left(x+s\right)-\sqrt{{\left(e^{\mu }x+\mu s\right)}^2+\left(\mu x^2+e^{\mu }{s}^2\right)+2{\mu }^{2}e}$ (3.1)

因此可考虑用牛顿法求解 $H\left(z\right)=0$，但对于所构造的 $H\left(z\right)$，其雅可比矩阵必须是非奇异的。在讨论 $H\left(z\right)$ 的性质之前先介绍相关结论。

引理3.1 (文 [7] )对于任意的 $a^1,\cdots ,a^p\in R^n$，令 $\chi \left(a^1,\cdots ,a^p\right)=\sqrt{{\displaystyle \underset{i=1}{\overset{p}{\sum }}{\left(a^i\right)}^2}}$。则 $\chi$ 是全局利普希茨连续的；若 $v_1\ne \Vert v_2\Vert$，其中 $v=\left(v_1;v_2\right)\in R\times R^{n-1}$ 且 $v={\displaystyle \underset{i=1}{\overset{p}{\sum }}{\left(a^i\right)}^2}$，则 $\chi$ 在 $\left(a^1,\cdots ,a^p\right)$ 的任意邻域是连续可微的， $\chi$ 是强半光滑的。

引理3.2 (文 [9] )对于任意的 $x,y\in R$ 和 $w\succ K^{n}0$，如果 $w^2\succ K^n{x}^2+y^2$，则

$\left[Arw\left(w\right)-Arw\left(x\right)\right]\left[Arw\left(w\right)-Arw\left(y\right)\right]\succ \text{0},Arw\left(w\right)-Arw\left(x\right)\succ \text{0},Arw\left(w\right)-Arw\left(y\right)\succ \text{0}$，

且当 $\succ$ 变为 $\underset{\_}{\succ }$ 时，上述结论仍然成立。

定理3.1设 $z=\left(\mu ,x,y\right)\in R_{+}\times R^n\times R^m,H\left(z\right):R^{1+n+m}\to R^{1+m+n}$ 由(2.3)式定义，令

$a^1=e^{\mu }x+\mu s,a^2=\mu x+e^{\mu }s,a^3=\sqrt{2}\mu e,w^2=v={\left(a^1\right)}^2+{\left(a^2\right)}^2+{\left(a^3\right)}^2=\left(v_1;v_2\right)\in R\times R^{n-1}$，

则

(i) $H\left(z\right)$ 是 $R^{1+n+m}$ 上的全局利普希茨连续的处处强半光滑函数，且在 $\left(\mu ,x,y\right)\in R_{+}\times R^n\times R^m$ 处连续可微，其雅克比矩阵为

$H^{\prime }\left(z\right)=\left(\begin{array}{ccc}1& 0& 0\\ 0& -A& 0\\ {{\varphi }^{\prime }}_{\mu }\left(z\right)& {{\varphi }^{\prime }}_x\left(z\right)& -{{\varphi }^{\prime }}_s\left(z\right)A^{\text{T}}\end{array}\right)$ (3.2)

其中

${{\varphi }^{\prime }}_{\mu }\left(z\right)=\left(e^{\mu }+1\right)\left(x+s\right)-W^{-1}\left[A^1\left(e^{\mu }x+s\right)+A^2\left(x+e^{\mu }s\right)+2\mu e\right]$，

${{\varphi }^{\prime }}_x\left(z\right)=\left(e^{\mu }+\mu \right)E_n-W^{-1}\left(e^{\mu }{A}^1+\mu A^2\right)$，

${{\varphi }^{\prime }}_s\left(z\right)=\left(e^{\mu }+\mu \right)E_n-W^{-1}\left(\mu A^1+e^{\mu }{A}^2\right)$。

(ii) 如果矩阵A行满秩，对任意的 $\mu >0$， $H^{\prime }\left(z\right)$ 可逆。

证明：首先由引理3.1易知(i)成立。下证(ii)成立。对任意的 $\mu >0$，要证 $H^{\prime }\left(z\right)$ 可逆，只需要证方程组 $H^{\prime }\left(z\right)\Delta z=0$ 只有零解，即 $\Delta z=\left(\Delta \mu ,\Delta x,\Delta y\right)=0$。将(3.2)式代入 $H^{\prime }\left(z\right)\Delta z=0$ 可得

$\Delta \mu =0,A\Delta x=0,{{\varphi }^{\prime }}_x\left(z\right)\Delta x-{{\varphi }^{\prime }}_s\left(z\right)A^{\text{T}}\Delta y=0$ (3.3)

将 ${{\varphi }^{\prime }}_x\left(z\right)$， ${{\varphi }^{\prime }}_s\left(z\right)$ 代入(3.3)式并将等式两端同时左乘W，得

$\left[\left(e^{\mu }+\mu \right)W-\left(e^{\mu }{A}^1+\mu A^2\right)\right]\Delta x-\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]A^{\text{T}}y=0$ (3.4)

因为 ${\left(e^{\mu }+\mu \right)}^2{W}^2-{\left(e^{\mu }x+\mu s\right)}^2-{\left(\mu x+e^{\mu }s\right)}^2\in K^0$ 故由引理3.2知 $\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)$ 与 $\left(e^{\mu }+\mu \right)W-\left(e^{\mu }{A}^1+\mu A^2\right)$ 可逆。将方程(3.4)左乘 $\Delta x^{\text{T}}{\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]}^{-1}$，由 $A\Delta x=0$ 得 $\Delta x^{\text{T}}{\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]}^{-1}\left[\left(e^{\mu }+\mu \right)W-\left(e^{\mu }{A}^1+\mu A^2\right)\right]\Delta x=0$。

令

$\Delta \tilde{x}={\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]}^{-1}\Delta x$，

则

$\Delta {\tilde{x}}^{\text{T}}\left[\left(e^{\mu }+\mu \right)W-\left(e^{\mu }{A}^1+\mu A^2\right)\right]\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]\Delta \tilde{x}=0$ (3.5)

由引理3.2知矩阵 $\left[\left(e^{\mu }+\mu \right)W-\left(e^{\mu }{A}^1+\mu A^2\right)\right]\left[\left(e^{\mu }+\mu \right)W-\left(\mu A^1+e^{\mu }{A}^2\right)\right]$ 正定，因此 $\Delta \tilde{x}=0$，从而 $\Delta x=0$，又矩阵A行满秩，由(3.3)式可得 $\Delta y=0$，即 $H^{\prime }\left(z\right)\Delta z=0$ 只有零解，故 $H^{\prime }\left(z\right)$ 可逆。

4. 算法的描述

记 $z=\left(\mu ,x,y\right):R_{+}\times R^n\times R^m$，一般采用价值函数： ${\theta }_1\left(z\right)={\Vert H\left(z\right)\Vert }^2$，本文采用价值函数： $\theta \left(z\right)=\mu +{\Vert \Psi \left(z\right)\Vert }^2$。下面给出具体的算法描述：

算法4.1 (二阶锥规划的一个光滑牛顿法)

步骤0：(初始化)给出常数 $\delta ,\sigma \in \left(0,1\right),{\mu }_0\in R_{+},\eta ,\gamma \in \left(0,1\right)$ 满足 $\gamma <{\mu }_0$ 且 $\eta +\gamma <1$ 取 $\left(x^0,y^0\right)\in R^n\times R^m$ 为初始点，令 $z^0=\left({\mu }_0,x^0,y^0\right)$，令 $k:=0$。

步骤1：(终止准则)若 $H\left(z^k\right)=0$，停止，否则令

${\gamma }_k:=\left(\begin{array}{c}{\beta }_k\\ G_k\end{array}\right)$，其中 ${\beta }_k=\gamma \min \left\{1,\theta {\left(z^k\right)}^2\right\}$， $G_k=\frac{\eta \Vert H\left(z^k\right)\Vert }{1+\theta \left(z^k\right)}\Psi \left(z^k\right)$。

步骤2：(确定搜索方向)解线性方程组 $H\left(z^k\right)+H^{\prime }\left(z^k\right)\Delta z^k={\gamma }_k$ 得到搜索方向 $\Delta z^k$。

步骤3：(确定步长)记 $l_k$ 是满足下式的最小非负整数l：

$\theta \left(z^k+{\delta }^l\Delta z^k\right)\le \left[1-\sigma \left(1-\gamma +\eta \right){\delta }^l\right]\theta \left(z^k\right)$，

令步长 ${\alpha }_k={\delta }^{l_k}$。

步骤4：(迭代更新)令 $z^{k+1}=z^k+{\alpha }_k\Delta z^k,k:=k+1$，返回步骤1。

引理4.1令 $\Psi \left(z^k\right)$ 由(2.4)式所定义，如果 ${\mu }_k\ge 0$，则

$\Vert G\left(z^k\right)\Vert \le \eta \min \left\{1,\theta {\left(z^k\right)}^2\right\}$ (4.1)

证明：因为 ${\Vert H\left(z^k\right)\Vert }^2={\mu }_k^2+{\Vert \Psi \left(z^k\right)\Vert }^2\le {\left({\mu }_k+\Vert \Psi \left(z^k\right)\Vert \right)}^2=\theta {\left(z^k\right)}^2$，所以 ${\Vert H\left(z^k\right)\Vert }^2\le \theta \left(z^k\right)$。

又因为 $\Vert \Psi \left(z^k\right)\Vert \le \theta \left(z^k\right)$，故 $\Vert G_k\Vert =\frac{\eta \Vert H\left(z^k\right)\Vert }{1+\theta \left(z^k\right)}\Psi \left(z^k\right)\le \frac{\eta \theta {\left(z^k\right)}^2}{1+\theta {\left(z^k\right)}^2}\le \eta$。又从上式第一个不等式得

$\Vert G\left(z\right)\Vert \le \left(\eta -G\left(z^k\right)\right)\theta {\left(z^k\right)}^2$，故 $\Vert G\left(z^k\right)\Vert \le \eta \theta {\left(z^k\right)}^2$。综上可得(4.1)式成立。

引理4.2设 ${\beta }_k,G\left(z^k\right)$ 由算法的步骤2所定义，则对任意的 $k\ge 0$，有

${\beta }_k+\Vert G\left(z^k\right)\Vert \le \left(\gamma +\eta \right)\theta \left(z^k\right)$ (4.2)

证明：对任意的 $\zeta \ge 0$，有 $\min \left\{1,{\zeta }^2\right\}\le \zeta$ 成立，故由算法的步骤2得 ${\beta }_k=\gamma \min \left\{1,\theta {\left(z^k\right)}^2\right\}\le \gamma \theta \left(z^k\right)$， $\Vert G\left(z^k\right)\Vert \le \eta \min \left\{1,\theta {\left(z^k\right)}^2\right\}\le \eta \theta \left(z^k\right)$，故(4.2)式成立。

定理4.1设矩阵A行满秩，如果 ${\mu }_k>0$，则算法4.1是适定的。

证明：因为矩阵A行满秩且 ${\mu }_k>0$，由定理3.1知 $H^{\prime }\left(z\right)$ 可逆，所以算法4.1的步骤2是适定的。令 $\Delta z^k=\left(\Delta {\mu }_k,\Delta x^k,\Delta y^k\right)\in R\times R^n\times R^m$ 是步骤2中方程组的解，则对任意的 $\alpha \in \left(0,1\right]$，有

${\mu }_{k+1}={\mu }_k+\alpha \Delta {\mu }_k={\mu }_k+\alpha \left({\beta }_k-{\mu }_k\right)+\alpha {\beta }_k>0$ (4.3)

由于 $\Psi \left(z^k\right)$ 在任意的 $z^k\in R\times R^n\times R^m$ 处连续可微，因此对任意的 $\alpha \in \left(0,1\right]$，有

$\begin{array}{c}\Vert \Psi \left(z^k+\alpha \Delta z^k\right)\Vert =\Vert \Psi \left(z^k\right)+\alpha {\Psi }^{\prime }\left(z^k\right)\Delta z^k+o\left(\alpha \right)\Vert \\ =\Vert \left(1-\alpha \right)\Psi \left(z^k\right)+\alpha G\left(z^k\right)\Vert +o\left(\alpha \right)\\ \le \left(1-\alpha \right)\Vert \Psi \left(z^k\right)\Vert +\alpha \Vert G\left(z^k\right)\Vert +o\left(\alpha \right)\end{array}$ (4.4)

由(4.3)式和(4.4)式得

$\begin{array}{c}\Vert \theta \left(z^k+\alpha \Delta z^k\right)\Vert ={\mu }_k+\alpha \Delta {\mu }_k+\Vert \Psi \left(z^k+\alpha \Delta z^k\right)\Vert \\ \le \left(1-\alpha \right){\mu }_k+\alpha {\beta }_k+\left(1-\alpha \right)\Vert \Psi \left(z^k\right)\Vert +\alpha \Vert G\left(z^k\right)\Vert +o\left(\alpha \right)\\ =\left(1-\alpha \right)\theta \left(z^k\right)+\alpha \left({\beta }_k+\Vert G\left(z^k\right)\Vert \right)+o\left(\alpha \right)\\ \le \left(1-\alpha \right)\theta \left(z^k\right)+\alpha \left(\gamma +\eta \right)\theta \left(z^k\right)+o\left(\alpha \right)\\ =\left[1-\left(1-\gamma -\eta \right)\alpha \right]\theta \left(z^k\right)+o(\alpha )\end{array}$

上式第二个不等式由引理4.2可得，又因为 $\gamma +\eta <1$，所以存在一个常数 $\bar{\alpha }\in \left(0,1\right]$，使得对任意的 $\alpha \in \left(0,\bar{\alpha }\right]$，有

$\theta \left(z^k+t\Delta z^k\right)\le \left[1-\sigma \left(1-\gamma -\eta \right)\alpha \right]\theta \left(z^k\right)$ (4.5)

即步骤3可在有限步终止，故步骤3是适定的。综上可知，算法4.1是适定的。

5. 收敛性分析

定理5.1 (i) 设矩阵A行满秩且 $\left\{z^k=\left({\mu }_k,x^k,y^k\right)\right\}$ 是算法4.1生成的无穷迭代点列，则对 $\forall k\ge 0$，有 ${\mu }_k>0$，，其中

$\Lambda :=\left\{z=\left(\mu ,x,y\right)\in R_{+}\times R^n\times R^m|\mu \ge \beta \left(z\right)\right\}$， (5.1)

(ii) (全局收敛) $\left\{z^k\right\}$ 的任意聚点 $z^{*}=\left({\mu }^{*},x^{*},y^{*}\right)$ 都是 $H\left(z^k\right)=0$ 的解。

证明：(i) 由算法4.1的步骤4可知 $\left\{\theta \left(z^k\right)\right\}$ 单调下降，由 $\left\{{\beta }_k\right\}$ 的定义可知 $\left\{{\beta }_k\right\}$ 单调下降。先用数学归纳法证明 ${\mu }_k>0$，由算法4.1的步骤0知 ${\mu }_0>\gamma >0$，假设 ${\mu }_k>0$，下证 ${\mu }_{k+1}>0$，由于 ${\alpha }_k={\delta }^{l_k}\in \left(0,1\right]$， ${\beta }_k\in \left(0,1\right)$，由(4.3)式知 ${\mu }_{k+1}>0$，故 ${\mu }_k>0$。

同理用数学归纳法证明 $$，由算法4.1的步骤0知 ${\mu }_0>\gamma \ge {\beta }_0$，即 $z^0\in \Lambda$，假设 $z^k\in \Lambda$，

下证 $z^{k+1}\in \Lambda$，由(4.3)式可得 ${\mu }_{k+1}=\left(1-\alpha \right){\mu }_k+\alpha {\beta }_k\ge \left(1-\alpha \right){\beta }_k+\alpha {\beta }_k={\beta }_k\ge {\beta }_{k+1}$，故 $z^{k+1}\in \Lambda$。

(ii) 不失一般性，设 $z^{*}$ 是点列 $\left\{z^k\right\}$ 的任意聚点，要证 $\theta \left(z^{*}\right)=0$，用反证法。假设 $\Vert \theta \left(z^{*}\right)\Vert >0$，由算法4.1的步骤3知 $\left\{\Vert \theta \left(z^k\right)\Vert \right\}$ 单调下降其有下界，结合 $\theta \left(z^k\right)$ 的连续性，有 $\underset{k\to +\infty }{\lim }\Vert \theta \left(z^k\right)\Vert =\Vert \theta \left(z^{*}\right)\Vert$。由 $\beta \left(z^k\right)$ 的定义知 $\beta \left(z^k\right)$ 单调下降且趋于 $\beta \left(z^{*}\right)$ ： ${\beta }_{*}=\beta \left(z^{*}\right)=\gamma \min \left\{1,\theta \left(z^{*}\right)\right\}>0$。另外，由(5.1)知，对任意的 $k>0$，有 ${\mu }_k\ge {\beta }_k$，从而 ${\mu }_{*}\ge {\beta }_{*}{\mu }_0>0$。又因为 $H^{\prime }\left(z^{*}\right)$ 可逆，令 $\Delta z^k=\left(\Delta {\mu }_k,\Delta x^k,\Delta y^k\right)$ 为算法4.1的步骤2的解，存在一个非负整数 $\bar{l}$ 使得 ${\delta }^{\bar{l}}\in \left[0,\bar{\alpha }\right]$，当k充分大时，有 $\theta \left(z^{k+1}\right)\le \left[1-\sigma \left(1-\gamma -\eta \right){\delta }^{\tau }\right]\theta \left(z^k\right)$。存在 $z^{*}$ 的一个闭邻域 $N\left(z^{*}\right)$ 和正数 $\bar{t}\in \left(0,1\right]$，使得对于任意的 $z=\left(\mu ,x,y\right)\in N\left(z^{*}\right)$ 和所有的 $t\in \left[0,\bar{t}\right]$，都有 $\mu >0$， $H^{\prime }\left(z\right)$ 非奇异且

$\theta \left(z^k+t\Delta z^k\right)\le \left[1-\sigma \left(1-2\gamma {\mu }_0\eta \right)t\right]\theta \left(z^k\right)$ (5.2)

由算法4.1的步骤3知，对于充分大的k，步长 ${\alpha }_k={\delta }^{l_k}\ge {\delta }^{\tau }$，因此有

$\theta \left(z^{k+1}\right)\le \left[1-\sigma \left(1-\gamma -\eta \right){\delta }^{l_l}\right]\theta \left(z^k\right)\le \left[1-\sigma \left(1-\gamma -\eta \right){\delta }^{\tau }\right]\theta (zk)$

上式两端取极限得

由 $\theta \left(z^{*}\right)>0$ 知， $\sigma \left(1-\gamma -\eta \right){\delta }^{\tau }\le 0$，即 $\gamma +\eta \ge 1$，与算法步骤0中 $\gamma +\eta <1$ 矛盾，故 $\theta \left(z^{*}\right)=0$。因此算法4.1是全局收敛的。

定理5.2 (局部二次收敛)设矩阵A行满秩且 $z^{*}$ 是算法4.1产生的迭代点列 $\left\{z^k\right\}$ 的任意聚点，若 $V\in \partial H\left(z^{*}\right)$ 都是非奇异的，则 $\Vert z^{k+1}-z^{*}\Vert =O\left({\Vert z^k-z^{*}\Vert }^2\right)$，且 ${\mu }_{k+1}=O\left({\mu }_k^2\right)$。

证明：类似文献 [10] 中定理8的证明可得此结论，在此省略。

文章引用

梁晓娟. 二阶锥规划基于新价值函数的新光滑牛顿算法
A New Smoothing Newton Algorithm Based on the New Valued Function for Se-cond-Order Cone Programming[J]. 运筹与模糊学, 2019, 09(03): 215-221. https://doi.org/10.12677/ORF.2019.93024

参考文献