梯度下降法

问题:寻找到N个点距离和最小的点

思路:

深度截图20170422001700.png

import numpy as np
from matplotlib import pyplot as plt

# p到points的距离和
def f(p, points) :
    return np.sum(np.sum((p - points) ** 2, axis=1) ** 0.5)

#  距离和函数在p点的梯度
def fgrad(p, points):
    dx = np.sum((p[0] - points[:, 0]) / np.sum((p - points) ** 2, axis=1) ** 0.5)
    dy = np.sum((p[1] - points[:, 1]) / np.sum((p - points) ** 2, axis=1) ** 0.5)
    return np.array([dx, dy])

# points = np.random.rand(20, 2) # 随机或者自定义几个点，寻找距离这些点之和最小值的点
points = np.array([
            [0,0],
            [0,2],
            [2,0],
            [2,2]
    ]) # 定义一个正方形
x = np.random.rand(2) # x为随机初始点
step = 0.2
xhistory = x #用来存储历史值

for k in range(100):
    l = f(x, points)
    xk = x - step * fgrad(x, points)
    lk = f(xk, points)
    if l - lk > 1e-8:
        x = xk
        xhistory = np.vstack((xhistory, x))
    elif l - lk <0:
        #步子太大，超过极值后调整步伐大小
        step *= 0.5
    else:
        break

print(xhistory)

[[ 0.17005619  0.77382012]
 [ 0.45001009  0.81002093]
 [ 0.61803208  0.85141979]
 [ 0.7298659   0.88861665]
 [ 0.80752889  0.91829   ]
 [ 0.86240553  0.94071626]
 [ 0.90147962  0.95722978]
 [ 0.9294022   0.96923281]
 [ 0.94939105  0.97790027]
 [ 0.96371305  0.98413816]
 [ 0.97397936  0.98861982]
 [ 0.98134014  0.99183687]
 [ 0.98661833  0.99414511]
 [ 0.99040338  0.99580088]
 [ 0.99311776  0.99698848]
 [ 0.99506437  0.99784024]
 [ 0.99646039  0.9984511 ]
 [ 0.99746154  0.99888919]
 [ 0.99817953  0.99920337]
 [ 0.99869444  0.99942869]
 [ 0.99906371  0.99959028]
 [ 0.99932853  0.99970617]
 [ 0.99951845  0.99978928]
 [ 0.99965465  0.99984888]
 [ 0.99975233  0.99989162]
 [ 0.99982238  0.99992228]
 [ 0.99987262  0.99994426]]

# print(points[:, 0])
plt.plot(points[:, 0], points[:, 1], 'bo')
plt.plot(xhistory[:, 0], xhistory[:, 1], 'ro')
plt.plot(xhistory[:, 0], xhistory[:, 1], 'k-')
plt.title(u'迭代次数 = %d, 距离和 = %.3f, 极值点 = (%.3f, %.3f), 最后步长 = %f' % (k, l, x[0], x[1], step))
plt.show()

output_7_0.png