ABSTRACT

For semi-infinite programming problems, we provide a new generalized exact penalty function, which contains many commonly used penalty functions as a special case. It is proved that the local optimal solution of the unconstrained optimization subproblem is also the local optimal solution of the original problem when the penalty parameter is sufficiently large under some constraint qualification. Moreover, under suitable conditions, we also prove that the global optimal solution sequence of unconstrained optimization subproblem converges to the global optimal solution of the original problem.

Keywords:Semi-Infinite Programming, Exact Penalty Function, Penalty Function Algorithm

求解半无限规划问题的一类新的精确 罚函数方法

张艳萍，刘茜

山东师范大学数学与统计学院，山东 济南

收稿日期：2017年10月21日；录用日期：2017年11月3日；发布日期：2017年11月15日

摘 要

对于半无限规划问题，我们提供了一种新的概括性的精确罚函数，它包含了许多常用的罚函数作为特例。我们证明了在适当的约束规格条件下，当罚参数充分大的时候，罚问题的局部最优解也是原问题的局部最优解。另外，在适当的条件下我们证明了罚问题的全局最优解序列收敛于原问题的全局最优解。

关键词 :半无限规划，精确罚函数，罚函数算法

Copyright © 2017 by authors and Hans Publishers Inc.

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

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

1. 引言

在工程设计中的许多实际最优问题，如抗震系统的设计，控制系统设计，电路设计等问题(例如 [1] [2] )都可以归纳为如下形式的半无限规划问题(P)：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}{g}_j\left(x,\omega \right)\le 0,\forall \omega \in \Omega ,j=1,\cdots ,m\end{array}$ (1.1)

其中， $x\in R^n$ 是一个决策向量，Ω为R中一紧致区间， $f:R^n\to R$ 是关于x连续可微的函数。对任意 $j=1,\cdots ,m$ ， $g_j:R^n\times \Omega \to R$ 是关于x和ω连续可微的函数。

由于半无限规划问题的约束有无限多个，不能直接应用一般的约束优化算法。针对这一情况，人们对半无限规划问题提出了许多解决的办法。目前，求解半无限规划问题的方法主要有转化方法、离散化方法、对偶参数法(如文献 [3] - [8] )等。通过这些方法使得原有的半无限规划问题可以利用已有的约束优化算法加以解决。

罚函数方法是解决约束优化问题一种重要的方法，它通过增加一个罚项，把原问题转化成一序列的无约束优化问题或者一序列简单约束优化问题来进行求解。1949年Couran首次提出了外罚函数方法，当罚参数趋于无穷大时，罚问题的最优解将收敛于原问题的最优解。随后，Frish [9] 和Carroll [9] 提出了更加完善的的内罚函数方法。由于上述内外罚函数方法，都需要罚参数无限大才能得到原问题的最优解，这会导致数值实验中的不稳定。为了解决这一困难，许多学者相继提出了精确罚函数的方法，并展开了相关研究。1967年Zangwill在文 [10] 中提出了第一个精确罚函数，在一定的条件下证明了当罚参数充分大的时候，对应罚问题的最优解就是原问题的最优解。1973年Fletcher在文 [11] 中针对不等式约束非线性规划问题提出了一类更一般的精确罚函数。2003年, Huyer和Neumaier在文 [12] 中，介绍了关于等式约束问题的一种新的精确罚函数，并在一些非退化条件下保证了罚参数充分大时罚问题的局部最优解也是原问题的局部最优解。2014年Wang, Ma和Zhou [13] 推广了文 [12] 中的精确罚函数，并讨论了罚函数存在的充分必要条件。

文献 [3] 介绍了一种通过约束转化来求解半无限规划问题(P)的方法。文中将原问题(P)中的无限个不等式约束转化成积分形式的有限个等式约束的优化问题。考虑到这样的约束函数是非光滑的，文献 [14] 和 [15] 又根据文献 [12] 中的精确罚函数和光滑近似的技巧提出了下面的罚函数：

