运筹说 第102期 | 非线性规划—制约函数法

2023-11-11 22:12

本文主要是介绍运筹说 第102期 | 非线性规划—制约函数法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

       通过上期学习,大家已经了解了非线性规划中约束极值问题的最优性条件。本期小编将为大家介绍约束极值问题的求解方法:制约函数法,包括概念以及最基本的两种制约函数法:罚函数法障碍函数法等内容。

图片

       制约函数法是通过构造某种制约函数,并将它加到非线性规划的目标函数上,从而将原来的约束极值问题,转化为无约束极值问题来求解。此处介绍的方法用来求解一系列无约束问题,故称为序列无约束极小化技术。

一、罚函数法

        对于非线性规划

图片

构造函数

图片

g_{j}(X)视为t,将约束条件的函数加到原目标函数中,构造新的目标函数:

图片

      新的目标函数转变为求解无约束问题,假定该问题极小点为X*,必有g_{j}(X)\geq 0X*是新构造无约束问题的极小点,同样也是原非线性规划问题的极小点。

       但是,如上构造的函数ψ(t)在0处不连续,不可导,这就无法使用很多有效的无约束极值极小化方法进行求解。因此将其修改为

图片

       修改后的ψ(t)处处可导,ψ(t)ψ′(t)处处连续。这时,修改后的函数的极小点不一定就是原非线性规划问题的极小点。于是,选取很大的实数M>0,作为惩罚因子,则得到

图片

该式也可以写成另一种形式

图片

在这个式子中,M称为惩罚因子M\sum_{j=1}^{l}\Psi (g_{j}(\mathbf{X}))为惩罚项,P(X,M)罚函数

X∈R时,P(X,M)=P(X);当X∉R时,M\sum_{j=1}^{l}\Psi (g_{j}(\mathbf{X)})就会很大,离可行域越远,惩罚越大。当M足够大时,是新构造无约束问题的极小点,同样也是原非线性规划问题的极小点。

       现引进阶跃函数

图片

得到如下转变

图片

       随着罚因子M增大,惩罚项起到的作用就越大,minP(X,M)越趋近于可行域d_{0},当0<M1<M2<...Mk<...,趋于无穷大时,点列\left \{ \mathbf{X}(M_{k}) \right \}会从可行域R的外部趋于原非线性规划的问题的极小点(此处假设点列\left \{ \mathbf{X}(M_{k}) \right \}收敛)。

       和不等式约束问题类似,对于等式约束问题,也可做如下变换:

图片

对于既含有等式约束,又有不等式约束的一般非线性规划问题

图片

其罚函数为

图片

图片

迭代步骤

       (1)取第一个罚因子M_{1}>0,允许ε>0,并令k:=1。

       (2)求下述无约束极值问题的最优解:minP(\mathbf{X},M_{k}),设其极小点为\mathbf{X}^{(k)}

       (3)若存在某一个j (1≤jl),有-g_{j}(X)>\varepsilon,或(和)存在某一个(1≤im),有\left | h_{i} (X^{K})\right |> \varepsilon,则取M_{k+1}>M_{k}(例如M_{k+1}=cM_{k},c=5),并令K:=k+1。然后,转回第(2)步;否则停止迭代,得到所要的点\mathbf{X}^{(k)}

例题

       用罚函数法求解

图片

解:

(1)构造罚函数

图片

(2)对于固定的M,令

图片

对于不满足约束条件的点x,有

图片

(3)求得其极小点x(M)

图片

M=0,x(M)=1/2

M=1,x(M)=1/4

M=10,x(M)=1/22

M→∞,x(M)→0

因此,原约束问题的极小点x*=0

图片

二、障碍函数法

       对于罚函数而言,函数P(X,M)可在整个E_{n}空间内进行优化,迭代过程往往在可行域外进行,不能以中间结果作为近似解使用。同时,目标函数在可行域外的性质比较复杂,甚至没有定义,就无法使用罚函数法。

       障碍函数法与其不同,该方法要求迭代过程始终在可行域内进行。如果初始迭代点取在可行域内部(严格内点),在进行无约束极小化时,会阻止函数迭代到R的边界上,使迭代过程始终在可行域内部。此时的极小化是在不包括可行域边界的可行域开集上进行的,是一种具有无约束性质的极值问题,可用无约束极小化方法求解。

       考虑非线性规划

