cjones6/cubic_reg

Implementation of Nesterov and Polyak's (2006) cubic regularization algorithm and Cartis et al's (2011) adaptive cubic regularization algorithm

cubic_reg's Issues

Possible incorrect handling of f_xold

In cubic_reg.py, f_xold (line 302) is calculated only once, then used as f_x for every calculation of rho going forward. Is this correct?

How to solve the subproblem

What approach do you take to solving subproblems in the literature? Is this an approximate way of solving subproblems or an exact way of solving them? It the article is "Trust region methods (Vol. 1). Siam." ?

Possible incorrect handling of hard case

Hey again! Thanks for your quick response on my previous issue. I may have stumbled across another one. Consider the following:

N = 50

B = np.random.rand(N, N)
B += B.T
g = np.random.rand(N)
lambda_nplus = max(-scipy.linalg.eigh(B, eigvals_only=True, eigvals=(0, 0)), 0)
eigs, V = np.linalg.eigh(B)
# make sure indefinite
assert min(eigs) < 0 and max(eigs) > 0
v1 = V[:, 0]

# make gamma_1 = Ug_1 == 0
g = v1 - g * (v1.T @ v1)/(g.T @ v1)
assert abs(v1 @ g) < 1e-10
assert (V.T @ g)[0] < 1e-10
p = _AuxiliaryProblem(None, g, B, 10, lambda_nplus, 1e-4, 1e4)

print(p.solve())

This should trigger the hard-case (B indefinite, Ug_1 == 0) [1], but it does not reliably. Sometimes, it will trigger the hard case code, but then the output will be imaginary.

I'd love to submit a pull-request with a fix, but I'm actually not quite sure on how to fix this one!

[1]: https://people.maths.ox.ac.uk/cartis/papers/ARCpI.pdf -- Page 27, just below formula 6.5.