$f_{\sigma }\left(x,\epsilon \right)=\{\begin{array}{l}f\left(x\right),\epsilon =0,g_j\left(x,\omega \right)\le 0\left(\omega \in \Omega \right),\\ f\left(x\right)+{\epsilon }^{-\alpha }\Delta \left(x,\epsilon \right)+\sigma {\epsilon }^{\beta },\epsilon >0,\\ +\infty ,其他,\end{array}$

其中，

$\Delta \left(x,\epsilon \right)={\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[\max \{0,g_j\left(x,\omega \right)-{\left(\epsilon \right)}^{\gamma }\}\right]}^2\text{d}\omega }}$

文献 [16] 中也提出了一类求解半无限规划问题的对数罚函数：

$f_{\sigma }\left(x,\epsilon \right)=\{\begin{array}{l}f\left(x\right),\epsilon =0,g_j\left(x,\omega \right)\le 0\left(\omega \in \Omega \right),\\ f\left(x\right)-{\epsilon }^{-\alpha }\log \left(1-\Delta \left(x,\epsilon \right)\right)+\sigma {\epsilon }^{\beta },\epsilon >0,\Delta \left(x,\epsilon \right)<1,\\ +\infty ,\text{otherwise}.\end{array}$

受文献 [13] 的启发, 我们注意到上述两种罚函数的中间项都是关于 $\Delta \left(x,\epsilon \right)$ 的光滑凸函数。在本文中， 我们提出了一种新的概括性的精确罚函数，它包含了许多常见的罚函数，其中文献 [14] [15] [16] 中的罚函数都是它的特例。通过该罚函数，建立了相应的精确罚函数算法。我们在适当的约束规格条件下，证明了当罚参数充分大的时候，罚问题的局部最优解也是原问题的局部最优解。另外，在适当的条件下我们证明了罚问题的全局最优解序列收敛于原问题的全局最优解。

本篇论文的结构概述如下：在第二部分，我们介绍了一种新的精确罚函数，并分析了其收敛性质；在第三部分，介绍了求解半无限规划问题(P)的精确罚函数算法。最后，通过数值实验，验证了该算法的有效性。

2. 一种新的精确罚函数

在这一部分，我们介绍一种新的精确罚函数 $f_{\sigma }\left(x,\epsilon \right)$ 如下：

$f_{\sigma }\left(x,\epsilon \right)=\{\begin{array}{l}f\left(x\right),\epsilon =0,g_j\left(x,\omega \right)\le 0\left(\omega \in \Omega \right),\\ f\left(x\right)+{\epsilon }^{-\alpha }\varphi \left(\Delta \left(x,\epsilon \right)\right)+\sigma {\epsilon }^{\beta },\epsilon >0,\Delta \left(x,\epsilon \right)<1,\\ +\infty ,\text{otherwise}.\end{array}$

其中 $\sigma >0$ 为罚参数， $\alpha >0$ ， $\beta >2$ 。 $\Delta \left(x,\epsilon \right)$ 是一个违反约束估计, 即

$\Delta \left(x,\epsilon \right)={\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[\max \{0,g_j\left(x,\omega \right)-{\left(\epsilon \right)}^{\gamma }\}\right]}^2\text{d}\omega }}$

其中 $\gamma >0$ ，光滑函数 $\varphi :\left[0,a\right)\to \left[0,+\infty \right)$ 满足下列性质：

1) $\varphi$ 在 $\left[0,a\right)$ 上是凸函数，连续可微的，且 $\varphi \left(0\right)=0$ 。

2) ${\varphi }^{\prime }\left(t\right)>0,\forall t\in \left[0,a\right)$ 。

许多函数满足上述两条性质，例如：

$\begin{array}{l}{\varphi }_1\left(t\right)=\frac{t}{{\left(1-qt\right)}^{\alpha }}\left(a=q^{-1},\alpha \ge 1\right)\\ {\varphi }_2\left(t\right)=\tan \left(t\right)\left(a=\frac{\text{π}}{2}\right)\\ {\varphi }_3\left(t\right)=-\log \left(1-t^{\alpha }\right)\left(a=1,\alpha \ge 1\right)\\ {\varphi }_4\left(t\right)=t\left(a=+\infty \right)\\ {\varphi }_5\left(t\right)={\text{e}}^t-1\left(a=+\infty \right)\\ {\varphi }_6\left(t\right)=\frac{1}{2}\left(\sqrt{t^2+4}+t\right)-1\left(a=+\infty \right)\end{array}$

