内点法[通俗易懂]

内点法[通俗易懂]内点法属于约束优化算法。约束优化算法的基本思想是:通过引入效用函数的方法将约束优化问题转换成无约束问题,再利用优化迭代过程不断地更新效用函数,以使得算法收敛。内点法(罚函数法的一种)的主要思想是:

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

文字理解

内点法属于约束优化算法。约束优化算法的基本思想是:通过引入效用函数的方法将约束优化问题转换成无约束问题,再利用优化迭代过程不断地更新效用函数,以使得算法收敛。
内点法(罚函数法的一种)的主要思想是:在可行域的边界筑起一道很高的“围墙”,当迭代点靠近边界时,目标函数徒然增大,以示惩罚,阻止迭代点穿越边界,这样就可以将最优解“档”在可行域之内了。

数学定义

对于下面的不等式约束的优化问题:

\[\min f(x), x \in R^n \]

\[s.t \quad g_{i}(x) \leq0, i=1,2,…,m \]

利用内点法进行求解时,构造惩罚函数的一般表达式为

\[\varphi (X, r)=f(X)-r\sum_{i=1}^{m}\frac{1}{g_{i}(X)} \]

或者

\[\varphi (X, r)=f(X)-r\sum_{i=1}^{m}{\ln[-g_{i}(X)]} \]

算法步骤

  1. 取初始惩罚因子\(r^{(0)}>0\),允许误差\(\epsilon>0\)
  2. 在可行域\(D\)内选取初始点\(X^{(0)}\),令\(k=1\)
  3. 构造惩罚函数\(\varphi (X, r^{(k)})\),从\(X^{(k-1)}\)点出发用无约束优化方法求惩罚函数\(\varphi (X, r^{(k)})\)的极值点\((X^{*}, r^{(k)})\)
  4. 检查迭代终止准则:如果满足$$|X^{} r{(k)}-X{} r{(k-1)}|\leq\epsilon_{1}=10{-5}-10^{-7}$$或者$$|\frac{\varphi (X^{} ,r^{(k)})-\varphi (X^{}, r^{(k-1)})}{\varphi (X^{*}, r{(k-1)})}|\leq\epsilon_{2}=10{-3}-10^{-4}$$则停止迭代计算,并以\((X^{*}, r^{(k)})\)作为原目标函数\(f(X)\)的约束最优解,否则转入下一步;
  5. \(r^{(k+1)}=cr^{(k)}\)\(X^{(0)}=X^{*}r^{(k)}\)\(k=k+1\),转向步骤3。递减系数\(c=0.1-0.5\),通常取0.1。

内点惩罚函数法特点及其应用

  • 惩罚函数定义于可行域内,序列迭代点在可行域内不断趋于约束边界上的最优点(这就是称为内点法的原因)
  • 只适合求解具有不等式约束的优化问题

内点法求解案例

用内点法求下面约束优化问题的最优解,取迭代初始\(X^0 = [0, 0]^{\mathrm{T}}\),惩罚因子的初始值\(r^0 = 1\),收敛终止条件\(\|X^k – X^{k-1}\| \leq \varepsilon\)\(\varepsilon = 0.01\)

\[\min f(X) = x_1^2 + x_1^2 – x_1x_2 – 10x_1 – 4x_2 + 60 \]

\[\mathrm{s.t.}\; g(X) = x_1 + x_2 -8 \leq 0 \]

  1. 构造内惩罚函数:\(\varphi(X, r) = x_1^2 + x_1^2 – x_1x_2 – 10x_1 – 4x_2 + 60 -r\ln(x_1 + x_2 -8)\)
  2. 用解析法求内惩罚函数的极小值
\[\nabla\varphi(X, r) = [2x_1 – x_2 – 10 – \frac{r}{x_1 + x_2 – 8} \quad 2x_2 – x_1 – 4 – \frac{r}{x_1 + x_2 – 8}] \]

\(\nabla \varphi(X, r) = 0\)得:\(\begin{align}2x_1 – x_2 – 10 – \frac{r}{x_1 + x_2 – 8} = 0 \\ 2x_2 – x_1 – 4 – \frac{r}{x_1 + x_2 – 8} = 0\end{align}\)

解得:

