具有不等式约束的优化问题的微分方程方法

The Differential Equation Method for Solving the Optimization with the Inequality Constraints

摘要: 本文研究了具有不等式约束的优化问题的微分方程方法。首先建立优化问题的拉格朗日函数，运用鞍点的性质和投影算子，将原始的优化问题转化为等式方程。再利用等式方程建立微分方程系统，并证明了该微分方程系统的轨迹的聚点是原始的优化问题的解。

Abstract: This paper presents a class of differential equation method for solving the optimization with the inequality constraints. Firstly, the Lagrange function for the optimization is established, then the original convex optimization can be transformed to be the equations based on the nature of saddle point and the projection operator. The differential equation systems are obtained by applying the equations, and the convergence of the trajectories of these differential equation systems are proved.

1. 引言

本文将研究具有不等式约束的优化问题，如下：求解 $x^{*}\in Q$ 使得

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}g\left(x\right)\le 0\\ x\in Q\end{array}$ (1.1)

其中， $f:R^n\to R$ 是凸函数， $g:R^n\to R^m$ 是凸向量值映射，Q是非空闭凸集合。

优化应用于很多学科领域，诸如自动控制系统，信号处理，通讯和网络，电子电路设计，数据分析和建模，统计学(最优化设计)，以及金融等。其求解方法有内点法、罚函数方法等许多经典的求解方法。本文通过对Antipin [1] [2] 文章的学习和研究，运用微分方程方法求解具有不等式约束的优化问题(1.1)。

投影算子在具有不等式约束的优化问题(1.1)转化为等式时起着重要的作用，下面介绍投影算子的定义及与其相关的重要引理。

设C是闭凸集合，对每一个 $x\in R^n$，存在唯一的 $\hat{x}\in C$ 使得

$\Vert x-\hat{x}\Vert =\min \left\{\Vert x-y\Vert |y\in C\right\},$

称 $\hat{x}$ 是点x到集合C的投影，记作 ${\Pi }_C\left(x\right)$。投影算子 ${\Pi }_C\left(x\right):R^n\to C$ 是定义好的，且 ${\Pi }_C\left(x\right)$ 是非扩张映射。

引理1.1 ( [3] )设H是实希尔伯特空间， $C\subset H$ 是闭凸集合。对给定的 $z\in H$， $u\in C$ 满足不等式

$\langle u-z,v-u\rangle \ge 0,\forall v\in C,$

当且仅当 $u-{\Pi }_C\left(z\right)=0$。

2. 具有不等式约束的凸优化问题的充分条件

本节将运用拉格朗日函数及投影算子等将原始的具有不等式约束的优化问题(1.1)经过计算、转化得到其由等式表示的充分条件，为微分方程系统的建立做好充分的准备。

具有不等式约束的优化问题(1.1)的拉格朗日函数如下：

$L\left(x,u\right)=f\left(x\right)+\langle u,g\left(x\right)\rangle \text{,}\forall x\in Q,\forall u\in R_{+}^m,$ (2.1)

由于 $x^{*}$ 是 $f\left(y\right)$ 的最优值点，点对 $\left(x^{*},u^{*}\right)$ (在一定的正则条件下)是拉格朗日函数 $L\left(x,u\right)$ 的鞍点，即

$f\left(x^{*}\right)+\langle u,g\left(x^{*}\right)\rangle \le f\left(x^{*}\right)+\langle u^{*},g\left(x^{*}\right)\rangle \le f\left(x\right)+\langle u^{*},g\left(x^{*}\right)\rangle ,$ (2.2)

不等式组(2.2)中左边的不等式和右边不等式可分别转化为下面的包含形式

$u^{*}\in \arg \max \left\{\langle u,g\left(x^{*}\right)\rangle |u\in R_{+}^m\right\},$ (2.3)

$x^{*}\in \arg \min \left\{f\left(x\right)+\langle u^{*},g\left(x\right)\rangle |x\in Q\right\}.$ (2.4)

在一定的条件下，可以得到(2.4)成立的充分条件，见下面的命题：

命题2.1：若 $f:R^n\to R$ 为凸函数， $g:R^n\to R^m$ 为向量值映射，则(2.4)式成立的充分条件为

$\langle \nabla f\left(x^{*}\right)+\nabla g\left(x^{*}\right)u^{*},x-x^{*}\rangle \ge 0,\forall x\in Q.$ (2.5)

