梯度下降算法

Question

我正在尝试Boyd的“凸优化”一书中的问题9.30。但出于某种原因我不能让回溯线搜索起作用。这是我的代码：

import numpy as np

n, m = 100, 200
A = np.random.randn(m, n)
a, b = 0.01, 0.5
gtol = 1e-3


def f(x):
    # return - np.sum(np.log(1-x*x)) - np.sum(np.log(1-A @ x))
    return -np.sum(np.log(1-A@x)) - np.sum(np.log(1+x)) - np.sum(np.log(1-x))


def G(x):
    # return 2*x/(1-x*x) + np.sum(A, 0)/np.sum(1-A@x)
    return A.T @ (1/(1-A@x)) - 1/(1-x) + 1/(1+x)


def feasible(x):
    return np.all(x*x<1) and np.all(A@x<1)


def step_size(x, g, a, b):
    # backtracking line search
    fx = f(x)
    dx = -g
    t = 1
    while True:
        if not feasible(x+t*dx):
            t *= b
        else:
            if f(x+t*dx) <= fx+a*t*g.T@dx:
                break
            t *= b
    return t


def stopping_condition(g):
    return np.linalg.norm(g, 2) < gtol


def gradient_descent(x, a, b):
    flist, xlist, tlist = [f(x)], [x],[np.nan]
    while True:
        g = G(x)
        if stopping_condition(g):
            break
        t = step_size(x, -g, a, b)
        x -= t * g
        print(f(x), t, np.linalg.norm(g, 2))
        flist.append(f(x)), xlist.append(x), tlist.append(t)
    return flist, xlist, tlist


fx, x, t = gradient_descent(np.zeros(n), a, b)

我看到f(x)和G(x)正确地计算了这个值。然而，step_size函数似乎并不收敛，而理论认为它应该收敛。我似乎搞不懂为什么这不管用。

Answer 1

好吧，我发现问题了！

我正在传递-g，然后再乘以一个-ive！

谢谢。