# Non-linear root finding when the Jacobian is almost singular

I'm trying to solve a system non linear-equations: $$\frac{\partial K(\mathbf{\lambda})}{\partial \lambda_i} - c_i = 0$$ for $i = 1, \dots, 15$, using Newton's method: $$\lambda^{k + 1} = \lambda^k + p^{k+1}$$ $$p^{k+1} = - J(\lambda_k)^{-1} \big (\nabla_\lambda K(\lambda_k) - \mathbf{c}\big ).$$ I know that the Jacobian has to be positive definite in my problem, but in practice it is often quite bad conditioned ( $k(J) \approx 10^{15}$ ). I am perturbing it's eigenvalues but still the algorithm doesn't manage to satisfy the convergence criterion: $$\bigg |\frac{\partial K(\mathbf{\lambda})}{\partial \lambda_i} - c_i \bigg |= 0$$ for some of the equations, while others converge quite rapidly. Increasing the number of iterations doesn't change anything.

My supervisor suggested me to use a blocked scheme where, if some of the equations have converged you keep iterating on the equations that have not. I don't quite understand how to use Newton's algorithm on a subgroup of equations so I would like to ask if somebody knows how this can be done. Alternatively I would appreciate suggestions on how to deal with this problem.

Thanks!

EDIT:

I must add that I'm using line search with objective function: $$f(\lambda) = K(\mathbf{\lambda}) - \mathbf{\lambda}^T \mathbf{c}$$ which should be fine because it is convex (in theory though because the Hessian is almost singular). I'm checking whether the step is decreasing the objective enough, that is I check: $$f(\lambda^k + \alpha p^k) < f(\lambda^k) + \gamma \, \alpha \, (\nabla_\lambda K(\lambda_k) - \mathbf{c}\big )^T p^k$$ with $\gamma = 10^{-4}$. If the condition is not true I divide $\alpha$ by 2. Most of the time the condition is true in the first step, so I rarely have to halve the step.

EDIT 2

It seems to be converging if I use a QR decomposition to solve the linear system, without perturbing the eigenvalues of $J$. Not sure whether I should trust the output though!

• Have you tried using a global convergence strategy like line search or trust region methods? – Paul Mar 19 '13 at 23:01
• @Paul Yes, I edited the question to explain what strategy I'm using to decide the step-length. – Jugurtha Mar 19 '13 at 23:52
• Did you implement sufficient decrease conditions (armijo's condition)? – Paul Mar 20 '13 at 2:25
• No, if the step decreases the objective by any degree I just accept it. – Jugurtha Mar 20 '13 at 10:40
• That may not be enough to guarantee fast convergence... See here, here, here, and here for more details. – Paul Mar 20 '13 at 14:06

This enables you to obtain the "best" possible approximation of the newton direction at each step in your algorithm. If you are using line-searching with backtracking and Armijo's sufficient decrease condition, this should guarantee convergence to the true root (assuming your function $f$ is smooth).