全局最优化问题在工程设计、生产管理、资源分配等领域的应用越来越广泛.近些年来, 许多全局最优化理论与方法相继出现, 并得到广泛应用.其中, 关于全局最优解的研究已经取得一定的进展^[1-3], 得到了多种求解方法.对于目标函数具有一定单调性的非线性规划问题, 文献[4-6]给出了一些凸化、凹化法, 将单调非线性规划变换成相应的凸规划或凹规划.对于目标函数或约束函数非单调、非凸凹的非线性规划问题, 文献[7-9]给出了一些变换方法, 通过对目标函数凸化或凹化, 将原问题转化为等价的凹极小问题、反凸规划问题或标准D.C.规划问题.

本文对于目标函数是次正定函数的全局最优化问题, 给出一种新的凸化法, 通过将目标函数凸化, 从而将原问题转化为相应的凸规划, 并论证了次正定函数全局最优解的一些最优性条件.本文提出的凸化方法对目标函数在定义域上的值大于零或小于零的情形都可进行凸化, 从而扩大了方法的应用范围.

考虑下述全局最优化问题:

$\min f(x),\\ \textrm{s.t}. x \in X,$

(2.1)

其中$f$:$R^{n}\to R$, $f(x)\in C^2$, 有界闭凸集$ X=\{x\in X \mid l_i\leq x_i\leq u_i, i=1, 2, \cdots, n\}$.用$ S^n $表示$ R^n $中的单位球面, $ S^n=\{d\in R^n\mid \parallel d \parallel=1\}$.

记$ g(x)$为函数$ f(x)$在$ x$处的梯度, $ G(x) $为函数$ f(x)$在$ x$处的Hesse矩阵, $ G(x)>0 $表示函数$ f(x)$在$ x$处的Hesse矩阵正定, $ G(x)<0 $表示函数$ f(x)$在$ x$处的Hesse矩阵负定.

定义 ^[5] 设函数$f:R^n\rightarrow R$, $f(x)\in C^2$, 若对$\forall x\in X$, $d\in S^n$,

$d^\mathrm{T}[G(x)+g(x)g(x)^\mathrm{T}]d>0$

(2.2)

成立, 则称$ f(x)$是$X$上的次正定函数.

例1 函数$ f(x)=\dfrac{1}{2}x_1^2-x_1x_2-\dfrac{1}{2}x_2^2$, 其中$ x\in X = \{0\leq x_1\leq3, 3\leq x_2\leq6\}$.

函数$ f(x)$在$ X $上的梯度: $ g(x)=(x_1-x_2, -x_1-x_2)^\mathrm{T}$, 函数$ f(x)$在$ X $上的Hesse矩阵$ G(x)= \left[\begin{array}{cc} 1&-1\\-1&-1\\ \end{array} \right]$, 因此得到

$H_f(x)=G(x)+g(x)g(x)^\mathrm{T}= \left[\begin{array}{cc} (x_1-x_2)^2+1&-(x_1^2-x_2^2)-1\\-(x_1^2-x_2^2)-1&(x_1+x_2)^2-1\\ \end{array} \right], $

则由$ H_f(x)$的特征多项式$ |\lambda E-H_f(x)|=0$得

$\lambda=(x_1^2+x_2^2)\pm\sqrt{(x_1^2+x_2^2)^2-(2x_2^2-2x_1^2+4x_1x_2-2)}, $

则$ \forall x\in X$, $\lambda>0$恒成立, 故$ \forall x \in X$, $d \in S^2$, $d^\mathrm{T} H_f(x)d>0$成立, $ H_f(x)$是$ X $上的正定矩阵, $ f(x)$是$ X $上的次正定函数.

由此可知, 当函数$ f(x)$在$ X$上是非凸非凹函数时, 若$ G(x)+g(x)g(x)^\mathrm{T}$是正定矩阵, 则$ f(x)$是$ X$上的次正定函数.显然, 正定函数必为次正定函数, 但反之不然.

定理3.1 设函数$f$:$R^{n}\to R$, $f(x)\in C^2$, 且$ f(x)$为$ X$上的次正定函数, $ \forall x\in X $, $ f(x)>0 $, 令

$F(x)=qe^{f(x)}+\frac{1}{2}f^2(x),$

(3.1)

