Admin tsn le 5 septembre 2024 à 15:17

2024-09-05T15:17:45Z

Admin tsn : Page créée avec « NOTOC == Introduction == === Scope === This section describes PATRIUS optimization features. It will focus on the ''JOptimizer'' functionalities, which provides solv... »

2024-09-02T07:57:58Z

Page créée avec « __NOTOC__ == Introduction == === Scope === This section describes PATRIUS optimization features. It will focus on the ''JOptimizer'' functionalities, which provides solv... »

Nouvelle page

__NOTOC__
== Introduction ==
=== Scope ===
This section describes PATRIUS optimization features.

It will focus on the ''JOptimizer'' functionalities, which provides solvers for general convex optimization problems. In particular it provides the Following optimization solvers:
* LP: Linear programming (linear criterion and constraints)
* QP: Quadratic Programming (quadratic criterion and linear constraints)
* QCQP: Qaudratically Constrained Quadratic Programming (quadratic criterion and constraints)

=== Javadoc ===
The optimization classes are available in the package <code>fr.cnes.sirius.patrius.math.optim</code>.

{| class="wikitable"
|-
! scope="col"| Library
! scope="col"| Javadoc
|-
|Patrius
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/package-summary.html Package fr.cnes.sirius.patrius.math.optim]
|}

=== Links ===
None as of now.

=== Useful Documents ===
None as of now.

=== Package Overview ===
The optimization functionalities for joptimizer are organized in the following packages:
*<code>fr.cnes.sirius.patrius.math.optim.joptimizer.algebra</code> compounds the classes with the algebra functionalities.
*<code>fr.cnes.sirius.patrius.math.optim.joptimizer.functions</code> compounds the classes with the optimization functions.
*<code>fr.cnes.sirius.patrius.math.optim.joptimizer.optimizers</code> compounds the classes with the optimizers.
*<code>fr.cnes.sirius.patrius.math.optim.joptimizer.solvers</code> compounds the classes with the solvers.
*<code>fr.cnes.sirius.patrius.math.optim.joptimizer.util</code> compounds the utility classes.

== Features Description ==
Features descritpion for the joptimizer package.
=== Optimizers ===
The <code>JOptimizer</code> 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
**<code>PrimalDualMethod</code> : primal-dual interior-point method.
**<code>LPPrimalDualMethod</code> : primal-dual interior-point method for linear problems.
**<code>BarrierMethod</code>
*Quality constrained minimization
**<code>NewtonLEConstrainedFSP</code> : linear equality constrained newton optimizer, with a feasible starting point.
**<code>NewtonLEConstrainedISP</code> : linear equality constrained newton optimizer, with an infeasible starting point.
*Unconstrained minimization
**<code>NewtonUnconstrained</code> : unconstrained newton optimizer.

==== Optimization problem ====
The <code>OptimizationRequest</code> class has all the setting field's necessaires to define an optimization problem.

The <code>LPOptimizationRequest</code> is an extension of this class for linear optimization problems.

The general form of a linear problem is (1):
<syntaxhighlight lang="java">
min(c) s.t.
A.x = b
lb <= x <= ub
</syntaxhighlight>

The <code>OptimizationResponse</code> is the class with the getters and setters to set and get the response after the optimization.
The <code>LPOptimizationResponse</code> is the extended class applied to linear problems.

==== Standard converter ====
The <code>LPStandardConverter</code> converts a general linear problem stated in the form (2):
<syntaxhighlight lang="java">
min(c) s.t.
G.x < h
A.x = b
lb <= x <= ub
</syntaxhighlight>
to the (strictly)standard form:
<syntaxhighlight lang="java">
min(c) s.t.
A.x = b
x >= 0
</syntaxhighlight>
or to the (quasi)standard form (1).

==== Presolver ====
The <code>LPPresolver</code> implements a presolver for a linear problem in the form (1).

It applies a set of techniques to the linear programming problem before a linear programming solver solves it. This set of techniques aims 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 <code>AbstractKKTSolver</code> implements a solver for the KKT system:
<syntaxhighlight lang="java">
H.v + [A]T.w = -g
A.v = -h
</syntaxhighlight>
where H is a square and symmetric matrix.

The following classes are an extension of <code>AbstractKKTSolver</code>:
*<code>AugmentedKKTSolver</code> (for singular H)
*<code>BasicKKTSolver</code>
*<code>UpperDiagonalHKKTSolver</code> (for upper diagonal H)

