沈阳航空航天大学理学院，辽宁 沈阳

收稿日期：2023年9月26日；录用日期：2023年10月21日；发布日期：2023年10月30日

摘要

针对具有等式约束的随机优化问题，本文首先考虑基于SAA方法获取原始问题目标函数的SAA问题，并利用惩罚函数法将其转化为一般无约束凸优化问题。接下来建立二阶微分方程算法对所得到的问题进行求解。本文还证明了当算法的参数满足一定条件时，二阶微分方程算法具有良好的收敛性，其收敛率为 $o\left(\frac{1}{t^2}\right)$ ，最后给出具体的数值算例验证算法的可行性。

关键词

随机优化问题，二阶微分方程算法，凸优化问题，SAA方法

Second Order Differential Equation Algorithm for Solving Stochastic Optimization Problems with Equality Constraints

Qinan Lv, Juhe Sun, Li Wang, Hongjian Xie

School of Science, Shenyang University of Aeronautics and Astronautics, Shenyang Liaoning

Received: Sep. 26^th, 2023; accepted: Oct. 21^st, 2023; published: Oct. 30^th, 2023

ABSTRACT

For the stochastic optimization problem with equality constraint, this paper first considers the SAA problem of obtaining the objective function of the original problem based on the SAA method, and uses the penalty function method to transform it into a general unconstrained convex optimization problem. Next, a second-order differential equation algorithm is established to solve the obtained problem. This paper also proves that when the parameters of the algorithm meet certain conditions, the second-order differential equation algorithm has good convergence, and its convergence rate is $o\left(\frac{1}{t^2}\right)$ , and finally a specific numerical example is given to verify the feasibility of the algorithm.

Keywords:Stochastic Optimization Problem, Second-Order Differential Equation System, Convex Optimization Problem, SAA Method

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

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

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

1. 引言

随着经济发展，许多实际问题往往存在许多不确定性因素，例如物理不确定性，经济不确定性，统计不确定性等 [1] [2] 。因此，许多学者在研究优化问题时引入了随机变量，得到随机优化问题。随机优化问题作为确定性优化问题的延伸，在机械、经济、人工智能等领域都有很多应用。

随机优化问题首先被G. Dantzig提出，在文献 [3] 中，他提出了带补偿的两阶段随机优化问题，随着经济学和人类需求的进步，越来越多的学者开始关注随机优化问题。同时，针对各种形式的随机优化问题，许多学者给出了不同的算法 [2] [3] [4] [5] [6] 。

针对 ${\min }_{x\in C}\left\{f\left(x\right)=E\left[F\left(x,\xi \right)\right]\right\}$ 形式的问题，Guo等人在文献 [7] 中提出了随机无梯度的Frank-wolf方法，主要解释了目标函数中的随机函数可以证明算法在海德尔连续性条件下的收敛性，无需满足利普希茨的连续性。此外，Guo等人还指出，在算法的收敛分析中，梯度方差是均匀有界的假设是没有必要的。

Curtis等在文献 [8] 中提出了一种基于梯度下降算法方法的随机平均梯度(SAG)计算方法，并证明了一定条件下的线性收敛性。Schmidt等在文献 [9] 中提出了一种基于一阶SGD方法的后续方法。Chen等人在文献 [10] 中将不精确的牛顿方法与随机分解方法相结合，提出了一种解决两阶段随机问题的随机牛顿方法。但是对于特定结构之外的问题，计算起来比较麻烦。

然而，解决上述随机优化问题的最常用的方法是文献 [11] 中的样本均值近似(SAA)和随机近似(SA)。文献 [12] 研究了SAA方法并验证了其收敛性。虽然有很多学者 [13] [14] 致力于改进SA方法，但解决某些问题更麻烦，因为它涉及投影问题。

2. 预备知识

对于非光滑函数，本文选择用一串光滑函数来代替非光滑函数，下面给出光滑函数的定义。

