特征函数$1_{\left(0,+\infty \right)}\left(z\right)$的一个光滑D.C.近似

A Smooth D.C. Approximation of the Characteristic Function $1_{\left(0,+\infty \right)}\left(z\right)$

摘要: 特征函数1(0,+∞)(z)已经广泛地使用在实践中，许多重要的实际问题，如概率约束优化问题，可以表示为与特征函数相关的问题，该问题通常是非凸和非光滑的，因而在数值计算上有困难。本文构造了特征函数1(0,+∞)(z)的一个光滑D.C.近似函数。讨论了函数φ(z,t)的一些性质。在一定条件下，当所涉及的参数足够小时，所提出的光滑近似函数收敛到1(0,+∞)(z)。基于该函数，构建了概率约束优化问题的一个等价的近似问题。

Abstract: Characteristic function1(0,+∞)(z)have been widely used in practice, and many important practical problems, such as probabilistic constrained optimization problems, can be expressed as the problems associated with the characteristic function, which are usually non-convex and non-smooth, and thus difficult to calculate numerically. In this paper, we construct a smooth D.C. approximation functionφ(z,t)of the characteristic function. Some properties of the functionφ(z,t)are discussed. Under certain conditions, the proposed smooth approximation function converges to1(0,+∞)(z)when the involved parameters are sufficiently small. Based on this function, an equivalent approximation of the constrained optimization problem is constructed.

1. 引言

众所周知，许多重要的实际问题，如通信网络、产品设计、统计与财务等数学模型可以表示为如下概率约束优化问题。

$\underset{x\in X}{\min }f\left(x\right)$

$\text{s}.\text{t}.\text{Pr}\left\{c\left(x,\xi \right)\le 0\right\}\ge 1-\alpha$ ，(SCCP)

其中x是d维的决策随机向量，$\xi$ 是支撑$\Xi \subset {\Re }^k$ 上的k维随机向量，并且$X\subset {\Re }^d$ ，$f:{\Re }^d\to R$ ，$c:{\Re }^d\times \Xi \to R$ ，$\alpha \in \left(0,1\right)$ 。$\Omega$ 表示问题(SCCP)的可行集。在问题(SCCP)中，要求约束被满足的概率至少为$1-\alpha$ 。

为了简便记法，将问题(SCCP)改写成如下形式：

$\underset{x\in X}{\min }f\left(x\right)$

$\text{s}.\text{t}.E\left[1_{\left(0,+\infty \right)}\left(c\left(x,\xi \right)\right)\right]\le \alpha$ (P)