则存在$ q_1\geq0$, 使得当$ q>q_1$时, $ F(x)$为$ X$上的凸函数.

证  对$ \forall x\in X $和$ q>0 $, 由(3.1) 式得

$\dfrac{\partial F(x)}{\partial x_i}=qe^{f(x)}\dfrac{\partial f(x)}{\partial x_i}+f(x)\dfrac{\partial f(x)}{\partial x_i},$

计算得

$\begin{array}{l} \frac{{{\partial ^2}F(x)}}{{\partial x_i^2}} = q{e^{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial x_i^2}} + q{e^{f(x)}}{(\frac{{\partial f(x)}}{{\partial {x_i}}})^2} + f(x)\frac{{{\partial ^2}f(x)}}{{\partial x_i^2}} + {(\frac{{\partial f(x)}}{{\partial {x_i}}})^2},\\ \frac{{{\partial ^2}F(x)}}{{\partial {x_i}{x_j}}} = q{e^{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial {x_i}{x_j}}} + q{e^{f(x)}}\frac{{\partial f(x)}}{{\partial {x_i}}}\frac{{\partial f(x)}}{{\partial {x_j}}} + f(x)\frac{{{\partial ^2}f(x)}}{{\partial {x_i}{x_j}}} + \frac{{\partial f(x)}}{{\partial {x_i}}}\frac{{\partial f(x)}}{{\partial {x_j}}}\\ (i,j = 1,2, \cdots ,n.\quad i \ne j). \end{array}$

用$ H_F(x) $表示函数$ F(x) $在点$ x $处的Hesse矩阵, 则$ \forall x\in X $,

$H_F(x)=qe^{f(x)}[G(x)+g(x)g(x)^\mathrm{T}]+f(x)G(x)+g(x)g(x)^\mathrm{T}.$

令

$Q(x)=e^{f(x)}[G(x)+g(x)g(x)^\mathrm{T}],\quad \lambda=\min\limits_{\substack{x \in X\\ 1\leq i \leq n}} \lambda_i (Q(x)),$

其中$\lambda_i (Q(x))$表示$ Q(x)$的特征值,

$R(x)=f(x)G(x)+g(x)g(x)^\mathrm{T},\quad \gamma=\min\limits_{\substack{x\in X\\1\leq i \leq n}}\gamma_i(R(x)),$

其中$\gamma_i(R(x))$表示$ R(x)$的特征值.因此$ d^\mathrm{T} Q(x) d\geq \lambda, d^\mathrm{T} R(x) d\geq \gamma$.故

$d^\mathrm{T} H_F(x) d=q d^\mathrm{T} Q(x) d+d^\mathrm{T} R(x) d\geq q \lambda+\gamma,$

又由$ G(x)+g(x)g(x)^\mathrm{T} $是正定矩阵且$ e^{f(x)}>0$可知$ \lambda > 0 $.于是, 若令

$q_1=\max\{0, \frac{-\gamma}{\lambda}\},$

当$ q>q_1$时, 对$\forall x\in X$, $d \in S^n$, $ d^\mathrm{T} H_F(x)d >0$成立, $ H_F(x)$为$ X$上的正定矩阵, $ F(x)$为$ X $上的凸函数.

定理3.2 设函数$f$:$R^{n}\to R$, $f(x)\in C^2$, 且$ f(x)$为$ X$上的次正定函数, $ \forall x\in X $, $ f(x)<0 $, 令

$D(x)=qe^{f(x)}-\ln(-f(x)),$

(3.2)

则存在$ q_2\geq0$, 使得当$ q>q_2$时, $ D(x)$为$ X $上的凸函数.

证 $\quad \forall x\in X $和$ q>0 $, 由(3.2) 式得

$\dfrac{\partial D(x)}{\partial x_i}=qe^{f(x)}\dfrac{\partial f(x)}{\partial x_i}-\dfrac{1}{f(x)}\dfrac{\partial f(x)}{\partial x_i},$

计算得

