4
$\begingroup$

This is a very basic question about Newton's method for optimization, but I cannot seem to find the answer in any of my searches. If we are using Newton's method (or gradient descent), how do we find a maximum instead of a minimum? Do we just change the sign of the step size to positive instead of negative?

$\endgroup$

2 Answers 2

5
$\begingroup$

Newton's method for unconstrained optimization finds local extrema. Given a function $f(\mathbf{x}):\mathbb{R}^n \to \mathbb{R}$ which we wish to minimize, Newton's method works by finding a root of $\nabla f(\mathbf{x})$. Absent any other information about the behavior of $f$, if Newton's method converges for some arbitrary initial guess, we don't know whether we've found a local minimum or maximum (or saddle point). Writing the iteration as $$\mathbf{x}_{n+1} = \mathbf{x}_n - H^{-1}\nabla f(\mathbf{x}_n)$$ where $H$ is the Hessian, it sounds to me like you're asking whether we might find a maximum by instead computing $\mathbf{x}_{n+1} = \mathbf{x}_n + H^{-1}\nabla f(\mathbf{x}_n)$, where we have changed the sign of the second term. This will not get us anywhere, as it moves away from a stationary point. To use Newton's method in an unconstrained optimization problem to find a maximum, you would use it exactly the same way as if you sought a minimum, probably with a different initial guess. Wikipedia's entry on Newton's method in unconstrained optimization offers a succinct discussion of the concept.

Descent methods, on the other hand, work differently; gradient descent, for example, updates each iteration by moving along a direction such that $f(\mathbf{x})$ decreases. In this case, it makes sense to change the sign of the update if you are seeking a maximum instead.

$\endgroup$
4
$\begingroup$

Yes, that's exactly what you do. You can think of this sign change as causing you to perform gradient ascent instead of gradient descent (in the case of using a gradient method). Alternatively, you can think of flipping the sign in a gradient method as performing gradient descent in $-f$. By finding a minimum of $-f$ you find a maximum of $f$.

Similar reasoning holds for Newton's method (and various other methods as well).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .