长沙理工大学数学与统计学院，湖南 长沙

收稿日期：2023年4月28日；录用日期：2023年5月21日；发布日期：2023年5月31日

摘要

罚函数法是求解约束优化问题的一种经典方法，其基本思想是将约束优化问题转化为无约束优化问题进行求解。本文我们提出了一类新的具有二次连续可微性质的光滑化l₁精确罚函数，并证明了相应罚函数算法的全局收敛性。此外，我们进行了数值实验，数值结果表明了该方法比较有效。

关键词

约束优化问题，精确罚函数法，光滑罚函数

A New Smooth l₁ Exact Penalty Function Methods

Xiaomin Qu

School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha Hunan

Received: Apr. 28^th, 2023; accepted: May 21^st, 2023; published: May 31^st, 2023

ABSTRACT

Penalty function method is a classical method for solving constrained optimization problems. Its basic idea is to transform constrained optimization problem into constrained optimization problem for solving. In this article, we propose a new class of smoothing exact penalty function methods and prove their global convergence. In addition, we conducted numerical experiments, and the numerical results showed that the method is relatively effective.

Keywords:Constrained Optimization Problem, Accurate Penalty Function Method, Smooth Penalty Function

Copyright © 2023 by author(s) and Hans Publishers Inc.

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

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

1. 引言

罚函数法是求解约束优化问题的一种常用方法，其基本思想是：将约束条件转化为某种惩罚函数加到目标函数中去，从而将约束优化问题的求解转化为一系列无约束优化问题的求解。在一定条件下，如果罚问题的解是原问题的解或者原问题的解是罚问题的解，则称该罚函数为精确罚函数；如果罚函数中包含原问题的目标函数和约束函数而不包含它们的梯度，则称该罚函数为简单罚函数 [1] 。

本文考虑如下不等式约束优化问题：

$\begin{array}{cc}(\text{P})& \begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}.\begin{array}{c}\end{array}{g}_i\left(x\right)\le 0,\begin{array}{c}\end{array}i=1,\cdots ,m,\end{array}\end{array}$ (1.1)

其中 $f,g_i:R^n\to R$ ， $i\in I=\left\{1,2,\cdots ,m\right\}$ 是连续可微函数。记 $X_0=\left\{x\in R^n|g_i\left(x\right)\le 0,i=1,2,\cdots ,m\right\}$ ，则 $X_0$ 是问题(P)的可行集。下面给出一些关于近似最优解的定义。

定义1.1 [2] 如果 $x_{\epsilon }$ 是问题(P)的可行解， $x^{\text{*}}$ 是(P)的最优解，并且满足 $\left|f\left(x^{\text{*}}\right)-f\left(x_{\epsilon }\right)\right|\le \epsilon$ 。则称 $x_{\epsilon }$ 是(P)的ε-近似最优解。

定义1.2 [2] 如果满足对 $\forall i\in I$ 有 $g_i\left(x_{\epsilon }\right)\le \epsilon$ ，则 $x_{\epsilon }\in R^n$ 是问题(P)的ε-可行解。

$l_2$ 罚函数是一种经典常见的罚函数：

$F_2\left(x,\rho \right)=f\left(x\right)+\rho {\displaystyle \underset{i\in I}{\sum }\max {\left\{g_i\left(x\right),0\right\}}^2}$ .

$l_2$ 罚函数是光滑但非精确的。1967年，Zangwill [3] 提出了经典 $l_1$ 罚函数：

$F_1\left(x,\rho \right)=f\left(x\right)+\rho {\displaystyle \underset{i\in I}{\sum }\max \left\{g_i\left(x\right),0\right\}}$ .

其相应无约束优化问题为

$(\text{P}1)\min F_1\left(x,\rho \right)\text{s}\text{.t}x\in R^n$ .

$l_1$ 罚函数是精确的，但是不可微 [5] ，因而不能有效应用求解光滑优化问题的算法进行求解，对 $l_1$ 这样的非光滑罚函数进行光滑化是十分重要的。学者们对 $l_1$ 精确罚函数采用各种光滑化函数进行光滑化处理，以达到光滑精确罚函数的效果。

1994年，Mustafa Ç [4] 提出了一个可以求解大规模问题的光滑化 $l_1$ 罚函数。2012年，Lian [5] 提出了如下带有指数的光滑化 $l_1$ 罚函数：

