优化算法——坐标上升法
一、坐标上升法算法原理
坐标上升法(Coordinate Ascent)每次通过更新函数中的一维，通过多次的迭代以达到优化函数的目的。
假设需要求解的优化问题的具体形式如下：
maxαW(α1,α2,⋯,αm)
\underset{\alpha }{max}W\left ( \alpha _1,\alpha _2,\cdots ,\alpha _m \right )
其中，WW是向量α⃗ \vec{\alpha }的函数。
更新过程为每次固定除αi\alpha _i以外的参数，求得满足条件的αi\alpha _i，直到算法收敛，具体的算法过程如下所示：
(图片来自参考文献1)
下面以如下的优化问题为例：
f(x1,x2)=−x21−3x22+2x1x2+6
f\left ( x_1,x_2 \right )=-x_1^2-3x_2^2+2x_1x_2+6
在迭代的过程中，每次固定x2x_2更新x1x_1，在确定了x1x_1的条件下，固定x1x_1，更新x2x_2，即：
∂f∂x1=−2x1+2x2
\frac{\partial f}{\partial x_1}=-2x_1+2x_2
令其为00，得到：
x1=x2
x_1 = x_2
再固定x2x_2，得到：
∂f∂x2=−6x2+2x1
\frac{\partial f}{\partial x_2}=-6x_2+2x_1
得到：
x2=13x1
x_2 = \frac{1}{3}x_1
不断按照上述的过程，直到算法收敛。下图是算法在整个过程中的更新曲线：
代码如下：
'''
Date: 20160406
@author: zhaozhiyong
'''
import matplotlib
import numpy as np
import matplotlib.cm as cm
import matplotlib.mlab as mlab
import matplotlib.pyplot as plt
delta = 0.025
x = np.arange(-3.0, 3.0, delta)
y = np.arange(-3.0, 3.0, delta)
X, Y = np.meshgrid(x, y)
Z1 = -(X**2)
Z2 = -(Y**2)
Z = 1.0 * (Z1 + 3 * Z2 + 2 * X * Y)+6.0
plt.figure()
CS = plt.contour(X, Y, Z)
a = []
b = []
a.append(2.0)
b.append(2.0)
j = 1
for i in xrange(200):
a_tmp = b[j-1]
a.append(a_tmp)
b.append(b[j-1])
j = j+1
b_tmp = a[j-1] / 3
a.append(a[j-1])
b.append(b_tmp)
plt.plot(a,b)
plt.title('Coordinate Ascent')
plt.xlabel('x')
plt.ylabel('y')
plt.show()二、坐标上升法在函数优化中的应用
下面考虑求解如下的最大值问题：
argmaxx1,x2,x3f(x1,x2,x3)=−x21−2x22−3x23+2x1x2+2x1x3−4x2x3+6
\underset{x_1,x_2,x_3}{argmax}f\left ( x_1,x_2,x_3 \right )\\=-x_1^2-2x_2^2-3x_3^2+2x_1x_2+2x_1x_3-4x_2x_3+6
将上述函数分别对x1,x2,x3x_1,x_2,x_3求偏导，并令其为00，得到如下的等式：
x1=x2+x3
x_1=x_2+x_3
x2=12x1−x3
x_2=\frac{1}{2}x_1-x_3
x3=13x1−23x2
x_3=\frac{1}{3}x_1-\frac{2}{3}x_2
最终的结果为：
代码如下：
#!/bin/python
'''
Date: 20160406
@author: zhaozhiyong
'''
def f(x):
x_1 = x[0]
x_2 = x[1]
x_3 = x[2]
result = -(x_1*x_1)-2*(x_2*x_2)-3*(x_3*x_3)+2*x_1*x_2+2*x_1*x_3-4*x_2*x_3+6
return result
if __name__ == "__main__":
#print "hello world"
err = 1.0e-10
x = [1.0, 1.0, 1.0]
f_0 = f(x)
while 1:
#print "Hello"
x[0] = x[1] + x[2]
x[1] = x[0] / 2 - x[2]
x[2] = x[0] / 3 - 2 * x[1] / 3
f_t = f(x)
if (abs(f_t - f_0) < err):
break
f_0 = f_t
print "max: " + str(f_0)
print x