Generalized Newton method for linear optimization problems with inequality constraints

A dual problem of linear programming (LP) 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 on the set of solutions of the dual LP problem in dual and auxiliary variables is easily found by means of a single solution of an unconstrained maximization problem. The unconstrained maximization is carried out by the generalized Newton method, which is globally convergent in a finite number of steps. The results of numerical experiments are presented for randomly generated large-scale LP problems.