=== Functions ===
Different functions are implemented, all of them twice differentiable.
*Linear functions
The <code>LinearMultivariateRealFunction</code> represents a function in the form of:
<syntaxhighlight lang="java">
f(x) = q.x + r
</syntaxhighlight>

*Quadratic functions
The <code>QuadraticMultivariateRealFunction</code> represents a function in the form of:
<syntaxhighlight lang="java">
f(x) := 1/2 x.P.x + q.x + r
</syntaxhighlight>
where x, q ∈ R <sup>n</sup>, P is a symmetric nXn matrix and r ∈ R.

With the extended <code>PSDQuadraticMultivariateRealFunction</code> and <code>PDQuadraticMultivariateRealFunction</code> classes for P symmetric and positive semi-definite, and P symmetric and positive definite, respectively.

*Barrier functions
The <code>LogarithmicBarrier</code> is the default barrier function for the barrier method algorithm.

If f<sub>i</sub>(x) are the inequalities of the problem, then the function:
<syntaxhighlight lang="java">
Φ(x) = − ∑_i (log(−fi(x)))
</syntaxhighlight>

=== Algebra ===
==== Factorization ====
The <code>CholeskyFactorization</code> implements the Cholesky L . L[T] factorization and inverse for symmetric and positive matrix:
<syntaxhighlight lang="java">
Q = L.L[T]
</syntaxhighlight>
with L lower-triangular.

==== Rescaler ====
The <code>Matrix1NornRescaler</code> calculates the matrix rescaling factors, so that the 1-norm of each row and each column of the scaled matrix asymptotically converges to one.

== Getting Started ==
=== Example 1 ===
Example of a linear problem optimized by the primal-dual interior-point method.

The problem is:
<syntaxhighlight lang="java">
min(-100x + y) s.t.
x - y = 0
0 <= x <= 1
0 <= y <= 1
</syntaxhighlight>

First, the definition of the variables:
<syntaxhighlight lang="java">
final double[] c = new double[] { -100, 1 }
final double[][] a = new double[][] { { 1, -1 } }
final double[] b = new double[] { 0 }
final double[] lb = new double[] { 0, 0 }
final double[] ub = new double[] { 1, 1 }
</syntaxhighlight>

Definition of the optimization problem by setting the variables:
<syntaxhighlight lang="java">
final LPOptimizationRequest or = new LPOptimizationRequest()
or.setC(c)
or.setA(a)
or.setB(b)
or.setLb(lb)
or.setUb(ub)
</syntaxhighlight>

Additional parameters (tolerance, check the solution accuracy, etc) can also be setted:
<syntaxhighlight lang="java">
or.setCheckKKTSolutionAccuracy(true)
or.setToleranceFeas(1.E-7)
or.setTolerance(1.E-7)
or.setDumpProblem(true)
or.setRescalingDisabled(true)
</syntaxhighlight>

Definition of the optimizer and setting the optimization problem:
<syntaxhighlight lang="java">
LPPrimalDualMethod opt = new LPPrimalDualMethod()
opt.setLPOptimizationRequest(or)
</syntaxhighlight>

Optimization and check that it has not failed:
<syntaxhighlight lang="java">
final int returnCode = opt.optimize()
if (returnCode == OptimizationResponse.FAILED) {
fail()
}
</syntaxhighlight>

Recuperate the response and the solution:
<syntaxhighlight lang="java">
final LPOptimizationResponse response = opt.getLPOptimizationResponse()
final double[] sol = response.getSolution()
</syntaxhighlight>

Validation:
<syntaxhighlight lang="java">
final RealVector cVector = new ArrayRealVector(c)
final RealVector solVector = new ArrayRealVector(sol)
final double value = cVector.dotProduct(solVector)
assertEquals(2, sol.length)
assertEquals(1, sol[0], or.getTolerance())
assertEquals(1, sol[1], or.getTolerance())
assertEquals(-99, value, or.getTolerance())
</syntaxhighlight>

=== Example 2 ===
Example of the optimization of a linear objective function with quadratic constraints.

The problem is:
<syntaxhighlight lang="java">
min(-e.x) s.t.
1/2 x.P.x < v
x + y + z = 1
x > 0
y > 0
z > 0
</syntaxhighlight>

Definition of the linear objective function:
<syntaxhighlight lang="java">
final double[] e = { -0.018, -0.025, -0.01 }
final LinearMultivariateRealFunction objectiveFunction = new LinearMultivariateRealFunction(e, 0)
</syntaxhighlight>

