二阶微分方程方法求解带不等式约束的优化问题

Second-Order Differential Equation Method for Solving Optimization Problems with Inequality Constraints

摘要: 针对只含有不等式约束的优化问题，本文首先给出了其Karush-Kuhn-Tucker (KKT)条件，并利用光滑互补函数将KKT系统转化为一类光滑的方程组问题；其次，将光滑方程组问题转化为无约束优化问题；最后，本文提出一类二阶微分方程系统求解无约束优化问题，并讨论了二阶微分方程系统的解的稳定性及收敛速度。

Abstract: For optimization problems with only inequality constraints, this paper first presents their Karush-Kuhn-Tucker (KKT) conditions, and uses smooth complementarity functions to transform the KKT system into a class of smooth system of equations problems. Secondly, this article transforms the problem of smooth equation systems into an unconstrained optimization problem. Finally, this article proposes a class of second-order differential equation systems for solving unconstrained optimization problems, and discusses the stability and convergence speed of the solutions of second-order differential equation systems.

1. 引言

在现实世界中，大多数实际问题都是包含约束条件的。例如：在建筑结构设计中，设计师需要在满足建筑安全标准、材料强度限制、建筑空间需求等多种约束条件下，优化结构的设计方案，以实现成本最低或结构性能最优[1] [2]；企业在制定生产计划时，需要考虑设备产能、原材料供应、人力成本、生产周期等约束条件，以实现生产效益的最大化；物流配送过程中，需要考虑车辆的载重限制、行驶路线的交通状况、配送时间要求等约束条件，以优化物流配送方案，降低运输成本等等[3] [4]。因此，约束优化问题在很多领域都有着广泛的应用，近年来备受学者们的关注[5]-[7]。

本文考虑带不等式约束的优化问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}.x\in R^n\\ g\left(x\right)\le 0\end{array}$ (1)

其中$f:R^n\to R$ 和$g:R^n\to R^m$ 都是连续可微的，$R^n$ 表示为n维实向量空间。

本文将应用一类二阶微分方程方法求解约束优化问题。早期工作Arrow与Hurwicz [8]，应用微分方程研究了优化问题的最优性条件。Antipin [9]应用一阶微分方程方法研究了一类双约束变分不等式问题，并证明了算法的全局收敛性。Attouch [10] [11]应用二阶微分方程方法求解了凸优化问题。Evtushenko与Zhadan [12]-[14]对额二阶微分方程方法进行了系统的讨论和研究。微分方程方法的主要思想是，将原问题转化为无约束最小值问题，然后针对最小值问题构造相应的一阶或者二阶微分方程系统，讨论微分方程系统的解的稳定性。本文给出了一类带不等式约束的优化问题，应用一类光滑互补函数将带不等式约束的优化问题的KKT系统转化为最小值问题，从而构造出相应的二阶微分方程系统，为约束优化问题的方法研究提供思路。

2. 问题的转化

带不等式约束的优化问题(1)的Karush-Kuhn-Tucker (KKT)条件为：

$\begin{array}{c}L\left(x,\lambda \right)=\nabla f\left(x\right)+\nabla g\left(x\right)\lambda =0\\ -g\left(x\right)\perp \lambda \end{array}$ (2)

其中，$L\left(x,\lambda \right)$ 是约束优化问题的Lagrange函数，$\nabla f\left(x\right)$ 和$\nabla g\left(x\right)$ 分别是函数f和g的梯度，$\lambda \in R^m$ 是拉格朗日乘子。

为了将KKT条件(2)转化为光滑方程组问题，本文借助文献[15]中的光滑互补函数

${\varphi }_{NR}^{\epsilon }\left(a,b\right)=a-\phi \left(\epsilon ,a-b\right)$

其中

$\phi \left(\epsilon ,a-b\right)=\frac{1}{2}\left[a-b+\sqrt{{\epsilon }^2+{\left(a-b\right)}^2}\right]$