其中 $\nabla f$ 表示函数f的梯度， $\nabla g$ 表示映射g和雅可比阵的转置。

证明：如果函数g是凸的，则由凸性条件可得

$g\left(x\right)-g\left(x^{*}\right)\ge Jg\left(x^{*}\right)\left(x-x^{*}\right),$ (2.6)

其中 $Jg$ 表示映射g的雅可比阵。

同理，如果函数f是凸的，则由凸性条件可得

$f\left(x\right)-f\left(x^{*}\right)\ge Jf\left(x^{*}\right)\left(x-x^{*}\right),$ (2.7)

其中 $Jf$ 表示函数f的梯度的转置。

而事实上，由于共轭算子的性质可以得到

$\begin{array}{l}Jf\left(x^{*}\right)\left(x-x^{*}\right)+\langle u^{*},Jg\left(x^{*}\right)\left(x-x^{*}\right)\rangle \\ =\langle Jf{\left(x^{*}\right)}^{\text{T}},x-x^{*}\rangle +\langle Jg{\left(x^{*}\right)}^{\text{T}}{u}^{*},x-x^{*}\rangle \\ =\langle \nabla f\left(x^{*}\right),x-x^{*}\rangle +\langle \nabla g\left(x^{*}\right)u^{*},x-x^{*}\rangle .\end{array}$ (2.8)

则根据(2.6)与(2.7)，(2.5)成立时必有(2.4)成立，即

$f\left(x\right)-f\left(x^{*}\right)+\langle u^{*},g\left(x\right)-g\left(x^{*}\right)\rangle \ge 0.$

则本命题的结论成立。证毕。

下面的命题可以找到具有不等式约束的优化问题的等式转化，为微分方程系统的建立奠定基础。

命题2.2：若 $f:R^n\to R$ 为凸函数， $g:R^n\to R^m$ 为向量值凸映射，则若 $\left(x^{*},u^{*}\right)$ 使下面的等式方程

$x^{*}={\prod }_Q\left(x^{*}-\alpha \left(\nabla f\left(x^{*}\right)+\nabla g\left(x^{*}\right)\right)u^{*}\right),$ (2.9)

$u^{*}={\prod }_{+}\left(u^{*}+\alpha g\left(x^{*}\right)\right).$ (2.10)

成立，则 $\left(x^{*},u^{*}\right)$ 满足鞍点不等式(2.2)，即 $x^{*}$ 是具有不等式约束的优化问题(1.1)的解。

证明：根据(2.5)和(2.3)可以得到

$\langle \nabla f\left(x^{*}\right)+\nabla g\left(x^{*}\right)u^{*},x-x^{*}\rangle \ge 0,\forall x\in Q,$ (2.11)

$\langle -g\left(x^{*}\right),u-u^{*}\rangle \ge 0,\forall u\in R_{+}^m.$ (2.12)

由(2.11)式和(2.12)分别可以得到，对 $\alpha >0$ 有

$\langle x^{*}-x^{*}+\alpha \left(\nabla f\left(x^{*}\right)+\nabla g\left(x^{*}\right)\right)u^{*},x-x^{*}\rangle \ge 0,\forall x\in Q,$

$\langle u^{*}-u^{*}-\alpha g\left(x^{*}\right),u-u^{*}\rangle \ge 0,\forall u\in R_{+}^m.$

根据投影算子的定义和引理1.1，上述的两个变分不等式可转化为下面的等式形式

$x^{*}={\prod }_Q\left(x^{*}-\alpha \left(\nabla f\left(x^{*}\right)+\nabla g\left(x^{*}\right)u^{*}\right)\right),$ (2.13)

$u^{*}={\prod }_{+}\left(u^{*}+\alpha g\left(x^{*}\right)\right),$ (2.14)

其中 ${\Pi }_{+}(\cdot )$ 和 ${\Pi }_Q(\cdot )$ 分别是到正卦限 $R_{+}^m$ 和集合Q的投影算子， $\alpha >0$ 是一个参数。证毕。

注2.1：上面的讨论表明在一定的正则条件下，命题2.1和命题2.2给出了 $x^{*}$ 是具有不等式约束优化问题(1.1)的解的充分条件是 $x^{*}$ 及其拉格朗日函数中对偶最优解 $u^{*}$ 满足等式(2.9)和(2.10)。