定义2.1 $\Phi$ 为 $R\to R$ 的一个凸函数，称 $\tilde{\Phi }:R\times \left[0,\infty \right]\to R$ 为 $\Phi$ 的光滑函数。如果 $\tilde{\Phi }\left(z,\mu \right)$ 满足以下条件：

1) 对任意的固定的 $\mu >0$ ， $\Phi \left(·,\mu \right)$ 在R上是连续可微的，并且对任意固定的 $z\in R$ ， $\tilde{\Phi }\left(z,\mu \right)$ 在 $\left(\text{0},\infty \right)$ 上是连续可微的。

2) ${\lim }_{h\to z,\mu \downarrow 0}\tilde{\Phi }\left(h,\mu \right)=\Phi \left(z\right),\forall z\in R$ 。

3) $\tilde{\Phi }\left(z,\mu \right)$ 是在R上的凸函数，对于任何固定的 $\mu >0$ 。

4) 存在一个正的常数 $\kappa$ ，使得，

$\left|{\nabla }_{\mu }\tilde{\Phi }\left(z,\mu \right){\nabla }_{\mu }\tilde{\Phi }\left(z,\mu \right)\right|\le \kappa ,\forall \mu \in \left(0,\infty \right),z\in R$ (2.1)

5) 对于任意的 $\mu \in \left(0,\infty \right)$ ，存在一个常数 $L>0$ ${\nabla }_z\tilde{\Phi }\left(·,\mu \right)$ 在R上是Lipschitz连续的，并且有Lipschitz常数 $L{\mu }^{-\text{1}}$

6) 对于任意的 $h\in C$ ， ${\nabla }_h\tilde{\Phi }\left(h,\mu \right)$ 在 $\left(\text{0},\infty \right)$ 上是连续的，根据定义2.1，可得

$\left|\tilde{\Phi }\left(z,{\mu }_2\right)-\tilde{\Phi }\left(z,{\mu }_1\right)\right|\le \kappa \left|{\mu }_1-{\mu }_2\right|,\forall z\in R,{\mu }_1,{\mu }_2\in \left(0,\infty \right)$

并且

$\left|\tilde{\Phi }\left(z,\mu \right)-\Phi \left(z\right)\right|\le \kappa \mu ,\forall z\in R,\mu \in \left(0,\infty \right)$ (2.2)

3. 随机优化问题

本文主要研究以下形式的随机优化问题：

$\begin{array}{cc}\min & E_p\left[f\left(x,\xi \right)\right]\\ \begin{array}{l}s.t.\\ \end{array}& \begin{array}{l}g\left(x,\xi \right)=0\\ x\in C\end{array}\end{array}$ (3.1)

其中 $\xi$ 为定义在概率空间 $\left(\Omega ,F,P\right)$ 上的随机变量， $E_p\left[f\left(x,\xi \right)\right]={\displaystyle {\int }_{\Omega }f\left(x,\xi \right)\text{d}P\left(\xi \right)}$ 表示随机变量 $\xi$ 的理论数学期望。问题(3.1)中的随机函数 $f\left(x,\xi \right):R^n\times \Omega \to R$ 关于x连续并且 $g\left(x,\xi \right):R^n\times \Omega \to R^m$ 关于x连续。

对于以下形式的非光滑凸优化问题：

$\underset{x\in H}{\min }f(\; x\; )$

其中 $f\left(x\right)$ 是一个非光滑凸函数，H为希尔伯特空间。Qu和Biancite在文献 [15] 中提出了一种二阶微分方程方法，形式如下：

$\ddot{x}\left(t\right)+\frac{\alpha }{t}\stackrel{\dot{}}{x}\left(t\right)+{\nabla }_x\tilde{f}\left(x\left(t\right),\mu \left(t\right)\right)=0$

对于问题(3.1)，本文利用样本均值近似法(SAA)得到目标函数的SAA问题，则问题(3.1)可转化为

