解最优化问题_IT分享知识网

大家好，欢迎来到IT知识分享网。

解最优化问题

本文版权属于重庆大学计算机学院刘骥，禁止转载

解最优化问题

最优化问题的分类

本文余下部分，针对可导的目标函数进行讨论，这类问题存在大量通用的算法。人类历史发展到2017年，你甚至不需要了解具体算法的原理，也能够很happy的解决这类问题。

直接开始求解

arg min x, y f (x, y) = x 2 + y 2 + 1

$\begin{align} \mathop{\arg\min}_{x,y}f(x,y)=x^2+y^2+1 \end{align}$

显然 $x=0，y=0$ 时， $f(x,y)$ 有最小值1。问题在于，计算机如何求解这个问题呢？

downhill simplex

# encoding=utf-8 import scipy.optimize as opt #定义目标函数f def f(X): x=X[0] y=X[1] return x2+y2+1; x=10 y=10 X=[x,y] X=opt.fmin(f,X) #f是目标函数，X是初始猜测的解 x=X[0] y=X[1] print x,y

Conjugate Gradient

\partial f \partial x = 2 x \partial f \partial y = 2 y

$\begin{align} \frac{\partial f}{\partial x}=2x \\ \frac{\partial f}{\partial y}=2y \end{align}$

# encoding=utf-8 import scipy.optimize as opt import numpy as np #定义目标函数f def f(X): x=X[0] y=X[1] return x2+y2+1; #定义目标函数f对应的梯度函数 def gradf(X): x=X[0] y=X[1] gx=2*x gy=2*y return np.asarray((gx,gy)) #梯度以向量形式返回 x=10 y=10 X=[x,y] X=opt.fmin_cg(f,X,fprime=gradf) #f是目标函数，X是初始猜测的解，增加梯度 x=X[0] y=X[1] print x,y

你居然不会求偏导数！

OK！OK！有办法可以解决！今年是2017年，如果你还不会求偏导数，那么交给计算机吧！

X=opt.fmin_cg(f,X)

def gradf(X): x=X[0] y=X[1] gx=(f([x+0.0000001,y])-f([x,y]))/0.0000001 gy=(f([x,y+0.0000001])-f([x,y]))/0.0000001 return np.asarray((gx,gy))

f' (x) = f ( x + Δ x ) - f ( x ) Δ x

$\begin{align} f'(x)=\frac{f(x+\Delta x)-f(x)}{\Delta x} \end{align}$

Newton-CG

⎡ ⎣ ⎢ ⎢ ⎢ ⎢ \partial f 2 \partial x 2 \partial f 2 \partial y \partial x \partial f 2 \partial x \partial y \partial f 2 \partial y 2 ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ = [2002]

$\begin{align} \begin{bmatrix} \frac{\partial f^2}{\partial x^2} &\frac{\partial f^2}{\partial x \partial y}\\ \frac{\partial f^2}{\partial y \partial x} &\frac{\partial f^2}{\partial y^2} \end{bmatrix}= \begin{bmatrix} 2&0\\ 0&2 \end{bmatrix} \end{align}$
代码如下：

# encoding=utf-8 import scipy.optimize as opt import numpy as np #定义目标函数f def f(X): x=X[0] y=X[1] return x2+y2+1; #定义目标函数f对应的梯度函数 def gradf(X): x=X[0] y=X[1] gx=2*x gy=2*y return np.asarray((gx,gy)) #梯度以向量形式返回 def hess(X): return np.array([[2,0],[0,2]]) #hessian矩阵 x=10 y=10 X=[x,y] X=opt.fmin_ncg(f,X,fprime=gradf,fhess=hess) #f是目标函数，X是初始猜测的解，增加梯度 x=X[0] y=X[1] print x,y

X=opt.fmin_ncg(f,X,fprime=gradf) #注意梯度是必须的

总结

现在是2017年，基本的最优化问题已经经过了几百年的发展（不是几十年），因此有大量现成的函数库可以使用。直接调用这些库函数，你甚至不需要知道如何求导数、如何求Hessian矩阵，也可以很好的解决最优化问题（可导的）。如果不追求效率，如果精度可以接受，那么最最原始的downhill simplex方法已经能够适用于大多数场景（你需要小数点后几位的精度？）。

数学原理

大多数最优化的书籍，在讲解数学原理时，都抱着一定要让人看不懂，才能显得高深莫测的心态。其实求解可导目标函数的数学原理是极其简单的，那就是：穷举，更高效的穷举。

假设目标函数为 $f(X)$ ，其中 $X\in R^n$ （注意这意味着 $X$ 是一个向量， $f$ 是多元函数）。例如 $X=(x,y,z)^T$ ，则 $f(X)$ 表示的函数就是 $f(x,y,z)$ 。我如此定义不是为了把你搞晕，而是为了环保！试想如果我想定义函数 $f(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10},x_{11},x_{12},x_{13},x_{14},x_{15},x_{16},x_{17},x_{18},x_{19},x_{20},x_{21},x_{22})$ ，难道不是写成 $f(X)$ ， $X\in R^{22}$ 更环保吗？Yes，Yes，你从来没有见过3元以上的函数，那不是因为你一直都是在做考题吗？一道考试题，要是有22个变量，你要用多大的草稿纸？现实问题则不然，考虑女性择偶问题，男方必须有钱、长得帅、有安全感、父母双亡、有车、有房、有股票、有存款、初恋、非凤凰男等等。表示为函数就是：

f (钱, 颜 值, 安 全 感, 父 母, 车, 房, 股 票, 存 款, 情 史, 是 否 凤 凰 男)

$f(钱,颜值,安全感,父母,车,房,股票,存款,情史,是否凤凰男)$
学过代数吧？于是这个函数就变成了:

f (x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, x 9, x 10) = f (X)

$f(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10})=f(X)$
现在我们来讨论女性择偶函数f(X)的最优化！假定女性朋友给出的函数是这样的：

f (X) = X T C 10 \times 10 X

$\begin{align} f(X)=X^TC_{10\times 10}X \end{align}$
这是一个二次函数（请自行展开），C是系数矩阵（我们只是假设女性朋友给出了这样的二次函数，真实情况未必）。OK，其实这个函数长什么样子，不影响后面的讨论。我们所要讨论的是 $f(X)$ 可导的情况。如何确定 $f(X)$ 的极值呢？

最笨的方法就是穷举！！换言之，先试试 $f(X_1)$ ，再看看 $f(X_2)$ ，不停的尝试 $f(X_i)$ ，直到成为单身贵族……对，我告诉你的解法就是成为单身贵族的解法，因为解空间几乎是无限大的，穷举法太笨！

聪明一点的方式是穷举n次，找其中的最优。先试试 $f(X_1)$ ，再看看 $f(X_2)$ ，不停的尝试直到 $f(X_n)$ ，找出 $f(X_1)到f(X_n)$ 中最优的 $f(X_i)$ 。这个方法的缺陷在于，女性朋友不一定能够找到真正的灵魂伴侣。

再聪明一点的方法固定一些变量，搜索另外一些变量。必须长得帅，像鹿晗；必须有钱，和王思聪一样；必须是初恋。你看解空间一下就变小了。接下来的搜索就简单了很多。如果找不到解，那么就修改某些固定的变量。为什么长相必须像鹿晗？郭德纲也可以接受！这样我们就可以开始新的搜索啦！事实上，这就是绝大多数人，择偶的方式。

如果变量是连续的呢？数学家发现，在这种情况下，搜索策略其实是这样的：
1. 首先选择一个起始的解 $X_0$ 。
2. 比较 $f(X_0+\Delta)$ ，如果 $f(X_0+\Delta) <f(X_0)< script=""> 那么 X0+Δ <script type="math/tex" id="MathJax-Element-113">X_0+\Delta$ 是更好的解

3. 另 $X_1=X_0+\Delta$ ，跳到第1步重新执行。

上述方法的核心在于存在一个 $X$ 的更新公式：

X n + 1 = X n + Δ n

$\begin{align} X_{n+1}=X_{n}+\Delta_{n} \end{align}$

f (x, y) = x 2 + y 2 + 1

$\begin{align} f(x,y)=x^2+y^2+1 \end{align}$
假设初始值为 $X_0=(1,1)^T$ ，令 $\Delta_n=(-0.1,-0.1)^T$ ，于是：

