内点法属于约束优化算法。约束优化算法的基本思想是:通过引入效用函数的方法将约束优化问题转换成无约束问题,再利用优化迭代过程不断地更新效用函数,以使得算法收敛。 内点法(罚函数法的一种)的主要思想是:在可行域的边界筑起一道很高的“围墙”,当迭代点靠近边界时,目标函数徒然增大,以示惩罚,阻止迭代点穿越边界,这样就可以将最优解“档”在可行域之内了。
对于下面的不等式约束的优化问题:
\[\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)]} \]
或者
则停止迭代计算,并以\((X^{*}, r^{(k)})\)作为原目标函数\(f(X)\)的约束最优解,否则转入下一步;
用内点法求下面约束优化问题的最优解,取迭代初始\(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 \]
\[\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}}\)
当\(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)\)为最优解
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/167972.html原文链接:https://javaforall.cn