$\begin{array}{cc}\min & \frac{\text{1}}{N}{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(x,{\xi }_i\right)}\\ \begin{array}{l}s.t.\hfill \end{array}& \begin{array}{l}g\left(x,\xi \right)=\text{0}\hfill \\ x\in C\hfill \end{array}\end{array}$ (3.2)

利用罚函数方法将问题(3.2)转换为下面无约束优化形式：

$\begin{array}{cc}\underset{x\in C}{\min }& \Phi \left(\text{z}\right)=\frac{1}{N}\end{array}{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(x,{\xi }_i\right)}+\frac{1}{2}{\Vert g\left(x,\xi \right)\Vert }^2$

进而，采用二阶微分方程方法求解上述优化问题，其形式如下：

$\ddot{z}\left(t\right)+\frac{\alpha }{t}\stackrel{\dot{}}{z}\left(t\right)+{\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)=0$ (3.3)

其中参数 $\alpha >0$ ， $\tilde{\Phi }\left(z\left(t\right)\right)$ 是 $\Phi \left(z\left(t\right)\right)$ 的光滑函数， $\tilde{f}\left(z\left(t\right)\right)$ 是 $f\left(z\left(t\right)\right)$ 的光滑函数， $\mu :\left[0,\infty \right]\to \left[0,\infty \right]$ 是一个连续可微的递减函数，满足 ${\lim }_{t\to \infty }\mu \left(t\right)=0$ 。

对于式(3.3)中的函数 $\mu (·)$ ，本文做出如下假设

${\displaystyle {\int }_{t_0}^{\infty }t\mu \left(t\right)\text{d}t}<\infty$ (3.4)

带回定义1.1，则对于任意固定的 $t_0>0$ ，式(3.4)可以推出

${\displaystyle {\int }_{t_0}^{\infty }\frac{1}{t}\mu \left(t\right)\text{d}t}<\infty$

4. 收敛定理

定理1：假设 $z:\left[t_0,\infty \right]\to R^n$ 是式(3.3)的轨迹，并假设 $\arg \min \Phi \left(z\right)$ 非空。

1) 假设 $\alpha \ge \text{3}$ ，那么

$\Phi \left(z\left(t\right)\right)-\min \Phi ={\rm O}\left(\frac{1}{t^2}\right).$

2) 假设 $\alpha >\text{3}$ ，那么

$\begin{array}{l}{\displaystyle {\int }_{t_0}^{\infty }t\left(\Phi \left(z\left(t\right)-\min \Phi \right)\right)\text{d}t}<\infty \\ {\displaystyle {\int }_{t_0}^{\infty }t{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2\text{d}t}<\infty \\ \Phi \left(z\left(t\right)\right)-\min \Phi =o\left(\frac{1}{t^2}\right)\end{array}$ (4.1)

证明：1) 令 $z^{\ast }\in \arg \min \Phi$ ，并考虑如下函数

$\beta \left(t\right)=t^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)+\frac{1}{2}{\Vert \left(\alpha -1\right)\left(z\left(t\right)-z^{*}\right)+t\stackrel{\dot{}}{z}\left(t\right)\Vert }^2$

根据式(2.2)，可以得出

$\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)\text{+2}\kappa \mu \left(t\right)\ge \Phi \left(z\left(t\right)\right)-\Phi \left(z^{*}\right)\ge 0$ (4.2)

因此推导出 $\beta \left(t\right)\ge 0$ 。由(3.3)，得

$\begin{array}{c}\frac{\text{d}}{\text{d}t}\beta \left(t\right)=2t\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+\text{2}\kappa \mu \left(t\right)\right)\\ +t^2\left(\langle {\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right),\stackrel{\dot{}}{z}\left(t\right)\rangle +{\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)-{\nabla }_{\mu }\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)+\text{2}\kappa \stackrel{\dot{}}{\mu }\left(t\right)\right)\\ +\langle \left(\alpha -1\right)\left(z\left(t\right)-z^{*}\right)+t\stackrel{\dot{}}{z}\left(t\right),\alpha \stackrel{\dot{}}{z}\left(t\right)+t\ddot{z}\left(t\right)\rangle \\ =2t\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+\text{2}\kappa \mu \left(t\right)\right)-\left(\alpha -1\right)t\langle z\left(t\right)-z^{*},{\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\rangle \\ +t^2\left({\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)-{\nabla }_{\mu }\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)+\text{2}\kappa \stackrel{\dot{}}{\mu }\left(t\right)\right)\end{array}$ (4.3)

