梯度下降法

Question

我正在写一个程序，用来处理梯度下降的方法。我用这个方法来解决一些特定形式的方程。

Ax = b
where A is a random 10x10 matrix and b is a random 10x1 matrix

这是我的代码：

import numpy as np
import math
import random
def steepestDistance(A,b,xO, e):
    xPrev = xO
    dPrev = -((A * xPrev) - b)
    magdPrev = np.linalg.norm(dPrev)
    danger =  np.asscalar(((magdPrev * magdPrev)/(np.dot(dPrev.T,A * dPrev))))
    xNext = xPrev + (danger * dPrev)
    step = 1
    while (np.linalg.norm((A * xNext) - b) >= e and np.linalg.norm((A * xNext) - b) < math.pow(10,4)):
        xPrev = xNext
        dPrev = -((A * xPrev) - b)
        magdPrev = np.linalg.norm(dPrev)
        danger = np.asscalar((math.pow(magdPrev,2))/(np.dot(dPrev.T,A * dPrev)))
        xNext = xPrev + (danger * dPrev)
        step = step + 1
    return xNext

##print(steepestDistance(np.matrix([[5,2],[2,1]]),np.matrix([[1],[1]]),np.matrix([[0.5],[0]]), math.pow(10,-5)))

def chooseRandMatrix():
    matrix = np.zeros(shape = (10,10))
    for i in range(10):
        for a in range(10):
            matrix[i][a] = random.randint(0,100)
    return matrix.T * matrix

def chooseRandColArray():
    arra = np.zeros(shape = (10,1))
    for i in range(10):
        arra[i][0] = random.randint(0,100)
    return arra
for i in range(4): 
  matrix = np.asmatrix(chooseRandMatrix())
  array = np.asmatrix(chooseRandColArray())  
print(steepestDistance(matrix, array, np.asmatrix(chooseRandColArray()),math.pow(10,-5)))

当我在随机矩阵和列上运行steepestDistance这个方法时，我总是陷入一个无限循环。用简单的2x2矩阵作为A时，这个方法运行得很好，但用10x10的矩阵时就一直循环下去。问题出在np.linalg.norm((A * xNext) - b)这部分；它的值一直在增长，没完没了。所以我给它设置了一个上限，但其实这样做是不符合算法要求的。有人能告诉我问题出在哪里吗？

Answer 1

用梯度下降法来解决线性方程组 Ax=b 的问题，其实就是在最小化一个二次函数。

f(x) = 0.5*x^t*A*x - b^t*x. 

不过，这个方法只有在矩阵 A 是对称的，也就是 A=A^t 的情况下才有效，因为这个函数的导数或者说梯度是：

f'(x)^t = 0.5*(A+A^t)*x - b, 

而且，A 还必须是正定的。如果 A 有负特征值，那么梯度下降就会一直往负无穷走，这样就找不到最小值了。

---

一个解决方法是把 b 替换成 A^tb，把 A 替换成 A^t*A，也就是要最小化这个函数：

f(x) = 0.5*||A*x-b||^2
     = 0.5*x^t*A^t*A*x - b^t*A*x + 0.5*b^t*b

对应的梯度是：

f'(x)^t = A^t*A*x - A^t*b

但是对于大矩阵 A，这种做法不太推荐，因为 A^t*A 的条件数大约是 A 的条件数的平方。