值得注意的是，当光滑函数取 ${\varphi }_3$ 时，我们得到的是文献 [16] 中的建立的精确罚函数。当光滑函数取 ${\varphi }_4$ 时，得到的是文献 [14] 和 [15] 中的建立的精确罚函数。

根据上面介绍的精确罚函数，我们得到相应的带简单约束的子问题，记为问题 $\left(P_{\sigma }\right)$ 如下：

$\left(P_{\sigma }\right)\min f_{\sigma }\left(x,\epsilon \right)\text{s}\text{.t}\text{.}\left(x,\epsilon \right)\in R^n\times \left[0,+\infty \right)$

下面我们将给出在这类精确罚函数下的局部收敛性分析。设集合

$S_{\epsilon }=\left\{\left(x,\epsilon \right)\in R^n\times R_{+}:g_j\left(x,\omega \right)\le {\epsilon }^{\gamma },\forall \omega \in \Omega ,j=1,\cdots ,m\right\}$ (2.1)

其中 $R_{+}=\left\{\alpha \in R:\alpha \ge 0\right\}$ 。

定理1. 设 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为问题 $\left(P_{{\sigma }_k}\right)$ 的一局部最优解。假设 $f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 是有限的， ${\epsilon }^{k,\ast }>0$ ，则

$\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\notin S_{{\epsilon }^{k,\ast }}$

证明：由 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为问题 $\left(P_{{\sigma }_k}\right)$ 的局部最优解，我们有

$\frac{\partial f_{{\sigma }_k}\left(x^{\ast },{\epsilon }^{\ast }\right)}{\partial \epsilon }=0$

相反的，我们假设结论不成立，则有

$g_j\left(x^{k,\ast },\omega \right)\le {\left({\epsilon }^{k,\ast }\right)}^{\gamma },\forall \omega \in \Omega ,j=1,\cdots ,m$

由

$\begin{array}{l}\frac{\partial f_{{{\displaystyle \sigma }}_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}{\partial \epsilon }\\ =-\alpha {\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)-2\gamma \cdot {\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\\ \cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}}\cdot {\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega +\beta \sigma {\left({\epsilon }^{k,\ast }\right)}^{\beta -1}\end{array}$ (2.2)

则有 $0=\frac{\partial f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}{\partial \epsilon }=\beta \sigma {\left({\epsilon }^{k,\ast }\right)}^{\beta -1}>0$ 矛盾，所以 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\notin S_{{\epsilon }^{k,\ast }}$ 。

下面，我们证明子问题 $\left(P_{{\sigma }_k}\right)$ 的局部最优解序列的聚点一定是原问题 $\left(P_{\sigma }\right)$ 的可行解。

定义1. 称问题(P)的连续不等式约束在 $x=\overline{x}$ 处满足约束规格, 如果对任意满足

${\displaystyle {\int }_{\Omega }{\displaystyle \sum _{j=1}^m{\phi }_j\left(\omega \right)\frac{\partial g_j\left(\overline{x},\omega \right)}{\partial x}}}=0$

的式子都有 ${\phi }_j\left(\omega \right)=0,\forall \omega \in \Omega ,j=1,\cdots ,m$ 。

定理2. 假设 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为问题 $\left(P_{{\sigma }_k}\right)$ 的局部最优解， $f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 是有限的， ${\epsilon }^{k,\ast }>0$ 。当 $k\to +\infty$ 时， ${\sigma }_k\to +\infty$ ， $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\to \left(x^{\ast },{\epsilon }^{\ast }\right)$ ，且问题(P)的连续不等式约束在 $x=x^{\ast }$ 处满足约束规格，则 ${\epsilon }^{\ast }=0$ ， $x^{\ast }$ 为原问题(P)的可行解。

证明：由 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为问题 $\left(P_{{\sigma }_k}\right)$ 的局部最优解知

$\begin{array}{l}\frac{\partial f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}{\partial x}\\ =\frac{\partial f\left(x^{k,\ast }\right)}{\partial x}+2{\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right){\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}}\frac{\partial g_j\left(x^{k,\ast },\omega \right)}{\partial x}\text{d}\omega \\ =0\end{array}$ (2.3)