其中，$1_{\left(0,+\infty \right)}\left(z\right)=\{\begin{array}{l}1,z\in \left(0,+\infty \right)\\ 0,z\notin \left(0,+\infty \right)\end{array}$ 。

由于问题(P)通常是非凸和非光滑的[1]，解决这类问题一般比较困难，一种有效的方法就是寻找特征函数的近似函数[2]，具有代表性的近似函数有：二次近似[3]，D.C.近似[4]，和光滑近似[5]等。本文构造了一个特征函数的光滑D.C.近似函数，并建立了问题 (P)的等价近似问题。

2. 光滑函数$\phi \left(z,t\right)$

当$t>0$ 时，考虑函数：

${\phi }_1\left(z,t\right)=\ln \left(1+{\text{e}}^{\frac{1}{t}z}\right)$ 和${\phi }_2\left(z,t\right)=\ln \left(1+{\text{e}}^{\frac{1}{t}z-1}\right)$ ，

定义函数：

$\phi \left(z,t\right)={\phi }_1\left(z,t\right)-{\phi }_2\left(z,t\right)=\ln \left(1+{\text{e}}^{\frac{1}{t}z}\right)-\ln \left(1+{\text{e}}^{\frac{1}{t}z-1}\right).$

从图1和图2可以看出，当t足够小时，$\phi \left(z,t\right)$ 是特征函数$1_{\left(0,+\infty \right)}\left(z\right)$ 的一个光滑近似。

Figure 1. Characteristic function $1_{\left(0,+\infty \right)}\left(z\right)$

图1. 特征函数$1_{\left(0,+\infty \right)}\left(z\right)$

Figure 2. Function $\phi \left(z,t\right)$ (t = 0.1, t = 0.01, t = 0.001)

图2. 函数$\phi \left(z,t\right)$ (t = 0.1, t = 0.01, t = 0.001)

下述命题刻画了函数$\phi \left(z,t\right)$ 的性质。

命题1 对于$t>0$ 函数$\phi \left(z,t\right)$ 具有以下性质：

$\phi \left(z,t\right)$ 是关于z的D.C.函数。

$\phi \left(z,t\right)$ 在定义域内单调递增。

当$z>0$ 时，$\phi \left(z,t\right)$ 在t中是单调递减的，当$z<0$ 时，$\phi \left(z,t\right)$ 在t中是单调递增的。

$\phi \left(z,t\right)$ 是关于z的无穷阶连续可微的。

证明 (1) 很容易证明${\phi }_1\left(z,t\right)$ 和${\phi }_2\left(z,t\right)$ 是x中的凸函数。

函数${\phi }_1\left(z,t\right)$ 关于z的一阶导为：

$\frac{\partial }{\partial z}{\phi }_1\left(z,t\right)=\frac{{\text{e}}^{\frac{z}{t}}}{t\left(1+{\text{e}}^{\frac{z}{t}}\right)}$

${\phi }_1\left(z,t\right)$ 关于z的二阶导为：

$\frac{{\partial }^2}{\partial z^2}{\phi }_1\left(z,t\right)=\frac{\partial }{\partial z}\left(\frac{{\text{e}}^{\frac{z}{t}}}{t\left(1+{\text{e}}^{\frac{z}{t}}\right)}\right)=\frac{{\text{e}}^{\frac{z}{t}}}{t^2{\left(1+{\text{e}}^{\frac{z}{t}}\right)}^2}\ge 0$

当$t>0$ ，分子${\text{e}}^{\frac{z}{t}}$ 是正的且分母$t^2{\left(1+{\text{e}}^{\frac{z}{t}}\right)}^2$ 也为正，因此$\frac{{\partial }^2}{\partial z^2}{\phi }_1\left(z,t\right)$ 总是非负的，${\phi }_1\left(z,t\right)$ 是z中的凸函数。类似的${\phi }_2\left(z,t\right)$ 也是z中的凸函数。显然$\phi \left(z,t\right)$ 是关于z的D.C.函数。

(2) 函数$\phi \left(z,t\right)$ 关于z的微分函数。

$\frac{\partial }{\partial z}\phi \left(z,t\right)=\frac{{\text{e}}^{\frac{z}{t}}}{t\left(1+{\text{e}}^{\frac{z}{t}}\right)}-\frac{{\text{e}}^{\frac{z}{t}-1}}{t\left(1+{\text{e}}^{\frac{z}{t}-1}\right)}=\frac{{\text{e}}^{\frac{z}{t}}-{\text{e}}^{\frac{z}{t}-1}}{t\left(1+{\text{e}}^{\frac{z}{t}}\right)\left(1+{\text{e}}^{\frac{z}{t}-1}\right)}\ge 0$

由于${\text{e}}^{\frac{z}{t}}$ 是递增的，所以${\text{e}}^{\frac{z}{t}}-{\text{e}}^{\frac{z}{t}-1}>0$ ，同时分母$t\left(1+{\text{e}}^{\frac{z}{t}}\right)\left(1+{\text{e}}^{\frac{z}{t}-1}\right)$ 也大于0，$\frac{\partial }{\partial z}\phi \left(z,t\right)$ 大于0，$\phi \left(z,t\right)$ 在定义域内单调递增。

(3) 关于t的微分函数$\phi \left(z,t\right)$ ，有

$\frac{\partial }{\partial t}\phi \left(z,t\right)=\frac{z\left({\text{e}}^{\frac{z}{t}-1}-{\text{e}}^{\frac{z}{t}}\right)}{t^2\left(1+{\text{e}}^{\frac{z}{t}}\right)\left(1+{\text{e}}^{\frac{z}{t}-1}\right)}$

由于${\text{e}}^{\frac{z}{t}}$ 单调递减，${\text{e}}^{\frac{z}{t}-1}-{\text{e}}^{\frac{z}{t}}$ 总是小于0，分母$t^2\left(1+{\text{e}}^{\frac{z}{t}}\right)\left(1+{\text{e}}^{\frac{z}{t}-1}\right)$ 恒大于0。当$z>0$ 时，$\frac{\partial }{\partial t}\phi \left(z,t\right)<0$ ，$\phi \left(z,t\right)$ 在t中是单调递减的，当$z<0$ 时，$\frac{\partial }{\partial t}\phi \left(z,t\right)>0$ ，$\phi \left(z,t\right)$ 在t中是单调递增的。

(4) 我们知道${\text{e}}^{\frac{1}{t}z}$ 是关于z的无穷阶连续可微的，因此$\ln \left(z\right)$ 也是关于z的无穷阶连续可微的，故${\phi }_1\left(z,t\right)$ 是关于z的无穷阶连续可微的。类似的，${\phi }_2\left(z,t\right)$ 也是关于z的无穷阶连续可微函数。$\phi \left(z,t\right)$ 是关于z的无穷阶连续可微的。

定理1 对于$t>0$ 时，对任意$z\in R$ ，$\phi \left(z,t\right)\in \left(0,\text{1}\right)$ ，且当对任意$z\in R\backslash \left\{0\right\}$ ，$\underset{t\to 0}{\lim }\phi \left(z,t\right)=1_{\left(0,+\infty \right)}\left(z\right)$ 。

证明 对$\forall z\in R$ ，

$\phi \left(z,t\right)=\ln \left(1+{\text{e}}^{\frac{1}{t}z}\right)-\ln \left(1+{\text{e}}^{\frac{1}{t}z-1}\right)=\ln \left(\frac{1+{\text{e}}^{\frac{1}{t}z}}{1+{\text{e}}^{\frac{1}{t}z-1}}\right)$

由命题1(2)可知，$\phi \left(z,t\right)$ 在定义域内单调递增。

当$z\to +\infty$ 时，

$\underset{z\to +\infty }{\lim }\phi \left(z,t\right)=\underset{z\to +\infty }{\lim }\ln \left(\frac{1+{\text{e}}^{\frac{1}{t}z}}{1+{\text{e}}^{\frac{1}{t}z-1}}\right)=\underset{z\to +\infty }{\lim }\ln \left(\frac{\frac{1}{t}{\text{e}}^{\frac{1}{t}z}}{\frac{1}{t}{\text{e}}^{\frac{1}{t}z-1}}\right)=\underset{z\to +\infty }{\lim }\ln \left(\text{e}\right)=1$

故$\max \phi \left(z,t\right)<1$ 。

当$z\to -\infty$ 时，

$\underset{z\to +\infty }{\lim }\phi \left(z,t\right)=\underset{z\to -\infty }{\lim }\ln \left(\frac{1+{\text{e}}^{\frac{1}{t}z}}{1+{\text{e}}^{\frac{1}{t}z-1}}\right)=0$

故$\min \phi \left(z,t\right)>0$ 。

因此，对任意$z\in R$ ，$\phi \left(z,t\right)\in \left(0,\text{1}\right)$ 。

对$\forall z\in R\backslash \left\{0\right\}$ ，当$z>0$ 时，

$\underset{t\to 0}{\lim }\ln \left(\frac{1+{\text{e}}^{\frac{1}{t}z}}{1+{\text{e}}^{\frac{1}{t}z-1}}\right)=\underset{t\to 0}{\lim }\text{ln}\left(\frac{\frac{1}{t}{\text{e}}^{\frac{1}{t}z}}{\frac{1}{t}{\text{e}}^{\frac{1}{t}z-1}}\right)=\underset{t\to 0}{\lim }\text{ln}\left(\text{e}\right)=1$

当$z<0$ 时，

$\underset{t\to 0}{\lim }\ln \left(\frac{1+{\text{e}}^{\frac{1}{t}z}}{1+{\text{e}}^{\frac{1}{t}z-1}}\right)=0$

因此，$\underset{t\to 0}{\lim }\phi \left(z,t\right)=1_{\left(0,+\infty \right)}\left(z\right)$ ，$\forall z\in R\backslash \left\{0\right\}$ 。

3. 问题(P)的光滑近

令

${\Psi }_1\left(x,t\right)=E\left[{\phi }_1\left(c\left(x,\xi \right),t\right)\right]$ ，${\Psi }_2\left(x,t\right)=E\left[{\phi }_2\left(c\left(x,\xi \right),t\right)\right]$

$\phi \left(x,t\right)={\Psi }_1\left(x,t\right)-{\Psi }_2\left(x,t\right)$

$\widehat{p}\left(x\right)=\underset{t\to 0}{\lim }E\left[\phi \left(c\left(x,\xi \right),t\right)\right]$

考虑如下问题

$\underset{x\in X}{\min }f\left(x\right)$

$\text{s}.\text{t}.\widehat{p}\left(x\right)\le \alpha$ ($\widehat{\text{P}}$)

为了证明问题($\widehat{\text{P}}$)和问题(P)的等价性，给出如下假设。

假设1 集合$X\subset {ℝ}^d$ 是凸紧集，$\xi$ 的支撑集$\Xi$ 包含于${ℝ}^d$ 且是闭集，$\forall \xi \in \Xi$ ，$f\left(x\right)$ ，$c\left(x,\xi \right)$ ，关于$\forall x\in O$ 都是连续可微且是凸的，其中O是一个有界开集，且$X\subset O$ 。

假设2 函数$c\left(x,\xi \right)$ 是Carathoédory函数，即：对于每一个$X\subset {ℝ}^d$ ，$c\left(x,\cdot \right)$ 都是可测的，且$c\left(x,\cdot \right)$ 对于几乎每一个$\xi \in \Xi$ 都是连续的。

假设3 $\forall \overline{x}\in X$ ，集合$\left\{\xi \in \Xi :c\left(x,\xi \right)=0\right\}$ 的概率测度为0，即$c\left(x,\xi \right)\ne 0$ 。

下述问题描述了问题($\widehat{\text{P}}$)和问题(P)的等价性。

定理2 假设1~假设3均成立，则对任意的t趋于0，问题($\widehat{\text{P}}$)和问题(P)是等价的。

证明 由假设1~假设3和定理1可知，

$z>0$ 时，$\underset{t\to 0}{\lim }\phi \left(z,t\right)=1$ ；当$z<0$ 时，$\underset{t\to 0}{\lim }\phi \left(z,t\right)=0$ 。

令$z=c\left(x,\xi \right)$ ，可得

$\begin{array}{c}\underset{t\to 0}{\lim }E\left[\phi \left(c\left(x,\xi \right),t\right)\right]=\underset{t\to 0}{\lim }{\displaystyle {\int }_{\Omega }\phi \left(c\left(x,\xi \right),t\right)\text{d}P\left(\xi \right)}\\ ={\displaystyle {\int }_{\Omega }\underset{t\to 0}{\text{lim}}\phi \left(c\left(x,\xi \right),t\right)\text{d}P\left(\xi \right)}\\ ={\displaystyle {\int }_{\Omega }{1}_{\left(0,+\infty \right)}c\left(x,\xi \right)\text{d}P\left(\xi \right)}\\ =E\left[1_{\left(0,+\infty \right)}c\left(x,\xi \right)\right]\end{array}$

即$\widehat{p}\left(x\right)=E\left[1_{\left(0,+\infty \right)}c\left(x,\xi \right)\right]$ 。

因此问题($\widehat{\text{P}}$)和问题(P)等价。

基金项目

辽宁师范大学本科生科研训练项目(项目编号：CX202302014)。