3. 微分方程系统的建立

本节将要建立求解具有不等式约束的凸优化问题(1.1)的微分方程系统。

在等式方程(2.9)和(2.10)的基础上可建立如下的微分方程系统：

$\begin{array}{l}\frac{\text{d}x}{\text{d}t}+x={\prod }_Q\left(x-\alpha \left(\nabla f\left(x\right)+\nabla g\left(x\right)u\right)\right),x\left(t_0\right)=x_0,\\ \frac{\text{d}u}{\text{d}t}+u={\prod }_{+}\left(u+\alpha g\left(x\right)\right),u\left(t_0\right)=u_0,\end{array}$

其中 $\alpha >0$ 是参数。

为了证明二阶微分方程系统的轨迹收敛于拉格朗日函数 $L\left(x,u\right)$ 的鞍点 $\left(x^{*},u^{*}\right)$，受到文献Antipin [1] 和Antipin [2] 的启示，引入下面的具有控制过程的微分方程系统：

$\begin{array}{l}\bar{x}={\prod }_Q\left(x-\alpha \left(\nabla f\left(x\right)+\nabla g\left(x\right)\bar{u}\right)\right),\\ \bar{u}={\prod }_{+}\left(u+\alpha g\left(x\right)\right)\end{array}$ (3.1)

其中 $\bar{x}={\prod }_Q\left(x-\alpha \left(\nabla f\left(x\right)+\nabla g\left(x\right)\bar{u}\right)\right),\bar{u}={\prod }_{+}\left(u+\alpha g\left(x\right)\right)$。

为了简便计算，记 $\stackrel{\dot{}}{x}=\frac{\text{d}x}{\text{d}t}$ 和 $\stackrel{\dot{}}{u}=\frac{\text{d}u}{\text{d}t}$。根据投影定理，一阶微分方程系统(3.1)可转化成下面的变分不等式形式：

$\langle \stackrel{\dot{}}{x}+\alpha \left(\nabla f\left(\bar{x}\right)+\nabla g\left(\bar{x}\right)\bar{u}\right),y-x-\stackrel{\dot{}}{x}\rangle \ge 0,\forall y\in Q,$ (3.2)

$\langle \stackrel{\dot{}}{u}-\alpha g\left(\bar{x}\right),v-u-\stackrel{\dot{}}{u}\rangle \ge 0,\forall v\in R_{+}^m,$ (3.3)

$\langle \bar{x}-x+\alpha \left(\nabla f\left(x\right)+\nabla g\left(x\right)\bar{u}\right),y-\bar{x}\rangle \ge 0,\forall y\in Q,$ (3.4)

$\langle \bar{u}-u-\alpha g\left(x\right),v-\bar{u}\rangle \ge 0,\forall v\in R_{+}^m.$ (3.5)

接下来，如果 $g,\nabla f$ 和 $\nabla g$ 是Lipschitz连续的，Lipschitz常数分别是 $\left|g\right|,\left|\nabla f\right|$ 和 $\left|\nabla g\right|$，除此之外，假设 $\Vert \bar{u}\Vert \le C_0$ 且 $C_0$ 是一个常数。

在这些条件下，很容易证明得到下面的不等式关系：

$\Vert \stackrel{\dot{}}{u}+u-\bar{u}\Vert \le \alpha \Vert g\left(\bar{x}\right)-g\left(x\right)\Vert \le \alpha \left|g\right|\Vert \bar{x}-x\Vert$ (3.6)

和

$\begin{array}{c}\Vert \stackrel{\dot{}}{x}+x-\bar{x}\Vert \le \alpha \Vert \nabla f\left(\bar{x}\right)+\nabla g\left(\bar{x}\right)\bar{u}-\left(\nabla f\left(x\right)+\nabla g\left(x\right)\bar{u}\right)\Vert \\ =\alpha \Vert \nabla f\left(\bar{x}\right)+\nabla g\left(\bar{x}\right)\bar{u}-\nabla f\left(x\right)-\nabla g\left(x\right)\bar{u}\Vert \\ \le \alpha \left(\Vert \nabla f\left(\bar{x}\right)-\nabla f\left(x\right)\Vert +\Vert \nabla g\left(\bar{x}\right)-\nabla g\left(x\right)\Vert \Vert \bar{u}\Vert \right)\\ \le \alpha \left(\left|\nabla f\right|+C_0\left|\nabla g\right|\right)\Vert \bar{x}-x\Vert \\ =\alpha C\Vert \bar{x}-x\Vert ,\end{array}$ (3.7)