且$\epsilon \in R_{+}$ ，$a,b\in R_{+}$ ，$\varphi :R\times R\to R$ 满足$\varphi \left(a,b\right)=0$ 当且仅当$ab=0$ 。

由此，带不等式约束的优化问题(1)的KKT条件(2)可以转化下面光滑方程组问题

$H\left(\epsilon ,x,\lambda \right)=\left(\begin{array}{c}\epsilon \\ L\left(x,\lambda \right)\\ {\varphi }_{NR}^{\epsilon }\left(-g_1\left(x\right),{\lambda }_1\right)\\ ⋮\\ {\varphi }_{NR}^{\epsilon }\left(-g_m\left(x\right),{\lambda }_m\right)\end{array}\right)=0$ (3)

其中，$g_i\left(x\right),{\lambda }_i\in R_{+}$ 分别是$g\left(x\right),\lambda$ 的分量。

令

$\begin{array}{c}\theta \left(\epsilon ,x,\lambda \right)=\frac{1}{2}{H}^{\text{T}}\left(\epsilon ,x,\lambda \right)H\left(\epsilon ,x,\lambda \right)\\ =\frac{1}{2}{\Vert H\left(\epsilon ,x,\lambda \right)\Vert }^2\end{array}$

则光滑方程组(3)与下面无约束优化问题(4)同解。

$\min \theta \left(z\right)=\min \frac{1}{2}{\Vert H\left(z\right)\Vert }^2$ (4)

其中$z=\left(\epsilon ,x,\lambda \right)$ 。

3. 二阶微分方程系统

本文应用具有阻尼惯性系数$\gamma \left(t\right)$ 和时间缩放参数$\beta \left(t\right)$ 的二阶微分方程系统(DIN-AVD) [11]

$\ddot{z}\left(t\right)+\frac{\alpha }{t}\dot{z}\left(t\right)+\beta {\nabla }^2\theta \left(z\left(t\right)\right)\dot{z}\left(t\right)+\nabla \theta \left(z\left(t\right)\right)=0$ (5)

来求解无约束优化问题(4)，其中$\gamma \left(t\right)$ 和$\beta \left(t\right)$ 是$\left[t_0,+\infty \right)$ 上非负连续函数。

从而，建立与无约束优化问题所对应的二阶微分方程系统

$\left(\begin{array}{c}\ddot{\epsilon }\left(t\right)\\ \ddot{x}\left(t\right)\\ \ddot{\lambda }\left(t\right)\end{array}\right)+\frac{\alpha }{t}\left(\begin{array}{c}\dot{\epsilon }\left(t\right)\\ \dot{x}\left(t\right)\\ \dot{\lambda }\left(t\right)\end{array}\right)+\beta {\nabla }^2\theta \left(\begin{array}{c}\epsilon \left(t\right)\\ x\left(t\right)\\ \lambda \left(t\right)\end{array}\right)\left(\begin{array}{c}\dot{\epsilon }\left(t\right)\\ \dot{x}\left(t\right)\\ \dot{\lambda }\left(t\right)\end{array}\right)+\left(\begin{array}{c}{\nabla }_{\epsilon }{H}^{\text{T}}\left(z\right)H\left(z\right)\\ {\nabla }_x{H}^{\text{T}}\left(z\right)H\left(z\right)\\ {\nabla }_{\lambda }{H}^{\text{T}}\left(z\right)H\left(z\right)\end{array}\right)=0$ (6)

下面，分析二阶微分方程系统(6)沿轨迹值的收敛速度。假设$\alpha \ge 3$ 且$z^{{}_{*}}\in \arg \min \theta$ 。设z是(6)的解，则$z\left(t\right)\to z^{*}\left(t\to \infty \right)$ 。对于$\eta \in \left[2,\alpha -1\right]$ 我们定义函数${{\rm E}}_{\eta }\left(t\right):\left[t_0,+\infty \right)\to R$ 即

