A Gonzaga’s Problem for Linear Programming

This work introduces the Gonzaga’s problem as potential test case for evaluating infeasibleinterior-point algorithms in linear programming. The Gonzaga’s problem is a simple linear programming instance with two decision variables and a non-interior starting point. The study explores the impact of adjusting the optimality parameter µ to achieve algorithms with complexity O ( n L )-iterations. Two classes of algorithms, central surface and homogeneous and self-dual, are implemented and presented graphically. Results show that adjusting µ can sometimes improve efficiency, but the lack of theoretical validation remains a challenge. The work suggests that the Gonzaga’s problem can serve as a benchmark for developing and testing new infeasible-interior-point algorithms.