\(X^*_1(r) = \begin{bmatrix}\frac{13 + \sqrt{9+2r}}{2} & \frac{9 + \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

\(X^*_2(r) = \begin{bmatrix}\frac{13 – \sqrt{9+2r}}{2} & \frac{9 – \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

\(\because g(X^*_1(r)) > 0\)

\(\therefore\) 舍去\(X^*_1(r)\)

\(\because \varphi(X, r)\)为凸函数

\(\therefore\) 无约束优化问题的最优解为\(X^*(r) = X^*_2(r) = \begin{bmatrix}\frac{13 – \sqrt{9+2r}}{2} & \frac{9 – \sqrt{9+2r}}{2}\end{bmatrix}^{\mathrm{T}}\)

  1. 求最优解

\(r^0 = 1\)时,\(X^*(r^0) = \begin{pmatrix}4.8417 & 2.8417\end{pmatrix}^{\mathrm{T}}\)\(\|X^*(r^0) – X^0\| = 5.6140 > \varepsilon\)

\(r^1 = 0.1\)时,\(X^*(r^1) = \begin{pmatrix}4.9834 & 2.9834\end{pmatrix}^{\mathrm{T}}\)\(\|X^*(r^1) – X^*(r^0)\| = 0.2004 > \varepsilon\)

\(r^2 = 0.01\)时,\(X^*(r^2) = \begin{pmatrix}4.9983 & 2.9983\end{pmatrix}^{\mathrm{T}}\)\(\|X^*(r^2) – X^*(r^1)\| = 0.0211 > \varepsilon\)

\(r^3 = 0.01\)时,\(X^*(r^3) = \begin{pmatrix}4.9998 & 2.9998\end{pmatrix}^{\mathrm{T}}\)\(\|X^*(r^3) – X^*(r^2)\| = 0.0021 < \varepsilon\)

\(X^*(r^3)\)为最优解

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/167972.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • VM虚拟机Kali安装教程—kalrry

    VM虚拟机Kali安装教程—kalrryKali安装教程Kali安装教程Kali安装教程kali安装时间比较漫长,请耐心等待01.点击创建新的虚拟机02.选择自定义(高级)点击下一步(N)03.点击下一步(N)04.选择稍后安装操作系统(S);点击下一步(N)05.客户机操作系统选择Linux(L);Kali是基于Debian制作,这里的版本(V)我选择的选择是Debian9.x64位;点击下一步(N)06.为了好辨别,虚拟机名称(V)我修改成了Kali,安装位置(L)可自定义,此处位置指的是系统安装位置;点击下一步

  • pycahrm激活码【注册码】

    pycahrm激活码【注册码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 浅析Java中volatile关键字及其作用

    浅析Java中volatile关键字及其作用在Java多线程中如何保证线程的安全性?那我们可以使用Synchronized同步锁来给需要多个线程访问的代码块加锁以保证线程安全性。

  • Java中的Map及其使用「建议收藏」

    Java中的Map及其使用「建议收藏」MapMap集合概述和特点概述:将键映射到值的对象一个映射不能包含重复的键每个键最多只能映射到一个值Map接口和Collection接口的不同Map是双列的,Collection是单列的Map的键唯一,Collection的子体系Set是唯一的Map集合的数据结构针对键有效,跟值无关;Collection集合的数据结构是针对元素有效Map集合的功能概述a:添加功能Vput…

  • java heap space 什么意思_java heap space是什么意思?

    java heap space 什么意思_java heap space是什么意思?因为程序要从数据读取近10W行记录处理,当读到9W的时候就出现java.lang.OutOfMemoryError:Javaheapspace这样的错误。javaheapspace的意思为“java堆空间”。在网上一查可能是JAVA的堆栈设置太小的原因。跟据网上的答案大致有这两种解决方法:1、设置环境变量setJAVA_OPTS=-Xms32m-Xmx512m可以根据自己机器的…

  • datetime.date()_datenum函数使用

    datetime.date()_datenum函数使用比如在windowscmd命令行窗口执行date命令后这个环境变量的值为当前日期:2014-03-01 星期六那么如下的各个操作的意义如下:%date:~0,4% 表示从左向右指针向右偏0位,然后从指针偏移到的位置开始提取4位字符,结果是2014(年的值)%date:~5,2% 表示指针从左向右偏移5位,然后从偏移处开始提取2位字符,结果是03(月的值)%date:~8,

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号