Thread Subject: A technical question on stopping criterion of Newton Method

I'm composing an realtime algo by using Newton method to seek minimization of a log function:

min: a1*x1+b1*x2 - log (a2*x1+b2*x2 - c2) ... - log(a7*x1+b7*x2-c7)

Essentially, I'm using barrier method to transform an linear programming problem below

min: Cx
St. Ax<b

into a unconstrained minimization problem.

The standard stopping criterion is small enough
Gradient (Objective) * Hessian( Objective function) * Gradient (Objective), which is an approximation of f(x) and f(x*) (real optimized value).

However, the above value will not be small eventhough the x is very close to the solution because it is on the boundary of the log function. While the slope of log function is so steep on the boundary!

So how to handle those stopping cretirion when the solution is close to the boundary?

Thanks,
Hong

"Hong" <honghaot@gmail.com> wrote in message <hka4is$5f8$1@fred.mathworks.com>...
> I'm composing an realtime algo by using Newton method to seek minimization of a log function:
>
> min: a1*x1+b1*x2 - log (a2*x1+b2*x2 - c2) ... - log(a7*x1+b7*x2-c7)
>
> Essentially, I'm using barrier method to transform an linear programming problem below
>
> min: Cx
> St. Ax<b
>
> into a unconstrained minimization problem.
>
> The standard stopping criterion is small enough
> Gradient (Objective) * Hessian( Objective function) * Gradient (Objective), which is an approximation of f(x) and f(x*) (real optimized value).
>
> However, the above value will not be small eventhough the x is very close to the solution because it is on the boundary of the log function. While the slope of log function is so steep on the boundary!
>

I think you're really after is

Gradient (Objective) * inv(Hessian( Objective function)) * Gradient (Objective),

or perhaps more simply

 norm( inv(Hessian( Objective function)) * Gradient (Objective) )

Basically, it means you want to stop when the Newton step gets sufficiently small in magnitude. It's one of the better stopping criteria that you could use, but typically the computational cost of computing the Hessian (or it s inverse) precludes it.

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hka5d4$sl4$1@fred.mathworks.com>...

>
> norm( inv(Hessian( Objective function)) * Gradient (Objective) )
>
> Basically, it means you want to stop when the Newton step gets sufficiently small in magnitude. It's one of the better stopping criteria that you could use, but typically the computational cost of computing the Hessian (or it s inverse) precludes it.

You confuse me: inv(Hessian( Objective function)) * Gradient (Objective) IS the Newton step.

To OP: You simply bump into THE drawback of barrier method, the reason why this formulation should be avoid.

Bruno

Matt, you are absolutely right. The stopping cretirion is Gradient (Objective) * inv(Hessian( Objective function)) * Gradient (Objective).

the problem is that my objective function have log inside. And intuitively, the solution (min) will be close to the boundary of that log function, which is true.

However, the stopping criterion will give me a huge number since log function drop steeply when it is close to the boundary.

The assumption of above stopping criterion that gradient(Objective) = 0 is not true in this case.

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <hka5d4$sl4$1@fred.mathworks.com>...
> "Hong" <honghaot@gmail.com> wrote in message <hka4is$5f8$1@fred.mathworks.com>...
> > I'm composing an realtime algo by using Newton method to seek minimization of a log function:
> >
> > min: a1*x1+b1*x2 - log (a2*x1+b2*x2 - c2) ... - log(a7*x1+b7*x2-c7)
> >
> > Essentially, I'm using barrier method to transform an linear programming problem below
> >
> > min: Cx
> > St. Ax<b
> >
> > into a unconstrained minimization problem.
> >
> > The standard stopping criterion is small enough
> > Gradient (Objective) * Hessian( Objective function) * Gradient (Objective), which is an approximation of f(x) and f(x*) (real optimized value).
> >
> > However, the above value will not be small eventhough the x is very close to the solution because it is on the boundary of the log function. While the slope of log function is so steep on the boundary!
> >
>
> I think you're really after is
>
> Gradient (Objective) * inv(Hessian( Objective function)) * Gradient (Objective),
>
> or perhaps more simply
>
> norm( inv(Hessian( Objective function)) * Gradient (Objective) )
>
> Basically, it means you want to stop when the Newton step gets sufficiently small in magnitude. It's one of the better stopping criteria that you could use, but typically the computational cost of computing the Hessian (or it s inverse) precludes it.

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hka6d0$48g$1@fred.mathworks.com>...

> You confuse me: inv(Hessian( Objective function)) * Gradient (Objective) IS the Newton step.
===================

You're right, forget it. I was thinking of something else.

"Hong" <honghaot@gmail.com> wrote in message <hka4is$5f8$1@fred.mathworks.com>...
 
> However, the above value will not be small eventhough the x is very close to the solution because it is on the boundary of the log function. While the slope of log function is so steep on the boundary!
=======================

It's been a while since I've studied interior point methods, but I think the idea was that you apply the log() barrier homotopically. In other words, instead of using plain old -log() as a barrier, you solve a sequence of problems parametrized by t with a barrier looking something like -log(t*x). Each time you solve the problem subject to
-log(t*x) you then increase t and repeat the optimization using the last solution x as the initial point. With increasing t, the steep part of the barrier is pushed closer and closer to the boundary of the feasible set, allowing the algorithm to approach the boundary if it needs to. You continue to iterate over t and x this way until increasing t makes no significant change in the solution.


I think it's just a matter of going back to a reference book and seeing how they do this...