Generalized Newton method for linear optimization problems with inequality constraints

A dual problem of linear programming is reduced to the unconstrained maximization of a concave piecewise quadratic function for sufficiently large values of a certain parameter. An estimate is given for the threshold value of the parameter starting from which the projection of a given point to the set of solutions of the dual linear programming problem in dual and auxiliary variables is easily found by means of a single solution of the unconstrained maximization problem. The unconstrained maximization is carried out by the generalized Newton method, which is globally convergent in an a finite number of steps. The results of numerical experiments are presented for randomly generated large-scale linear programming problems.