自学内容网 自学内容网
自学内容网 > 正文

最优化方法_罚函数法

🕗 发布于 2024-11-19 15:38 算法  笔记  学习  

目录

序言

1 外点罚函数

2 内点罚函数法

3 广义乘子法

3.1 等式约束问题的广义乘子罚函数法

3.2 不等式约束问题的广义乘子罚函数法

3.3 一般约束问题的广义乘子罚函数法

序言

罚函数方法的基本思想是借助罚函数将约束问题转化为无约束优化问题，进而通过求解一系列无约束最优化问题来获取原约束问题的解。迭代过程中，罚函数法 通过对不可行点施加惩罚，迫使迭代点向可行域靠近。一旦迭代点成为可行点，则 这个可行点就是原问题的最优解。

采用不同的罚函数，就形成不同的罚方法。同时，我们是将求解约束问题转化为求解一系列无约束问题，从而获得原问题的逼近最优解。因此该方法也称为序列无约束极小化方法。

1 外点罚函数

我们考虑如下优化问题：

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20h_%7Bi%7D%28x%29%3D0%2Ci%5Cin%20%5Cvarepsilon

            eq?g_%7Bj%7D%28x%29%5Cgeq%200%2Cj%5Cin%20L

其中eq?%5Cvarepsilon%20%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cm%20%5Cright%20%5C%7D%2CL%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cl%20%5Cright%20%5C%7D。

一般地，罚函数是由目标函数及约束函数所构成的一辅助函数

eq?F%28x%2C%5Csigma%20%29%3Df%28x%29+%5Csigma%20P%28x%29

其中σ为一很大的正常数，称为罚因子，σP(x)称为罚项，且P(x)需满足

  1. P(x)为连续函数。
  2. 对所有eq?x%5Cin%20R%5E%7Bn%7D%2CP%28x%29%5Cgeq%200。
  3. eq?P%28x%29%3D0当且仅当x为问题可行点。

我们定义函数：

eq?P%28x%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bm%7D%5Cvarphi%20%28h_%7Bi%7D%28x%29%29+%5Csum_%7Bj%3D1%7D%5E%7Bl%7D%5Cpsi%20%28g_%7Bj%7D%28x%29%29

其中eq?%5Cvarphi%28x%20%29%2C%5Cpsi%28x%29满足

eq?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20%5Cvarphi%20%28x%29%3D0%2Cx%3D0%5C%5C%20%5Cvarphi%20%28x%29%3E%200%2Cx%5Cneq%200%2C%20%5Cend%7Bmatrix%7D%5Cright.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20%5Cpsi%20%28x%29%3D0%2Cx%5Cgeq%200%5C%5C%20%5Cpsi%20%28x%29%3E%200%2Cx%3C%200.%20%5Cend%7Bmatrix%7D%5Cright.

例如，我们取函数eq?%5Cvarphi%28x%20%29%2C%5Cpsi%28x%29为

eq?%5Cvarphi%20%28x%29%3D%5Cleft%20%7C%20h_%7Bi%7D%28x%29%20%5Cright%20%7C%5E%7B%5Calpha%20%7D%20%5C%5C%20%5Cpsi%20%28x%29%3D%20%5Bmax%5Cleft%20%5C%7B%200%2C-g_%7Bi%7D%28x%29%20%5Cright%20%5C%7D%5D%5E%7B%5Cbeta%20%7D

其中α≥1,β ≥1。通常我们设定α=β=2。

利用我们定义的函数P(x)，我们取一个趋向无穷大的严格递增正数序列{eq?%5Calpha%20_%7Bk%7D},将求解有约束问题转换为求解如下无约束问题：

eq?minF%28x%2C%5Csigma%20%29%3Df%28x%29+%5Calpha%20_%7Bk%7DP%28x%29

方法的优点在于初始点的选择没有可行性限制，且随着σ增大，迭代从可行域外部逼 近约束问题的最优解。我们把这种利用罚函数生成一系列外点逼近该约束问题最优 解的方法称为外点罚函数法。

