BSU Bulletin. Mathematics, Informatics
Bibliographic description:
, , D.C. PROGRAMMING APPROACH ТО МALFATTI'S PROBLEM // BSU Bulletin. Mathematics, Informatics. - 2018. №4. . - С. 72-83.
Title:
D.C. PROGRAMMING APPROACH ТО МALFATTI'S PROBLEM
Financing:
Codes:
Annotation:
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.
Keywords:
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.
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.
Article.pdf