com.numericalmethod.suanshu.optimization.unconstrained.steepestdescent

Class SteepestDescent

java.lang.Object

com.numericalmethod.suanshu.optimization.unconstrained.steepestdescent.SteepestDescent

All Implemented Interfaces:

Minimizer<C2OptimProblem,IterativeMinimizer<Vector>>, Optimizer<C2OptimProblem,IterativeMinimizer<Vector>>, MultivariateMinimizer<IterativeMinimizer<Vector>>, java.io.Serializable

Direct Known Subclasses:

ConjugateGradient, FirstOrder, GaussNewton.MySteepestDescent, NewtonRaphson, Powell, QuasiNewton, Zangwill

public abstract class SteepestDescent
extends java.lang.Object
implements MultivariateMinimizer<IterativeMinimizer<Vector>>

A steepest descent algorithm finds the minimum by moving along the negative of the steepest gradient direction. In each iteration, we compute a direction, e.g., d_k = −g as in the first order approximation. We search along this direction for an improved minimizer by analytically computing α_k that minimizes f(x_k + α_k * d_k). The minimizer x_k+1 = x_k + α_k * d_k is updated. This procedure is repeated until the increment |α_k * d_k| becomes sufficiently small, hence convergence.

See Also:

• "Andreas Antoniou and Wu-Sheng Lu, "Algorithms 5.2, 5.3, 5.5," Practical Optimization: Algorithms and Engineering Applications."
• Wikipedia: Gradient descent

, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	SteepestDescent.SteepestDescentImpl This is an implementation of the steepest descent method.

Field Summary

Fields

Modifier and Type	Field and Description
protected double	epsilon a precision parameter: when a number |x| ≤ ε, it is considered 0
protected double	maxIterations the maximum number of iterations

Constructor Summary

Constructors

Constructor and Description
SteepestDescent(double epsilon, int maxIterations) Construct a multivariate minimizer using a steepest descent method.
SteepestDescent(LineSearch linesearch, double epsilon, int maxIterations) Construct a multivariate minimizer using a steepest descent method.

Method Summary

Modifier and Type	Method and Description
abstract IterativeMinimizer<Vector>	solve(C2OptimProblem problem) Solve a minimization problem with a C2 objective function.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

epsilon

protected final double epsilon

a precision parameter: when a number |x| ≤ ε, it is considered 0

maxIterations

protected final double maxIterations

the maximum number of iterations

Constructor Detail

SteepestDescent

public SteepestDescent(LineSearch linesearch,
                       double epsilon,
                       int maxIterations)

Construct a multivariate minimizer using a steepest descent method.

Parameters:

linesearch - the line search method used in each iteration

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

maxIterations - the maximum number of iterations

SteepestDescent

public SteepestDescent(double epsilon,
                       int maxIterations)

Construct a multivariate minimizer using a steepest descent method.

Parameters:

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

maxIterations - the maximum number of iterations

Method Detail

solve

public abstract IterativeMinimizer<Vector> solve(C2OptimProblem problem)
                                          throws java.lang.Exception

Solve a minimization problem with a C² objective function.

Specified by:

solve in interface Optimizer<C2OptimProblem,IterativeMinimizer<Vector>>

Parameters:

problem - a minimization problem with a C² objective function

Returns:

a minimizer

Throws:

java.lang.Exception - when there is an error solving the problem