约束优化求解之罚函数法

这篇具有很好参考价值的文章主要介绍了约束优化求解之罚函数法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

罚函数法

本部分考虑约束优化问题:
min ⁡ f ( x ) s . t . x ∈ χ (1) \begin{aligned} \min f(x) \\ s.t. x\in\chi \end{aligned} \tag{1} minf(x)s.t.xχ(1)
这里 χ ⊂ R n \chi\subset\mathbb{R}^n χRn为问题的可行域。与无约束问题不同,约束优化问题中自变量 x x x不能任意取值,这导致无约束优化算法不能使用。例如梯度法中沿着梯度负方向下降所得的点未必是可行点,要寻找最优解处目标函数的梯度也不是零向量。这使得约束优化问题比无约束优化问题要复杂许多。本部分要介绍的罚函数法将约束作为惩罚项加到目标函数中,从而转化为我们熟悉的无约束优化问题求解。

一、等式约束的二次罚函数法
面对约束优化问题,我们试图通过变形将问题(1)转化为无约束问题来求解。一种简单的情况是,假设问题约束中仅含灯饰约束,即考虑问题
min ⁡ x f ( x ) s . t . c i ( x ) = 0 , i ∈ E (2) \begin{aligned} &\min_{x}f(x) \\ &s.t.\quad c_i(x)=0, i\in\mathcal{E} \end{aligned}\tag{2} xminf(x)s.t.ci(x)=0,iE(2)
其中变量 x ∈ R n , E x\in\mathbb{R}^n,\mathcal{E} xRn,E为等式约束的指标集, c i ( x ) c_i(x) ci(x)为连续函数。在某些特殊场合下,可以通过直接求解(非线性方程组) c i ( x ) = 0 c_i(x)=0 ci(x)=0消去部分变量,将其转化为无约束优化问题。但是对于一般函数来说,变量消去这一操作很难实现,我们必须采用其他方法来处理这种问题。
罚函数法的思想是将约束优化问题(1)转化为无约束优化问题来进行求解。为了保证解的逼近质量,无约束优化问题的目标函数为原约束优化问题的目标函数加上与约束函数有关的惩罚项。对于可行域外的点,惩罚项为正,即对该点进行惩罚;对于可行域内的点,惩罚项为0,即不做任何惩罚。因此惩罚项会促使无约束优化问题的解落在可行域内。
对于灯饰约束问题,惩罚项的选取方式有很多,结构最简单的是二次函数,这里给出二次罚函数的定义,
对于等式约束最优化问题(1),定义二次罚函数
P E ( x , σ ) = f ( x ) + 1 2 ∑ i ∈ E c i 2 ( x ) P_E(x,\sigma)=f(x)+\frac{1}{2}\sum_{i\in\mathcal{E}}c_i^2(x) PE(x,σ)=f(x)+21iEci2(x)
其中灯饰右端第二项称为惩罚项, σ > 0 \sigma>0 σ>0称为惩罚因子。
由于这种罚函数对不满足约束的点进行惩罚,在迭代过程中点列一般处于可行域外,因此它也被称为外点罚函数。二次罚函数的特点如下:对于非可行点而言,当 σ \sigma σ变大时,惩罚项在发函数中的权重加大,对罚函数求绩效,相当于迫使其极小点向可行域靠近;在可行域中, P E ( x , σ ) P_E(x,\sigma) PE(x,σ)的全局极小点于约束问题(1)的最优解相同。

举例1
考虑优化问题
min ⁡ x + 3 y s . t . x 2 + y 2 = 1 \begin{aligned} &\min\quad x + \sqrt{3}y \\ &s.t. \quad x^2 + y^2 = 1 \end{aligned} minx+3 ys.t.x2+y2=1
容易求出改问题的最优解为 ( − 1 2 , − 3 2 ) (-\frac{1}{2},-\frac{\sqrt{3}}{2}) (21,23 )。考虑二次罚函数
P E ( x , y , σ ) = x + 3 y + σ 2 ( x 2 + y 2 − 1 ) 2 , P_E(x,y,\sigma)=x+\sqrt{3}y+\frac{\sigma}{2}(x^2+y^2-1)^2, PE(x,y,σ)=x+3 y+2σ(x2+y21)2,
在下图中绘制出 σ = 1 \sigma=1 σ=1 σ = 8 \sigma=8 σ=8对应的罚函数的等高线。可以看出,随着 σ \sigma σ增大,二次罚函数 P E ( x , y , σ ) P_E(x,y,\sigma) PE(x,y,σ)的最小值和原问题最小值越来越接近,但最优点附近的等高线越来越趋于扁平,这导致求解无约束优化问题的难度变大。此外,当 σ = 8 \sigma=8 σ=8时函数出现了一个极大值,罚函数图形在 ( − 1 2 , − 3 2 ) T (-\frac{1}{2},-\frac{\sqrt{3}}{2})^T (21,23 )T附近出现一个鞍点。

