一种用于欠定非光滑方程的 Levenberg-Marquardt 型方法变体

《Journal of Computational and Applied Mathematics》：A variant Levenberg-Marquardt-type method for underdetermined nonsmooth equations

　　

摘要 本文提出了一种变分 Levenberg-Marquardt 型方法（记为 VLMM），用于求解欠定的非光滑方程。在每次迭代中，VLMM 求解一个修正的 Levenberg-Marquardt 方程，其规模显著小于传统的 Levenberg-Marquardt 方程。在适当条件下，建立了 VLMM 的全局收敛性。此外，在局部误差界条件下，VLMM 表现出局部超线性或二次收敛速率。数值实验表明，与传统的 Levenberg-Marquardt 型方法相比，我们的 VLMM 可以显著减少计算工作量。

引言 在 [1] 中，Pang 和 Qi 提出了非光滑方程 $F(x)=0$ 的动机和一种新的 Gauss-Newton 方法，其中映射 $F(x)=(F_1(x),...,F_n(x))^T: \mathbb{R}^n \rightarrow \mathbb{R}^n$ 假设是局部 Lipschitz 连续的但是非光滑的。非光滑方程 (1.1) 为研究许多重要的优化问题提供了统一框架，例如非线性互补问题、变分不等式问题、Karush-Kuhn-Tucker 系统、不等式可行性问题、极大单调算子、$LC^1$ 优化问题等，更多信息见 [1]。

求解非光滑方程 (1.1) 的一种流行算法是广义 Newton 方法 (GNM)。设 $x_k$ 为当前迭代点。GNM 采用迭代 $x_{k+1}=x_k+d_k$，其中 $d_k$ 是广义 Newton 方程 $V_{x_k}d=-F(x_k), V_{x_k} \in \partial F(x_k)$ 的解。这里 $\partial F(x_k)$ 表示 $F(x)$ 在 $x_k$ 处的 Clarke 广义 Jacobian [2]。Pang 和 Qi [1] 在 $F(x)$ 是半光滑且 BD 正则的条件下，给出了 GNM 超线性收敛的特征刻画。Qi 和 Sun [3] 证明了在非奇异性条件下，GNM 局部超线性/二次收敛。Martínez 和 Qi [4] 进一步研究了不精确 GNM 的收敛性质。

值得注意的是，当 $V_{x_k}$ 奇异时，广义 Newton 方程 (1.3) 并不总是可解的。为了克服这一缺点，Facchinei 和 Kanzow [5] 研究了一种用于求解由非线性互补问题重构的非光滑方程的 Levenberg-Marquardt 型方法 (LMM)。他们的方法采用迭代 (1.2)，其中 $d_k$ 是线性系统 $(V_{x_k}^T V_{x_k} + \mu_k I_n)d = -V_{x_k}^T F(x_k), V_{x_k} \in \partial F(x_k)$ 的解，其中 $\mu_k > 0$ 且 $I_n$ 是 $\mathbb{R}^{n \times n}$ 中的单位矩阵。方案 (1.4) 在形式上等同于光滑非线性方程的经典 Levenberg-Marquardt 方案。基于 $F(x)$ 的半光滑性和 BD 正则性，Facchinei 和 Kanzow [5] 证明了在适当条件下 LMM 超线性或二次收敛。最近，Levenberg-Marquardt 型方案 (1.4)（也称为阻尼 Gauss-Newton 方法）被研究用于求解半无限规划问题 [6]、垂直互补问题 [7]、随机线性互补问题 [8]、二阶锥互补问题 [9]、加权线性互补问题 [10]、非线性互补问题 [11], [12], [13], [14] 等。

在本文中，我们关注欠定的非光滑方程 $F(x)=0$，其中映射 $F(x)=(F_1(x),...,F_m(x))^T: \mathbb{R}^n \rightarrow \mathbb{R}^m$ 是局部 Lipschitz 连续的但是非光滑的且 $m < n$。欠定系统 (1.5) 出现在各种问题中。Chen 和 Yamamoto [15] 给出的一个典型例子是非光滑方程系统 $F(x)=(\min(\phi_1(x),\psi_1(x)),...,\min(\phi_m(x),\psi_m(x)))^T=0$，其中 $\phi_i(x), \psi_i(x): \mathbb{R}^n \rightarrow \mathbb{R} (i=1,...,m)$。该系统是非线性互补问题 $\phi(x) \ge 0, \psi(x) \ge 0, \phi(x)^T \psi(x)=0$ 的等式形式，其中 $\phi(x)=(\phi_1(x),...,\phi_m(x))^T$ 且 $\psi(x)=(\psi_1(x),...,\psi_m(x))^T$。作为另一个例子，我们考虑非线性不等式系统 $G(z) \le 0$，其中 $G(z)=(G_1(z),...,G_n(z))^T: \mathbb{R}^n \rightarrow \mathbb{R}^n$ 是连续可微的。由于其在水数据分析、集合分离问题、计算机辅助设计问题、图像重建等方面的各种应用，系统 (1.6) 在最近的论文中被广泛研究（例如，[16], [17], [18], [19]）。为了获得 (1.6) 的解，我们引入以下欠定非光滑系统 $F(x):=F(z,\zeta)=G(z)+|\zeta|=0$，其中 $|\zeta| := (|\zeta_1|, ..., |\zeta_n|)^T \in \mathbb{R}^n$。显然，如果 $(z, \zeta)$ 求解了 (1.7)，那么 $z$ 是 (1.6) 的解。更多关于欠定非光滑方程的例子见 [15]。