$P_{\epsilon }\left(t\right)=\{\begin{array}{c}\frac{3\epsilon }{2}{\text{e}}^{\frac{t}{\epsilon }}-2\epsilon ,\begin{array}{c}\end{array}t\le 0，\\ t-\frac{\epsilon }{2}{\text{e}}^{-\frac{t}{\epsilon }},\begin{array}{cc}& t>0.\end{array}\end{array}$

2016年，Ahmet [6] 提出了带有一个参数的一类光滑化 $l_1$ 罚函数，该罚函数对应的光滑化罚问题的解和原问题的解之间的误差较小。2009年，刘 [7] 提出了一种新的精确罚函数：

$P_{\epsilon }\left(t\right)=\{\begin{array}{c}\frac{\epsilon }{2}{\text{e}}^{\frac{t}{\epsilon }},\begin{array}{cc}& \end{array}t\le 0，\\ t+\frac{\epsilon }{2}{\text{e}}^{-\frac{t}{\epsilon }},\begin{array}{c}\end{array}t>0.\end{array}$

该罚函数至少两次连续可微。2013年，Xu [8] 提出了如下具有二阶连续可微性质的光滑化 $l_1$ 罚函数：

$P_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t<0,\\ \frac{t^3}{6{\epsilon }^2},0\le t<\epsilon \\ t+\frac{{\epsilon }^2}{2t}-\frac{4}{3}\epsilon ,\epsilon \le t.\end{array}$

2015年，BINH [9] 提出了一种带有指数的二阶连续可微光滑化 $l_1$ 罚函数。2019年，Xu [10] 提出了如下的二阶连续可微的光滑化 $l_1$ 罚函数：

$P_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t<0,\\ \frac{m^3{\rho }^3{t}^4}{10{\epsilon }^3},0\le t<\frac{\epsilon }{m\rho },\\ t+\frac{3{\epsilon }^2}{5m^2{\rho }^{2}t}-\frac{3\epsilon }{2m\rho }\begin{array}{c},\frac{\epsilon }{m\rho }\le t.\end{array}\end{array}$

此外有一些学者 [11] [12] 对低价精确罚函数的光滑化函数也进行了深入研究。

受文献 [8] 的启发，本文对 $l_1$ 罚函数提出了一类新的具有二次连续可微性质的光滑化罚函数，选择适当的参数可以得到较高的光滑化精度。在此基础上我们给出了求解不等式约束优化问题的 $l_1$ 光滑化罚函数法，并进行了数值实验。

2. 一类二阶光滑罚函数

考虑如下函数

$P\left(t\right)=\{\begin{array}{l}0,t\le 0,\\ t,t>0,\end{array}$

$l_1$ 罚函数的罚问题(P1)转化为如下形式：

$\min F_1\left(x,\rho \right)=f\left(x\right)+\rho {\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x\right)\right),\begin{array}{c}\end{array}}x\in R^n$ .

受文献 [8] 的启发，我们对 $P\left(t\right)$ 构造如下的光滑化函数：

$P_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t\le 0,\\ \frac{q{\epsilon }^{1-p}{t}^p}{p\left(p+q-1\right)},0<t<\epsilon ,\\ t+\frac{\left(1-p\right){\epsilon }^q{t}^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(1-q\right)}\epsilon ,\epsilon \le t.\end{array}$ (2.1)

其中 $p>2$ ， $q\ge 2$ ， $\epsilon >0$ 是光滑化参数。下面分析 $P_{\epsilon }\left(t\right)$ 的连续可微性质。

$P_{\epsilon }\left(t\right)$ 的一阶导数式(2.2)和二阶导数式(2.3)如下：

${P^{\prime }}_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t\le 0,\\ \frac{q}{\left(p+q-1\right)}{\left(t/\epsilon \right)}^{p-1},0<t<\epsilon ,\\ 1+\frac{1-p}{\left(p+q-1\right)}{\left(\epsilon /t\right)}^q,\epsilon \le t.\end{array}$ (2.2)

当 $t\le 0$ 时， $\underset{t\to 0}{\lim }{P^{\prime }}_{\epsilon }\left(t\right)=0$ ，当 $0<t<\epsilon$ 时， $\underset{t\to 0}{\lim }{P^{\prime }}_{\epsilon }\left(t\right)=0$ ， $\underset{t\to \epsilon }{\lim }{P^{\prime }}_{\epsilon }\left(t\right)=\frac{q}{p+q-1}$ ，当 $t\ge \epsilon$ 时， $\underset{t\to \epsilon }{\lim }{P^{\prime }}_{\epsilon }\left(t\right)=1+\frac{1-p}{p+q-1}=\frac{q}{p+q-1}$ ，因此 $P_{\epsilon }\left(t\right)$ 连续可微。

${P^{″}}_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t\le 0,\\ \frac{q\left(p-1\right)}{\left(p+q-1\right)\epsilon }{\left(t/\epsilon \right)}^{p-2},0<t<\epsilon ,\\ \frac{q\left(p-1\right)}{\left(p+q-1\right)t}{\left(\epsilon /t\right)}^q,\epsilon \le t.\end{array}$ (2.3)

当 $t\le 0$ 时， $\underset{t\to 0}{\lim }{P^{″}}_{\epsilon }\left(t\right)=0$ ，当 $0<t<\epsilon$ 时， $\underset{t\to 0}{\lim }{P^{″}}_{\epsilon }\left(t\right)=0$ ， $\underset{t\to \epsilon }{\lim }{P^{″}}_{\epsilon }\left(t\right)=\frac{q\left(p-1\right)}{p+q-1}$ ，当 $t\ge \epsilon$ 时， $\underset{t\to \epsilon }{\lim }{P^{″}}_{\epsilon }\left(t\right)=\frac{q\left(p-1\right)}{p+q-1}$ ，因此 $P_{\epsilon }\left(t\right)$ 二阶连续可微。

$l_1$ 的光滑化罚函数为：

$F\left(x,\rho ,\epsilon \right)=f\left(x\right)+\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x\right)\right)},$