X 0 = (1, 1) T X 1 = (0.9, 0.9) T . . . . . . X 10 = (0, 0) T X 11 = (- 0.1, - 0.1) T

$X_0=(1,1)^T\\X_1=(0.9,0.9)^T\\......\\X_{10}=(0,0)^T\\X_{11}=(-0.1,-0.1)^T$

Stop！不是 $X_{10}$ 已经达到最优了吗？为什么程序还在跑？问题在于那个 $\Delta_n$ ，如果它能够越接近最小值越小，程序不就可以停下来了吗？越接近你的灵魂伴侣，越需要放慢搜索的速度不是吗？
怎么解决这个问题呢？数学家出场了。我们知道 $f(X_{n+1})=f(X_n+\Delta_n)$ ，根据泰勒公式展开就是：

f (X n + 1) = f (X n + Δ n) = f (X n) + \partial f ( X n ) \partial X Δ n + Δ T n \partial f 2 ( X n ) \partial X 2 Δ n / 2 + . . . . . .

$\begin{align} f(X_{n+1})=f(X_n+\Delta_n)=f(X_n)+\frac{\partial f(X_n)}{\partial X}\Delta_n+\Delta_n^T\frac{\partial f^2(X_n)}{\partial X^2}\Delta_n /2+...... \end{align}$
针对该公式求 $\Delta_n$ 的导数，并令结果等于0，则：

\partial f ( X n ) \partial X + \partial f 2 ( X n ) \partial X 2 Δ n = 0 \partial f 2 ( X n ) \partial X 2 Δ n = - \partial f ( X n ) \partial X

$\begin{align} \frac{\partial f(X_n)}{\partial X}+\frac{\partial f^2(X_n)}{\partial X^2}\Delta_n =0\\ \frac{\partial f^2(X_n)}{\partial X^2}\Delta_n=-\frac{\partial f(X_n)}{\partial X} \end{align}$
现在我们可以解出 $\Delta_n$ ！如果你对上述推导的原理感到好奇，不奇怪啊，你不是数学家对吧？总之，我们会算就可以啦。现在用新的公式来求解老问题。

f (x, y) = x 2 + y 2 + 1 \partial f ( x , y ) \partial x = 2 x \partial f ( x , y ) \partial y = 2 y \partial f 2 ( x , y ) \partial x 2 = 2 \partial f 2 ( x , y ) \partial x \partial y = 0 \partial f 2 ( x , y ) \partial y 2 = 2 \partial f ( x , y ) \partial y \partial x = 0 [2002] Δ n = - [2 x n 2 y n] Δ n = - [x n y n]

$f(x,y)=x^2+y^2+1\\ \frac{\partial f(x,y)}{\partial x}=2x\\ \frac{\partial f(x,y)}{\partial y}=2y\\ \frac{\partial f^2(x,y)}{\partial x^2}=2\\ \frac{\partial f^2(x,y)}{\partial x\partial y}=0\\ \frac{\partial f^2(x,y)}{\partial y^2}=2\\ \frac{\partial f(x,y)}{\partial y\partial x}=0\\ \begin{bmatrix} 2 & 0\\ 0 & 2 \end{bmatrix}\Delta_n=- \begin{bmatrix} 2x_n&2y_n \end{bmatrix}\\ \Delta_n=- \begin{bmatrix} x_n&y_n \end{bmatrix}$
计算过程如下：

X 0 = (1, 1) T Δ 0 = (- 1, - 1) T X 1 = X 0 + Δ 0 = (0, 0) T Δ 1 = (0, 0) T ∵ Δ 1 = (0, 0) T ∴ X = X 1 就 是 最 优 解

$X_0=(1,1)^T \quad \Delta_0=(-1,-1)^T\\ X_1=X_0+\Delta_0=(0,0)^T \quad \Delta_1=(0,0)^T\\ \because \Delta_1=(0,0)^T \\ \therefore X=X_1就是最优解$

数学白痴表示求偏导数矩阵太难理解！！如何破！！数学家马上送上福利：

λ Δ n = - \partial f ( X n ) \partial X