通过 $\stackrel{\dot{}}{\mu }\left(t\right)\le 0$ 以及式(2.2)推导出

${\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)-{\nabla }_{\mu }\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)\le -\text{2}\kappa \stackrel{\dot{}}{\mu }\left(t\right)$ (4.4)

因为对于任意固定的 $\mu$ ， $\tilde{\Phi }\left(z,\mu \right)$ 相对于z都是凸函数，故有

$\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)-\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\ge \langle {\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right),z^{*}-z\left(t\right)\rangle$ (4.5)

若 $\alpha \ge 3$ ，则将式(4.4)和式(4.3)代入到式(4.2)中，则可以得到

$\begin{array}{c}\frac{\text{d}}{\text{d}t}\beta \left(t\right)\le -\left(\alpha -3\right)t\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)+2\left(\alpha -1\right)\kappa t\mu \left(t\right)\\ \le 2\left(\alpha -1\right)\kappa t\mu \left(t\right)\end{array}$ (4.6)

其中最后一个不等式可使用式(4.1)。

通过式(3.4)，有 ${\left[\frac{\text{d}}{\text{d}t}\beta \left(t\right)\right]}_{+}$ 属于 $L_1\left(t_0,\infty \right)$ ，令 $\rho \left(t\right):=\beta \left(t\right)-{\displaystyle {\int }_{t_0}^t{\left[\frac{\text{d}}{\text{d}t}\beta \left(t\right)\right]}_{+}}\text{d}t$ ，则由 $\beta \left(t\right)$ 和 ${\left[\frac{\text{d}}{\text{d}t}\beta \left(t\right)\right]}_{+}\in L_1\left(t_0,\infty \right)$ 的有界性可以发现 $\rho (·)$ 也是有界的。又因为 $\frac{\text{d}}{\text{d}t}\rho \left(t\right)=\frac{\text{d}}{\text{d}t}\beta \left(t\right)-{\left[\frac{\text{d}}{\text{d}t}\beta \left(t\right)\right]}_{+}\le 0$ ，故 $\underset{t\to \infty }{\lim }\rho \left(t\right)$ 是存在的。因此可得

$\underset{t\to \infty }{\lim }\beta \left(t\right)=\underset{t\to \infty }{\lim }w\left(t\right)+{\displaystyle {\int }_{t_0}^{\infty }{\left[\beta \left(s\right)\right]}_{+}}\text{d}s<\infty$ (4.7)

由此可知 $\beta (·)$ 在 $\left[t_0,\infty \right)$ 上是有界的，且 $t^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)$ 在 $\left[t_0,\infty \right)$ 上是有界的，故存在一个常数C，使得

$t^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)\le C,\forall t\ge t_0.$

因此，根据式(4.1)有

$\Phi \left(z\left(t\right)\right)-\Phi \left(z^{\ast }\right)\le \frac{C}{t^2}$

即

$\Phi \left(z\left(t\right)\right)-\Phi \left(z^{\ast }\right)={\rm O}\left(\frac{1}{t^2}\right)$

2) 假设 $\alpha >3$ ，对式(4.6)做t₀到t的积分，得到