其相应的光滑化罚问题：

$\begin{array}{cc}(\text{SP})& \begin{array}{cc}\min F\left(x,\rho ,\epsilon \right)=f\left(x\right)+\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x\right)\right)}& \text{s}\text{.t}.x\in R^n\end{array}\end{array}$

若f是二阶连续可微的，则 $F\left(x,\rho ,\epsilon \right)$ 也是二阶连续可微函数。下面我们给出 $P_{\epsilon }\left(t\right)$ 和 $P\left(t\right)$ 的误差估计。

定理2.1 对于任意的t和 $\epsilon >0$ ，下面的不等式成立：

$0\le P\left(t\right)-P_{\epsilon }\left(t\right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon$ .

证明：对于任意的t， $\epsilon >0$ ，由 $P\left(t\right)$ 和 $P_{\epsilon }\left(t\right)$ 的定义有

$P\left(t\right)-P_{\epsilon }\left(t\right)=\{\begin{array}{l}0,t\le 0,\\ t-\frac{q{\epsilon }^{1-p}{t}^p}{p\left(p+q-1\right)},0<t<\epsilon ,\\ -\frac{\left(1-p\right){\epsilon }^q{t}^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon ,\epsilon \le t.\end{array}$

当 $0<t<\epsilon$ 时， $P\left(t\right)-P_{\epsilon }\left(t\right)$ 可导，因而

$\nabla \left[P\left(t\right)-P_{\epsilon }\left(t\right)\right]=1-\frac{q}{\left(p+q-1\right)}{\left(t/\epsilon \right)}^{p-1}>0,$

即此时 $P\left(t\right)-P_{\epsilon }\left(t\right)=t-\frac{q{\epsilon }^{1-p}{t}^p}{p\left(p+q-1\right)}$ 单调递增，因此当 $t\in \left[0,\epsilon \right)$ 时有

$0\le P\left(t\right)-P_{\epsilon }\left(t\right)=t-\frac{q{\epsilon }^{1-p}{t}^p}{p\left(p+q-1\right)}<\frac{p\left(p+q-1\right)-q}{p\left(p+q-1\right)}\epsilon .$

当 $t\ge \epsilon$ 时，显然 $P\left(t\right)-P_{\epsilon }\left(t\right)=-\frac{\left(1-p\right){\epsilon }^q{t}^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon$ 是单调递增的，即此时

$\frac{p\left(p+q-1\right)-q}{p\left(p+q-1\right)}\epsilon \le P\left(t\right)-P_{\epsilon }\left(t\right)=-\frac{\left(1-p\right){\epsilon }^q{t}^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon \le \frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon .$

由上述可得

$0\le P\left(t\right)-P_{\epsilon }\left(t\right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}\epsilon ,i\in I.$

因此结论得证。

注记：当ε和q确定时， $\left(q\left(p-1\right)\epsilon /p\left(q-1\right)\right)$ 对于p单调递增，当ε和p确定时， $\left(q\left(p-1\right)\epsilon /p\left(q-1\right)\right)$ 对于q单调递减。由定理2.1可知， $P\left(t\right)$ 和 $P_{\epsilon }\left(t\right)$ 的误差可以任意小，只要光滑参数ε足够小，即

$\underset{\epsilon \to 0}{\lim }{P}_{\epsilon }\left(t\right)=P\left(t\right)$ 。

下面分析 $l_1$ 精确罚函数的罚问题(P1)和光滑化罚问题(SP)之间的关系。

定理2.2 若 ${\left\{{\epsilon }_j\right\}}_0^{\infty }$ 是一正序列，且 $\underset{j\to \infty }{\lim }{\epsilon }_j=0$ ，对于某个给定的 $\rho >0$ ，设 $x_j$ 是问题(SP)： $\underset{x\in R^n}{\min }F\left(x,\rho ,{\epsilon }_j\right)$ 的一个解， $x^{\prime }$ 是序列 $\left\{x_j\right\}$ 的一个极限点，则 $x^{\prime }$ 是问题(P1)： $\underset{x\in R^n}{\min }{F}_1\left(x,\rho \right)$ 的最优解。

证明：由 $x_j$ 是问题(SP)的一个解可知，

$F\left(x_j,{\rho }_j,{\epsilon }_j\right)\le F\left(x,{\rho }_j,{\epsilon }_j\right).$

结合定理2.1有

$0\le {\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x\right)\right)}-{\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x\right)\right)}\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\epsilon ,$

$0\le \rho {\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x\right)\right)}-\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x\right)\right)}\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\epsilon \rho ,$

