2
$\begingroup$

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.

enter image description here

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?

$\endgroup$
8
  • 1
    $\begingroup$ Jumping may happen if you use inexact line search. Next time add labels to your axes. $\endgroup$
    – LinAlg
    Oct 27 '16 at 16:01
  • $\begingroup$ @LinAlg What is inexact line search? Can I disable it? $\endgroup$
    – tomka
    Oct 27 '16 at 16:02
  • $\begingroup$ @LinAlg see update for options in fmin_tnc related to line search. Any idea? $\endgroup$
    – tomka
    Oct 27 '16 at 16:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – user251257
    Oct 27 '16 at 16:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – user251257
    Oct 27 '16 at 16:22
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So your alpha is probably eta in the function? See edit above. It seems that there is no way to switch exact line search on? $\endgroup$
    – tomka
    Oct 27 '16 at 16:30
  • $\begingroup$ No, $\eta$ is a parameter of a heuristic that selects $\alpha$. $\endgroup$
    – LinAlg
    Oct 27 '16 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.