Barrier method convergence criteria

Answer

CPLEX's barrier method assesses feasibility and optimality differently from CPLEX's simplex methods. The primal and dual simplex methods assess feasibility and optimality using feasibility and optimality tolerances that, while adjustable, are set to specific values regardless of the problem data. By contrast, the barrier method uses relative measures of primal feasibility, dual feasibility and complementary slackness to assess convergence to an optimal solution (if one exists). For example, with primal feasibility, the barrier method considers the violations of the constraints relative to the norm of the associated right hand side vector. In other words, for

min c'x

Ax = b

x >= 0

the barrier method assess convergence of a solution x* by examining ||b - Ax||/||b|| relative to its convergence tolerance. Similarly, optimality (or, equivalently, dual feasibility), is measured in terms of dual feasibility violations relative to the norm of the objective vector. As a result, solutions found by the barrier method aren't guaranteed to satisfy feasibility or optimality criteria within any specific value controlled by the user. However, users can control the accuracy of the barrier method solution by adjusting the barrier convergence tolerance (CPX_PARAM_BAREPCOMP/IloCplex::BarEpComp) for linear and quadratic programs or qcp convergence tolerance (CPX_PARAM_BARQCPEPCOMP/IloCplex::BarQCPEpComp) for models with quadratic constraints. Reducing these from their defaults will yield more precise solutions, but may increase run time. And, setting them to values below possible round off error values that can arise in the barrier algorithm may compromise convergence completely. For linear and quadratic programs, CPLEX by default will follow up the barrier optimization with a crossover procedure that obtains a basic solution from the barrier method's interior point solution. Unless the crossover procedure dramatically slows performance, we recommend using it rather than trying to adjust the barrier convergence tolerance to obtain more precise solutions.