$0\le \left[f\left(x\right)-\rho {\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x\right)\right)}\right]-\left[f\left(x\right)-\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x\right)\right)}\right]\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\epsilon \rho ,$

故

$0\le F_1\left(x,\rho \right)-F\left(x,\rho ,\epsilon \right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\epsilon \rho ,$ (2.4)

于是

$\begin{array}{l}{F}_1\left(x_j,\rho \right)\le F\left(x_j,\rho ,{\epsilon }_j\right)+\frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho {\epsilon }_j\\ \begin{array}{ccc}& & \end{array}\le F\left(x,\rho ,{\epsilon }_j\right)+\frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho {\epsilon }_j\\ \begin{array}{ccc}& & \end{array}\le F_1\left(x,\rho \right)+\frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho {\epsilon }_j,\end{array}$

当 $j\to \infty$ 时有 $F_1\left(x^{\prime },\rho \right)\le F_1\left(x,\rho \right)$ ，因此 $x^{\prime }$ 是问题(P1)的最优解。结论得证。

定理2.3对于某个给定的 $\rho >0$ ， $\epsilon >0$ ，如果 $x^{\text{*}}$ 是问题(P1)的最优解， $x^{\prime }$ 是问题(SP)的最优解，则

$0\le F\left(x^{\text{*}},\rho \right)-F\left(x^{\prime },\rho ,\epsilon \right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon .$

特别地，如果 $x^{\prime }$ 是原问题(P)的ε-可行解， $x^{\text{*}}$ 是原问题(P)的可行解，则 $x^{\prime }$ 是原问题(P)的近似最优解。

证明：由式(2.4)可知，

$0\le F\left(x^{\text{*}},\rho \right)-F\left(x^{\text{*}},\rho ,\epsilon \right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon ,$

$0\le F\left(x^{\prime },\rho \right)-F\left(x^{\prime },\rho ,\epsilon \right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon .$

因为 $x^{\text{*}}$ 是问题(P1)的最优解， $x^{\prime }$ 是问题(SP)的最优解，则有

$F\left(x^{\text{*}},\rho \right)\le F\left(x^{\prime },\rho \right),$

$F\left(x^{\prime },\rho ,\epsilon \right)\le F\left(x^{\text{*}},\rho ,\epsilon \right),$

因而

$\begin{array}{c}0\le F\left(x^{\text{*}},\rho \right)-F\left(x^{\text{*}},\rho ,\epsilon \right)\\ \le F\left(x^{\text{*}},\rho \right)-F\left(x^{\prime },\rho ,\epsilon \right)\\ \le F\left(x^{\prime },\rho \right)-F\left(x^{\prime },\rho ,\epsilon \right)\\ \le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon ,\end{array}$

$0\le F\left(x^{\text{*}},\rho \right)-F\left(x^{\prime },\rho ,\epsilon \right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon .$

即

$0\le \left[f\left(x^{\text{*}}\right)+\rho {\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x^{\text{*}}\right)\right)}\right]-\left[f\left(x^{\prime }\right)+\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x^{\prime }\right)\right)}\right]\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon ,$

