# Is it normal that Newton Conjugate gradient algorithm makes "jumps"?

I maximize a (log-likelihood) function and I have been told that this function for this particular implementation should be monotonically increasing during maximization. I am using Newton conjugate gradient ascent implemented in Python's scipy.optimize.fmin_tnc (and I believe there is a similar matlab implementation).

I observe the objective function as it is maximized. See picture. I observe jumps in the function values in many repetitions of the procedure (with different random starting initializations; each line is one optimization path with different starting values).

I wonder whether this is possible when the function in monotonic and may be due to the algorithm, but I know too little about the algorithm and its implementation to be able to tell. Is this plausible at all?

The final solution seems close to what is expected.

Edit: Following @LinAlg's answer: there are two parameters to contol line search:

eta : float, optional. Severity of the line search. if < 0 or > 1, set to 0.25. Defaults to -1.

stepmx : float, optional. Maximum step for the line search. May be increased during call. If too small, it will be set to 10.0. Defaults to 0.

What could I try here?

• Jumping may happen if you use inexact line search. Next time add labels to your axes. Oct 27 '16 at 16:01
• @LinAlg What is inexact line search? Can I disable it? Oct 27 '16 at 16:02
• @LinAlg see update for options in fmin_tnc related to line search. Any idea? Oct 27 '16 at 16:06
• only if you could compute in exact arithmetic ... which is basically never the case. Apart from rounding error, most nonlinear problem can be solved exactly and in finitely many steps. Oct 27 '16 at 16:17
• As @LinAlg said, it could happen. The mode and dynamic of the oscillation depend on many factors. To start with, you should post the objective function. But probably only few people know the implementation in scipy and are able to say something about your particular case. Oct 27 '16 at 16:22

You want to minimize $f(x)$ (which is the negative log-likelihood). The conjugate gradient method gives a search direction $v$. In iteration $k$, the iterate is updated $x^{k+1} = x^k + \alpha v$. Selecting $\alpha$ is called line search. If line search is exact (meaning that it minimizes $f(x^k + \alpha v)$), jumping cannot occur. However, exact line search takes time, especially for nonconvex functions (your $f$ is probably convex).
From the source code (look for static ls_rc linearSearch) it becomes clear that scipy uses the Line search algorithm of Gill and Murray. It does not always find the best $\alpha$, but makes a trade-off with the number of function evaluations.
• No, $\eta$ is a parameter of a heuristic that selects $\alpha$. Oct 27 '16 at 16:35