User Manual 4.6 Optimization
Introduction
Scope
This section describes PATRIUS optimization features. It provides solvers for general convex optimization problems, such as LP, QP, QCQP, etc.
Javadoc
The math framework classes are available in the package fr.cnes.sirius.patrius.math.optim.
| Library | Javadoc |
|---|---|
| Patrius | Package fr.cnes.sirius.patrius.math.optim |
Links
None as of now.
Useful Documents
None as of now.
Package Overview
TODO
Features Description
Optimizers
The JOptimizer class implements the convex optimizer (see "S.Boyd and L.Vandenberghe, Convex Optimization").
The algorithm selection is implemented as a Chain of Responsibility pattern, and this class is the client of the chain.
The different methods implemented to solve the convex optimization problem are:
- Interior point methods
PrimalDualMethod: primal-dual interior-point method.LPPrimalDualMethod: primal-dual interior-point method for linear problems.BarrierMethod
- Quality constrained minimization
NewtonLEConstrainedFSP: linear equality constrained newton optimizer, with feasible starting point.NewtonLEConstrainedISP: linear equality constrained newton optimizer, with infeasible starting point.
- Unconstrained minimization
NewtonUnconstrained: unconstrained newton optimizer.
Optimization problem
The OptimizationRequest class has all the settting field's necessaires to define an optimization problem.
The LPOptimizationRequest is an extension of this class for linear optimization problems.
The general form of a linear problem is (1):
min(c) s.t. A.x = b lb <= x <= ub
The OptimizationResponse is the class with the getters and setters to set and get the response after the optimization.
The LPOptimizationResponse is the extension class applied to linear problems.
Standard converter
The LPStandardConverter converts a general linear problem stated in the form (2):
min(c) s.t. G.x < h A.x = b lb <= x <= ub
to the (strictly)standard form:
min(c) s.t. A.x = b x >= 0
or to the (quasi)standard form (1).
Presolver
The LPPresolver implements a presolver for a linear problem in the form (1).
It applies a set of techniques on the linear programming problem before a linear programming solver solves it. This set of techniques aim at reducing the size of the LP problem by eliminating redundant constraints and variables and identifying possible infeasibility and unboundedness of the problem.
Solvers
The AbstractKKTSolver implements a solver for the KKT system:
H.v + [A]T.w = -g A.v = -h
where H is a square and symmetric matrix.
The following classes are an extension of AbstractKKTSolver:
AugmentedKKTSolver(for singular H)BasicKKTSolverUpperDiagonalHKKTSolver(for upper diagonal H)
Functions
Different functions are implemented, all of them twice differentiable.
- Linear functions
The LinearMultivariateRealFunction represents a function in the form of:
f(x) = q.x + r
- Quadratic functions
The QuadraticMultivariateRealFunction represents a function in the form of:
f(x) := 1/2 x.P.x + q.x + r
where x, q ∈ R n, P is a symmetric nXn matrix and r ∈ R.
With an extension in PSDQuadraticMultivariateRealFunction and PDQuadraticMultivariateRealFunction for P symmetric and positive semi-definite, and P symmetric and positive definite,respectively.
- Barrier functions
The LogarithmicBarrier is the default barrier function for the barrier method algorithm.
If fi(x) are the inequalities of the problem, then the function:
Φ(x) = − ∑_i (log(−fi(x)))
Algebra
Factorization
The CholeskyFactorization implements the Cholesky L.L[T] factorization and inverse for symmetric and positive matrix:
Q = L.L[T]
with L lower-triangular.
Getting Started
TODO
Contents
Interfaces
The most relevant interfaces related to the optimization are listed here :
| Interface | Summary | Javadoc |
|---|---|---|
| BarrierFunction | Interface for the barrier function used by a given barrier optimization method. | ... |
| ConvexMultivariateRealFunction | Interface for convex multivariate real functions. | ... |
| MatrixRescaler | An interface to classes that implement an algorithm to rescale matrices. | ... |
| StrictlyConvexMultivariateRealFunction | Interface for striclty convex multivariate real functions. | ... |
| TwiceDifferentiableMultivariateRealFunction | Interface for twice-differentiable multivariate functions. | ... |
Classes
The most relevant classes related to the optimization are listed here :
| Class | Summary | Javadoc |
|---|---|---|
| AbstractKKTSolver | Abstract class for solving KKT systems. | ... |
| AbstractLPOptimizationRequestHandler | Abstract class for Linear Problem Optimization Request Handler. | ... |
| BarrierMethod | Implements the Barrier Method. | ... |
| BasicPhaseIBM | Implements the Basic Phase I Method as a Barried Method. | ... |
| BasicPhaseILPPDM | Implements the Basic Phase I Method form LP problems as a Primal-Dual Method. | ... |
| BasicPhaseIPDM | Implements the Basic Phase I Method as a Primal-Dual Method. | ... |
| CholeskyFactorization | Implements the Cholesky L.L[T] factorization and inverse for symmetric and positive matrix. | ... |
| JOptimizer | Implements the convex optimizer. | ... |
| LinearMultivariateRealFunction | Defines a linear multivariate function in the form f(x) = q.x + r. | ... |
| LogarithmicBarrier | Default barrier function for the barrier method algorithm. | ... |
| LPOptimizationRequest | Implements a linear optimization problem. | ... |
| LPOptimizationResponse | Response of the linear optimization problem. | ... |
| LPPresolver | Presolver for a linear problem. | ... |
| LPPrimalDualMethod | Implements the Primal-dual interior-point method for linear problems. | ... |
| LPStandardConverter | Converts a general LP problem into a strictly standard or quasi standard form. | ... |
| Matrix1NornRescaler | Calculates the matrix rescaling factors so that the 1-norm of each row and each column of the scaled matrix asymptotically converges to one. | ... |
| NewtonLEConstrainedFSP | Linear equality constrained newton optimizer, with feasible starting point. | ... |
| NewtonLEConstrainedISP | Linear equality constrained newton optimizer, with infeasible starting point. | ... |
| NewtonUnconstrained | Unconstrained newton optimizer. | ... |
| OptimizationRequest | Implements an optimization problem. | ... |
| OptimizationRequestHandler | Generic class for optimization process. | ... |
| OptimizationResponse | Optimization process output: stores the solution as well as an exit code. | ... |
| PrimalDualMethod | Implements a primal-dual interior-point method. | ... |
| QuadraticMultivariateRealFunction | Implements a quadratic multivariate function in the form of f(x):= 1/2 x.P.x + q.x + r. | ... |