具体计算步骤如下：

算法1 外点罚函数法

  1. 给定初点eq?x%5E%7B%281%29%7D%5Cin%20R%5E%7Bn%7D，初始罚因子eq?%5Csigma%20_%7B1%7D,放大系数eq?%5Cgamma%20%3E1，允许误差eq?%5Cvarepsilon%20%3E0，置k=1。
  2. 以eq?x%5E%7B%28k%29%7D为初始点，求解无约束问题eq?minF%28x%2C%5Csigma%20%29得最优解eq?x%5E%7B%28k+1%29%7D。
  3. 如果eq?%5Csigma%20_%7Bk%7DP%28x%5E%7B%28k+1%29%7D%29%3C%5Cvarepsilon,则停止计算，eq?x%5E%7B%28k+1%29%7D为约束问题的近似最优解；否 则，增大罚因子eq?%5Csigma%20_%7Bk+1%7D%3D%5Cgamma%20%5Csigma%20_%7Bk%7D，令k=k+1,转步骤2。

定理 1 设约束最优化存在最优解，其中 eq?f%28x%29%2Ch_%7Bi%7D%2Cg_%7Bj%7D为实值连续函数，eq?%5Cleft%20%5C%7B%20%5Csigma%20_%7Bk%7D%20%5Cright%20%5C%7D为严格递增正数列且趋向于无穷大的数列，序列eq?%5Cleft%20%5C%7B%20x%5E%7B%28k%29%7D%20%5Cright%20%5C%7D 由算法1 外点罚函数产生，则序eq?%5Cleft%20%5C%7B%20x%5E%7B%28k%29%7D%20%5Cright%20%5C%7D的任何极限点是问题优化的解。

2 内点罚函数法

内点罚函数法是一类保持严格可行性的方法，它总是从可行点出发，并保持 在可行域内部进行搜索。因而这类方法只适用于只有不等式约束的非线性最优化问题：

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20g_%7Bi%7D%28x%29%5Cgeq%200%2Ci%5Cin%20L

其中eq?L%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cl%20%5Cright%20%5C%7D。

内点罚函数法的基本思想为在目标函数上引入一个关于约束的障碍项，当迭代 点由可行域的内部接近可行域的边界时,障碍项将趋于无穷大来迫使迭代点返回可行 域的内部,从而保持迭代点的严格可行性。进而将求解约束问题转为求解一系列容易 的子问题，从而获得原问题的最优逼近解。方法也称为内点障碍函数法。

记优化问题的可行域F，可行域的内部

eq?int%5C%3B%20F%3D%5Cleft%20%5C%7B%20x%5Cin%20R%5E%7Bn%7D%7Cg_%7Bi%7D%3E0%2Ci%5Cin%20L%20%5Cright%20%5C%7D

对于优化问题，障碍函数B(x)一般满足：

  1. 在eq?int%5C%3B%20F中连续
  2. 当x趋于eq?int%5C%3B%20F边界，eq?B%28x%29%5Crightarrow%20%5Cinfty

两种常用的障碍函数形式为

  1. 倒数障碍函数eq?B%28x%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bl%7D%5Cfrac%7B1%7D%7Bg_%7Bi%7D%28x%29%7D
  2. 对数障碍函数eq?B%28x%29%3D-%5Csum_%7Bi%3D1%7D%5E%7Bl%7Dlng_%7Bi%7D%28x%29

由障碍函数，我们可以定义罚函数

eq?F%28x%2C%5Cmu%20%29%3Df%28x%29+%5Cmu%20B%28x%29

其中 µ 是很小的数。则当 x 趋于边界时，eq?F%28x%2C%5Cmu%20%29%5Crightarrow%20+%5Cinfty，否则，当 µ 很小 时，F(x,µ) 的数值近似于 f(x)。因此，我们可以通过求解

eq?min%5C%3B%20%5C%3B%20F%28x%2C%5Cmu%20_%7Bk%7D%29%20%5C%5Cs.t.%5C%3B%20%5C%3B%20x%5Cin%20int%5C%3B%20F