如果 $x^{\prime }$ 是原问题(P)的ε-可行解， $x^{\text{*}}$ 是原问题(P)的可行解，则 $x^{\text{*}}$ 是原问题(P)的最优解且

$g_i\left(x^{\prime }\right)\le \epsilon ,$

${\displaystyle \underset{i\in I}{\sum }P\left(g_i\left(x^{\text{*}}\right)\right)}=0.$

结合 $P_{\epsilon }\left(t\right)$ 得

$0\le {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x^{\prime }\right)\right)}\le \frac{q}{p\left(p+q-1\right)}m\epsilon ,$

$\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }\left(g_i\left(x^{\prime }\right)\right)}\le f\left(x^{\text{*}}\right)-f\left(x^{\prime }\right)\le \frac{q\left(p-1\right)}{p\left(q-1\right)}m\rho \epsilon +\rho {\displaystyle \underset{i\in I}{\sum }{P}_{\epsilon }}\left(g_i\left(x^{\prime }\right)\right),$

$\left|f\left(x^{\text{*}}\right)-f\left(x^{\prime }\right)\right|\le \frac{q\left(p+q-2\right)}{\left(q-1\right)\left(p+q-1\right)}m\epsilon \rho ,$

因此 $x^{\prime }$ 是原问题(P)的近似最优解。结论得证。

3. 罚函数算法和收敛性分析

基于光滑化罚问题(SP)，提出如下求解问题(P)的一个罚函数算法。

定理3.1 假设 $\underset{\left|\right|x\left|\right|\to \infty }{\lim }f\left(x\right)=+\infty$ ，序列 $\left\{x_j\right\}$ 是由Algorithm I产生的，若 $\left\{F\left(x_j,{\rho }_j,{\epsilon }_j\right)\right\}$ 有界，则 $\left\{x_j\right\}$ 有

界，且 $\left\{x_j\right\}$ 的极限点是问题(P)的最优解。

证明：首先证 $\left\{x_j\right\}$ 有界。由 $\left\{F\left(x_j,{\rho }_j,{\epsilon }_j\right)\right\}$ 有界可知，存在一个数L使得

$F\left(x_j,{\rho }_j,{\epsilon }_j\right)\le L,\begin{array}{cc}& j=0,1,2,\cdots \end{array}$

即

$f\left(x_j\right)+{\rho }_j{\displaystyle \underset{i\in I}{\sum }{P}_{{\epsilon }_j}}\left(g_i\left(x_j\right)\right)\le L,\begin{array}{cc}& j=0,1,2,\cdots \end{array}$ (3.1)

假设 $\left\{x_j\right\}$ 无界，不失一般性，不妨设 $\Vert x_j\Vert \to +\infty \left(j\to \infty \right)$ ，由 $\underset{\Vert x\Vert \to \infty }{\lim }f\left(x\right)=+\infty$ 可知， $\underset{j\to \infty }{\lim }f\left(x_j\right)=+\infty$ ，

与式(3.1)矛盾，因此 $\left\{x_j\right\}$ 有界。

其次证 $\left\{x_j\right\}$ 的极限点是问题(P)的最优解。设 $\left\{x_j\right\}$ 的极限点是 $x^{\prime }$ ，即 $\underset{j\to \infty }{\lim }{x}_j=x^{\prime }$ 。下面我们分两步完成证明。

第一步，假设 $x^{\prime }$ 不是问题(P)的ε-可行解，则存在 $i_1\in I$ ， $\alpha >0$ 使得 $g_{i_{{}_1}}\left(x^{\prime }\right)\ge \alpha >\epsilon$ ，由 $P_{\epsilon }\left(t\right)$ 单调递增可知，