$\begin{array}{l}\frac{\partial f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}{\partial \epsilon }\\ =-\alpha {\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)-2\gamma {\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\\ \cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}}\cdot {\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega +\beta {\sigma }_k{\left({\epsilon }^{k,\ast }\right)}^{\beta -1}\\ =0\end{array}$ (2.4)

假设 ${\epsilon }^{k,\ast }\to {\epsilon }^{\ast }\ne 0$ ，由(2.4)式我们得

$\begin{array}{l}-\alpha {\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\end{array}$ $-2\gamma {\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right){\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}}\cdot {\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega$ $=-{\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\{\alpha \varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)+2\gamma {\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right){\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \{0,g_j\left(x^{k,\ast },\omega \right)}}$ $-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\left\}{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\text{d}\omega \right\}$

是趋向于一个有限值，然而当 $k\to +\infty ,{\sigma }_k\to +\infty$ 时， ${\sigma }_k{\left({\epsilon }^{k,\ast }\right)}^{\beta -1}\to +\infty$ ，与(2.4)式矛盾，则有 ${\epsilon }^{\ast }=0$ 。

由等式(2.3)有

$\frac{{\left({\epsilon }^{k,\ast }\right)}^{\alpha }}{{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}\cdot \frac{\partial f\left(x^{k,\ast }\right)}{\partial x}+2{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}}\frac{\partial g_j\left(x^{k,\ast },\omega \right)}{\partial x}\text{d}\omega =0$

等式两边取极限得

$2{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{\ast },\omega \right)\right\}}}\frac{\partial g_j\left(x^{\ast },\omega \right)}{\partial x}=0$

由约束规格知对 $\forall j=1,\cdots ,m,\omega \in \Omega$ ，

$\max \left\{0,g_j\left(x^{\ast },\omega \right)\right\}=0$

即 $g_j\left(x^{\ast },\omega \right)\le 0,\forall \omega \in \Omega ,j=1,\cdots ,m$ ，所以 $x^{\ast }$ 为问题(P)的可行解。

根据约束函数的连续性，我们很容易得到如下推论：

推论1. 若 $x^{k,\ast }\to x^{\ast },{\epsilon }^{k,\ast }\to {\epsilon }^{\ast },\left(x^{\ast },{\epsilon }^{\ast }\right)\in S_0$ ，则有

$\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\to \Delta \left(x^{\ast },{\epsilon }^{\ast }\right)=0$

定理3. 假设 $g_j\left(x^{k,\ast },\omega \right)=o\left({\left({\epsilon }^{k,\ast }\right)}^{\delta }\right),\delta >0,j=1,\cdots ,m$ 。若 $\gamma >\alpha$ ， $\delta >\alpha$ ， $-\alpha -1+2\delta >0$ ， $2\gamma -\alpha -1>0$ ，则当 $x^{k,\ast }\to x^{\ast },{\epsilon }^{k,\ast }\to {\epsilon }^{\ast },\left(x^{\ast },{\epsilon }^{\ast }\right)\in S_0$ ，有

$f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\to f_{{\sigma }_k}\left(x^{\ast },0\right)=f(x\ast )$

${\nabla }_{\left(x,\epsilon \right)}{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\to {\nabla }_{\left(x,\epsilon \right)}{f}_{{\sigma }_k}\left(x^{\ast },0\right)=\left(\nabla f\left(x^{\ast }\right),0\right)$

证明：

$\begin{array}{l}\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\left\{f\left(x^{k,\ast }\right)+{\left({\epsilon }^{k,\ast }\right)}^{-\alpha }\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)+{\sigma }_k{\left({\epsilon }^{k,\ast }\right)}^{\beta -1}\right\}\\ =f(x\ast )\end{array}$

由于

$\begin{array}{c}\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha }}=\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}\cdot \frac{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha }}\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}\cdot \frac{{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}\right]}^2\text{d}\omega }}}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha }}\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}\cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[\max \left\{0,\frac{g_j\left(x^{k,\ast },\omega \right)}{{\left({\epsilon }^{k,\ast }\right)}^{\delta }}\cdot {\left({\epsilon }^{k,\ast }\right)}^{\delta -\frac{\alpha }{2}}-\frac{{\left({\epsilon }^{k,\ast }\right)}^{\gamma }}{{\left({\epsilon }^{k,\ast }\right)}^{\frac{\alpha }{2}}}\right\}\right]}^2\text{d}\omega }}\\ =0\end{array}$

