BSU bulletin
Mathematics, Informatics

BSU bulletin. Mathematics, Informatics

Bibliographic description:
Enkhbat R.
Barkova M. V.
Batblleg S.
D.C. PROGRAMMING APPROACH ТО МALFATTI'S PROBLEM // BSU bulletin. Mathematics, Informatics. - 2018. №4. . - С. 72-83.
DOI: 10.18101/2304-5728-2018-4-72-83UDK: 519.853
In previous works R. Enkhbat showed that the Malfatti's proЫem can Ье treated as the convex maximization proЫem and provided with an algorithm based on Global Optimality Conditions of А S. Strekalovsky. In this article we reformulate Mal­ fatti's proЫem as а D.C. programming proЫem with а nonconvex constraint. Тhе reduced proЫem as an optimization proЫem with D.C. constraints belongs to а class of global optimization. We apply the local and global optimality conditions Ьу А S. Strekalovsky developed for D.C programming. Based on local search methods for D.C. programming, we have developed an algorithm for numerical solution of Malfatti's proЫem. 1n numerical experiments, initial points of the proposed algo­ rithm are chosen randomly. Global solutions have been found in all cases.
D.C. programming; global optimality conditions; Malfatti's proЫem; convex maximization; local search algorithm; D.C. constraint, global optimization, Malfatti circles; linearized proЫem; D.C. minimization.
List of references:
Andreatta М., Bezdek А and Boroaski Jan Р. Тhе ProЫem of Malfatti: Two Centuries ofDebate. The Mathematical lntelligencer. 2011. No. 33. Рр. 72-76.

Andrei N. Hybrid Conjugate Gradient Algorithm for Unconstrained Optimiza­ tion. JOTA . 2009. No. 141. Рр. 249-264.

Anikin А , Gomov А , and Andrianov А Computational Technologies for Morse Potential Optimization. Optimization and Applications (ОРТ!МА-2013): Ab­ stracts of IV lnternetional Conference. 2013. Рр. 22-23.

David J. W. and Doye J. Р. К. Global optimization Ьу basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms. The Journal of Physical Chemistry А. 1997. V. 28. No. 101. Рр. 5111 -5116.

Nocedai J., Wright St. J. Numerical Optimization. New York: Springer, 2006. 685 р.

Vasiliev F. Р. Metody optimizatsii [Optimization Methods]. Moscow: Factorial Press, 2002. 824 р.

Enkhbat R. An Algorithm for Maximizing а Convex Function over а Simple Set. Journal of Global Optimization. 1996. No. 8. Рр. 379-391.

Enkhbat R. Global Optimization Approach to Malfatti's ProЫem. Journal of Global Optimization. 2016. No. 65. Рр. 33-39.

Enkhbat R., Barkova M.V. and Strekalovsky M.V. Solving Malfatti's Нigh Di­ mensional ProЫem Ьу Global Optimization. Numerical Algebra, Control and Optimi­ zation. 2016. V. 6. No. 2. Рр. 153-160.

Fedorenko R. Р. PriЫizhennoye resheniye nekotorykh zadach optimal'nogo upravleniya [Approximate Solution of Some Optimal Control ProЫems]. Zhurnal vy­ chislitel'noi matematiki i matematicheskoi fiziki - USSR Computational Mathematics and Mathematical Physics. 1964. V. 4. N. 6. Р. 153-160.

Gabai Н. and Liban Е. Оп Goldberg's lnequality Associated with the Malfatti РrоЫе т. 1967. V. 41. No. 5. Рр. 251-252.

Gernet N. ОЬ osnovnoi prosteishei zadache variatsionnogo ischisleniya [Тhе Fundamental ProЫem ofthe Calculus ofVariations]. St. Petersburg: Erlich, 1913.

Goldberg М. On the Original Malfatti ProЫem. Math. Mag. 1967. V. 40. No. 5. Рр. 241-247.

Lob Н. and Richmond Н. W. On the Solutions of the Malfatti ProЫem for а Triangle. London Math. Soc. 1930. V. 2. No. 30. Рр. 287-301.

Los G. А Malfatti's Optimization ProЫem. Dep. Ukr. NIINТI. 1998. [in Rus.]

Malfatti G. Memoria sopra una proЫema stereotomico. Memoria di Matematica е di Fisica della Societa italiana della Scienze. 1803. V. 10. No. 1. Рр. 235 -244.

Melissen Н. Packing and Covering with Circles. Ph. D. Thesis. Univ. of Utrecht, 1997.

Polyak В. Т. Metod sopryazhennykh gradiyentov v ekstremalnykh zadachakh [Тhе Conjugate Gradient Method in Extremal ProЫems]. Zhurnal vychislitel'noi mate­ matiki i matematicheskoi fiziki - USSR Computational Mathematics and Mathematical Physics. 1969. V. 9. No. 4. Рр. 94-112.

Pervin М., Roy S. К. and Weber G. W. А Two-Echelon Inventory Model with Stock-Dependent Demand and VariaЫe Holding Cost for Deteriorating ltems. Numeri­ cal Algebra, Control and Optimization. 2016. V. 7. No. 1. Рр. 21-50.

Pervin М., Roy S. К. , and Weber G. W. Analysis of Inventory Control Model with Shortage under Time-Dependent Demand and Time-Varying Holding Cost In­ cluding Stochastic Deterioration. Annals of Operations Research. 2016. DOI: 10.1007/sl 0479-016-2355-5.

Roy S. К. , Maity G., Weber G. W., and Alparslan Gok S. Z. Conic Scalariza­ tion Approach to Solve Multi-Choice Multi-Objective Transportation ProЫem with Interval Goal. Annals of Operations Research. 2016. DOI 10.1007/sl 0479-016-2283- 4.

Roy S. К. , Maity G., and Weber G. W. Multi-Objective Two-Stage Grey Trans­ portation ProЫem Using Utility Function with Goals. Central European Journal of Operations Research. 2016. V. 7. No. 1. Рр. 21-50.

Strekalovsky А S. К proЫeme globalnogo ekstremuma [On the Global Ex­ trema ProЫem]. Doklady Akademii nauk SSSR - Proc. of the USSR Academy of Sci­ ences. 1987. V. 295. No. 5. Рр. 1062-1066.

Strekalovsky А S. On Local Search in D.C. Optimization ProЫem. Applied Mathematics and Computation. 2015. V. 255. Р. 73-83.

Тео К. L., Goh С. J., and Wong К. Н. А Unified Computational Approach to Optimal Control ProЫems. Pitman Monographs and Surveys in Pure and Applied Mathematics. New York, Longman Scientific & Technical, 1991.

Valentine F. А The РrоЫет of Lagrange with Differential lnequalities as Added Side Conditions. Dissertation Univ. ofChicago, 1937.

Zalgaller V. А and Los G. А Тhе Solution of Malfatti's ProЫem. Journal of Mathematical Sciences. 1994. V. 72. No. 4. Рр. 3163-3177.