具体步骤如下：

算法2 内点罚函数

  1. 给定初点eq?x%5E%7B%281%29%7D%5Cin%20int%5C%3B%20F,初始罚函数因子eq?%5Cmu%20_%7B1%7D缩小系数eq?%5Cgamma%20%3C1，允许误差eq?%5Cvarepsilon%20%3E0，置k=1。
  2. 以eq?x%5E%7B%28k%29%7D为初始点，求解无约束问题eq?min%5C%3B%20%5C%3B%20F%28x%2C%5Cmu%20_%7Bk%7D%29得最优解eq?x%5E%7B%28k+1%29%7D。
  3. 如果eq?%5Cmu%20_%7Bk%7DB%28x%5E%7B%28k+1%29%7D%29%3C%5Cvarepsilon,则停止计算，eq?x%5E%7B%28k+1%29%7D为约束问题的近似最优解；否 则，增大罚因子eq?%5Csigma%20_%7Bk+1%7D%3D%5Cgamma%20%5Csigma%20_%7Bk%7D，令k=k+1,转步骤2。

定理2 设约束最优化的可行域内部eq?int%5C%3B%20F非空且存在最优解，其中eq?f%28x%29%2Cg_%7Bi%7D为实值连续函数，eq?%5Cleft%20%5C%7B%20%5Cmu%20_%7Bk%7D%20%5Cright%20%5C%7D 为严格递减正数列且趋向于零的数列， 序列eq?%5Cleft%20%5C%7B%20x%5E%7B%28k%29%7D%20%5Cright%20%5C%7D 由算法2 内点罚函数产生，则序eq?%5Cleft%20%5C%7B%20x%5E%7B%28k%29%7D%20%5Cright%20%5C%7D的任何极限点是问题优化的解。

3 广义乘子法

广义乘子法的基本思为把外点罚函数与Lagrange函数结合起来，构造出新罚函 数，使得在罚因子适当大的情况下，借助于Lagrange乘子就能逐步达到原约束问题的最优解。

3.1 等式约束问题的广义乘子罚函数法

我们首先考虑等式约束问题

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20h_%7Bi%7D%28x%29%3D0%2Ci%5Cin%20%5Cvarepsilon

其中eq?%5Cvarepsilon%20%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cm%20%5Cright%20%5C%7D

记

eq?h%28x%29%3D%5Cbegin%7Bpmatrix%7D%20h_%7B1%7D%28x%29%5C%5C%20%5Cvdots%20%5C%5C%20h_m%28x%29%20%5Cend%7Bpmatrix%7D%2Cv%3D%5Cbegin%7Bpmatrix%7D%20v_%7B1%7D%5C%5C%20%5Cvdots%20%5C%5C%20v_%7Bm%7D%5Cend%7Bpmatrix%7D

定义乘子罚函数：

eq?%5Cphi%20%28x%2Cv%2C%5Csigma%20%29%3Df%28x%29-%5Csum_%7Bi%3D1%7D%5E%7Bm%7Dv_%7Bi%7Dh_%7Bi%7D%28x%29+%5Cfrac%7B%5Csigma%20%7D%7B2%7D%5Csum_%7Bi%3D1%7D%5E%7Bm%7Dh_%7Bi%7D%5E%7B2%7D%28x%29%5C%5C%3Df%28x%29-v%5E%7BT%7Dh%28x%29+%5Cfrac%7B%5Csigma%20%7D%7B2%7Dh_%7B%28x%29%7D%5E%7BT%7Dh%28x%29

进而我们可以通过求解

eq?min%5C%3B%20%5Cphi%20%28x%2Cv%2C%5Csigma%20%29

获得原函数的局部最优解。