$f\left(x_j\right)+{\rho }_j\left(\alpha +\frac{\left(1-p\right){\epsilon }_j^q{\alpha }^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(1-q\right)}{\epsilon }_j\right)\le F\left(x_j,{\rho }_j,{\epsilon }_j\right)\le L,$ (3.2)

当 $j\to \infty$ 时，由Algorithm I知 ${\rho }_j\to +\infty$ ， ${\epsilon }_j\to 0$ ，即

$f\left(x_j\right)+{\rho }_j\left(\alpha +\frac{\left(1-p\right){\epsilon }_j^q{\alpha }^{1-q}}{\left(1-q\right)\left(p+q-1\right)}+\frac{q\left(p-1\right)}{p\left(1-q\right)}{\epsilon }_j\right)\to +\infty ,$ (3.3)

与式(3.2)矛盾，因此 $x^{\prime }$ 是原问题(P)的ε-可行解。

第二步，设 $x^{\text{*}}$ 是原问题(P)的最优解，由于序列 $\left\{x_j\right\}$ 是由Algorithm I产生的，则

$F\left(x_j,{\rho }_j,{\epsilon }_j\right)\le F\left(x^{\text{*}},{\rho }_j,{\epsilon }_j\right),\begin{array}{cc}& j=0,1,2,\cdots \end{array}$

即

$f\left(x_j\right)+{\rho }_j{\displaystyle \underset{i\in I}{\sum }{P}_{{\epsilon }_j}}\left(g_i\left(x_j\right)\right)\le f\left(x^{\text{*}}\right)+{\rho }_j{\displaystyle \underset{i\in I}{\sum }{P}_{{\epsilon }_j}}\left(g_i\left(x^{\text{*}}\right)\right)=f\left(x^{\text{*}}\right).$

由 $P_{\epsilon }\left(g_i\left(x_j\right)\right)>0$ 可知， $f\left(x_j\right)\le f\left(x^{\text{*}}\right)$ ，当 $j\to \infty$ 时，有 $f\left(x^{\prime }\right)\le f\left(x^{\text{*}}\right)$ 。又因为 $x^{\text{*}}$ 是原问题(P)的最优解，所以 $f\left(x^{\text{*}}\right)\le f\left(x^{\prime }\right)$ 。综上 $f\left(x^{\prime }\right)=f\left(x^{\text{*}}\right)$ ，结论得证。

4. 数值实验

下面通过求解5个不等式约束优化问题数值算例，验证Algorithm I的有效性，并与 $l_1$ 罚函数法、 $l_2$ 罚函数法以及文献 [5] [7] [8] [10] 罚函数算法的数值结果进行比较。在式(2.1)中取p = 3，q = 7。

例4.1 考虑如下约束优化问题(文献 [13] 中的例4.1)

$\begin{array}{l}\min \begin{array}{cc}& f\left(x\right)=x_1^2+x_2^2+2x_3^2+x_4^2-5x_1-5x_2-21x_3+7x_4\end{array},\\ \text{s}\text{.t}.\begin{array}{cc}& g_1\left(x\right)=\end{array}2x_1^2+x_2^2+x_3^2+2x_1+x_2+x_4-5\le 0,\\ \begin{array}{ccc}& & g_2\left(x\right)=x_1^2+x_2^2+x_3^2+x_4^2+x_1-x_2+x_3-x_4-8\le 0,\end{array}\\ \begin{array}{ccc}& & g_3\left(x\right)=x_1^2+2x_2^2+x_3^2+2x_4^2-x_1-x_4-10\le 0.\end{array}\end{array}$

令 $x_0=\left(0,0,0,0\right),{\epsilon }_0=0.0001,{\rho }_0=5,N=2,\eta =0.01,\epsilon ={10}^{-6}$ 。数值实验结果如表1所示，其中文献 [7] 的算法结果不收敛，Algorithm I所得目标函数值最小，且最小值为−44.233837585，迭代次数为2次。

表1. 例4.1对比结果

例4.2 考虑如下约束优化问题(文献 [14] 中的例4.1)

$\begin{array}{l}\min \begin{array}{cc}& f\left(x\right)=x_1^2+x_2^2\end{array},\\ \text{s}\text{.t}.\begin{array}{cc}& g_1\left(x\right)=\end{array}{x}_1^2-x_2\le 0,\\ \begin{array}{ccc}& & \begin{array}{cc}{g}_2\left(x\right)=-x_1\le 0.& \end{array}\end{array}\end{array}$