$\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }{\nabla }_{\left(x,\epsilon \right)}{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)=\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }{\left[{\nabla }_x{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right){\nabla }_{\epsilon }{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right]}^{\text{T}}$

其中

而

$\begin{array}{l}\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }{\nabla }_{\epsilon }{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\{-\alpha {\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)-2\gamma {\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\\ \cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}{\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega }+\beta {\sigma }_k{\left({\epsilon }^{k,\ast }\right)}^{\beta -1}\}\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\left\{\left(-\alpha \right)\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha +1}}-2\gamma {\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\frac{{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\left\{g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}{\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega }}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha }}\right\}\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\left(-\alpha \right)\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha +1}}\\ =\underset{e^{k,\ast }\to {\epsilon }^{\ast }=0}{\lim }\left(-\alpha \right)\frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}.\frac{{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right]}^2\text{d}\omega }}}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha +1}}=0\end{array}$

则定理成立。

定理4. 令 $-\alpha -\beta +2\delta >0$ ， $-\alpha -\beta +2\gamma >0$ ，设 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 是子问题 $\left(P_{{\sigma }_k}\right)$ 的局部最优解， $f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 是有限值，则存在 $k_0>0$ ，对所有 $k>k_0$ ，局部最优解 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 都具有 $\left(x^{\ast },0\right)$ 的形式， $x^{\ast }$ 为原问题(P)的局部最优解。

证明：反证法。假设该结论不成立，则在序列 $\left\{\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right\}$ 中，对任意的 $k_0>0$ ，总存在 $k^{\prime }>k_0$ ，使得 ${\epsilon }^{k^{\prime },\ast }\ne 0$ ，这样就构成了 $\left\{\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right\}$ 的一个子序列。不失一般性，我们将该序列仍然用原序列 $\left\{\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right\}$ 表示，根据定理2，我们知道当 $k\to +\infty$ 时，

${\epsilon }^{k,\ast }\to {\epsilon }^{\ast }=0,x^{k,\ast }\to x^{\ast },\left(x^{\ast },{\epsilon }^{\ast }\right)\in S_0$

由于 ${\epsilon }^{k,\ast }\ne 0$ ，等式(2.4)除以 ${\left({\epsilon }^{k,\ast }\right)}^{\beta -1}$ 得

$\begin{array}{l}{\left({\epsilon }^{k,\ast }\right)}^{1-\beta }[\left(-\alpha \right){\left({\epsilon }^{k,\ast }\right)}^{-\alpha -1}\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)-2\gamma {\left({\epsilon }^{k,\ast }\right)}^{-\alpha }{\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\\ \cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}{\left({\epsilon }^{k,\ast }\right)}^{\gamma -1}\text{d}\omega }+\beta {\sigma }_k{\left({\epsilon }^{k,\ast }\right)}^{\beta -1}]=0\end{array}$

即

$\begin{array}{l}{\left({\epsilon }^{k,\ast }\right)}^{-\alpha -\beta }\{\alpha \varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)+2\gamma {\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\\ \cdot {\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}}{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\text{d}\omega \}}=\beta {\sigma }_k\end{array}$

上式等价于：