Definition of the quadratic and linear constraints:
<syntaxhighlight lang="java">
final double[][] p = { { 1.68, 0.34, 0.38 }, { 0.34, 3.09, -1.59 }, { 0.38, -1.59, 1.54 } }
final double v = 0.3
final PDQuadraticMultivariateRealFunction qc0 = new PDQuadraticMultivariateRealFunction(p, null,-v)
final LinearMultivariateRealFunction lc0 = new LinearMultivariateRealFunction(new double[] { -1, 0, 0 }, 0)
final LinearMultivariateRealFunction lc1 = new LinearMultivariateRealFunction(new double[] { 0, -1, 0 }, 0)
final LinearMultivariateRealFunction lc2 = new LinearMultivariateRealFunction(new double[] { 0, 0, -1 }, 0)
final ConvexMultivariateRealFunction[] constraints = new ConvexMultivariateRealFunction[] { qc0, lc0, lc1, lc2 }
</syntaxhighlight>

Definition of the equality constraint:
<syntaxhighlight lang="java">
final double[][] a = {{ 1, 1, 1 }}
final double[] b = { 1 }
</syntaxhighlight>

Definition of the optimization problem and setting the parameters:
<syntaxhighlight lang="java">
final OptimizationRequest or = new OptimizationRequest()
or.setF0(objectiveFunction)
or.setFi(constraints)
or.setA(a)
or.setB(b)
or.setToleranceFeas(1.e-6) // additional parameter
</syntaxhighlight>

Definition of the optimizer and setting the optimization problem:
<syntaxhighlight lang="java">
final JOptimizer opt = new JOptimizer()
opt.setLPOptimizationRequest(or)
</syntaxhighlight>

Optimization and check that it has not failed:
<syntaxhighlight lang="java">
final int returnCode = opt.optimize()
if (returnCode == OptimizationResponse.FAILED) {
fail()
}
</syntaxhighlight>

Recuperate the response and the solution:
<syntaxhighlight lang="java">
final LPOptimizationResponse response = opt.getLPOptimizationResponse()
final double[] sol = response.getSolution()
</syntaxhighlight>

Validation:
<syntaxhighlight lang="java">
assertEquals(1., sol[0] + sol[1] + sol[2], 1.e-6)
assertTrue(sol[0] > 0)
assertTrue(sol[1] > 0)
assertTrue(sol[2] > 0)
final RealVector xVector = MatrixUtils.createRealVector(sol)
final RealMatrix pMatrix = MatrixUtils.createRealMatrix(p)
final double xPx = xVector.dotProduct(pMatrix.operate(xVector))
assertTrue(0.5 * xPx < v)
</syntaxhighlight>

== Contents ==
=== Interfaces ===
The interfaces related to the joptimizer are listed here :

{| class="wikitable"
|-
! scope="col"| Interface
! scope="col"| Summary
! scope="col"| Javadoc
|-
|'''BarrierFunction'''
|Interface for the barrier function used by a given barrier optimization method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/BarrierFunction.html ...]
|-
|'''ConvexMultivariateRealFunction'''
|Interface for convex multivariate real functions.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/ConvexMultivariateRealFunction.html ...]
|-
|'''MatrixRescaler'''
|An interface to classes that implement an algorithm to rescale matrices.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/algebra/MatrixRescaler.html ...]
|-
|'''StrictlyConvexMultivariateRealFunction'''
|Interface for striclty convex multivariate real functions.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/StrictlyConvexMultivariateRealFunction.html ...]
|-
|'''TwiceDifferentiableMultivariateRealFunction'''
|Interface for twice-differentiable multivariate functions.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/TwiceDifferentiableMultivariateRealFunction.html ...]
|}

=== Classes ===
The classes related to the joptimizer are listed here :

