Non-linear root finding when the Jacobian is almost singular

Question

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!

Answer 1

Assuming your jacobian isn't too large, it's a good idea to solve for your newton direction by QR factorization when your jacobian has a large condition number. It is numerically stable since it breaks the problem into two separate systems with the minimum error amplification factor allowed by the original problem. See here for details.

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).