其中， $C=\left|\nabla f\right|+C_0\left|\nabla g\right|$。

4. 主要结果

定理3.1设具有不等式约束的优化问题(1.1)的解集 ${\Omega }^{*}$ 是非空的， $\nabla f$ 是单调的且Lipschitz连续的，Lipschitz常数为 $\left|\nabla f\right|$；g是凸可微的且Lipschitz连续的，Lipschitz常数为 $\left|g\right|$。设对任意 $t\to \infty$ 满足 $\Vert u\left(t\right)\Vert \le C_0$， $\nabla g$ 是Lipschitz连续的，Lipschitz常数为 $\left|\nabla g\right|$， $Q\subseteq R^n$ 是闭凸集合。则当

${\alpha }^2{\left(\left|\nabla f\right|+C_0\left|\nabla g\right|\right)}^2+{\left|g\right|}^2<\frac{1}{2}$ 时，微分方程系统(3.1)的轨迹 $x\left(t\right)$ 的聚点是具有约束不等式约束的优化问题(1.1)的解。

证明：在变分不等式(3.2)中令 $y=x^{*}\in {\Omega }^{*}$，有

$\langle \stackrel{\dot{}}{x}+\alpha \left(\nabla f\left(\bar{x}\right)+\nabla g\left(\bar{x}\right)\bar{u}\right),x^{*}-x-\stackrel{\dot{}}{x}\rangle \ge 0.$ (3.8)

在变分不等式(3.4)中令 $y=x+\stackrel{\dot{}}{x}$，可得

$\begin{array}{l}\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla f\left(\bar{x}\right),x+\stackrel{\dot{}}{x}-\bar{x}\rangle -\alpha \langle \nabla f\left(\bar{x}\right)-\nabla f\left(x\right),x+\stackrel{\dot{}}{x}-\bar{x}\rangle \\ +\alpha \langle \nabla g\left(\bar{x}\right)\bar{u},x+\stackrel{\dot{}}{x}-\bar{x}\rangle -\alpha \langle \nabla g\left(\bar{x}\right)\bar{u}-\nabla g\left(x\right)\bar{u},x+\stackrel{\dot{}}{x}-\bar{x}\rangle \ge 0,\end{array}$

通过不等式(3.7)，上述不等式变为

$\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla f\left(\bar{x}\right),x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla g\left(\bar{x}\right)\bar{u},x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\left(\alpha C^2\right){\Vert x-x\Vert }^2\ge 0.$ (3.9)

其中， $C=\left|\nabla f\right|+C_0\left|\nabla g\right|$。将不等式(3.8)与(3.9)相加可得

$\begin{array}{l}\langle \stackrel{\dot{}}{x},x^{*}-x-\stackrel{\dot{}}{x}\rangle +\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla f\left(\bar{x}\right),x^{*}-\bar{x}\rangle \\ +\alpha \langle \nabla g\left(\bar{x}\right)\bar{u},x^{*}-\bar{x}\rangle +{\left(\alpha C\right)}^2{\Vert \bar{x}-x\Vert }^2\ge 0.\end{array}$ (3.10)

由于g是凸的，有

$\langle \nabla g\left(\bar{x}\right)\bar{u},x^{*}-\bar{x}\rangle =\langle \bar{u},Jg\left(\bar{x}\right)\left(x^{*}-\bar{x}\right)\rangle \le \langle \bar{u},g\left(x^{*}\right)-g\left(\bar{x}\right)\rangle .$ (3.11)

因此。由(3.10)和(3.11)可得

$\begin{array}{l}\langle \stackrel{\dot{}}{x},x^{*}-x-\stackrel{\dot{}}{x}\rangle +\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla f\left(\bar{x}\right),x^{*}-\bar{x}\rangle \\ +\alpha \langle \bar{u},g\left(x^{*}\right)-g\left(\bar{x}\right)\rangle +{\left(\alpha C\right)}^2{\Vert \bar{x}-x\Vert }^2\ge 0.\end{array}$ (3.12)