$\begin{array}{l}\alpha \frac{\varphi \left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)}{\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)}\frac{{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }{\left[\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}\right]}^2\text{d}\omega }}}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha +\beta }}\\ +2\gamma {\varphi }^{\prime }\left(\Delta \left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right)\frac{{\displaystyle \sum _{j=1}^m{\displaystyle {\int }_{\Omega }\max \left\{0,g_j\left(x^{k,\ast },\omega \right)-{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\right\}{\left({\epsilon }^{k,\ast }\right)}^{\gamma }\text{d}\omega }}}{{\left({\epsilon }^{k,\ast }\right)}^{\alpha +\beta }}=\beta {\sigma }_k\end{array}$ (2.5)

又由于 $-\alpha -\beta +2\delta >0$ ， $-\alpha -\beta +2\gamma >0$ ，当 $k\to +\infty$ 时，等式左边趋向于零，等式右边趋向于一个无限值，矛盾。故对充分大的 $k$ ，罚问题的任意局部最优解 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 都有 $\left(x^{\ast },0\right)$ 的形式。

由定理2知 $x^{\ast }$ 为问题(P)的可行解，则表明存在 $x^{\ast }$ 的某一邻域 $U\left(x^{\ast }\right)$ ，对问题(P)的任意可行解 $x\in U\left(x^{\ast }\right)$ ，有

$f\left(x\right)=f_{{\sigma }_k}\left(x,0\right)\ge f_{{\sigma }_k}\left(x^{\ast },0\right)=f(x\ast )$

所以， $x^{\ast }$ 为问题(P)的局部最优解。

定理5. 假设 $\left\{{\sigma }_k\right\}$ 为递增的罚参数序列，满足 $k\to +\infty$ 时， ${\sigma }_k\to +\infty$ 。若 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为问题 $\left(P_{{\sigma }_k}\right)$ 的全局最优解，则 ${\left\{x^{k,\ast }\right\}}_{k=1}^{\infty }$ 的任一聚点为原问题(P)的全局最优解。

证明：不失一般性，假设当 $k\to +\infty$ 时， $x^{k,\ast }\to \overline{x}$ 。设 $x^{\ast }$ 为原问题(P)的一个全局最优解，由于 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为 $\left(P_{{\sigma }_k}\right)$ 的全局最优解，故

$f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\le f_{{\sigma }_k}\left(x^{\ast },0\right)=f\left(x^{\ast }\right),\forall k\ge 1$ (2.6)

则序列 ${\left\{f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right\}}_{k=1}^{\infty }$ 是有界的，又由于 ${\sigma }_k<{\sigma }_{k+1}$ ，得

$f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\le f_{{\sigma }_k}\left(x^{k+1,\ast },{\epsilon }^{k+1,\ast }\right)\le f_{{\sigma }_{k+1}}\left(x^{k+1,\ast },{\epsilon }^{k+1,\ast }\right)$

因此序列 ${\left\{f_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\right\}}_{k=1}^{\infty }$ 是非减的，因此该序列是收敛的。由(2.6)式可得

$\underset{k\to +\infty }{\lim }{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\le f(x\ast )$

另一方面，由定理2知， $\overline{x}$ 为原问题(P)的可行解。

$\underset{k\to +\infty }{\lim }{f}_{{\sigma }_k}\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)\ge \underset{k\to +\infty }{\lim }f\left(x^{k,\ast }\right)=f\left(\overline{x}\right)\ge f(x\ast )$

则 $f\left(\overline{x}\right)=f\left(x^{\ast }\right)$ ，这表明聚点 $\overline{x}$ 为原问题(P)的全局最优解。

3. 罚函数算法

在这个部分，我们主要提供一个罚函数算法，其中 ${\sigma }^{\ast }$ 为罚参数的上界， ${\epsilon }^{\ast }$ 为 $\epsilon$ 的下界。基于前面提供的新的精确罚函数以及相应的罚问题，我们提出了一种有效的算法：

算法1

1) 令 ${\sigma }_0=1,{\epsilon }_0=0.1,{\sigma }^{\ast }={10}^5,{\epsilon }^{\ast }={10}^{-9}$ ，设初始点为 $\left(x_0,{\epsilon }_0\right)$ ，迭代指数 $k=0$ ，选择合适的参数 $\alpha ,\beta ,\gamma$ ，其中参数的选择依赖于相应的原问题(P)。

2) 求解罚问题 $\left(P_{{\sigma }_k}\right)$ ，令 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 为其得到的最优解。

3) 如果 ${\epsilon }^{k,\ast }>{\epsilon }^{\ast },{\sigma }_k<{\sigma }^{\ast }$ ，令 ${\sigma }_{k+1}=10\times {\sigma }_k,k:=k+1$ ，返回到步骤(2)中，其中 $\left(x^{k,\ast },{\epsilon }^{k,\ast }\right)$ 作为新的初始解进行。否则，令 ${\epsilon }^{k,\ast }:={\epsilon }^{\ast }$ ，进行步骤(4)。

4) 检验 $x^{k,\ast }$ 是否可行。如果 $x^{k,\ast }$ 是一可行解，则它是原问题(P)的局部最优解，否则进行步骤(5)。