$\begin{array}{c}{\displaystyle {\int }_{t_0}^{t}s\left(\tilde{\Phi }\left(z\left(s\right),\mu \left(s\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(s\right)\right)+2\kappa \mu \left(s\right)\right)\text{d}s}\le \frac{1}{\alpha -3}\left(\beta \left(t_0\right)-\beta \left(t\right)\right)+\frac{2\left(\alpha -1\right)\kappa }{\alpha -3}{\displaystyle {\int }_{t_0}^{t}s\mu \left(s\right)\text{d}s}\\ \le \frac{1}{\alpha -3}\beta \left(t_0\right)+\frac{2\left(\alpha -1\right)\kappa }{\alpha -3}{\displaystyle {\int }_{t_0}^{t}s\mu \left(s\right)\text{d}s}\end{array}$

在式(3.4)下，有

${\displaystyle {\int }_{t_0}^{\infty }s\left(\tilde{\Phi }\left(z\left(s\right),\mu \left(s\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(s\right)\right)+2\kappa \mu \left(s\right)\right)\text{d}s}<\infty$ (4.8)

通过式(4.2)，可以得到

${\displaystyle {\int }_{t_0}^{\infty }t\left(\Phi \left(z\left(t\right)\right)-\min \Phi \right)\text{d}t}<\infty$

接下来证明 $\Phi \left(z\left(t\right)\right)-\min \Phi =o\left(\frac{1}{t^2}\right)$

取算法(3.3)的标量乘以 $t^2\stackrel{\dot{}}{x}\left(t\right)$ ，则有

$\begin{array}{c}\frac{t^2}{2}\frac{\text{d}}{\text{d}t}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2+\alpha t{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2+t^2\frac{\text{d}}{\text{d}t}\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)\\ =t^2({\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)-{\nabla }_{\mu }\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)\stackrel{\dot{}}{\mu }\left(t\right)+2\kappa \stackrel{\dot{}}{\mu }(\; t\; ))\end{array}$

对上述方程做 $t_0$ 到 $t$ 的积分，则有

$\begin{array}{l}\frac{t^2}{2}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2-\frac{t_0{}^2}{2}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2+\left(\alpha -1\right){\displaystyle {\int }_{t_0}^{t}s{\Vert \stackrel{\dot{}}{z}\left(s\right)\Vert }^2}\text{d}s+t^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)\\ -t_0^2\left(\tilde{\Phi }\left(z\left(t_0\right),\mu \left(t_0\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t_0\right)\right)+2\kappa \mu \left(t_{\text{0}}\right)\right)-2{\displaystyle {\int }_{t_0}^{t}s\left(\tilde{\Phi }\left(z\left(s\right),\mu \left(s\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(s\right)\right)+2\kappa \mu \left(s\right)\right)\text{d}s}\\ ={\displaystyle {\int }_{t_0}^t{s}^2{\nabla }_{\mu }\tilde{\Phi }\left(z\left(s\right),\mu \left(s\right)\right)\stackrel{\dot{}}{\mu }\left(s\right)-{\nabla }_{\mu }\tilde{\Phi }(z^{*},\mu (\; s\; ))}\end{array}$

结合上述关系式以及式(4.2)和(4.4)，由于 $\frac{t^2}{2}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2\ge 0$ ，则有

$\left(\alpha -1\right){\displaystyle {\int }_{t_0}^{t}s{\Vert \stackrel{\dot{}}{z}\left(s\right)\Vert }^2}\text{d}s\le \tilde{C}+2{\displaystyle {\int }_{t_0}^{t}s\left(\tilde{\Phi }\left(z\left(s\right),\mu \left(s\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(s\right)\right)+2\kappa \mu \left(s\right)\right)\text{d}s}$

其中

$\tilde{C}=\frac{t_0^2}{2}{\Vert \stackrel{\dot{}}{z}\left(t_0\right)\Vert }^2+t_0^2\left(\tilde{\Phi }\left(z\left(t_0\right),\mu \left(t_0\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t_0\right)\right)+2\kappa \mu \left(t_0\right)\right)$

由式(4.8)和 $\alpha >3$ 可得式(4.1)。

接下来考虑

$E\left(t\right):=\frac{1}{2}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2+\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu (\; t\; )$

由于他在 $\left[t_0,\infty \right)$ 上是非负的，根据式(4.1)和(4.8)，

${\displaystyle {\int }_{t_0}^{\infty }tE\left(t\right)\text{d}t}<\infty$ (4.9)

对 $t^{2}E\left(t\right)$ 进行微分，则有

$\begin{array}{c}\frac{\text{d}}{\text{d}t}\left(t^{2}E\left(t\right)\right)=2tE\left(t\right)+t^2\frac{\text{d}E\left(t\right)}{\text{d}t}\\ =2t\left(\frac{1}{2}{\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert }^2+\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{*},\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)\\ +t^2\left(\langle \stackrel{\dot{}}{z}\left(t\right),\ddot{z}\left(t\right)\rangle +\langle {\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right),\stackrel{\dot{}}{z}\left(t\right)\rangle \right)\\ +{\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{z}\left(t\right)-\left({\nabla }_{\mu }\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)\stackrel{\dot{}}{z}\left(t\right)+2\kappa \stackrel{\dot{}}{\mu }\left(t\right)\right)\\ +t^2\left(\langle \stackrel{\dot{}}{z}\left(t\right),\ddot{z}\left(t\right)\rangle +\langle {\nabla }_z\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right),\stackrel{\dot{}}{z}\left(t\right)\rangle \right)\\ +{\nabla }_{\mu }\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)\stackrel{\dot{}}{z}\left(t\right)-\left({\nabla }_{\mu }\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)\stackrel{\dot{}}{z}\left(t\right)+2\kappa \stackrel{\dot{}}{\mu }\left(t\right)\right)\end{array}$ (4.10)

