com.numericalmethod.suanshu.optimization.constrained.convex.sdp.pathfollowing

Class PrimalDualPathFollowing

java.lang.Object

com.numericalmethod.suanshu.optimization.constrained.convex.sdp.pathfollowing.PrimalDualPathFollowing

All Implemented Interfaces:

ConstrainedMinimizer<SDPDualProblem,IterativeMinimizer<CentralPath>>, Minimizer<SDPDualProblem,IterativeMinimizer<CentralPath>>, Optimizer<SDPDualProblem,IterativeMinimizer<CentralPath>>, java.io.Serializable

public class PrimalDualPathFollowing
extends java.lang.Object
implements ConstrainedMinimizer<SDPDualProblem,IterativeMinimizer<CentralPath>>

The Primal-Dual Path-Following algorithm is an interior point method that solves Semi-Definite Programming problems. In theory, the algorithm assumes feasible starting points. In practice when there is no feasible starting point, the program utilizes an infeasible interior point method. Specifically, this implementation relaxes the feasible constraints and require only the initials X₀ and S₀ be positive definite. For example, let X₀ and S₀ be identity matrices, y₀ be a zero vector. This implementation adds one more condition to the terminal condition of iterations. That is,

phi = delta(duality gap) + norm(rd) + norm(rp)

where norm(rd) + norm(rp) measures the feasibility of solution.

See Also:

"Andreas Antoniou, Wu-Sheng Lu, "Algorithm 14.1, Primal-dual path-following algorithm," Practical Optimization: Algorithms and Engineering Applications.", Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	PrimalDualPathFollowing.Solution This is the solution to a Semi-Definite Programming problem using the Primal-Dual Path-Following algorithm.

Constructor Summary

Constructors

Constructor and Description
PrimalDualPathFollowing(double epsilon) Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.
PrimalDualPathFollowing(double gamma0, double epsilon) Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.
PrimalDualPathFollowing(double gamma0, double sigma0, double epsilon) Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.

Method Summary

Modifier and Type	Method and Description
protected static double	getMinEigenValue(Matrix A, double epsilon) Get the minimum of all the eigen values of a matrix.
PrimalDualPathFollowing.Solution	solve(SDPDualProblem problem) Solve an optimization problem, e.g., OptimProblem.

Methods inherited from class java.lang.Object

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

Constructor Detail

PrimalDualPathFollowing

public PrimalDualPathFollowing(double gamma0,
                               double sigma0,
                               double epsilon)

Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.

Parameters:

gamma0 - \(0 < \gamma < 1\). It ensures the next iterates are inside the feasible set; suggested values are between 0.9 and 0.99.

sigma0 - \(0 \leq \sigma < 1\), the centering parameter

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

PrimalDualPathFollowing

public PrimalDualPathFollowing(double gamma0,
                               double epsilon)

Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.

Parameters:

gamma0 - \(0 < \gamma < 1\). It ensures the next iterates are inside the feasible set; suggested values are between 0.9 and 0.99.

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

PrimalDualPathFollowing

public PrimalDualPathFollowing(double epsilon)

Construct a Primal-Dual Path-Following minimizer to solve semi-definite programming problems.

Parameters:

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

Method Detail

solve

public PrimalDualPathFollowing.Solution solve(SDPDualProblem problem)
                                       throws java.lang.Exception

Description copied from interface: Optimizer

Solve an optimization problem, e.g., OptimProblem.

Specified by:

solve in interface Optimizer<SDPDualProblem,IterativeMinimizer<CentralPath>>

Parameters:

problem - an optimization problem

Returns:

a solution to the optimization problem

Throws:

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

getMinEigenValue

protected static double getMinEigenValue(Matrix A,
                                         double epsilon)

Get the minimum of all the eigen values of a matrix.

Parameters:

A - a matrix

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

Returns:

the minimum of all the eigen values of a matrix