# linear programming¶

Linear programming [LP] is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints such as:

\begin{split}\begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0} \end{align}\end{split}

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients.

## openMVG linear programming tools¶

openMVG provides tools to:

• configure Linear programs (LP container),
• solve Linear Programs (convex or quasi convex ones).

### openMVG linear program container¶

openMVG provides a generic container for LP (Linear Programming problems) that can be dense of sparse.

// Dense LP
LP_Constraints
// Sparse LP
LP_Constraints_Sparse


It allows to embed:

• objective function c and the problem type (minimization or maximization),
• constraints (coefficients A, Sign, objective value b),
• bounds over x parameters (<=, =, >=).

### openMVG linear program solvers¶

• OSI_CLP (COIN-OR) project,
• MOSEK commercial, free in a research context.

Those solver have been choosen due to the stability of their results and ability to handle large problems without numerical stability (LPSolve and GPLK have been discarded after extensive experiments).

I refer the reader to openMVG/src/openMVG/linearProgramming/linear_programming_test.cpp to know more.

### openMVG linear programming module usage¶

The linear programming module of openMVG can be used for:

• solve classical linear problem (optimization),
• test the feasibility of linear problem,
• optimize upper bound of feasible problem (quasi-convex linear programs).

classical linear problem solving (optimization)

Here an example of usage of the framework:

// Setup the LP (fill A,b,c and the constraint over x)
LP_Constraints cstraint;
BuildLinearProblem(cstraint);

// Solve the LP with the solver of your choice
std::vector<double> vec_solution(2);
#if OPENMVG_HAVE_MOSEK
MOSEK_SolveWrapper solver(2);
#else
OSI_CLP_SolverWrapper solver(2);
#endif
// Send constraint to the LP solver
solver.setup(cstraint);

// If LP have a solution
if (solver.solve())
// Get back estimated parameters
solver.getSolution(vec_solution);


Linear programming, feasible problem

openMVG can be use also to test only the feasibility of a given LP

\begin{split}\begin{align} & \text{find} && \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0} \end{align}\end{split}

Linear programming, quasi convex optimization

openMVG used a lot of L infinity minimisation formulation. Often the posed problems are quasi-convex and dependent of an external parameter that we are looking for (i.e the maximal re-projection error for which the set of contraint is still feasible).

Optimization of this upper bound parameter can be done by iterating over all the possible value or by using a bisection that reduce the search range at each iteration.

Require: gammaLow, gammUp (Low and upper bound of the parameter to optimize)
Require: the LP problem (cstraintBuilder)
Ensure: the optimal gamma value, or return infeasibility of the contraints set.

BisectionLP(
LP_Solver & solver,
ConstraintBuilder & cstraintBuilder,
double gammaUp  = 1.0,  // Upper bound
double gammaLow = 0.0,  // lower bound
double eps      = 1e-8, // precision that stop dichotomy
const int maxIteration = 20) // max number of iteration
{
ConstraintType constraint;
do
{
++k; // One more iteration

double gamma = (gammaLow + gammaUp) / 2.0;

//-- Setup constraint and solver
cstraintBuilder.Build(gamma, constraint);
solver.setup( constraint );

//-- Solving
bool bFeasible = solver.solve();

//-- According feasibility update the corresponding bound
//-> Feasible, update the upper bound
//-> Not feasible, update the lower bound
(bFeasible) ? gammaUp = gamma; : gammaLow = gamma;

} while (k < maxIteration && gammaUp - gammaLow > eps);
}


## Multiple View Geometry solvers based on L-Infinity minimization¶

openMVG provides Linear programming based solvers for various problem in computer vision by minimizing at the same time the maximal error over a series of cost function and some model parameters. It uses a L-Infinity minimization method.

openMVG implements problems introduced by [LinfNorm] and generalized by [LinfNormGeneric] to solve multiple view geometry problem.

Rather than considering quadratic constraints that require SOCP (Second Orde Cone Programming) we consider their LP (linear program) equivalent. It makes usage of residual error expressed with absolute error ( |a|<b). Inequalities are transformed in two linear inequalities a<b and -b<-a to be used in the LP framework. Using LP rather than SCOP allow to have better solving time and easier constraint to express (see. [Arnak] for more explanation).

OpenMVG propose solvers for the following problems:

• N-view triangulation [LinfNorm],
• Resection or pose matrix estimation [LinfNorm],
• Estimation of translations and structure from known rotations,
• Translation averaging: - Registration of relative translations to compute global translations [GlobalACSfM].