Boyd《凸优化》9.30题：梯度下降回溯线搜索不收敛问题

1. 梯度计算符号错误 #

目标函数中-np.sum(np.log(1+x)) - np.sum(np.log(1-x))等价于-np.sum(np.log(1-x²))，其对x的导数应为：
$$\frac{d}{dx} \left( -\sum \log(1-x_i^2) \right) = \sum \frac{2x_i}{1-x_i^2}$$
但你的代码中这部分实现为-1/(1-x) + 1/(1+x)，计算后是：
$$-\frac{1}{1-x} + \frac{1}{1+x} = \frac{-(1+x) + (1-x)}{(1-x)(1+x)} = \frac{-2x}{1-x^2}$$
符号完全相反，导致梯度方向错误。修正后的梯度函数应为：

def G(x):
    return A.T @ (1/(1-A@x)) + 1/(1-x) - 1/(1+x)

或者更直观的等价写法：

def G(x):
    return A.T @ (1/(1-A@x)) + 2*x/(1 - x**2)

2. 回溯线搜索的方向传递错误 #

在gradient_descent函数中，你调用step_size(x, -g, a, b)，而step_size内部定义dx = -g——这会导致搜索方向变成正梯度方向（传入的g是-原梯度，dx=-g就等于原梯度），完全违背梯度下降的方向要求。

正确的调用应该是传递原梯度g，让dx=-g成为负梯度方向：

t = step_size(x, g, a, b)

3. 其他潜在优化点 #

• 可行域检查中，x*x<1可以写成np.abs(x) < 1，更直观且避免平方运算的精度问题；
• 回溯线搜索中建议添加最小步长阈值，防止t无限缩小导致死循环。

修复后的完整代码 #

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-A@x)) - np.sum(np.log(1+x)) - np.sum(np.log(1-x))


def G(x):
    return A.T @ (1/(1-A@x)) + 2*x/(1 - x**2)


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


def step_size(x, g, a, b):
    fx = f(x)
    dx = -g
    t = 1.0
    while t > 1e-10:
        x_new = x + t * dx
        if not feasible(x_new):
            t *= b
        else:
            fx_new = f(x_new)
            if fx_new <= 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)

内容的提问来源于stack exchange，提问作者manav