由于g是凸的，则由(2.11)式可得

$\langle \nabla f\left(x^{*}\right),x-x^{*}\rangle \text{+}\langle u^{*},g\left(x\right)-g\left(x^{*}\right)\rangle \ge 0,\forall x\in Q.$

在上式中令 $x=\bar{x}$，对 $\alpha >0$ 有

$\alpha \langle \nabla f\left(x^{*}\right),\bar{x}-x^{*}\rangle +\alpha \langle u^{*},g\left(\bar{x}\right)-g\left(x^{*}\right)\rangle \ge 0.$ (3.13)

将(3.12)和(3.13)相加，得

$\begin{array}{l}\langle \stackrel{\dot{}}{x},x^{*}-x-\stackrel{\dot{}}{x}\rangle +\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\alpha \langle \nabla f\left(\bar{x}\right)-\nabla f\left(x^{\ast }\right),x^{*}-\bar{x}\rangle \\ +\alpha \langle \bar{u}-u^{*},g\left(x^{*}\right)-g\left(\bar{x}\right)\rangle +{\left(\alpha C\right)}^2{\Vert \bar{x}-x\Vert }^2\ge 0.\end{array}$ (3.14)

接下来，令(3.3)中 $v=u^{*}$，令(3.5)中 $v=u+\stackrel{\dot{}}{u}$，分别得到

$\langle \stackrel{\dot{}}{u},u^{*}-u-\stackrel{\dot{}}{u}\rangle -\alpha \langle g\left(\bar{x}\right),u^{*}-u-\stackrel{\dot{}}{u}\rangle \ge 0$ (3.15)

和

$\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle -\alpha \langle g\left(\bar{x}\right),u+\stackrel{\dot{}}{u}-\bar{u}\rangle +\alpha \langle g\left(\bar{x}\right)-g\left(x\right),u+\stackrel{\dot{}}{u}-\bar{u}\rangle \ge 0$ (3.16)

将不等式(3.15)和(3.16)相加，利用不等式(3.6)得

$\langle \stackrel{\dot{}}{u},u^{*}-u-\stackrel{\dot{}}{u}\rangle +\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle -\alpha \langle g\left(\bar{x}\right),u^{*}-\bar{u}\rangle +{\left(\alpha \left|g\right|\right)}^2{\Vert \bar{x}-x\Vert }^2\ge 0.$

由于 $\langle \bar{u},g\left(x^{*}\right)\rangle \le 0$ 和 $\langle u^{*},g\left(x^{*}\right)\rangle =0$，将上述不等式写成

$\langle \stackrel{\dot{}}{u},u^{*}-u-\stackrel{\dot{}}{u}\rangle +\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle \text{+}\alpha \langle g\left(x^{*}\right)-g\left(\bar{x}\right),u^{*}-\bar{u}\rangle +{\left(\alpha \left|g\right|\right)}^2{\Vert \bar{x}-x\Vert }^2\ge 0$ (3.17)

将(3.14)和(3.17)相加，考虑到映射 $\nabla f$ 的单调性，有

$\begin{array}{l}\langle \stackrel{\dot{}}{x},x^{*}-x-\stackrel{\dot{}}{x}\rangle +\langle \stackrel{\dot{}}{u},u^{*}-u-\stackrel{\dot{}}{u}\rangle +\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle \\ +\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle +{\alpha }^2\left(C^2+{\left|g\right|}^2\right){\Vert \bar{x}-x\Vert }^2\ge 0.\end{array}$

得到

$\begin{array}{l}\langle \stackrel{\dot{}}{x},x^{*}-x\rangle -{\Vert \stackrel{\dot{}}{x}\Vert }^2+\langle \stackrel{\dot{}}{u},u^{*}-u\rangle -{\Vert \stackrel{\dot{}}{u}\Vert }^2+{\alpha }^2\left(C^2+{\left|g\right|}^2\right){\Vert \bar{x}-x\Vert }^2\\ +\langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle +\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle \ge 0.\end{array}$ (3.18)

通过下面的范数和内积等式