{| class="wikitable"
|-
! scope="col"| Class
! scope="col"| Summary
! scope="col"| Javadoc
|-
|'''AlgebraUtils'''
|Algebraic utility operations
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/algebra/AlgebraUtils.html ...]
|-
|'''CholeskyFactorization'''
|Implements the Cholesky L.L[T] factorization and inverse for symmetric and positive matrix.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/algebra/CholeskyFactorization.html ...]
|-
|'''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.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/algebra/Matrix1NornRescaler.html ...]
|-
|'''FunctionsUtils'''
|Utility class for optimization function building.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/FunctionsUtils.html ...]
|-
|'''LinearMultivariateRealFunction'''
|Represents a function f(x) = q.x + r.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/LinearMultivariateRealFunction.html ...]
|-
|'''LogarithmicBarrier'''
|Default barrier function for the barrier method algorithm.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/LogarithmicBarrier.html ...]
|-
|'''PDQuadraticMultivariateRealFunction'''
|Extends the class QuadraticMultivariateRealFunction with P symmetric and positive definite.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/PDQuadraticMultivariateRealFunction.html ...]
|-
|'''PSDQuadraticMultivariateRealFunction'''
|Extends the class QuadraticMultivariateRealFunction with P symmetric and positive semi-definite.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/PSDQuadraticMultivariateRealFunction.html ...]
|-
|'''QuadraticMultivariateRealFunction'''
|Represents a quadratic multivariate function in the form of f(x):= 1/2 x.P.x + q.x + r.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/functions/QuadraticMultivariateRealFunction.html ...]
|-
|'''AbstractLPOptimizationRequestHandler'''
|Abstract class for Linear Problem Optimization Request Handler.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/AbstractLPOptimizationRequestHandler.html ...]
|-
|'''BarrierMethod'''
|Implements the Barrier Method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/BarrierMethod.html ...]
|-
|'''BasicPhaseIBM'''
|Implements the Basic Phase I Method as a Barried Method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/BasicPhaseIBM.html ...]
|-
|'''BasicPhaseILPPDM'''
|Implements the Basic Phase I Method form LP problems as a Primal-Dual Method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/BasicPhaseILPPDM.html ...]
|-
|'''BasicPhaseIPDM'''
|Implements the Basic Phase I Method as a Primal-Dual Method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/BasicPhaseIPDM.html ...]
|-
|'''JOptimizer'''
|Implements the convex optimizer.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/JOptimizer.html ...]
|-
|'''LPPresolver'''
|Presolver for a linear problem.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/LPPresolver.html ...]
|-
|'''LPPrimalDualMethod'''
|Implements the Primal-dual interior-point method for linear problems.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/LPPrimalDualMethod.html ...]
|-
|'''LPStandardConverter'''
|Converts a general LP problem into a strictly standard or quasi standard form.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/LPStandardConverter.html ...]
|-
|'''NewtonLEConstrainedFSP'''
|Linear equality constrained newton optimizer, with feasible starting point.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/NewtonLEConstrainedFSP.html ...]
|-
|'''NewtonLEConstrainedISP'''
|Linear equality constrained newton optimizer, with infeasible starting point.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/NewtonLEConstrainedISP.html ...]
|-
|'''NewtonUnconstrained'''
|Unconstrained newton optimizer.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/NewtonUnconstrained.html ...]
|-
|'''OptimizationRequest'''
|Implements an optimization problem.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/OptimizationRequest.html ...]
|-
|'''OptimizationRequestHandler'''
|Generic class for optimization process.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/OptimizationRequestHandler.html ...]
|-
|'''OptimizationResponse'''
|Optimization process output: stores the solution as well as an exit code.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/OptimizationResponse.html ...]
|-
|'''PrimalDualMethod'''
|Implements a primal-dual interior-point method.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/optimizers/PrimalDualMethod.html ...]
|-
|'''AbstractKKTSolver'''
|Abstract class for solving KKT systems.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/solvers/AbstractKKTSolver.html ...]
|-
|'''AugmentedKKTSolver'''
|Extension of AbstractKKTSolver for singular matrix.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/solvers/AugmentedKKTSolver.html ...]
|-
|'''BasicKKTSolver'''
|Extension of AbstractKKTSolver for the basic solver.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/solvers/BasicKKTSolver.html ...]
|-
|'''UpperDiagonalHKKTSolver'''
|Extends the class AbstractKKTSolver for upper diagonal matrix.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/solvers/UpperDiagonalHKKTSolver.html ...]
|-
|'''ArrayUtils'''
|Class offering operations on arrays, primitive arrays (like int[]) and primitive wrapper arrays (like Integer[]).
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/util/ArrayUtils.html ...]
|-
|'''MutableInt'''
|A mutable (int) wrapper.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/util/MutableInt.html ...]
|-
|'''Utils'''
|Utility class.
|[{{JavaDoc4.13}}/fr/cnes/sirius/patrius/math/optim/joptimizer/util/Utils.html ...]
|}

[[Category:User_Manual_4.14_Mathematics]]

User Manual 4.14 Optimization - Historique des versions

Admin tsn le 5 septembre 2024 à 15:17

Admin tsn : Page créée avec « __NOTOC__ == Introduction == === Scope === This section describes PATRIUS optimization features. It will focus on the ''JOptimizer'' functionalities, which provides solv... »

Admin tsn : Page créée avec « NOTOC == Introduction == === Scope === This section describes PATRIUS optimization features. It will focus on the ''JOptimizer'' functionalities, which provides solv... »