On solving convex programming problem
Keywords:
convex programming, linear constraints, linearization, admissible solution, auxilary appraximation, optimal solution, optimization problemAbstract
In this paper an algorithm for solving convex programming problem is proposed. The specific feature of the considered problem is that its constraints contain only linear equalities. This feature is a basis for the replacement the nonlinear objective function in the neighbourhood of the tested point by a linear one, due to what solving an original problem is reduced to sequential solving linear programming problems. The obtained linear programming problem is solved by sequential correction the value of an objective function on a set of admissible solutions and an admissible as well as optimal solutions are found. Further values of an original objective function at the found admissible and optimal points are calculated and an auxiliary approach is determined. The next approach is defined as a convex combination of a previous and an auxiliary approaches. Note that unlike the Lagrange multipliers method the developed method is applied to problems with the Lagrange function which hasn’t a saddle point. The paper contains a description of the method, a proof of its convergence, schemes of algorithms and experimental results. The proposed algorithm combines ideas of the conditional gradient method [1] and a method for solving linear programming problem [2].
References
[2] Aisagaliev S.А., Aisagaliev Zh.K. Research on mathematical programming // The Bulletin of KazNU, ser. math., mech., inf. –2013. – No 2(77). –P. 4-20.(in Russian)
[3] Kuznetcov A.V., Sakovich A.V., Holod N.I. Higher mathematics. Mathematical programming. – Minsk: Vysschaya schkola, 1973. – 470 p. (in Russian)
[4] Karmanov V.G. Mathematical programming. – M.: Fizmatlit, 2004. – 264 p.(in Russian)
[5] John С. Chambers, S. K. Mullick, and D. Smith How to Choose the Right Forecasting Technique // Harvard Business Review. – 1971. – P. 45-74.
[6] Egan M. Interfaces Between Tourism and outdoor Recreation // Paper presented at the Western Economic Association Annual Conference. – San Diego, California, 1975.
[7] Holman M.A. A National Time - Budget for Year 2000 // Sociology and Social Res., 42,1. – 1961.
[8] Burd O.R., Brewer D. Estimation of Net Social Benefits from Outdor Recreation // Econometrica. – 9, N 5. – P. 813-827.
[9] Gearing C.E. Determining the Optimal Investment policy for the Tourism sector of a Developing Country // Management Sci, Part I. – 1973. – 20, N 4. – P. 487-497.
[10] Gearing C.E. Establishing a Measure of Touristic Attractiveness // J. travel Res., XII. – 1974. – N 4(1-8).
[11] Gearing C.E. A Multi-Period Planning Model for Tourism Development // Paper presented at the TIMS XXII International Meeting. – Kyoto, Japan, 1975.
[12] Gearing C.E. Planning for Tourism Development: Quantitative Approaches, Praeger Publishers. – New York, 1976.
[13] Arcger B.H. The Primary and Secondary Beneficiaries of Touristspending // Tourist Rev., 27. – 1972. – P. 42-45.
[14] Crampon L.J. Factors Influencing Travel Flow into and within the Pacific Basin // Paper presented at the ORSA/TIMS Joint national Meeting. – San Juan, Puerto Rico, 1974. – P. 16-18.
[15] Popov L.D. Ob odnoi modifikacii metoda logarifmicheskih bariernyh funkciy v lineinom i vypuklom programmirovanii // Trudy IMM UrO RAN. – 2008. 14, No 2. – P. 103-114.(in Russian)
[16] Vylegzhanin O.N., Shkatova G.I. uchet ogranicheniy ravenstv pri reshenii optimizacionnyh zadach s lineinymi ogranicheniyami // Izvestiya Tomskogo politehnicheskogo universiteta. – 2008. – Т. 312, No 5. – P. 76-78.(in Russian)
[17] Skarin V.D. Approksimacionnye i regulyarizuiuschie svoistva rasshirennyh shtrafnyh funkciy v vypuklom programmirovanii // Trudy IMM UrO RAN. – 2009. – Т. 15, N 4. – P. 234-250.(in Russian)
[18] Zilberova I.Iu., Mailyan A.L., Barkalov S.A., Uksusov S.N. Metod Shtifelya v vypuklom programmirovanii // Internet- journal "Naukovedenie". –2015. –Т. 7, No6. –URL: http://naukovedenie.ru/PDF/122TVN615.pdf.(in Russian)
[19] Dantzig J.B. Linear programming and Extensions. Princeton University Press, Princeton, NJ, 1963.
