User Manual 4.6 Optimization : Différence entre versions

Version du 13 janvier 2021 à 07:53

Introduction

Scope

This section describes PATRIUS optimization features.

It will focus on the JOptimizer functionalities, which provides solvers for general convex optimization problems.

Javadoc

The optimization classes are available in the 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)
• BasicKKTSolver
• UpperDiagonalHKKTSolver (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 ⁿ, 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 f_i(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.

Rescaler

The 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.

Getting Started

Example 1

Example of a linear problem optimized by the primal-dual interior-point method.

The linear problem is:

min(100x + y) s.t.
x - y = 0
0 <= x <= 1
0 <= y <= 1

First, the definition of the variables:

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 }

Definition of the optimization problem by settling the variables:

final LPOptimizationRequest or = new LPOptimizationRequest()
or.setC(c)
or.setA(a)
or.setB(b)
or.setLb(lb)
or.setUb(ub)

Additional parameters (tolerance, check the solution accuracy, etc) can also be settled:

or.setCheckKKTSolutionAccuracy(true)
or.setToleranceFeas(1.E-7)
or.setTolerance(1.E-7)
or.setDumpProblem(true)
or.setRescalingDisabled(true)

Definition of the optimizer and setting the optimization problem:

LPPrimalDualMethod opt = new LPPrimalDualMethod()
opt.setLPOptimizationRequest(or)

Optimization and check that it has not failed:

final int returnCode = opt.optimize()
if (returnCode == OptimizationResponse.FAILED) {
    fail()
}

Recuperate the response and the solution:

final LPOptimizationResponse response = opt.getLPOptimizationResponse()
final double[] sol = response.getSolution()

Validation:

final RealVector cVector = new ArrayRealVector(c)
final RealVector solVector = new ArrayRealVector(sol)
final double value = cVector.dotProduct(solVector)
assertEquals(2, sol.length)
TO FINISH

Example 2

Example of a linear problem optimized by the primal-dual interior-point method.

The linear problem is:

min(100x + y) s.t.
x - y = 0
0 <= x <= 1
0 <= y <= 1

First, the definition of the variables:

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 }

Definition of the optimization problem by settling the variables:

final LPOptimizationRequest or = new LPOptimizationRequest()
or.setC(c)
or.setA(a)
or.setB(b)
or.setLb(lb)
or.setUb(ub)

Definition of the optimizer and setting the optimization problem:

LPPrimalDualMethod opt = new LPPrimalDualMethod()
opt.setLPOptimizationRequest(or)

Optimization and check that it has not failed:

final int returnCode = opt.optimize()
if (returnCode == OptimizationResponse.FAILED) {
    fail()
}

Recuperate the response and the solution:

final LPOptimizationResponse response = opt.getLPOptimizationResponse()
final double[] sol = response.getSolution()

Validation:

final RealVector cVector = new ArrayRealVector(c)
final RealVector solVector = new ArrayRealVector(sol)
final double value = cVector.dotProduct(solVector)
assertEquals(2, sol.length)
TO FINISH

Contents

Interfaces

The most relevant interfaces related to the optimization are listed here :

Classes

The most relevant classes related to the optimization are listed here :