$\begin{array}{l} \frac{{{\partial ^2}D(x)}}{{\partial x_i^2}} = q{e^{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial x_i^2}} + q{e^{f(x)}}{(\frac{{\partial f(x)}}{{\partial {x_i}}})^2} - \frac{1}{{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial x_i^2}} + \frac{1}{{{f^2}(x)}}{(\frac{{\partial f(x)}}{{\partial {x_i}}})^2},\\ \frac{{{\partial ^2}D(x)}}{{\partial {x_i}{x_j}}} = q{e^{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial {x_i}{x_j}}} + q{e^{f(x)}}\frac{{\partial f(x)}}{{\partial {x_i}}}\frac{{\partial f(x)}}{{\partial {x_j}}} - \frac{1}{{f(x)}}\frac{{{\partial ^2}f(x)}}{{\partial {x_i}{x_j}}} + \frac{1}{{{f^2}(x)}}\frac{{\partial f(x)}}{{\partial {x_i}}}\frac{{\partial f(x)}}{{\partial {x_j}}}\\ (i,j = 1,2, \cdots ,n.\quad i \ne j). \end{array}$

用$ H_D(x) $表示函数$ D(x) $在点$ x $处的Hesse矩阵, 则$ \forall x\in X $,

$H_D(x)=qe^{f(x)}[G(x)+g(x)g(x)^\mathrm{T}]-\frac{1}{f(x)}G(x)+\frac{1}{f^2(x)}g(x)g(x)^\mathrm{T}.$

令

$Q_1(x)=e^{f(x)}[G(x)+g(x)g(x)^\mathrm{T}],\quad \lambda^\prime= \min\limits_{\substack{x\in X\\1\leq i\leq n}}\lambda_i (Q_1(x)),$

其中$\lambda_i (Q_1(x))$表示$ Q_1(x)$的特征值,

$R_1(x)=-\dfrac{1}{f(x)}G(x)+\dfrac{1}{f^2(x)}g(x)g(x)^\mathrm{T},\quad \gamma^\prime=\min\limits_{\substack{x\in X\\1\leq i \leq n}}\gamma_i(R_1(x)),$

其中$\gamma_i(R_1(x))$表示$ R_1(x)$的特征值.因此$d^\mathrm{T} Q_1(x) d\geq \lambda^\prime, d^\mathrm{T} R_1(x) d\geq \gamma^\prime $故

$d^\mathrm{T} H_D(x) d=q d^\mathrm{T} Q_1(x) d+d^\mathrm{T} R_1(x) d \geq q \lambda^\prime+\gamma^\prime,$

又由$ G(x)+g(x)g(x)^\mathrm{T} $是正定矩阵且$ e^{f(x)}>0$可知$ \lambda^\prime > 0 $.于是, 若令

$q_2=\max\{0, \frac{-\gamma^\prime}{\lambda^\prime}\},$

当$ q>q_2$时, 对$\forall x\in X$, $d \in S^n$, $d^\mathrm{T} H_D(x)d>0$成立, $ H_D(x)$为$ X $上的正定矩阵, $ D(x)$为$ X $上的凸函数.

本节给出一个实例说明可将全局优化问题中具有次正定性质的目标函数转化为相应的凸函数.

例2 考虑如下全局最优化问题:

$\min f(x)=\frac{1}{2}x_1^2-x_1x_2-\frac{1}{2}x_2^2,\\ \textrm{s.t.} \quad x\in X = \{0\leq x_1\leq3, 3\leq x_2\leq6\}. $

图 1给出了函数$ f(x)$在$X$上的图像, 由图 1可知$ f(x)$是$ X$上的非凸非凹函数.

由例1知$ f(x)$是$ X$上的次正定函数, 又$ \forall x \in X$, $f(x)<0$, 根据定理3.2可知

$Q_1(x)=e^{f(x)}[G(x)+g(x)g(x)^\mathrm{T}],$

计算得$ \lambda^\prime= \min\limits_{\substack{x\in X\\1\leq i\leq 2}}\lambda_i (Q_1(x))=2.92e-014$,

$R_1(x)=-\frac{1}{f(x)}G(x)+\frac{1}{f^2(x)}g(x)g(x)^\mathrm{T},$

计算得$ \gamma^\prime=\min\limits_{\substack{x\in X\\1\leq i \leq 2}}\gamma_i(R_1(x))=0.033$.故$ q_2 =\max\{0, \dfrac{-\gamma^\prime}{\lambda^\prime}\}=0$, 又$ q>q_2$, 取$ q=1$.此时,