$\begin{array}{l}\frac{1}{2}\frac{\text{d}}{\text{d}t}{\Vert x-x^{*}\Vert }^2=\langle \stackrel{\dot{}}{x},x-x^{*}\rangle ,\frac{1}{2}\frac{\text{d}}{\text{d}t}{\Vert u-u^{*}\Vert }^2=\langle \stackrel{\dot{}}{u},u-u^{*}\rangle ,\\ \langle \bar{x}-x,x+\stackrel{\dot{}}{x}-\bar{x}\rangle =\frac{1}{2}{\Vert \stackrel{\dot{}}{x}\Vert }^2-\frac{1}{2}{\Vert \bar{x}-x\Vert }^2-\frac{1}{2}{\Vert x+\stackrel{\dot{}}{x}-\bar{x}\Vert }^2,\end{array}$

和

$\langle \bar{u}-u,u+\stackrel{\dot{}}{u}-\bar{u}\rangle =\frac{1}{2}{\Vert \stackrel{\dot{}}{u}\Vert }^2-\frac{1}{2}{\Vert \bar{u}-u\Vert }^2-\frac{1}{2}{\Vert u+\stackrel{\dot{}}{u}-\bar{u}\Vert }^2,$

不等式(3.18)变为

$\begin{array}{l}\frac{1}{2}\frac{\text{d}}{\text{d}t}{\Vert x-x^{*}\Vert }^2+\frac{1}{2}\frac{\text{d}}{\text{d}t}{\Vert u-u^{*}\Vert }^2+\frac{1}{2}{\Vert \stackrel{\dot{}}{x}\Vert }^2+\frac{1}{2}{\Vert \stackrel{\dot{}}{u}\Vert }^2+\left(\frac{1}{2}-{\alpha }^2\left(C^2+{\left|g\right|}^2\right)\right){\Vert \bar{x}-x\Vert }^2\\ +\frac{1}{2}{\Vert x+\stackrel{\dot{}}{x}-\bar{x}\Vert }^2+\frac{1}{2}{\Vert \bar{u}-u\Vert }^2+\frac{1}{2}{\Vert u+\stackrel{\dot{}}{u}-\bar{u}\Vert }^2\le 0.\end{array}$

考虑到 ${\alpha }^2{\left(\left|\nabla f\right|+C_0\left|\nabla g\right|\right)}^2+{\left|g\right|}^2<\frac{1}{2}$，将上述不等式从 $t_0$ 到t积分

$\begin{array}{l}\frac{1}{2}{\Vert x-x^{*}\Vert }^2+\frac{1}{2}{\Vert u-u^{*}\Vert }^2+\frac{1}{2}{\displaystyle {\int }_{t_0}^t{\Vert \stackrel{\dot{}}{x}\Vert }^2\text{d}\tau }+\frac{1}{2}{\displaystyle {\int }_{t_0}^t{\Vert \stackrel{\dot{}}{u}\Vert }^2\text{d}\tau }+{\alpha }_0{\displaystyle {\int }_{t_0}^t{\Vert \bar{x}-x\Vert }^2\text{d}\tau }+\frac{1}{2}{\displaystyle {\int }_{t_0}^t{\Vert \bar{u}-u\Vert }^2\text{d}\tau }\\ +\frac{1}{2}{\displaystyle {\int }_{t_0}^t{\Vert \bar{x}-x-\stackrel{\dot{}}{x}\Vert }^2\text{d}\tau }+\frac{1}{2}{\displaystyle {\int }_{t_0}^t{\Vert \bar{u}-u-\stackrel{\dot{}}{u}\Vert }^2\text{d}\tau }\le \frac{1}{2}{\Vert x_0-x^{*}\Vert }^2+\frac{1}{2}{\Vert u_0-u^{*}\Vert }^2,\end{array}$

其中 ${\alpha }_0=\frac{1}{2}-{\alpha }^2\left(C^2+{\left|g\right|}^2\right)$。

很容易看出 $x\left(t\right)$ 和 $u\left(t\right)$ 都是收敛的轨迹，而且，下面的积分当 $t\to \infty$ 时是收敛的

${\displaystyle {\int }_{t_0}^t{\Vert \stackrel{\dot{}}{x}\Vert }^2\text{d}\tau }<\infty ,{\displaystyle {\int }_{t_0}^t{\Vert \stackrel{\dot{}}{u}\Vert }^2\text{d}\tau }<\infty ,{\displaystyle {\int }_{t_0}^t{\Vert \bar{x}-x\Vert }^2\text{d}\tau <\infty ,}{\displaystyle {\int }_{t_0}^t{\Vert \bar{u}-u\Vert }^2\text{d}\tau }<\infty .$