$\begin{array}{l}{{\rm E}}_{\eta }\left(t\right)=t\left(t-\beta \left(\eta +2-\alpha \right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)+\frac{1}{2}{\Vert \eta \left(z\left(t\right)-z^{*}\right)+t{\dot{u}}_{\beta }\left(t\right)\Vert }^2\\ +\eta \left(\alpha -\eta -1\right)\frac{1}{2}{\Vert z\left(t\right)-z^{*}\Vert }^2\end{array}$ (7)

其中，${\dot{u}}_{\beta }\left(t\right)=\dot{z}\left(t\right)+\beta \nabla \theta \left(z\left(t\right)\right)$。下面，讨论$\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)$ 的表达式。

$\begin{array}{l}\frac{\text{d}}{\text{d}t}\left[t\left(t-\beta \left(\eta +2-\alpha \right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)\right]=\left(2t-\beta \left(\eta +2-\alpha \right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)\\ +t\left(t-\beta \left(\eta +2-\alpha \right)\right)\langle \dot{z}\left(t\right),\nabla \theta \left(z\left(t\right)\right)\rangle \end{array}$

$\begin{array}{c}\frac{\text{d}}{\text{d}t}\frac{1}{2}{\Vert \eta \left(z\left(t\right)-z^{*}\right)+t{\dot{u}}_{\beta }\left(t\right)\Vert }^2=\langle \eta \left(z\left(t\right)-z^{*}\right)+t{\dot{u}}_{\beta }\left(t\right),\eta \dot{z}\left(t\right)+{\dot{u}}_{\beta }\left(t\right)+t{\ddot{u}}_{\beta }\left(t\right)\rangle \\ =\langle \eta \left(z\left(t\right)-z^{*}\right)+t{\dot{u}}_{\beta }\left(t\right),\left(\eta +1-\alpha \right)\dot{z}\left(t\right)-\left(t-\beta \right)\nabla \theta \left(z\left(t\right)\right)\rangle \\ =\eta \left(\eta +1-\alpha \right)\langle z\left(t\right)-z^{*},\dot{z}\left(t\right)\rangle -t\left(\alpha -\eta -1\right){\Vert \dot{z}\left(t\right)\Vert }^2\\ -\beta t\left(t-\beta \right){\Vert \nabla \theta \left(z\left(t\right)\right)\Vert }^2-\eta \left(t-\beta \right)\langle z\left(t\right)-z^{*},\nabla \theta \left(z\left(t\right)\right)\rangle \\ -t\left(t-\beta \left(\eta +2-\alpha \right)\right)\langle \dot{z}\left(t\right),\nabla \theta \left(z\left(t\right)\right)\rangle \end{array}$

$\frac{\text{d}}{\text{d}t}\eta \left(\alpha -\eta -1\right)\frac{1}{2}{\Vert z\left(t\right)-z^{*}\Vert }^2=\eta \left(\alpha -\eta -1\right)\langle z\left(t\right)-z^{*},\dot{z}\left(t\right)\rangle$

因此，

$\begin{array}{l}\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)=\left(2t-\beta \left(\eta +2-\alpha \right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)-\eta \left(t-\beta \right)\langle z\left(t\right)-z^{*},\nabla \theta \left(z\left(t\right)\right)\rangle \\ -t\left(\alpha -\eta -1\right){\Vert \dot{z}\left(t\right)\Vert }^2-\beta t\left(t-\beta \right){\Vert \nabla \theta \left(z\left(t\right)\right)\Vert }^2\end{array}$

由于$\langle z\left(t\right)-z^{*},\nabla \Psi \left(z\left(t\right)\right)\rangle \ge \Psi \left(z\left(t\right)\right)-\Psi \left(z^{*}\right)$ ，当$t\ge \max \left\{t_0,\beta \right\}$ ，我们得到

$\begin{array}{l}\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)\le -\left(\left(\eta -2\right)t-\beta \left(\alpha -2\right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)-t\left(\alpha -\eta -1\right){\Vert \dot{z}\left(t\right)\Vert }^2\\ -\beta t\left(t-\beta \right){\Vert \nabla \theta \left(z\left(t\right)\right)\Vert }^2\end{array}$ (8)

由定义可知函数${{\rm E}}_{\eta }$ 是非负的。对于不等式(8)：如果$\eta >2$ ，当$t\ge t_1=\max \left\{t_0,\beta ,\frac{\beta \left(\alpha -2\right)}{\eta -2}\right\}$ 时，有$\left(\eta -2\right)t-\beta \left(\alpha -2\right)\ge 0$ 。由$\alpha -\eta -1\ge 0$ 得$\eta \le \alpha -1$ 。因此有$2<\eta \le \alpha -1$ 即$\alpha >3$ 。其极限情况$\eta =2$ (结果为$\alpha =3$ )定理3.1也包含。当$t\ge \beta$ 时有$\beta t\left(t-\beta \right)\ge 0$ 。综上可得，若$\eta \in \left(2,\alpha -1\right]$ ，可推导出${{\rm E}}_{\eta }$ 在$\left[t_1,+\infty \right)$ 上是非递增的且$\underset{t\to +\infty }{\lim }{{\rm E}}_{\eta }\left(t\right)$ 存在。

定理3.1 令$\alpha \ge 3$ 且$\arg \min \theta \ne \phi$ ，设$z:\left[t_0,+\infty \right)\to R$ 是(6)的解，若$\eta \in \left[2,\alpha -1\right]$ ，则函数

$t\mapsto {\left(\frac{t}{t-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(t\right)$

是非递增的且$\underset{t\to +\infty }{\lim }{{\rm E}}_{\eta }\left(t\right)$ 存在。

证明：设$t>\max \left\{t_0,\beta \right\}$ ，由(8)可得

$\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)\le \beta \left(\alpha -2\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)$ (9)

在式(9)两边同时乘以$t\left(t-\beta \right)$ ，由$\lambda +2-\alpha \le 1$ ，得

$\begin{array}{c}t\left(t-\beta \right)\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)\le \beta \left(\alpha -2\right)t\left(t-\beta \right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)\\ \le \beta \left(\alpha -2\right)t\left(t-\beta \left(\eta +2-\alpha \right)\right)\left(\theta \left(z\left(t\right)\right)-\min \theta \right)\\ \le \beta \left(\alpha -2\right){{\rm E}}_{\eta }\left(t\right)\end{array}$ (10)

将(10)两边同时乘以$t^{\alpha -3}{\left(t-\beta \right)}^{1-\alpha }$ ，得

${\left(\frac{t}{t-\beta }\right)}^{\alpha -2}\frac{\text{d}}{\text{d}t}{{\rm E}}_{\eta }\left(t\right)\le \beta \left(\alpha -2\right)\frac{t^{\alpha -3}}{{\left(t-\beta \right)}^{\alpha -1}}{{\rm E}}_{\eta }\left(t\right)$

进一步得

$\frac{\text{d}}{\text{d}t}\left[{\left(\frac{t}{t-\beta }\right)}^{\alpha -2}{{\rm E}}_{\lambda }\left(t\right)\right]\le 0$

因此，${\left(\frac{t}{t-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(t\right)$ 是非递增的。由${{\rm E}}_{\eta }$ 的非负性，当$t\to +\infty$ 时，其极限存在。

定理3.2 令$\alpha >3$ 且$\arg \min \theta \ne \varphi$ ，设$z:\left[t_0,+\infty \right)\to R$ 是(6)的解，则z有界。同时，设$\eta \in \left[2,\alpha -1\right]$ ，$t_1=\max \left\{t_0,\beta \right\}$ ，对于所有的$t\ge s>t_1$ ，我们有

$\theta \left(z\left(t\right)\right)-\min \theta \le \frac{1}{t^2}{\left(\frac{s}{s-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(s\right)={\rm O}\left(t^{-2}\right)$

证明：取$\eta \in \left[2,\alpha -1\right]$ ，由${{\rm E}}_{\eta }$ 的定义，有

$\frac{1}{2}{\Vert \lambda \left(z\left(t\right)-z^{*}\right)+t\left(\dot{z}\left(t\right)+\beta \nabla \theta \left(z\left(t\right)\right)\right)\Vert }^2\le {{\rm E}}_{\eta }\left(t\right)$ (11)

根据定理3.1，有$\underset{t\to +\infty }{\lim }{{\rm E}}_{\eta }\left(t\right)$ 存在，令M为${{\rm E}}_{\eta }$ 的上界。将(11)左侧的平方项展开，有

$\begin{array}{l}{\lambda }^2\frac{1}{2}{\Vert z\left(t\right)-z^{*}\Vert }^2+\lambda t\langle z\left(t\right)-z^{*},\dot{z}\left(t\right)\rangle \\ +\lambda t\langle z\left(t\right)-z^{*},\beta \nabla \Psi \left(z\left(t\right)\right)\rangle +t^2\frac{1}{2}{\Vert \dot{z}\left(t\right)+\beta \nabla \Psi \left(z\left(t\right)\right)\Vert }^2\le M\end{array}$ (12)

由此可以推导出

$\eta \frac{1}{2}{\Vert z\left(t\right)-z^{*}\Vert }^2+t\langle z\left(t\right)-z^{*},\dot{z}\left(t\right)\rangle \le \frac{M}{\eta }$ (13)

令$h\left(t\right)=\frac{1}{2}{\Vert z\left(t\right)-z^{*}\Vert }^2$ ，式(13)两边同时乘$t^{\lambda -1}$ ，可以得到

$\eta t^{\eta -1}h\left(t\right)+t^{\eta }\dot{h}\left(t\right)=\frac{\text{d}}{\text{d}t}\left(t^{\eta }h\left(t\right)\right)\le \frac{M}{\eta }{t}^{\eta -1}$ (14)

将(14)两边从$t_1$ 到$t>t_1$ 进行求定积分，得到

$t^{\eta }h\left(t\right)-t_1^{\eta }h\left(t_1\right)\le \frac{M}{{\eta }^2}\left(t^{\eta }-t_1^{\eta }\right)$

因此

$h\left(t\right)\le h\left(t_1\right)+\frac{M}{{\eta }^2}$

因此h是有界的。有${{\rm E}}_{\eta }$ 的定义，有

$\theta \left(z\left(t\right)\right)-\min \theta \le \frac{{{\rm E}}_{\eta }\left(t\right)}{t\left(t-\beta \left(\eta +2-\alpha \right)\right)}\le \frac{{{\rm E}}_{\eta }\left(t\right)}{t\left(t-\beta \right)}$

由定理3.1，函数${\left(\frac{t}{t-\beta }\right)}^{\alpha -2}{{\rm E}}_{\lambda }\left(t\right)$ 是非递增的。因此，当$t\ge s>t_1$ 时，可以推出

$\begin{array}{c}\theta \left(z\left(t\right)\right)-\min \theta \le \frac{1}{t\left(t-\beta \right)}{\left(\frac{t-\beta }{t}\right)}^{\alpha -2}{\left(\frac{s}{s-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(s\right)\\ \le \frac{1}{t^2}{\left(\frac{t-\beta }{t}\right)}^{\alpha -3}{\left(\frac{s}{s-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(s\right)\\ \le \frac{1}{t^2}{\left(\frac{s}{s-\beta }\right)}^{\alpha -2}{{\rm E}}_{\eta }\left(s\right)\end{array}$

由此定理3.2得证。

4. 结论

本文应用一类光滑互补函数(NR函数)，将带不等式约束的优化问题的KKT条件转化为一个无约束优化问题。基于无约束优化问题，本文构造了一个二阶微分方程系统，说明了二阶微分方程系统的解收敛到无约束最优化问题，并通过讨论二阶微分方程系统的解稳定性理论，说明了其解的收敛速度。本文基于约束优化问题的理论研究，为约束优化问题的求解方法提供思路。