$D(x)=e^{\frac{1}{2}x_1^2-x_1x_2-\frac{1}{2}x_2^2}-\ln(\frac{1}{2}x_2^2+x_1x_2-\frac{1}{2}x_1^2),$

因此当$ q=1$时, $ \forall x \in X, d\in S^2$, $ d^\mathrm{T} H_D(x) d>0$, 即$ H_D(x)$是$ X$上的正定矩阵.

图 2给出了$ D(x)(q=1)$在$ X$上的图像, 由图 2可知, 对$ \forall x \in X$, $ D(x)$是$ X$上的凸函数.

定理5.1 设函数$f$:$R^{n}\to R$, $f(x)\in C^2$, 且$ f(x)$为$ X$上的次正定函数, $ \forall x\in X $, $ f(x)>0 $, 令

$F(x)=qe^{f(x)}+\frac{1}{2}f^2(x),$

若函数$ f(x)$在$ X$上存在全局极小点, 则存在$ q_1\geq0$, 使得当$ q>q_1$时, $ x_0$为$ f(x)$的全局极小点的充要条件是$ x_0$为$F(x)$的全局极小点.

证  必要性.设$x_0$是$f(x)$的全局极小点, 则有$0<f(x_0)\leq f(x)$, 故

$\frac{1}{2}f^2(x_0)\leq\frac{1}{2}f^2(x).$

(5.1)

又因为$ q>q_1\geq0$, 所以

$qe^{f(x_0)}\leq qe^{f(x)}.$

(5.2)

由(5.1),(5.2) 式得

$qe^{f(x_0)}+\frac{1}{2}f^2(x_0)\leq qe^{f(x)}+\frac{1}{2}f^2(x),$

因此 $ x_0$是$F(x)$的全局极小点.

充分性.设$x_0$是$ F(x)$的全局极小点, 有

$\nabla F(x_0)=[qe^{f(x_0)}+f(x_0)]g(x_0)=0.$

又因为$ qe^{f(x_0)}+f(x_0)>0$, 所以$ g(x_0)=0$.

又由定理3.1可知当$ q>q_1\geq0$时, $ F(x)$不仅是$ X$上的凸函数, 而且是严格凸函数, 则$ x_0$是$F(x)$在$ X$上唯一的全局极小点, 由于$ F(x)$在$ x_0$处二次可微且$ \nabla F(x_0)=0$, 因此有

$F(x_0+\delta d)=F(x_0)+\frac{1}{2}\delta^2 d^\mathrm{T} H_F(x_0)d+\delta^2\parallel d \parallel^2 \alpha(x_0, \delta d),$

其中当$ \delta \rightarrow 0$时, $ \alpha(x_0, \delta d)\rightarrow 0$, 于是

$\frac{F(x_0+\delta d)-F(x_0)}{\delta^2}=\frac{1}{2}d^\mathrm{T} H_F(x_0)d+\parallel d \parallel^2 \alpha(x_0, \delta d),$

由于$ x_0$是$ F(x)$唯一的全局极小点, 当$\mid \delta \mid$充分小时, 必有$ F(x_0+\delta d)>F(x_0)$, 又$ \delta \rightarrow 0$时, $ \alpha(x_0, \delta d)\rightarrow 0$, 因此 $ d^\mathrm{T} H_F(x_0)d>0$.故

$H_F(x_0)=[qe^{f(x_0)}+f(x_0)]G(x_0)>0.$

因为$ qe^{f(x_0)}+f(x_0)>0$, 所以$ G(x_0)>0$.

由局部极小点的二阶充分条件^[10]知$ x_0$是$f(x)$的局部极小点.

下证$ x_0$是$ f(x)$的全局极小点.

用反证法.假设$ x_0$不是$ f(x)$的全局极小点, 则存在点$x^\prime \in X(x^\prime \neq x_0)$, 使得$ 0<f(x^\prime)<f(x_0)$, 利用定理5.1证明中的必要性证明方法可得

$qe^{f(x^\prime)}+\frac{1}{2}f^2(x^\prime)<qe^{f(x_0)}+\frac{1}{2}f^2(x_0), $

与$ x_0$是$ F(x)$的全局极小点矛盾, 故$ x_0$是$ f(x)$的全局极小点.