在(3.3)和式(4.4)的基础上可推出

$\begin{array}{c}\frac{\text{d}}{\text{d}t}\left(t^{2}E\left(t\right)\right)\le \text{2}t\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)+t\left(1-\alpha \right)\Vert \stackrel{\dot{}}{z}\left(t\right)\Vert \\ \le \text{2}t(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)+2\kappa \mu (\; t\; ))\end{array}$

结合式(4.8)和(4.10)发现 ${\left[\frac{\text{d}}{\text{d}t}\left(t^{2}E\left(t\right)\right)\right]}_{+}$ 属于 $L_1\left(t_0,\infty \right)$ ，因此类比式(4.7)的推导过程可知 $\underset{t\to \infty }{\lim }{t}^{2}E\left(t\right)$ 存在，通过式(4.9)可知 ${\displaystyle {\int }_{t_0}^{\infty }tE\left(t\right)\text{d}t}={\displaystyle {\int }_{t_0}^{\infty }\frac{1}{t}\left(t^{2}E\left(t\right)\right)\text{d}t}$ ，又由于 ${\displaystyle {\int }_{t_0}^{\infty }\frac{1}{t}\text{d}t}=\infty$ 和 $\underset{t\to \infty }{\lim }{t}^{2}E\left(t\right)$ 的存在性可知

$\underset{t\to \infty }{\lim }{t}^{2}E\left(t\right)=0$

在E的定义下有

$0\le \underset{t\to \infty }{\lim }{t}^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)\le \underset{t\to \infty }{\lim }{t}^{2}E\left(t\right)=0$

并且

$\begin{array}{c}0\le \underset{t\to \infty }{\lim }{t}^2\left(\Phi \left(z\left(t\right)\right)-\Phi \left(z^{\ast }\right)\right)\\ \le \underset{t\to \infty }{\lim }{t}^2\left(\tilde{\Phi }\left(z\left(t\right),\mu \left(t\right)\right)-\tilde{\Phi }\left(z^{\ast },\mu \left(t\right)\right)+2\kappa \mu \left(t\right)\right)=0\end{array}$

即

$\Phi \left(z\left(t\right)\right)-\min \Phi =o\left(\frac{1}{t^2}\right)$

5. 数值模拟

在数值模拟部分，本文将二阶微分方程算法用于求解以下两个问题，它们的目标函数是凸优化函数，其中问题1是无约束随机优化问题。结果表明，二阶微分方程算法计算的结果具有较好的收敛性，计算程序用MATLAB编写。