函数3 等式约束问题的广义乘子罚函数法

  1. 给定初点eq?x%5E%7B%281%29%7D，初始乘子向量eq?v%5E%7B%281%29%7D,初始罚因子eq?%5Csigma%20_%7B1%7D，放大系数eq?%5Cgamma%20%3C1，允许误差eq?%5Cvarepsilon%20%3E0，置k=1。
  2. 以eq?x%5E%7B%28k%29%7D为初始点，固定eq?v%3Dv%5E%7B%28k%29%7D求解无约束问题eq?min%5C%3B%20%5Cphi%20%28x%2Cv%2C%5Csigma%20%29得最优解eq?x%5E%7B%28k+1%29%7D。
  3. 如果eq?%5Cleft%20%5C%7C%20h%28x%5E%7B%28k+1%29%7D%29%20%5Cright%20%5C%7C%3C%5Cvarepsilon，则停止计算，eq?x%5E%7B%28k+1%29%7D为约束问题eq?min%20f%28x%29的近似最优解；否 则，进行步骤4。
  4. 若eq?%5Cfrac%7B%5Cleft%20%5C%7C%20h%28x%5E%7B%28k+1%29%7D%29%20%5Cright%20%5C%7C%7D%7B%5Cleft%20%5C%7C%20h%28x%5E%7B%28k%29%7D%29%20%5Cright%20%5C%7C%7D%5Cgeq%20%5Cbeta，令eq?%5Csigma%20_%7Bk+1%7D%3D%5Cgamma%20%5Csigma%20_%7Bk%7D，否则转步骤5;否则，进行步骤5。
  5. 用eq?v_%7Bi%7D%5E%7B%28k+1%29%7D%3Dv_%7Bi%7D%5E%7B%28k%29%7D-%5Csigma%20h_%7Bi%7D%28x%5E%7B%28k%29%7D%29%2Ci%3D1%2C...%2Cm更新乘子，令k=k+1,转步骤2.

3.2 不等式约束问题的广义乘子罚函数法

考虑不等式约束问题

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20g_%7Bi%7D%28x%29%5Cgeq%200%2Ci%5Cin%20L

其中eq?L%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cl%20%5Cright%20%5C%7D，为应用等式约束问题的广义乘子方法，我们引入变量eq?y_%7Bi%7D%5Cgeq%200,将 不等式约束问题化为如下等式约束问题

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3A%20%5C%3B%20%5C%3B%20g_%7Bi%7D%28x%29-y_%7Bi%7D%3D0%2Ci%5Cin%20L

由上式定义Lagrange函数

1dc47c4620c741a48259d345f781257f.png

将eq?%5Cvarphi%20%28x%2Cy%2Cv%2C%5Csigma%20%29关于y极小化，且由eq?y_%7Bi%7D%5Cgeq%200,我们有

9326645bee6a4e66881b87fcee16ab18.png

即

661216413fcc4d15ab5c5bae7a744de6.png

带入到Lagrange函数得

37b18bdcc4334a4f9b9e410bfcb7ee73.png

则我们可以通过Lagrange函数极小化问题，获得原问题的逼近最优解。同时类似等式约束问题 的方法，我们可以获得乘子得更新公式为

be1bf204492b478a9c214b3111d22403.png

