Interior Point Polynomial-Time Algorithms for Linearly Constrained Convex Programming

Convex programming problems arise in many fields of science, engineering, finance, business and management. Hong Kong, as one of the world centers of finance and logistics, has a very strong need for the cutting edge technology in convex programming. For instance, the portfolio optimization in finance and supply chain management in logistics often involve large scale data and require fast and efficient solvers for convex programming. The algorithms studied in this proposal ensure the polynomial-time complexity which is very crucial in developing efficient computational schemes for solving linearly constrained convex programming problems.

In the literature, the following two groups of methods are very successful for linearly constrained convex programming. (a) Interior point methods: The success of interior point methods lies in the strong theoretical results. In particular, the polynomial-time complexity has been ensured for linear programming. But the polynomial-time complexity has been only available for certain special classes of linearly constrained convex programming problems. (b) Neural network methods: Besides the attractive hardware implementation, the success of neural network methods is also recognized by the introduction of a continuous trajectory in the form of the solution of some ordinary differential equation. However, the intermediate solution trajectory may not always stay in the interior of the feasible region, which could cause degeneracy issues in some cases. Based on the success of the interior point methods and neural network methods for linearly constrained convex programming, recently the interior point continuous trajectory approach has been introduced. Several interior point continuous trajectories with strong convergence results have been studied for linearly constrained convex programming. These new convergent continuous trajectories have provided alternative choices besides the central path, which could fail to converge for certain linearly constrained convex programming problems.

Based on these new convergent interior point continuous trajectories, the main goal of this research project is to develop some interior point polynomial-time algorithms for linearly constrained convex programming. Specifically, in this research project, we will propose a class of novel interior point polynomial-time algorithms for linearly constrained convex programming. Theoretical and numerical investigations on this class of algorithms will be also addressed.

In this research proposal, by completing the above tasks, we will be able to develop some new theoretically sound (polynomial-time) and numerical efficient interior point algorithms for convex programming with linear constraints. Our results will advance the state-of-the-art in both theoretical and computational aspects for convex programming.