定理5.2 设函数$f$:$R^{n}\to R$, $f(x)\in C^2$, 且$ f(x)$为$ X$上的次正定函数, $ \forall x\in X $, $ f(x)<0 $, 令

$D(x)=qe^{f(x)}-\ln(-f(x)),$

若函数$ f(x)$在$ X$上存在全局极小点, 则存在$ q_2\geq0$, 使得当$ q>q_2$时, $ x^\ast$为$ f(x)$的全局极小点的充要条件是$ x^\ast$为$D(x)$的全局极小点.

证  必要性.设$x^\ast$是$f(x)$的全局极小点, 则有$f(x^\ast)\leq f(x)<0$, 故

$-\ln(-f(x^\ast))\leq -\ln(-f(x)),$

(5.3)

又因为$ q>q_2\geq0$, 所以

$qe^{f(x^\ast)}\leq qe^{f(x)}.$

(5.4)

由(5.3),(5.4) 式得

$qe^{f(x^\ast)}-\ln[-f(x^\ast)]\leq qe^{f(x)}-\ln[-f(x)],$

因此 $ x^\ast$是$D(x)$的全局极小点.

充分性.设$x^\ast$是$D(x)$的全局极小点, 有

$\nabla D(x^\ast)=[qe^{f(x^\ast)}-\frac{1}{f(x^\ast)}]g(x^\ast)=0.$

又因为$qe^{f(x^\ast)}-\dfrac{1}{f(x^\ast)}>0$, 所以$ g(x^\ast)=0$.又由定理3.2可知当$ q>q_2\geq0$时, $ D(x)$不仅是$ X$上的凸函数, 而且是严格凸函数, 则$ x^\ast$是$D(x)$在$ X$上唯一的全局极小点, 由于$ D(x)$在$ x^\ast$处二次可微且$ \nabla D(x^\ast)=0$, 因此有

$D(x^\ast+\delta d)=D(x^\ast)+\frac{1}{2}\delta^2 d^\mathrm{T} H_D(x^\ast)d+\delta^2\parallel d \parallel^2 \alpha(x^\ast, \delta d),$

其中当$ \delta \rightarrow 0$时, $ \alpha(x^\ast, \delta d)\rightarrow 0$, 于是

$\frac{D(x^\ast+\delta d)-D(x^\ast)}{\delta^2}=\frac{1}{2}d^\mathrm{T} H_D(x^\ast)d+\parallel d \parallel^2 \alpha(x^\ast, \delta d).$

由于$ x^\ast$是$D(x)$唯一的全局极小点, 当$\mid \delta \mid$充分小时, 必有$ D(x^\ast+\delta d)>D(x^\ast)$, 又$ \delta \rightarrow 0$时, $ \alpha(x^\ast, \delta d)\rightarrow 0$, 因此, $ d^\mathrm{T} H_D(x^\ast)d>0$.故

$H_D(x^\ast)=[qe{f(x^\ast)}-\frac{1}{f(x^\ast)}]G(x^\ast)>0.$

因为$ qe^{f(x^\ast)}-\dfrac{1}{f(x^\ast)}>0$, 所以$ G(x^\ast)>0 $.

由局部极小点的二阶充分条件知$ x^\ast$是$f(x)$的局部极小点.

下证$ x^\ast$是$ f(x)$的全局极小点.

用反证法.假设$ x^\ast$不是$ f(x)$的全局极小点, 则存在点$x_1\in X(x_1\neq x^\ast)$, 使得$ f(x_1)<f(x^\ast)<0$, 利用定理5.2证明中的必要性证明方法可得

$qe^{f(x_1)}-\ln[-f(x_1)]<qe^{f(x^\ast)}-\ln[-f(x^\ast)],$

与$ x^\ast$是$ D(x)$的全局极小点矛盾, 故$ x^\ast$是$ f(x)$的全局极小点.

由定理5.1,5.2知可通过凸化方法, 将次正定函数在有界闭凸集上的全局优化问题转化为相应的凸规划.

本研究对目标函数为次正定函数的全局最优化问题, 给出了一种新的凸化方法, 通过将目标函数凸化, 从而将原问题转化为相应的凸规划, 然后论证了这一类函数全局最优解的最优性条件.对于次正定函数的全局最优化问题还需有进一步的研究, 期望得到更好的凸化方法与最优性条件.