算法4 不等式约束问题的广义乘子罚函数法

  1. 给定初点eq?x%5E%7B%281%29%7D，初始乘子向量eq?v%5E%7B%281%29%7D,初始罚因子eq?%5Csigma%20_%7B1%7D，放大系数eq?%5Cgamma%20%3C1，允许误差eq?%5Cvarepsilon%20%3E0，置k=1。
  2. 以eq?x%5E%7B%28k%29%7D为初始点，固定eq?v%3Dv%5E%7B%28k%29%7D求解无约束问题eq?min%5C%3B%20%5Cvarphi%20%28x%2Cv%2C%5Csigma%20%29得最优解eq?x%5E%7B%28k+1%29%7D。
  3. 如果eq?%5Cleft%20%5C%7C%20max%5Cleft%20%5C%7B%200%2C-g%28x%5E%7B%28k+1%29%7D%29%20%5Cright%20%5C%7D%5Cright%20%5C%7C%3C%5Cvarepsilon，则停止计算，eq?x%5E%7B%28k+1%29%7D为约束问题eq?min%20f%28x%29的近似最优解；否 则，进行步骤4。
  4. 若eq?%5Cfrac%7B%5Cleft%20%5C%7C%20max%5Cleft%20%5C%7B%200%2C-g%28x%5E%7B%28k+1%29%7D%29%20%5Cright%20%5C%7D%5Cright%20%5C%7C%7D%7B%5Cleft%20%5C%7C%20max%5Cleft%20%5C%7B%200%2C-g%28x%5E%7B%28k%29%7D%29%20%5Cright%20%5C%7D%5Cright%20%5C%7C%7D%5Cgeq%20%5Cbeta，令eq?%5Csigma%20_%7Bk+1%7D%3D%5Cgamma%20%5Csigma%20_%7Bk%7D，否则转步骤5;否则，进行步骤5。
  5. 用eq?v_%7Bi%7D%5E%7B%28k+1%29%7D%3Dmax%280%2Cv_%7Bi%7D%5E%7B%28k%29%7D-%5Csigma%20g_%7Bi%7D%28x%5E%7B%28k%29%7D%29%29%2Ci%3D1%2C...%2Cl更新乘子，令k=k+1,转步骤2.

3.3 一般约束问题的广义乘子罚函数法

对于一般约束问题

eq?min%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20f%28x%29

eq?s.t.%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20%5C%3B%20h_%7Bi%7D%28x%29%3D0%2Ci%5Cin%20%5Cvarepsilon

            eq?g_%7Bj%7D%28x%29%5Cgeq%200%2Cj%5Cin%20L

其中eq?%5Cvarepsilon%20%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cm%20%5Cright%20%5C%7D%2CL%3D%5Cleft%20%5C%7B%201%2C2%2C...%2Cl%20%5Cright%20%5C%7D。我们综合以上两种情形得到增广Lagrange函数

4130d268746443a4aedf9e7500001432.png

同时也可得到乘子w,v的更新

d5137a27e9fe4f6a9a637481d26551ff.png

记eq?c%28x%29%3D%5Cleft%20%5C%7C%20h%28x%29%20%5Cright%20%5C%7C+%5Cleft%20%5C%7C%20max%5Cleft%20%5C%7B%200%2C-g%28x%29%20%5Cright%20%5C%7D%20%5Cright%20%5C%7C则计算步骤为：

算法5 一般约束问题的广义乘子罚函数法

  1. 给定初点eq?x%5E%7B%281%29%7D，初始乘子向量eq?v%5E%7B%281%29%7D,初始罚因子eq?%5Csigma%20_%7B1%7D，放大系数eq?%5Cgamma%20%3E%201，常数eq?%5Cbeta%20%5Cin%20%280%2C1%29允许误差eq?%5Cvarepsilon%20%3E0，置k=1。
  2. 以eq?x%5E%7B%28k%29%7D为初始点，固定eq?v%3Dv%5E%7B%28k%29%7D求解无约束问题eq?min%5C%3B%20%5Cvarphi%20%28x%2Cw%2Cv%2C%5Csigma%20%29得最优解eq?x%5E%7B%28k+1%29%7D。
  3. 如果eq?c%28x%5E%7B%28k+1%29%7D%29%3C%5Cvarepsilon，则停止计算，eq?x%5E%7B%28k+1%29%7D为约束问题eq?min%20f%28x%29的近似最优解；否 则，进行步骤4。
  4. 若eq?%5Cfrac%7Bc%28x%5E%7B%28k+1%29%7D%29%7D%7Bc%28x%5E%7B%28k%29%7D%29%7D%5Cgeq%20%5Cbeta，令eq?%5Csigma%20_%7Bk+1%7D%3D%5Cgamma%20%5Csigma%20_%7Bk%7D，否则转步骤5;否则，进行步骤5。
  5. 用fd61f4ccf74d49d4bf9f273da4728c6c.png更新乘子,令k=k+1,转步骤2.

 

 

 


原文地址：https://blog.csdn.net/qq_58675332/article/details/143866252

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024