5) 调整参数 $\alpha ,\beta ,\gamma$ ，令 $k:=0$ ，返回步骤(2)。

为了检验算法的有效性,，我们考虑了文献 [16] 中的两个例子。我们是通过MATLAB工具箱中的fmincon函数解决优化问题 $\left(P_{\sigma }\right)$ ，其中，函数 $f_{\sigma }\left(x,\epsilon \right)$ 中的积分部分是通过离散化步长h利用Simpson’s Rule来解决的。下面是我们考虑的问题：

例1. 考虑下面的半无限规划问题：

$\begin{array}{l}\min {\left(x_1\right)}^2+{\left(x_2-3\right)}^2\\ \text{s}\text{.t}\text{.}{x}_2-2+x_1\sin \left(\frac{t}{x_2-\omega }\right)\le 0,\forall t\in \left[0,\text{π}\right],\\ -1\le x_1\le 1,0\le x_2\le 2\end{array}$

其中 $\omega$ 是一个控制约束频率的参数，如在文献 [15] 中参数 $\omega$ 选作2.032。

根据辛普森法则对区间 $\left[0,\text{π}\right]$ 平均分割成1000个子区间，在这些子区间上利用精确罚函数来计算相应的约束变量。其中那些离散点也定义成区间 $\left[0,\text{π}\right]$ 的一个稠密子区间，用来检验连续不等式约束的可行性。在本篇论文中，相应的精确罚函数 $f_{\sigma }\left(x,\epsilon \right)$ 有多种，其约束违反度为

$\Delta \left(x,\epsilon \right)={\displaystyle {\int }_0^{\text{π}}{\left[\max \left\{0,x_2-2+x_1\sin \left(\frac{t}{x_2-\omega }\right)-{\epsilon }^{\gamma }{W}_j\right\}\right]}^2\text{d}t}$

初始点为 $\left[0.5,0,5\right]$ ，无论选择哪种精确罚函数都可以得到和文献 [16] 一样的最优解，得到的结论如表1。

表1说明的是精确罚函数解决上述半无限规划问题的结果。表中 $\sigma$ 为子问题 $\left(P_{\sigma }\right)$ 的罚参数， $\left(x_1,x_2,\epsilon \right)$ 为子问题 $\left(P_{\sigma }\right)$ 的局部最优解， $f$ 为原问题的最优值。

表1. 例1的数据结果

表2. 例2的数据结果

从上述实验数据可以看出，该问题的最优解为 $\left(x_1^{\ast },x_2^{\ast }\right)=\left(0,2\right)$ ，目标函数的最优值为 $f^{\ast }=1$ 。

例2. 考虑下面的半无限规划问题：

$\begin{array}{l}\min {\left(x_1+x_2-2\right)}^2+{\left(x_1-x_2\right)}^2+30{\left[\min \left\{0,x_1-x_2\right\}\right]}^2\\ \text{s}\text{.t}\text{.}{x}_1\cos t+x_{2}x\sin t-1\le 0,\forall t\in \left[0,\text{π}\right]\end{array}$

再一次，根据辛普森法则对区间 $\left[0,\text{π}\right]$ 平均分割成1000个子区间，在这些子区间上利用精确罚函数来计算相应的约束变量。其中那些离散点也定义成区间 $\left[0,\text{π}\right]$ 的一个稠密子区间，用来检验连续不等式约束的可行性。现在利用算法1和初始点 $\left[0.5,0,5\right]$ ，选择不同的精确罚函数会有不同的收敛速度，我们利用的 $\varphi \left(t\right)=\tan \left(t\right)$ 得到如表2中的结论。

从上述实验数据可以看出，该问题的最优解为 $\left(x_1,x_2\right)=\left(0.7298,0.6904\right)$ ，目标函数的最优值为 $f^{\ast }=0.3378$ 。

文章引用

张艳萍,刘 茜. 求解半无限规划问题的一类新的精确罚函数方法
A New Exact Penalty Function Method for Solving Semi-Infinite Programming Problems[J]. 运筹与模糊学, 2017, 07(04): 138-147. http://dx.doi.org/10.12677/ORF.2017.74014

参考文献 (References)