令 $x_0=\left(2,2\right),{\epsilon }_0=0.1,{\rho }_0=1,N=2,\eta =0.01,\epsilon ={10}^{-6}$ 。数值实验结果如表2所示，Algorithm I、 $l_1$ 、 $l_2$ 、文献 [8] 和文献 [10] 都能计算出目标函数值最小值，且最小值均为0，迭代次数均为1次。

表2. 例4.2对比结果

例4.3 考虑如下约束优化问题(文献 [15] 中的例3.3)

$\begin{array}{l}\min \begin{array}{cc}& f\left(x\right)=-2x_1-6x_2+x_1^2-2x_1{x}_2+2x_2^2\end{array},\\ \text{s}\text{.t}\text{.}\begin{array}{cc}& g_1\left(x\right)=\end{array}{x}_1+x_2-2\le 0,\\ \begin{array}{ccc}& & g_2\left(x\right)=-x_1+2x_2-2\le 0,\end{array}\\ \begin{array}{ccc}& & g_3\left(x\right)=-x_1\le 0,\end{array}\\ \begin{array}{ccc}& & g_3\left(x\right)=-x_2\le 0.\end{array}\end{array}$

令 $x_0=\left(0,0\right),{\epsilon }_0=0.1,{\rho }_0=5,N=2,\eta =0.01,\epsilon ={10}^{-6}$ 。数值实验结果如表3所示，其中 $l_2$ 、文献 [8] 、文献 [10] 的算法结果不收敛，Algorithm I所得目标函数值最小，且最小值为−7.200000084，迭代次数为4次。

表3. 例4.3对比结果

例4.4 考虑如下约束优化问题

$\begin{array}{l}\min \begin{array}{cc}& f\left(x\right)=9-8x_1-6x_2-4x_3+2x_1^2+2x_2^2+2x_3^2+2x_1{x}_2+2\end{array}{x}_1{x}_3,\\ \text{s}\text{.t}\text{.}\begin{array}{cc}& g_1\left(x\right)=\end{array}{x}_1+x_2+2x_3-3\le 0.\end{array}$

令 $x_0=\left(0,0,0\right),{\epsilon }_0=0.1,{\rho }_0=2,N=4,\eta =0.01,\epsilon ={10}^{-6}$ 。数值实验结果如表4所示，其中文献 [10] 的算法结果不收敛，Algorithm I所得目标函数值最小，且最小值为0.11111090，迭代次数为3次。

表4. 例4.4对比结果

例4.5 考虑如下约束优化问题

$\begin{array}{l}\min \begin{array}{cc}& f\left(x\right)={\left(x_1-1\right)}^2+{\left(x_2-2\right)}^2\end{array},\\ \text{s}\text{.t}.\begin{array}{cc}& g_1\left(x\right)=\end{array}-x_1+x_2-1\le 0,\\ \begin{array}{ccc}& & g_2\left(x\right)=x_1+x_2-2\le 0,\end{array}\\ \begin{array}{ccc}& & g_3\left(x\right)=-x_1\le 0,\end{array}\\ \begin{array}{ccc}& & g_3\left(x\right)=-x_2\le 0.\end{array}\end{array}$

令 $x_0=\left(0,0\right),{\epsilon }_0=0.1,{\rho }_0=2,N=10,\eta =0.01,\epsilon ={10}^{-6}$ 。数值实验结果如表5所示，其中文献 [8] 的算法结果不收敛，Algorithm I所得目标函数值最小，且最小值为0.499999198，迭代次数为3次。

表5. 例4.5对比结果

从这5个数值例子可以看出，Algorithm I所得目标函数值是最小的，因此其对于求解不等式约束优化问题的最优解是有效的。

5. 结论

本文提出了一类新的光滑化 $l_1$ 精确罚函数，其具有二阶连续可微性质。并且证明了对应算法的全局收敛性。最后通过数值实验说明了该算法的有效性。

文章引用

瞿小敏. 一类新的光滑化l₁精确罚函数法
A New Smooth l₁ Exact Penalty Function Methods[J]. 应用数学进展, 2023, 12(05): 2582-2592. https://doi.org/10.12677/AAM.2023.125259

参考文献