本文的目的是提出一种变分 Levenberg-Marquardt 型方法 (VLMM) 来求解欠定非光滑系统 (1.5)。在每次迭代中，VLMM 首先通过求解 $(V_{x_k} V_{x_k}^T + \mu_k I_m)s = -F(x_k), V_{x_k} \in \partial F(x_k)$ 计算 $s_k$，然后设置方向 $d_k^{VLMM} := V_{x_k}^T s_k$。从 $V_{x_k} \in \mathbb{R}^{m \times n}$ 可以看出，线性系统 (1.4) 和 (1.8) 的系数矩阵分别是 $V_{x_k}^T V_{x_k} + \mu_k I_n \in \mathbb{R}^{n \times n}$ 和 $V_{x_k} V_{x_k}^T + \mu_k I_m \in \mathbb{R}^{m \times m}$。因此，当 $m \ll n$ 时，线性系统 (1.8) 的规模远小于原始线性系统 (1.4) 的规模，这可以显著降低计算成本。设计了一种线搜索技术以确保 VLMM 的全局收敛性。此外，基于 $F(x)$ 的（强）半光滑性，我们证明了在局部误差界条件下 VLMM 超线性（二次）收敛。报告了一些计算结果，表明与原始 Levenberg-Marquardt 型方案 (1.4) 相比，我们的 VLMM 可以节省相当数量的计算工作量。

论文组织如下。在第 2 节，我们提出了 VLMM 并给出了一些性质。在第 3 节，我们证明了 VLMM 的全局收敛性。在第 4 节，我们分析了 VLMM 的局部收敛速率。一些数值结果和结论分别在第 5 节和第 6 节给出。

章节片段

算法 我们首先回顾 Clarke 广义 Jacobian [2] 的定义。由于 (1.5) 中给出的函数 F 是局部 Lipschitz 连续的，根据 Rademacher 定理，F 几乎处处可微。设 $DF \subset \mathbb{R}^n$ 表示 F 可微点的集合。对于任意 $x \in \mathbb{R}^n$，集合 $\partial_B F(x) = \{V_x \in \mathbb{R}^{m \times n} | \exists \{x_k\} \subset DF: x_k \rightarrow x, F'(x_k) \rightarrow V_x\}$ 是非空的，称为 F 在 x 处的 B-次微分。如果 $n=m$ 且 $\partial_B F(x)$ 中的所有成员都是非奇异的，那么我们说 F 在 x 处是 BD-正则的。Clarke 广义

全局收敛 引理 3.1 对于所有 $k \ge 0$，算法 VLMM 生成的方向 $\{d_k^{VLMM}\}$ 满足 $\|d_k^{VLMM}\| \le (e^\eta \|F(x_0)\|)^{1-\delta} 2^{2\theta}$。

证明 由于对于所有 $k \ge 0$ 有 $f(x_{k+1}) \le (1+\eta_k)f(x_k)$ 且 $\sum_{k=0}^\infty \eta_k \le \eta$，根据 [21, Lemma 2.1] 的证明，我们有 $f(x_k) \le e^\eta f(x_0)$，因此对于所有 $k \ge 0$，$\|F(x_k)\| \le e^\eta \|F(x_0)\|$。对于任意 $k \ge 0$，我们假设 $V_{x_k}$ 的奇异值分解为 $V_{x_k} = P_k \Sigma_k Q_k^T$，其中 $P_k \in \mathbb{R}^{m \times m}$ 和 $Q_k \in \mathbb{R}^{n \times n}$ 是正交矩阵，且 $\Sigma_k = \text{diag}(\sigma_1^k, ..., \sigma_r^k, 0, ..., 0)$，满足 $\sigma_1^k \ge \dots \ge \sigma_r^k > 0$ 和 $r \le m$。那么，根据 (2.9)，$\|d_k^{VLMM}\| = \|V_{x_k}^T(V_{x_k}V$

局部收敛速率 在本节中，我们假设算法 VLMM 生成的序列 $\{x_k\}$ 收敛到 $x^*$ 且 $F(x^*)=0$。我们将证明在以下假设下 $\{x_k\}$ 超线性或二次收敛到 $x^*$。

假设 4.1 存在常数 $\kappa > 0$ 和 $\epsilon > 0$ 使得 $\|F(x)\| \ge \kappa \|x-x^*\|, \forall x \in N(x^*, \epsilon)$，其中 $N(x^*, \epsilon) := \{x \in \mathbb{R}^n | \|x-x^*\| \le \epsilon\}$。假设 4.1 是一个局部误差界条件，它已被用于分析一些光滑化 Levenberg-Marquardt 方法的局部收敛性质（例如，[22], [23]）和

数值结果 在本节中，我们给出一些数值结果来说明算法 VLMM 的有效性。所有实验都在一台 PC 上进行，CPU 为 Intel(R) Core(TM) i7-7700 CPU @ 3.60 GHz，RAM 为 8.00GB。代码用 MATLAB 编写并在 MATLAB R2018a 环境中运行。我们比较以下两种算法。
• 本文研究的算法 VLMM，记为 VLMM；
• [5] 中提出的传统 LMM 方法，它通过求解 LM 方程 (1.4) 计算方向 $d_k^{LMM}$，记为 LMM。
该

结论 我们提出了一种变分 Levenberg-Marquardt 型方法，即算法 VLMM，用于求解欠定的非光滑方程。在适当的假设下，建立了算法的全局和局部超线性（二次）收敛性。VLMM 的主要理论优势在于它求解一个 $m \times m$ 线性系统 (1.8)，而传统的 LMM 求解的是 $n \times n$ 系统 (1.4)。当 $m \ll n$ 时，这显著降低了每次迭代的计算复杂度，

利益冲突声明 作者声明他们没有利益冲突。

唐景勇 | 彭建华
信阳师范大学数学与统计学院，中国信阳 464000