sigma = 1;


x = -2:0.01:2;
y = -2:0.01:1.5;

[X, Y] = meshgrid(x, y);
%X = X;
%Y = Y;
P_E = X + sqrt(3) * Y + sigma/2 * (X.^2+Y.^2-1).^2;

figure
subplot(121)
contour(X, Y, P_E, 80)


sigma = 8;
x = -2:0.01:2;
y = -2:0.01:1.5;

[X, Y] = meshgrid(x, y);
%X = X;
%Y = Y;
P_E = X + sqrt(3) * Y + sigma/2 * (X.^2+Y.^2-1).^2;
subplot(122)
contour(X, Y, P_E, 180)


约束优化求解之罚函数法

从以上例子知道,给定罚因子 σ \sigma σ,我们可通过求解 P E ( x , σ ) P_E(x,\sigma) PE(x,σ)的最小值点作为原问题的近似解。当实际情况并不总是这样,当 σ \sigma σ选取过小时罚函数可能无下届。

举例2
考虑优化问题
min ⁡ − x 2 + 2 y 2 s . t x = 1 \begin{aligned} &\min\quad -x^2+2y^2 \\ &s.t \quad x = 1 \end{aligned} minx2+2y2s.tx=1
通过消去变量容易得知最优解就是 ( 1 , 0 ) T (1,0)^T (1,0)T。但考虑罚函数
P E ( x , y , σ ) = − x 2 + 2 y 2 + σ 2 ( x − 1 ) 2 , P_E(x,y,\sigma)=-x^2+2y^2+\frac{\sigma}{2}(x-1)^2, PE(x,y,σ)=x2+2y2+2σ(x1)2,
对任意的 σ ≤ 2 \sigma\le 2 σ2,该罚函数是无界的。

出现以上现象的原因时当罚因子过小时,不可行点处的函数下降抵消了罚函数对约束违反的惩罚。实际上所有外点罚函数法均存在这个问题,因此 σ \sigma σ的初值选取不应该太小。
我们在这里给出等式约束罚函数法的算法,之后再对每一步进行具体解释。


二次罚函数法

  1. 给定 σ 1 > 0 , x 0 , k ← 1 \sigma_1>0,x^0,k\leftarrow 1 σ1>0,x0,k1,罚因子增长系数 ρ > 0 \rho > 0 ρ>0
  2. while 未达到收敛准则 do
  3. x k x^k xk为初始点,求解 x k + 1 = a r g min ⁡ x P E ( x , σ k ) x^{k+1}=arg\min_{x}P_E(x,\sigma_k) xk+1=argminxPE(x,σk)
  4. 选取 σ k + 1 = ρ σ k \sigma_{k+1}=\rho\sigma_k σk+1=ρσk
  5. k ← k + 1 k\leftarrow k+1 kk+1
  6. end while

算法的执行过程比较直观:即先选取一系列指数增长的罚因子 σ k \sigma_k σk,然后针对每个罚因子求解二次罚函数

约束优化求解之罚函数法文章来源地址https://www.toymoban.com/news/detail-417909.html

