Abstract
In order to solve an underdetermined system of linear equations with nonnegative variables, the projection of a given point onto its solutions set is sought. The dual of this problem—the problem of unconstrained maximization of a piecewise-quadratic function—is solved by Newton’s method. The problem of unconstrained optimization dual of the regularized problem of finding the projection onto the solution set of the system is considered. A connection of duality theory and Newton’s method with some known algorithms of projecting onto a standard simplex is shown. On the example of taking into account the specifics of the constraints of the transport linear programming problem, the possibility to increase the efficiency of calculating the generalized Hessian matrix is demonstrated. Some examples of numerical calculations using MATLAB are presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. I. Golikov and Yu. G. Evtushenko, “Solution method for large-scale linear programming problems,” Dokl. Math. 70 (1), 615–619 (2004).
V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, and M. Kh. Nguen, “Parallel implementation of Newton’s method for solving large-scale linear programs,” Comput. Math. Math. Phys. 49 (8), 1303–1317 (2009).
O. L. Mangasarian, “A Newton method for linear programming,” J. Optim. Theory Appl. 121, 1–18 (2004).
L. D. Popov, “Quadratic approximation of penalty functions for solving large-scale linear programs,” Comput. Math. Math. Phys. 47 (2), 200–214 (2007).
L. D. Popov, “Experience in organizing hybrid parallel calculations in the Evtushenko–Golikov method for problems with block-angular structure,” Autom. Remote Control 75 (4), 622–631 (2014).
I. I. Eremin, “On quadratic and fully quadratic problems of convex programming,” Russ. Math. 42 (12), 20–26 (1998).
M. Frank and P. Wolfe, “An algorithm for quadratic programming,” Naval Res. Logist. Quart. 3, 95–110 (1956).
A. N. Tikhonov, “On ill-posed problems in linear algebra and a stable method for their solution,” Dokl. Akad. Nauk SSSR 163 (4), 591–594 (1965).
V. N. Malozemov and G. Sh. Tamasyan, “Two fast algorithms for projecting a point onto the canonical simplex,” Comput. Math. Math. Phys. 56 (5), 730–743 (2016).
G. Sh. Tamasyan, E. V. Prosolupov, and T. A. Angelov, “Comparative study of two fast algorithms for projecting a point to the standard simplex,” J. Appl. Ind. Math. 10 (2), 288–301 (2016).
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the 100th birthday of Academician N.N. Moiseev
Original Russian Text © B.V. Ganin, A.I. Golikov, Yu.G. Evtushenko, 2018, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2018, Vol. 58, No. 2, pp. 169–180.
Rights and permissions
About this article
Cite this article
Ganin, B.V., Golikov, A.I. & Evtushenko, Y.G. Projective-Dual Method for Solving Systems of Linear Equations with Nonnegative Variables. Comput. Math. and Math. Phys. 58, 159–169 (2018). https://doi.org/10.1134/S0965542518020057
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542518020057