4
$\begingroup$

So given an objective function $f({\bf x})$, I would like to include a positivity constraint when I perform the fixed point iteration: $${\bf x}^{(t+1)}={\bf x}^{(t)} - \text{H}_f^{-1}\nabla f({\bf x}^{(t)}),$$

for ${\bf x}^{(0)}>{\bf 0}$.

The best way I've found to do it is to add a log barrier to the objective function so it becomes $$g({\bf x}) = f({\bf x})+\frac{1}{n}\sum_{i=1}^n\log{\bf x}_i,$$ since this will cause $\nabla g$ to shoot to infinity as one approaches $\bf 0$ from the positive orthant. And then to modify the iteration step size to prevent the step size from being large enough to cross all the way over the log barrier to the other side: $${\bf x}^{(t+1)}={\bf x}^{(t)} - \frac{1}{2}\min\Big[2, \frac{\left\|{\bf x}^{(t)}\right\|}{\left\|\text{H}_g^{-1}\nabla g({\bf x}^{(t)})\right\|}\Big]\text{H}_g^{-1}\nabla g({\bf x}^{(t)}).$$

Is this the best way to enforce a positivity constraint on Newton's Method, or is there a better way?

$\endgroup$
  • 1
    $\begingroup$ That is indeed the standard approach; besides modifying the step size, one usually also tries to reduce the log barrier influence by replacing $1/n$ by a sequence $\beta_k\to 0$. If both modifications are done in a certain way, this is known as an interior point method (which is still the state of the art for problems of this type). $\endgroup$ – Christian Clason Mar 29 '16 at 10:51
  • $\begingroup$ @ChristianClason, ok well it looks like I'm on the right track then, I'll check out interior point methods, thanks. $\endgroup$ – Thoth Mar 29 '16 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.