例5.1

$\begin{array}{c}\min f\left(x\right):=E_{\theta }\left[f\left(x,\theta \right)\right]\\ :=E_{\theta }\left[\frac{1}{2}{x}^{\text{T}}\left(A+Adiag\left(\theta \right)x+b^{\text{T}}x\right)\right]\end{array}$

其中对角矩阵 $A\in R^{n\times n}$ ，向量 $b\in R^n$ ，随机向量 $\theta \in R^n$ ， $diag\left(\theta \right)$ 是由 $\theta$ 生成的对角矩阵。 $\theta$ 是在四维向量空间 $\theta ={\left[-{\theta }_0,{\theta }_0\right]}^n$ 中随机均匀选取的，并且 ${\theta }_0<1$ 。

为了研究的简便性，本文在 ${\left[0,1\right]}^n$ 中随机选取向量b，并在离散集 $\left\{1,{10}^{-1},\cdots ,{10}^{-\xi }\right\}$ 中随机选取元素作为矩阵A的对角元素，矩阵A的变化决定了该问题的最优解。将本题参数设置为 $n=4,{\theta }_0=0.5,\xi =3,\alpha =20$ ，其最优解为 $x^{*}=A^{-1}b$ ，接下来用本文的二阶微分方程算法进行求解。所求解与最小值点之间距离的变化图像如图1所示：

图1. 所求解与最小值点之间的距离随时间变化图像

例5.2

$\begin{array}{l}\min f\left(x\right)=E_{\theta }\left[f\left(x,\theta \right)\right]\\ =E_{\theta }\left[{\displaystyle \underset{i=1}{\overset{n/4}{\sum }}\left(1+{\theta }_i\right)}\left({\left(x_{4i-1}+10x_{4i-2}\right)}^2+5{\left(x_{4i-1}-x_{4i}\right)}^2+{\left(x_{4i-2}-2x_{4i-1}\right)}^4+10{\left(x_{4i-3}-x_{4i}\right)}^4\right)\right]\\ \text{s}\text{.t}\text{.}g\left(x,\theta \right)=-\theta x=0\end{array}$

其中 $x\in C,\theta \in R^{n/4}$ ，随机变量 $\theta$ 在 ${\left[-{\theta }_0,{\theta }_0\right]}^{n/4}$ 中均匀随机选择。

首先将目标函数转化为SAA问题，接下来利用罚函数发将其转化为无约束问题，即

$\begin{array}{cc}\underset{x\in C}{\text{min}}& \Phi \left(z\right)=\frac{1}{N}\end{array}{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(x,{\theta }_i\right)}+\frac{1}{2}{\Vert g\left(x,\theta \right)\Vert }^2$

接下来利用二阶微分方程算法求解，发现例5.2有唯一最小值的点 $x^{*}=\left(0,0,0,0\right)$ ，并且最小值为0。求解出的点与最小值点之间距离的变化图像如图2所示：

图2. 所求解与最小值点之间的距离随时间变化图像

6. 结论

目前常用SAA方法求解有约束随机优化问题，但其计算较为复杂。通过上述数值模拟可以发现，本文提出的二阶微分方程方法求解例5.1和例5.2的速度较快，精度较小，并且所求的结果能够较为平滑的收敛到最优解。因此，二阶微分方程方法在求解等式约束随机优化问题时是收敛的。

但本文只验证了二阶微分方程算法可以求解等式约束下的随机优化问题，对于求解不等式约束的随机优化问题和随机约束的随机优化问题，二阶微分方程方法是否也具有良好的收敛性，值得下一步的探讨和研究。

文章引用

吕琪楠,孙菊贺,王 莉,谢红俭. 求解具有等式约束的随机优化问题的二阶微分方程方法
Second Order Differential Equation Algorithm for Solving Stochastic Optimization Problems with Equality Constraints[J]. 应用数学进展, 2023, 12(10): 4529-4537. https://doi.org/10.12677/AAM.2023.1210444

参考文献