3
$\begingroup$

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!

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

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

$\endgroup$
  • $\begingroup$ Thank for the link Paul. It's not a first time that I manage to solve a system with the QR, when every other method fails. Now it's time for me to understand why! :) $\endgroup$ – Jugurtha Mar 20 '13 at 22:05
  • $\begingroup$ No problem. However, I must also caution that QR factorization has a high computational cost (at least as much as LU factorization). $\endgroup$ – Paul Mar 20 '13 at 22:55

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.