$\begin{align} \lambda\Delta_n=-\frac{\partial f(X_n)}{\partial X} \end{align}$
假设 $\lambda=2$ ，我们看看目标函数 $f(x,y)=x^2+y^2+1$ 的计算过程：

Δ n = - [x n y n] X 0 = (1, 1) T Δ 0 = (- 1, - 1) T X 1 = X 0 + Δ 0 = (0, 0) T Δ 1 = (0, 0) T ∵ Δ 1 = (0, 0) T ∴ X = X 1 就 是 最 优 解

$\Delta_n=- \begin{bmatrix} x_n&y_n \end{bmatrix}\\X_0=(1,1)^T \quad \Delta_0=(-1,-1)^T\\ X_1=X_0+\Delta_0=(0,0)^T \quad \Delta_1=(0,0)^T\\ \because \Delta_1=(0,0)^T \\ \therefore X=X_1就是最优解$
运气不错！如果 $\lambda=4$ 呢？推导如下：

Δ n = - [0.5 x n 0.5 y n] X 0 = (1, 1) T Δ 0 = (- 0.5, - 0.5) T X 1 = X 0 + Δ 0 = (0.5, 0.5) T Δ 1 = (- 0.25, - 0.25) T X 2 = X 1 + Δ 1 = (0.25, 0.25) T Δ 2 = (- 0.0625, - 0.0625) T . . . . . . 若 干 步 后 收 敛

$\Delta_n=- \begin{bmatrix} 0.5x_n&0.5y_n \end{bmatrix}\\X_0=(1,1)^T \quad \Delta_0=(-0.5,-0.5)^T\\ X_1=X_0+\Delta_0=(0.5,0.5)^T \quad \Delta_1=(-0.25,-0.25)^T\\ X_2=X_1+\Delta_1=(0.25,0.25)^T \quad \Delta_2=(-0.0625,-0.0625)^T\\ ......\\ 若干步后收敛$
如果 $\lambda=1$ ，推导如下：

Δ n = - [2 x n 2 y n] X 0 = (1, 1) T Δ 0 = (- 2, - 2) T X 1 = X 0 + Δ 0 = (- 1, - 1) T Δ 1 = (2, 2) T X 2 = X 1 + Δ 1 = (1, 1) T Δ 2 = (- 2, - 2) T . . . . . . 无 法 收 敛

$\Delta_n=- \begin{bmatrix} 2x_n&2y_n \end{bmatrix}\\X_0=(1,1)^T \quad \Delta_0=(-2,-2)^T\\ X_1=X_0+\Delta_0=(-1,-1)^T \quad \Delta_1=(2,2)^T\\ X_2=X_1+\Delta_1=(1,1)^T \quad \Delta_2=(-2,-2)^T\\ ......\\ 无法收敛$
可见如果采用新的计算公式， $\lambda$ 的取值会影响算法的收敛速度，甚至无法收敛。但的确这种算法避免了计算Hessian，数学白痴非常高兴！那么它存在的问题可以解决吗？当然可以，方法就是 动态调整 $\lambda$ 的取值，从而加快收敛，避免震荡。
最后，再来考虑一下，如果数学白痴连梯度都不会算怎么办？Nelder–Mead Method！对有高等数学背景的人而言，理解Nelder–Mead Method反而很困难！这里就不再详谈了。

数学白痴的福利

我们都不喜欢数学，还好现在是2017年，大量的工作已经由擅长数学的科学家做完了。你所需要的就是找一个算法丰富的库！比如的scipy或者matlab。为了写作本文，我对最优化问题进行了很多简化，首先只考虑可导的目标函数，其次也没有考虑函数变量的条件约束（比如 $X$ 必须是整数、 $X$ 必须大于0）。但无论问题多么复杂，这些问题已经被充分研究，充分解决。99%的情况，你只需要scipy或者matlab，剩下0.9999%的情况需要github。最后，还剩下一丢丢的未知领域，等待着学者去研究。别抢他们的饭碗，茶叶蛋已经够贵的啦！

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/117127.html

解最优化问题

解最优化问题

最优化问题的分类

直接开始求解

downhill simplex

Conjugate Gradient

你居然不会求偏导数！

Newton-CG

总结

数学原理

数学白痴的福利

相关推荐

发表回复