Welcome to the OR-Exchange, your site for questions and answers in operations research.

3

Hi all,

I want to solve a large-scale system of nonlinear equations. The number of variables is greater than 20,000.

I would like to use Newton's method for this problem. Since the Jacobian matrix is too large to invert (>20,000x20,000 in dimension, and it is dense), I decide to approximate it by its diagonal. Under this approximation I obtain the (approximated) Newton direction, I then perform a line search along this direction using Armijo's rule (also called backtracking line search) to minimize the sum of squared residuals of all equations.

The problem is, Armijo's rule only works when the search direction is a descent direction, but in my problem the approximated Newton direction may turn out to be an ascent direction. In this case the line search algorithm breaks down. How should I fix the line search if the approximated Newton direction is an ascent direction?

The actual dilemma is the following. If I move too little in this step, the approximated Newton direction in the next step may remain an ascent direction, because nothing changes very much. If I move too much, the further I move, the greater the sum of squared residuals (which means I am further away from the solution - EDIT an increase in the sum of squared residuals doesn't necessarily imply moving away from the solution. Thanks to Sid for pointing out this.). Hence it is important to find a good step size.

Thank you! By the way I love this website! (I am a master student studying Operations Research.)

flag
Hey, I'm basically a novice with nonlinear numerical optimization. I would like to ask a question about your question though - I don't understand why moving too much in the ascent direction would necessarily mean moving away from the solution unless this is system of equations is convex. Please correct me if I'm getting something wrong here! – Sid Jul 18 at 2:05
more specifically unless the sum of squared residuals is a convex function. – Sid Jul 18 at 2:13
Yes you are right. In my case, the sum of squared residuals is not a convex function, hence an increase in its value doesn't necessarily imply moving away from the solution. – Daizhuo Chen Jul 18 at 2:55

2 Answers

4

I may be missing something quite basic here. If d is the direction you obtain from the approximated Jacobian, are you saying that the sum of squares increases in both directions d and -d? (So your current solution x is a local min along the line x +/- d?) Otherwise, I don't see the problem: if SSE increases in direction d, go in direction -d.

link|flag
5

In my experience working with nonlinear optimization problems (not nonlinear system of equations), I have seen that direct implementation of Wolfe-Powell conditions are better than backtracking line search algorithms for finding step length. For one such implementation, see Section 3.5 of Numerical Optimization, 2nd Ed., Nocedal and Wright. This algorithm is actually and adaptation of the same from "Practical Methods of Optimization, 2nd ed." by Fletcher. I suggest you take a look at both the books and the line search paper by More and Thuente. My implementation was an adaptation of the Nocedal-Wright algorithm, augmented by a few things from the Fletcher book, and then I added some boundary conditions from the More-Thuente paper. You can also look at the code for More-Thuente algorithm, it is available inside quite a few open-source packages. Hope this helps.

link|flag
Nocedal and Wright's book is very helpful. I will try the Nocedal-Wright algorithm later on. Thank you very much! – Daizhuo Chen Jul 20 at 2:24

Your Answer

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