Вестник БГУ. Математика, информатика
Библиографическое описание:
, , D.C. ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАЛЬФАТТИ // Вестник БГУ. Математика, информатика. - 2018. №4. . - С. 72-83.
Заглавие:
D.C. ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАЛЬФАТТИ
Финансирование:
Коды:
Аннотация:
В предыдущих работах Р. Энхбат показал, что проблему Малфатги можно рассматривать как проблему выпуклой максимизации и решать алгоритмом на основе глобальных условий оптимальности А. С. Стрекаловского. В этой статье мы переформулируем проблему Малфатги как проблему D.C. программирования с невьшуклым ограничением. Приведенная проблема, как проблема оптимизации с D.C. ограничениями, принадлежит классу глобальной оптимизации. Мы при меняем локальные и глобальные условия оптимальности А. С. Стрекаловского, разработанные для D.C. программирования. Основываясь на методах локального поиска для D.C. программирования, мы разработали алгоритм для численного решения задачи Малфатти. В численных экспериментах исходные точки предла гаемого алгоритма выбираются случайным образом. Во всех случаях найдены глобальные решения.
Ключевые слова:
D.C. оптимизация; условия глобальной оптимальности; за дача Мальфатги; выпуклая максимизация; алгоритм локального поиска; D.C. ограничение; глобальная оптимизация; круrи Малфатги; линеаризованная задача; D.C. минимизация.
Список литературы:
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.
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.
Статья.pdf