优化
graph LR;
SVM_模型分析-->优化;优化-->无约束优化;优化-->等式约束优化;优化-->不等式约束优化;
SVM_模型分析-->什么是对偶;
SVM_模型分析-->拉格朗日乘子法;拉格朗日乘子法-->对w和b的偏导为0可得;
SVM_模型分析-->等价凸函数;等价凸函数-->约束条件;
SVM_模型分析-->核函数;
SVM_模型分析-->参考文献;
click 优化 "#menu_index_1"
click 无约束优化 "#menu_index_2"
click 等式约束优化 "#menu_index_3"
click 不等式约束优化 "#menu_index_4"
click 什么是对偶 "#menu_index_5"
click 拉格朗日乘子法 "#menu_index_6"
click 对w和b的偏导为0可得 "#menu_index_7"
click 等价凸函数 "#menu_index_8"
click 约束条件 "#menu_index_9"
click 核函数 "#menu_index_10"
click 参考文献 "#menu_index_11"
无约束优化
$$\min_x f(x)$$
### 无约束优化
# 使用troch求解
import torch
from torch.autograd import Variable
#使用梯度下降法求y=x^2+2x+1 最小值 从x=3开始
x=Variable(torch.Tensor([3]),requires_grad=True)
for epoch in range(100):
y=x**2+2*x+1
y.backward()
x.data-=x.grad.data*0.05
x.grad.data.zero_()
print('min y={1:.2}, x={0:.2}'.format(x.data[0],y.data[0]))
# 使用TF求解
import tensorflow as tf
x = tf.Variable(0,dtype = tf.float32) # 定义一个可以优化的x值
cost = tf.add(tf.add(x**2,tf.multiply(10.,x)),26) # x**2 -10x + 26 即 (x-5)**2 + 1 最小值应该是1
train = tf.train.GradientDescentOptimizer(0.01).minimize(cost) # 用梯度下降法优化
init = tf.global_variables_initializer() # 初始化所有的变量节点
with tf.Session() as sess:
sess.run(init) # 初始化所有变量节点
for i in range(1000):
sess.run(train) # 进行优化
print('当前最小值是:',sess.run(cost),'\t对应的x值是:',sess.run(x))
# 使用
from scipy.optimize import fsolve
def f(x):
return (x**2+2*x+1)
result = fsolve(f, 3)
print ("x=",result)
print ("y=",f(result))
# 求解方程组,J是雅克比矩阵
from math import sin, cos
def func(args):
x0,x1,x2 = args.tolist()
return [5 * x1 + 3,
4 * x0 * x0-2 * sin(x1 * x2),
x1 * x2 -1.5]
def J(args):
x0,x1,x2 = args.tolist()
return[[0, 5, 0],
[8 * x0, -2*x2*cos(x1*x2),-2*x1*cos(x1*x2)],
[0, x2,x1]]
result = fsolve(func, [1,1,1],fprime = J)
print (result)
print (func(result))
等式约束优化
- 形式化表示
$$\begin{aligned} &\min_{x } \ f(x) \\ &s.t. \ \ \ h_i(x) = 0 , i = 1,2,...,m \\ \end{aligned}$$
from scipy.optimize import fsolve
def func(args):
x,y = args.tolist()
return [x**2-y,
x+y-2]
args = [1,1]
result = fsolve(func, args)
print (result)
print (func(result))
- Lagrangian
$$L(x,\alpha) = f(x) + \sum_{i=1}^m \alpha_i h_i(x)$$ - 几何含义
$$\nabla _xf(x) – \alpha \nabla_xh(x) = 0$$
不等式约束优化
满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多,其实很好理解:
(1) :拉格朗日取得可行解的必要条件;
(2) :这就是以上分析的一个比较有意思的约束,称作松弛互补条件;
(3) ∼ (4) :初始的约束条件;
(5) :不等式约束的 Lagrange Multiplier 需满足的条件。
主要的KKT条件便是 (3) 和 (5) ,只要满足这俩个条件便可直接用拉格朗日乘子法, SVM 中的支持向量便是来自于此,需要注意的是 KKT 条件与对偶问题也有很大的联系,下一篇文章就是拉格朗日对偶。
形式化表示
$$\begin{aligned} &\min_x \ f(x) \\ & \ s.t. \ \ g(x) \le 0 \end{aligned}$$$$L(x, \lambda) = f(x) + \lambda g(x)$$
$$-\nabla_x f(x) = \lambda \nabla_xg(x)$$
$$L(x,\alpha,\beta) =f(x) + \sum_{i=1}^m \alpha_i h_i(x) + \sum_{j=1}^n\beta_ig_i(x)$$
$$\begin{align} \nabla_x L(x,\alpha,\beta) &= 0 \\ \beta_jg_j(x) &= 0 , \ j=1,2,...,n\\ h_i(x)&= 0 , \ i=1,2,...,m \\ g_j(x) &\le 0 , \ j=1,2,...,n \\ \beta_j &\ge 0 , \ j=1,2,...,n \\ \end{align}$$
什么是对偶
在优化理论中,目标函数 f(x) 会有多种形式:如果目标函数和约束条件都为变量 x 的线性函数, 称该问题为线性规划;
如果目标函数为二次函数, 约束条件为线性函数, 称该最优化问题为二次规划;
如果目标函数或者约束条件均为非线性函数, 称该最优化问题为非线性规划。
每个线性规划问题都有一个与之对应的对偶问题,对偶问题有非常良好的性质,以下列举几个:
- 对偶问题的对偶是原问题;
- 无论原始问题是否是凸的,对偶问题都是凸优化问题;
- 对偶问题可以给出原始问题一个下界;
- 当满足一定条件时,原始问题与对偶问题的解是完全等价的;
首先要明白为什么要引入对偶问题,或者说为什么要将求解原问题转化为其求解对偶问题。
答:这是因为有些优化问题的原问题很难求解或者是原问题无法用现有的优化方法求解,但其对偶优化问题容易求解。所以在讲到SVM(Support Vector Machines),必定要提到Lagrange Dual问题,而且转化为对偶问题后能引入Kernel Fuction,也就是所谓的核函数。
比如下边这个例子
$$\begin{aligned} &\min_x \ \left ( x^4-50x^2+100x \right ) \\ &\ s.t.\ \ \ x \ge 4.5 \end{aligned}$$
import numpy as np
import matplotlib.pyplot as plt
def f(x):
return x**4 -50*x**2 + 100*x
def lamata(x):
return 4*x**3 - 100*x + 100
def dual(x):
return f(x) + lamata(x)*(4.5-x)
X = np.linspace(4.5 , 12, 1024)
plt.plot(X, f(X),color='b')
plt.plot(X, dual(X),color='r')
print("f(X) min:",np.min(f(X)))
print("dual(X) max:",np.max(dual(X)))
plt.show()
拉格朗日乘子法
$$L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))$$
求L的最小值等价于求对偶式的最大值
对w和b的偏导为0可得
$$w=\sum^m_{i=1}\alpha_iy_ix_i$$
$$0=\sum_{i=2}^m\alpha_iy_i$$
带入原函数求对偶式的最大值
等价凸函数
$$\max_\alpha \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$$
约束条件
$$\alpha\geqslant0$$
$$\sum_{i-1}^{m} \alpha_i\cdot y_i=0$$
核函数
$$\max_\alpha \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)$$
$$k(x_i,x_j)=\phi(x_i)^T\phi(x_j)$$
$$k(x,y) = exp(\frac{-||x-y||^2}{2\sigma^2})$$
参考文献
约束优化方法之拉格朗日乘子法与KKT条件
拉格朗日对偶
约束优化代码
SVM分析
核函数
本文由 admin 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 7, 2019 at 11:24 am