6
$\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?

Improve this question
$\endgroup$
2
  • 3
    $\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
    Commented Mar 29, 2016 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$
    – Set
    Commented Mar 29, 2016 at 20:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.