Interior point based continuous methods for linear programming

Linear programming problems arise in many fields of science, engineering, finance, business and management. There are two milestones in linear programming. The first occurred in mid-20th century, where the Simplex method was introduced. The second was the introduction of the polynomial-time interior point algorithm in 1980’s. Generally speaking, all the existing interior point algorithms would generate a sequence of converg- ing points which forms a discrete path from the initial point to an optimal solution for linear programming. It would be very desirable and important to study the behavior of the continuous trajectory formed by this sequence of points.

Since 1980’s, the neural network approach for linear programming has been very suc- cessful in finding the optimal solution. A key component of the neural network approach is a dynamical system or ordinary differential equation, which generates a continuous trajectory converging to an optimal solution. However, in the neural network approach, the continuous trajectory may not be always stay inside the feasible region, this could cause some degeneracy problems in some cases. Based on the success of the iterative in- terior point methods and the neural network approach, in this project, by combining the attractive features for both approaches, we will introduce the interior point based contin- uous method for linear programming. Our study will focus on the following aspects: (a) to establish some continuous method models based on various interior point algorithms and the general framework for the continuous method; (b) to investigate the theoretical properties including the strong convergence for each model established in (a); and (c) to conduct extensive numerical simulations for all of our continuous method models for linear programming.

The contributions of this project should include both some theoretical advancements and efficient numerical solution schemes for linear programming. Our results will advance the state-of-the-art in both theoretical and computational aspects for linear program- ming.