On adjusting parameters in homotopy methods for linear programming

Michael Todd

Several algorithms in optimization can be viewed as following a solution as a parameter or set of parameters is adjusted to a desired value. Examples include homotopy methods in complementarity problems and path-following (infeasible-) interior-point methods. If we have a metric in solution space that corresponds to the complexity of moving from one solution point to another, there is an induced metric in parameter space, which can be used to guide parameter-adjustment schemes. We investigate this viewpoint for feasible- and infeasible- interior-point methods for linear programming.

Technical Report 1170, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801.

Contact: miketodd@cs.cornell.edu