Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:1, 98-111
Volume 25, No 1, 2018, P. 75-97
UDC 519.8
A. Yu. Krylatov
Reduction of a minimization problem of a separable convex function under linear constraints to a fixed point problem
Abstract:
The paper is devoted to studying a constrained nonlinear optimization problem of a special kind. The objective functional of the problem is a separable convex function whose minimum is sought for on a set of linear constraints in the form of equalities. It is proved that, for this type of optimization problems, the explicit form can be obtained of a projection operator based on a generalized projection matrix. The projection operator allows us to represent the initial problem as a fixed point problem. The explicit form of the fixed point problem makes it possible to run a process of simple iteration. We prove the linear convergence of the obtained iterative method and, under rather natural additional conditions, its quadratic convergence. It is shown that an important application of the developed method is the flow assignment in a network of an arbitrary topology with one pair of source and sink.
Bibliogr. 10.
Keywords: constrained nonlinear optimization, fixed point problem, generalized projection matrix, network flow assignment.
DOI: 10.17377/daio.2018.25.560
Alexander Yu. Krylatov 1,2
1. Saint-Petersburg State University,
7/9 Universitetskaya nab., 199034 Saint-Petersburg, Russia
2. Solomenko Institute of Transport Problems,
13 on the 12th line of V.O., 199178 Saint-Petersburg, Russia
e-mail: a.krylatov@spbu.ru, aykrylatov@yandex.ru
Received 26 December 2016
Revised 8 August 2017
References
[1] F. R. Gantmakher, Teoriya matrits (Theory of Matrices), Nauka, Moscow, 1966 [Russian].[2] I. V. Konnov, Nelineinaya optimizatsiya i variatsionnye neravenstva (Nonlinear Optimization and Variational Inequalities), Kazan. Univ., Kazan, 2013 [Russian].
[3] A. Yu. Krylatov, Network flow assignment as a fixed point problem, Diskretn. Anal. Issled. Oper., 23, No. 2, 63–87, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 2, 243–256, 2016.
[4] M. N. S. Swamy and K. Thulasiraman, Graphs, Networks, and Algorithms, Wiley, New York, 1981. Translated under the title Grafy, seti i algoritmy, Mir, Moscow, 1984 [Russian].
[5] M. J. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation, Yale Univ. Press, New Haven, CT, 1956.
[6] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, 1999.
[7] R.-J. Chen and R. R. Meyer, Parallel optimization for traffic assignment, Math. Program., 42, No. 1–3,
[8] M. Patriksson, A unified description of iterative algorithms for traffic equilibria, Eur. J. Oper. Res., 71, No. 2, 154–176, 1993.
[9] M. Patriksson, The Traffic Assignment Problem: Models and Methods, Dover Publ., Mineola, NY, 2015.
[10] J. G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. Civil Eng., 1, No. 3, 325–362, 1952.