假设对所有的 $t\ge t_0$，存在 $\epsilon >0$ 使得 $\Vert \stackrel{\dot{}}{x}\left(t\right)\Vert \ge \epsilon$， $\Vert \stackrel{\dot{}}{u}\left(t\right)\Vert \ge \epsilon$， $\Vert x-\bar{x}\Vert \ge \epsilon$ 和 $\Vert u-\bar{u}\Vert \ge \epsilon$。则这与积分当 $t\to \infty$ 时是收敛的相矛盾。所以，存在子列 $\left\{t_i\right\}$，当 $t_i\to \infty$ 时有 $\Vert \stackrel{\dot{}}{x}\left(t_i\right)\Vert \to 0$， $\Vert \stackrel{\dot{}}{u}\left(t_i\right)\Vert \to 0$， $\Vert x\left(t_i\right)-\bar{x}\left(t_i\right)\Vert \to 0$ 和 $\Vert u\left(t_i\right)-\bar{u}\left(t_i\right)\Vert \to 0$。由于 $x\left(t\right)$ 和 $u\left(t\right)$ 都是有界的，所以 $x\left(t_i\right)$ 和 $u\left(t_i\right)$ 也是有界的。选择 $x\left(t_i\right)$ 和 $u\left(t_i\right)$ 的子列 $x\left(t_{i_j}\right)$ 和 $u\left(t_{i_j}\right)$，则存在 $x^{\prime }$ 和 $u^{\prime }$ 使得 $x\left(t_{i_j}\right)\to x^{\prime }$， $u\left(t_{i_j}\right)\to u^{\prime }$， $\Vert x\left(t_{i_j}\right)-\bar{x}\left(t_{i_j}\right)\Vert \to 0$， $\Vert u\left(t_{i_j}\right)-\bar{u}\left(t_{i_j}\right)\Vert \to 0$， $\Vert \stackrel{\dot{}}{x}\left(t_{i_j}\right)\Vert \to 0$ 和 $\Vert \stackrel{\dot{}}{u}\left(t_{i_j}\right)\Vert \to 0$。

在(3.1)中取 $t_{i_j}$，令 $j\to \infty$ 取极限得

$\begin{array}{l}{x}^{\prime }={\Pi }_Q\left(x^{\prime }-\alpha \left(\nabla f\left(x^{\prime }\right)+\nabla g\left(x^{\prime }\right)u^{\prime }\right)\right),\\ u^{\prime }={\Pi }_{+}\left(u^{\prime }+\alpha g\left(x^{\prime }\right)\right),\end{array}$

根据命题2.2，上式表明 $x^{\prime }\in {\Omega }^{*}$ 是具有不等式约束的凸优化问题(1.1)的解。证毕。

□

5. 算例

本节给出下面的算例说明微分方程方法的有效性。

例：求解优化问题

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}g\left(x\right)\le 0\\ x\in R_{+}^5\end{array}$ (4.1)

其中 $f\left(x\right)=2-x_1{x}_2{x}_3{x}_4{x}_5/120$， $g\left(x\right)={\left(x_1-1,x_2-2,x_3-3,x_4-4,x_5-5\right)}^{\text{T}}$。本例在Hock和Schittkowski [4] 中研究过，其最优解为 $x^{*}={\left(1,2,3,4,5\right)}^{\text{T}}$。

应用微分方程方法(3.1)，取 $\alpha =1.5$，得到从四个随机初始点的微分方程系统的路径的轨迹图如下：

Figure 1. Transient behavior of $x\left(t\right)$ and $u\left(t\right)$ of the differential equation system of problem (4.1)

图1. 问题(4.1)的微分方程系统的轨迹 $x\left(t\right)$ 和 $u\left(t\right)$ 的收敛情况

上图1说明微分方程系统(3.1)的轨迹 $x\left(t\right)$ 收敛于优化问题的解 $x^{*}={\left(1,2,3,4,5\right)}^{\text{T}}$。

6. 结论

本文给出了具有不等式约束条件的优化问题的微分方程方法，并给出算例说明该方法的可行性。

基金项目

国家自然科学基金青年基金(编号：11801381)；沈阳航空航天大学2019年大学生创新创业训练计划项目(编号：201910143237)。