图片

       当X点从可行域R内部趋于边界时,至少有某一个约束函数g_{j}(X)(j=1,2,...,l)趋于0,从而得到倒数函数\sum_{j=1}^{l}\frac{1}{g_{j}(\mathbf{X})}以及(负)对数函数-\sum_{j=1}^{l}lg(g_{j}(\mathbf{X}))都无限增大。

把倒数函数或对数函数加到目标函数上,则能构成新目标函数。取实数并构成一系列无约束性质的极小化问题如下:

图片

其中

图片

图片

此处,R_{0}为严格内点的集合,即

图片

       上述式子中,r_{k}\sum_{j=1}^{l}\frac{1}{g_{j}(\mathbf{X})}r_{k}\sum_{j=1}^{l}lg(g_{j}(\mathbf{X}))被称为障碍项,此处r_{k}为障碍因\left (r_{k}>0\right ),函数\bar{P}(\mathbf{X},r_{k})障碍函数

       若从某一点X^{(0)}出发,按无约束极小化方法对问题进行迭代,随着障碍因子r_{k}减小,障碍项起到的作用越小,minP(X,M)求得的解会逐步逼近原约束问题的最小解。

r_{1}>r_{2}>...r_{k}>...>0

       因而,求得问题的解X(r_{k})就会逐步逼近原约束问题的极小解。若原问题在可行域R的边界上,则随着r_{k}的减小,所求得障碍函数的极小点会不断靠近R的边界,直到满足某一精度要求时为止。

迭代步骤

(1)取第一个障碍因子r_{1}>0,允许误差ε>0,并令k:=1。

(2)构造障碍函数,如下所示。

图片

(3)对障碍函数进行无约束极小化(注意,迭代点必须在R_{0}内),设极小解为X^{(k)}\in R_{0}

(4)检查是否满足收敛准则:

图片

满足则停止迭代并得到所要的近似极小解{X}^{(k)}。否则取r_{(k+1)}<r_{k}并令k:=k+1。然后,转回第(3)步继续迭代。

例题

       用障碍函数法求解

图片

解:

(1)构造障碍函数

图片

(2)对于固定的r_{k},由

图片

(3)求得其极小点x(r)x(r)=\pm \sqrt{r_{k}}

r=1,x(r)=1

r=0.1,x(r)=0.316

r=0.01,x(r)=0.1

r→0,x(r)→0

因此,原约束问题的极小点 x*= 0

图片

初始内点迭代步骤

(1)任取一点X^{(1)}\in E_{n}r_{1}>0,并令k:=1。

(2)确定指标集\bar{T_{k}}T_{k}

图片

(3)检查\bar{T_{k}}是否为空集,若为空集,则取X^{(k)}为初始内点,停止迭代;否则,进行下一步。

(4)构造函数,将严格不等式不能满足的约束函数为假拟目标函数,严格满足的约束函数形成障碍项,构成一无约束性质问题,构造函数

图片

X^{(k)}为初始点,求解

图片

其中,

图片

设求出的极小点\mathbf{X}^{(k+1)},则\mathbf{X}^{(k+1)}\in \bar{R_{k}}。令0\leq r_{k+1}\leq r_{k}k:=k+1,转回第(2)步。

       以上就是非线性规划中罚函数法与障碍函数法的全部内容了,通过本节学习大家是否对制约函数法有了一个大致的认识呢?到此为止,非线性规划的所有知识点就已经介绍完了,想要进一步了解运筹学,关注公众号运筹说,快快学起来吧!下期小编将为大家介绍与非线性规划相关的精品案例,敬请关注!

作者 |林若唯 唐京茹

责编 | 陈梦

审核 | 徐小峰

知乎 :运筹说

Bilibili :运筹说

 CSDN :运筹说

这篇关于运筹说 第102期 | 非线性规划—制约函数法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/393164

相关文章

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、

golang panic 函数用法示例详解

《golangpanic函数用法示例详解》在Go语言中,panic用于触发不可恢复的错误,终止函数执行并逐层向上触发defer,最终若未被recover捕获,程序会崩溃,recover用于在def... 目录1. panic 的作用2. 基本用法3. recover 的使用规则4. 错误处理建议5. 常见错

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详