Summary: We develop a complex interior boundary method for solving linear programming (LP) problems with interior search directions. The complex interior-boundary method (as the name suggests) moves in the interior of the feasible region from one boundary point of the feasible region to another bypassing several extreme points at a time. These directions of movement are guaranteed to improve the objective function. As a result, the complex method aims to reach the optimal point faster than the simplex method on large LP programs. The method also extends to nonlinear programming (NLP) with linear constraints in contrast to the generalized-reduced gradient.
The complex method is based on a pivoting operation which is a computationally efficient operation compared to some interior-point methods. In addition, our algorithm offers more flexibility in choosing the search direction than other pivoting methods (such as reduced gradient methods). The interior direction of movement aims at reducing the number of iterations and running time to obtain the optimal solution of the LP problem compared to the simplex method. Furthermore, this method is advantageous to simplex and other convex programs with regard to starting at a basic feasible solution; i.e., the method has the ability to start at any given feasible solution.
Preliminary testing shows that the reduction of the computational effort is promising compared to the simplex method.