到了这里,关于约束优化求解之罚函数法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 详细介绍如何使用Ipopt非线性求解器求解带约束的最优化问题

       本文中将详细介绍如何使用Ipopt非线性求解器求解带约束的最优化问题,结合给出的带约束的最优化问题示例,给出相应的完整的C++程序,并给出详细的解释和注释,以及编译规则等    一、Ipopt库的安装和测试    本部分内容在之前的文章《Ubuntu20.04安装Ipopt的流程介

    2024年02月08日
    浏览(75)
  • 机器学习笔记之最优化理论与方法(九)无约束优化问题——常用求解方法(下)

    上一节介绍了 牛顿法、拟牛顿法 。本节将继续以 拟牛顿法 为基础,介绍 DFP , BFGS text{DFP},text{BFGS} DFP , BFGS 方法 。 经典牛顿法缺陷与修正牛顿法 关于 经典牛顿法 中关于 下降方向 D k ( k = 1 , 2 , ⋯   , ∞ ) mathcal D_k(k=1,2,cdots,infty) D k ​ ( k = 1 , 2 , ⋯ , ∞ ) 的 数学符号 表

    2024年02月09日
    浏览(54)
  • 机器学习笔记之最优化理论与方法(七)无约束优化问题——常用求解方法(上)

    本节将介绍 无约束优化问题 的常用求解方法,包括 坐标轴交替下降法、最速下降法 。 本节是对优化算法(十~十七)最速下降法(梯度下降法)的理论补充,其中可能出现一些定理的 证明过程 这里不再赘述,并在相应位置 附加链接 。 从本节开始,将介绍 四大类 无约束优化问

    2024年02月10日
    浏览(52)
  • 基于梯度下降算法的无约束函数极值问题求解

    导数(Derivative),也叫 导函数值 。又名 微商 ,是微积分中的重要基础概念。 导数是函数的局部性质。一个函数在某一点的导数描述了这个函数在这一点附近的变化率 。如果函数的自变量和取值都是实数的话,函数在某一点的导数就是该函数所代表的曲线在这一点上的切线

    2024年02月13日
    浏览(50)
  • 利用 MATLAB 编程实现乘子法求解约束最优化问题。 拟 Newton 法

    1、画出 PH 法的算法流程图; 2、MATLAB 编写 PH 法求解约束优化问题的函数,无约束子问题用精确一 维搜索的拟 Newton 法((函数式 M 文件,精度设为 epson 可调);编写程序(命 令式 M 文件),调用 PH 法,求解如下问题:   初始点取(10,10),按教材 P217,例 12 取不同的参

    2024年02月11日
    浏览(51)
  • Python中scipy.optimize求解有无约束的最优化算法举例(附代码)

    目录 算法需要输入的参数 算法输出的优化结果 优化算法应用举例 优化算法举例代码  优化算法输出结果  其他优化问题举例 最优化求解问题标准格式如下:  Python中scipy库有很多包,其中一个就是scipy.optimize.minimize求解有无约束的最小化问题。 原文请参考: scipy.optimize.m

    2024年02月09日
    浏览(51)
  • 【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)

    💥💥💞💞 欢迎来到本博客 ❤️❤️💥💥 🏆博主优势: 🌞🌞🌞 博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️ 座右铭: 行百里者,半于九十。 📋📋📋 本文目录如下: 🎁🎁🎁 目录 💥1 概述 📚2 运行结果 2.1 CCGKKT 2.2  CCGSD 2.3  SPKKT 2.4 SDSP 2.5 

    2023年04月15日
    浏览(58)
  • matlab进阶:求解在约束条件下的多元目标函数最值(fmincon函数详解)

    欢迎来到馒头侠的博客,该类目主要讲数学建模的知识,大家一起学习,联系最后的横幅! 喜欢的朋友可以关注下,私信下次更新不迷路! 资源链接:点击这里获取众多源码、数模资料、思路精讲、论文模板latex和word、学习书籍等 Matlab 的 fmincon 函数: 寻找约束非线性多变

    2024年02月11日
    浏览(46)
  • 通用的改进遗传算法求解带约束的优化问题(MATLAB代码精讲、实际工程经验分享)

    在对多约束、非线性问题的求解上,传统线性规划等方法往往无法有效求解(求解时间过长、无法处理非线性约束等。 进化算法是一类强有力的工具,已经在多个领域有了较为成功的应用。然而,在利用遗传算法、粒子群等等进化算法求解实际的优化问题时,还存在许多困难

    2023年04月19日
    浏览(86)
  • 【运筹优化】带时间窗约束的车辆路径规划问题(VRPTW)详解 + Python 调用 Gurobi 建模求解

    车辆路径规划问题(Vehicle Routing Problem,VRP)一般指的是:对一系列发货点和收货点,组织调用一定的车辆,安排适当的行车路线,使车辆有序地通过它们,在满足指定的约束条件下(例如:货物的需求量与发货量,交发货时间,车辆容量限制,行驶里程限制,行驶时间限制等)

    2024年02月02日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包