автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование и разработка метода и комплекса программ для поиска условного глобального экстремума липшицевой функции на симплексе

ВВЕДЕНИЕ.

9 ГЛАВА I. ИССЛЕДОВАНИЕ МЕТОДА СЕКУЩИХ УГЛОВ

ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ И РАЗРАБОТКА ЕГО МОДИФИКАЦИИ.

• 1.1. Метод условной минимизации липшецевых функций.

1.2. Задачи минимизации Липшицевой функции на

I; симплексе.

1.3. Метод секущих углов.

1.4 Вспомогательная задача.

1.5 Решение вспомогательной задачи.

1.6 Условная задача липшицевого программирования.

1.7 Точная вспомогательная функция.

1.8 Метод внешних центров.

1.9 Сходимость метода внешних центров.

Выводы по главе 1.

9 ГЛАВА И. ТЕХНИКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ ПОИСКА

ГЛОБАЛЬНОГО ЭКСТРЕМУМА.

2.1. Общая схема работы программного комплекса.

2.2. Алгоритм распараллеливания вычислительного процесса реализованного метода секущих углов. 69 2.3. Особенности реализации ключевых компонентов

9 программного комплекса.

Выводы по главе II.

ГЛАВА III ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ » РАЗРАБОТАННОГО ПРОГРАММНОГО КОМПЛЕКСА

И ЕГО ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ В

ТЕХНОЛОГИИ МИКРО- И НАНОЭЛЕКТРОНИКИ.

3.1. Тестирование программного комплекса.

3.2. Оптимизация банка данных с виртуальными объектами, описывающими геометрические размеры элементов топологии субмикронного диапазона с использованием разработанного программного комплекса.

Выводы по главе III.

Актуальность темы. Математическое моделирование позволяет решать самые разнообразные задачи в различных областях практической деятельности. Использование современных достижений вычислительной техники дает возможность исследовать поведение объектов путем изучения поведения их математических моделей.

В настоящее время одними из актуальных задач математического моделирования являются задачи рационального выбора, и в частности, задачи оптимизации. Важное место среди задач оптимизации занимают задачи многоэкстремальной оптимизации и поиска глобального решения.

Особенностью решения задач поиска глобального экстремума является тот факт, что аналитическое решение возможно получить лишь в редких случаях. В связи с этим большую роль играют численные методы поиска оптимального решения. Трудности при решении задач поиска глобального экстремума вызваны большой размерностью задачи, наличием ограничений, многоэкстремальностью и негладкостью функции. Это привело к большому разнообразию вычислительных методов, как правило, существенным образом учитывающих свойства входящих в постановку задачи функций.

К настоящему времени разработано большое число различных подходов к решению задач глобальной оптимизации. Отметим среди них такие методы как метод неравномерного покрытия, метод случайного поиска, различные варианты метода ветвей и границ, методы представления функций в виде суммы выпуклой и вогнутой составляющих, методы основанные на одномерной глобальной оптимизации и многие, многие другие. Значительный вклад в развитие теории и методов глобальной оптимизации внесли такие отечественные и зарубежные ученные, как Ю.Г. Евтушенко, С.Н. Пиявский, В.П. Булатов, Р.Г. Стронгин, Я.Д. Сергеев, А.Г. Жилинскас, А.С. Стрекаловский, Р. Хорст, X. Туй, A.M. Рубинов, И. Торн, П. Пардалос, К. Флоудас.

Возрастающая сложность практических задач во всех перечисленных выше методах приводит к существенному увеличению времени расчетов, поскольку эти задачи обладают большой вычислительной трудоемкостью и их машинная реализация малоэффективна при работе с функциями число переменных в которых равняется нескольким десяткам и более. Таким образом, прежде чем приступить к решению подобных сложных вычислительных задач, необходимо сначала решить первостепенную задачу повышения эффективности методов поиска глобального экстремума.

Одним из наиболее важных классов задач, рассматриваемых в глобальной оптимизации, являются задачи нахождения глобального экстремума липшицевой функции. В последние десятилетия для решения этих задач были предложены несколько эффективных численных методов, в частности, A.M. Рубиновым, М. Андрамоновым, Б. Гловером был разработан метод секущих углов. С помощью метода внешних штрафных функций были разработаны также варианты метода секущих углов, предназначенные для решения задач с ограничениями. В таких методах, как известно, всегда имеется проблема выбора штрафных коэффициентов, причем при их увеличении возрастает константа Липшица. С другой стороны, эффективность большинства методов поиска глобального экстремума, в том числе и метода секущих углов, снижается с ростом значения константы Липшица.

В представленной диссертации для решения задач минимизации липшицевой функции при ограничениях предлагается несколько иной подход, основанный на комбинации метода секущих углов и метода внешних центров (метода параметризации целевой функции). В нем вместо штрафных коэффициентов используется оценка снизу оптимального значения целевой функции. Для метода характерно то обстоятельство, что имеется четкая политика измерения этой оценки и значения константы Липшица уменьшается в ходе вычислительного процесса. Это приводит к увеличению эффективности вычислительного процесса.

Современная тенденция развития технологической и компьютерной индустрии заключается в возможности распределения ресурсов и вычислительных мощностей в сетевой среде. Среда распределенных вычислений позволяет по новому взглянуть на возможности существующих методов поиска глобального экстремума за счет равномерного, программируемого распределения вычислительной нагрузки. Однако использование распределенных вычислений для программной реализации приведенных методов без их изменения (распараллеливание алгоритмов) не представляется возможным. Таким образом, одним из путей решения данной проблемы является разработка модифицируемого метода для его последующей реализации в распределенной среде.

Направлением исследований в настоящей работе является разработка программного комплекса для нахождения глобального экстремума функции многих переменных, который должен реализовать модификацию метода секущих углов и обладать следующими свойствами: маштабируемость, платформонезависимость.

Целью работы является совершенствование метода секущих углов для нахождения безусловного и условного глобального экстремума функции многих переменных, для равномерного, программируемого распределения вычислительной нагрузки при решении задачи в распределенной среде программирования.

Для достижения цели необходимо решить следующие задачи исследований:

1. модифицировать метод секущих углов для решения задачи условной глобальной оптимизации на основе использования специальной вспомогательной функции с целью достижения возможности дальнейшего использования алгоритмов параллельной обработки данных при его реализации.

2. обосновать сходимость специальной модификации метода секущих углов использующей оценку снизу оптимального значения целевой функции.

3. разработать алгоритм реализации модифицированного метода поиска глобального экстремума в рамках парадигмы распределенных вычислений.

4. разработать программный комплекс, воплощающий предложенные алгоритмы реализации модифицированного метода секущих углов для решения задачи глобальной оптимизации.

5. Протестировать и применить разработанные алгоритмы на практических и прикладных задачах. Провести оптимизацию выбора объектов виртуального банка данных описывающего геометрические размеры элементов топологии ИМС субмикронного диапазона.

Научная новизна. К новым результатам, полученным в диссертационной работе относятся:

1. Разработан модифицированный метод секущих углов для решения задачи условной глобальной оптимизации на основе использования специальной вспомогательной функций.

2. Доказана сходимость модифицированного метода секущих углов.

3. Предложен рекурсивный алгоритм решения вспомогательной задачи метода секущих углов, позволяющий находить все локальные точки минимума.

4. Предложен алгоритм реализации модифицированного метода секущих углов для решения задачи глобальной оптимизации, позволяющий использовать параллельную обработку данных, что приводит к сокращению времени вычислений по сравнению с существующими аналогами.

5. На основе использования полученного программного комплекса проведена оптимизация выбора объектов виртуального банка данных описывающего геометрические размеры элементов топологии ИМС субмикронного диапазона.

6.

Практическая ценность работы заключается в созданном программном комплексе позволяющем решать задачи глобальной оптимизации с большой скоростью сходимости и может применяться в различных предметных областях. В работе описано практическое применение построенного алгоритма и комплекса программ при повышении эффективности работы системы измерения геометрических размеров элементов топологии ИМС нанометрового диапазона.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Международной XXX, XXXI НТК

Гагаринские чтения», (Москва, 2004, 2005 г.), Международной научно-технической конференции «Международный форум молодых ученых и студентов» (Турция, 2004г.), Научной конференции «Современные наукоемкие технологии» (Испания, 2005г.), Юбилейной конференции РАЕ «Современные проблемы науки и образования» (Москва, 2005г.).

ВЫВОДЫ ПО РАБОТЕ

На основе результатов проведенных исследований предложен алгоритм поиска условного глобального экстремума функции многих переменных на симплексе на основе использования предложенной в работе модификации метода секущих углов, позволяющий решать задачи глобальной оптимизации с большой скоростью сходимости и который может применяться в различных предметных областях. При этом:

1. Модифицирован метод секущих углов для решения задачи глобальной оптимизации, на основе использования специальной вспомогательной функции для условной оптимизации, позволяющий значительно уменьшить время расчетов.

2. Обоснована сходимость специальной модификации метода секущих углов на основе построения алгоритма использующего оценку снизу оптимального решения.

3. Предложен рекурсивный алгоритм решения вспомогательной задачи метода секущих углов позволяющий находить все локальные точки минимума.

4. Разработан алгоритм реализации модифицированного метода поиска глобального экстремума в рамках парадигмы распределенных вычислений.

5. Разработан программный комплекс, реализующий предложенные алгоритмы реализации модифицированного метода секущих углов для решения задачи глобальной оптимизации, позволяющий в п раз уменьшить время расчетов (где п - количество машино-узлов в системе)

6. Проведена оптимизация выбора виртуальных объектов банка данных описывающих геометрические размеры элементов топологии ИМС субмикронного диапазона для системы измерений на основе дифрактометрии.

1. Ю.Г.Евтушенко. Численный метод поиска глобального экстремума функции (перебор на неравномерной сетке) // Журнал вычисл. матем. и матем. физики, 1971. Т. 11. № 6. С. 1390-1403.

2. Пиявский С.А. Один алгоритм отыскания абсолютного экстемума функции // Журнал вычисл. матем. и матем. физики, 1972. Т. 12. № 4. С. 888-896.

3. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.

4. Нефедов В.Н. Отыскание глобального максимума функции нескольких переменных на множестве, заданном ограничениями типа неравенств // Журнал вычисл. математики и матем. физики, 1987. Т. 27. № 1.С. 35-51.

5. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

6. Гергель В.П. Алгоритм глобального поиска, использующий производные // Динамика систем и оптимизация. Нижний Новгород: ННГУ, 1992. С. 161-178.

7. Horst R., Tuy Н. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1996.

8. Strongin R.G., Sergeev Ya.D. Global optimization with non-convex constraints: Sequential and parallel algorithms. Kluwer Academic Publishers, Dordrecht, 2000.

9. Стрекаловский A.C. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003.

10. A.M.Rubinov and B.M.Glover. Increasing convex along rays functions with applications to global optimization. — Research Report 21/96, University of Ballarat, 1996.

11. M. Yu. Andramonov, A. M. Rubinov and В. M. Glover, Cutting angle method for minimizing increasing convex-along-rays functions. ~ Research Report 97/7, SITMS, University of Ballarat, 1997.

12. M. Yu. Andramonov, A.M. Rubinov and В. M. Glover, Cutting angle methods in global optimization // Applied Mathematics Letters, 1999. V. 12. P. 95-100.

13. Rubinov A. Andramonov M. Lipschitz programming via increasing convex-along-rays functions // Optimization Methods and Software, 1999. V. 10. P. 763-781.

14. С.С.Кутателадзе, А.М.Рубинов. Двойственность Минковского и ее приложения. ~ Новосибирск: Наука, 1976.

15. Pallachke D., Rolewicz S. Foundations of Mathematical Optimization (Convex Analysis without Linearity). Kluwer Academic Publishers, Dordrecht, 1997.

16. Singer I. Abstract Convex Analysis. New York: Willey \& Sons, 1997.

17. A.M.Rubinov. Abstract Convexity and Global Optimization. Dordrecht, Kluwer Academic Publishers, 2000.

18. J. Kelley. The cutting plane method for solving convex programs // SIAM Journal, 1960. V. 8, № 4. P. 703-712.

19. Анциферов Е.Г., Ащепков JI.E., Булатов В.П. Методы оптимизации и их приложения. 4.1. Математическое программирование. Новосибирск: Наука, 1990.

20. Хамисов О.В. Глобальная оптимизация функций с вогнутой минорантой // Журнал вычисл. математики и матем. физики. 2004. Т. 44. №9. С. 1552-1563.

21. А.Р.Ершов, О.В.Хамисов. Автоматическая глобальная оптимизация // Дискретный анализ и исследование операций. 2004. Серия 2. Т.11, №2. С 45-68.

22. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

23. Гроссман К., Каплан А.А. Нелинейное программирование на основе без условной минимизации. Новосибирск: Наука, 1981.

24. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

25. D.D. Morrison, Optimization by least squares // SIAM J. Numer. Analysis, 1968. № 5. P. 83-88.

26. J. Kowalik, M.R. Osborn and D.M. Ryan, A new method for constrained optimization problems // Operat. Res., 1969. V. 17. P. 973-989.

27. Еремин И.И. Метод "штрафов" в выпуклом программировании // Докл. АН СССР. 1967. Т.-173, №~4. С.-748-751.

28. Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптимизации // Журнал вычисл. матем. и матем. физики, 1990. Т. 30. № 1. С.31-42.

29. Evtushenko Yu.G., Rubinov A.M. and Zhadan V.G. General Lagrange-type functions in constrained global optimization. Part II: Exact auxiliary functions // Optimization

30. Methods and Software, 2002. Vol. 16, № 1-4. P. 231-256.

31. A.M.Bagirov and A.M.Rubinov. Global minimization of increasing positively homogeneous functions over the unit simplex, Research Report 99/37, University of Ballarat, 1999.

32. A.M.Bagirov and A.M.Rubinov. Cutting angle method in global optimization: theoretical and numerical aspects, Research Report 00/8, University of Ballarat, 2000.

33. D.Babaev. An exact method for solving the subproblem of the cutting angle method of global optimization. In "Optimization and Related Topics" A.Rubinov and B.Glover (eds.). Kluwer Academic Publishers, 2001. P. 15-26.

34. Gourdine E., Jaumard В., Ellaia R. Global optimization of Holder functions // J. Global Optim. 1996. V.8, N 4. P.323-348.

35. Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа. М.: Наука, 1989.

36. Hansen P., Jaumard В., Lipschitz optimization // Handbook of global optimization. Dordrecht: Kluwer Acad. Publ., 1995. P. 407-494

37. Horst R., Nast M., Thoai N.V. New LP bound in multivariable Lipschitz optimization: theory and applications // J. Optim. Theory Appl. 1995. V. 86, №2. P. 369-388

38. Pinter J. Global optimization in action. Dordrecht: Kluwer Acad. Publ., 1996.

39. Sergeev Ya.D. An one-dimensional deterministic global optimization algorithm. // Журн. вычисл. математики и матем. физики. 1995. Т. 35, №5. Р. 705-717

40. Wood G.R., Zhang В.P. Estimation of the Lipschitz constant of a function//J. Global Optim. 1996. V.8, N 1. P. 91-103.

41. Baritompa W. Accelerations for a variety of global optimization methods //J. Global Optim. 1994. V.4, N 1. P. 37-45.

42. Breiman L., Cutler A. A deterministic algorithm for global optimization // Math. Program. 1993. V. 58, N 2, P. 179-199.

43. Gergel V.P. A global optimization algorithm for multivariable functions with Lipschitzian first derivatives // J. Global Optim. 1997. V.10, N 3. P. 257-281.

44. Tuy H. D.C. optimization: theory, methods and algorithms // Handbook of global optimization. Dordrecht: Kluwer Acad. Publ., 1995. P. 149-216

45. Khamisov O.V. On optimization properties of functions with a concave minorant. //J. Global Optim. 1999. V.14, N 1. P. 79-101.

46. Сухарев А.Г., Подобедов B.E., Алгоритм поиска глобального максимума функции нескольких переменных. // Вычислительные комплексы и моделирование сложных систем. М.: МГУ, 1989. С. 124-134.

47. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления

48. Шнитман В., Отказоустойчивые компьютеры компании Stratus // Открытые Системы № 1 1998

49. Кронид Эрглис, Эффективность процессоров, работающих в системе РСИ // Открытые Системы № 6 1997

50. Коржов В., Асинхронные вычисления, или компьютер без процессора // Открытые Системы № 6 1997

51. Кузьминский М., Архитектура S2MP свежий взгляд на cc-NUMA // Открытые Системы № 2 1997

52. Шнитман В., Архитектура PowerScale // Открытые Системы № 4 1996

53. Вьюкова Н., Сервер для кластерных и массово-параллельных архитектур // Открытые Системы № 4 1995

54. Бронсон Марк, Высокопроизводительные ALPHA-серверы в стандарте VME // Открытые Системы № 4 1995

55. Арапов Д., Можно ли превратить сеть в суперкомпьютер? // Открытые Системы № 4 1997

56. Кузьминский М., Современные суперкомпьютеры: состояние и перспективы// Открытые Системы № 6 1995

57. Дубова Н., Суперкомпьютеры nCube // Открытые Системы № 2 1995

58. Макстеник М., Сравнение сетевых архитектур // Сети № 2 1997

59. Французов Д., Оценка производительности вычислительных систем // Открытые Системы № 2 1996

60. Французов Д., Оценка производительности суперкомпьютеров // Открытые Системы № 6 1995

61. Воеводин Вл.В., Параллельная обработка данных, http://www.parallel.ru/vvv/

62. Комолкин А.В., Немнюгин С.А., Программирование для высокопроизводительных ЭВМ, http://www.hpc.nw.ru/COURSES/HPC/

63. Крюков В.А., Операционные системы распределенных вычислительных систем (распределенные ОС), http://www.parallel.ru/krukov/66.1ап Foster, Designing and Building Parallel Programs, http://rsusul.rnd.runnet.ru/tutor/design/dbpp/text/book.html

64. Booth S., MacDonald N., Perfomance Optimization, http://www.hpc.nw.ru/COURSES/

65. Спыну C.K. Поиск глобального экстремума с использованием параллельных вычислений. Сб. трудов Международной НТК «XXX Гагаринские чтения», (Москва, 6-10 апреля 2004 г.). - М.: «МАТИ» - РГТУ им. К.Э.Циолковского, 2004, т.5, с. 101

66. Спыну С.К. Поиск глобального экстремума с использованием параллельных вычислений. «Успехи современного естествознания» 2004, №7, с. 94,94.

67. Беневоленский Д.С., Жадан И.В., Спыну С.К. Использование параллельных вычислений при расчете метода половинных делений для глобальной оптимизации функции многих переменных. «Успехи современного естествознания» 2005, №7, с. 94,94.

68. Беневоленский Д.С., Жадан И.В., Спыну С.К. Виртуальная суперЭВМ на основе использования распределенных вычислений в локальной вычислительной сети для решения сложных научно-технических задач. «Успехи современного естествознания» 2005, №7, с. 94,94.

69. Беневоленский С.Б., Жадан В.Г., Жадан И.В., Истомина H.JL, Спыну М.В., Спыну С.К. Принципы создания программного обеспечения для систем распределенного вычисления. «Успехи современного естествознания» 2005, №7, с. 94,94.

70. Свидетельство об отраслевой регистрации разработки №5383 «Программное обеспечение для поиска глобального экстремума функции многих переменных Globex», Дата регистрации 16 ноября 2005г.

71. Томас Ньюман, "Сортировка и поиск: рецептурный справочник", 1995.

72. Кукушкин Б.А., "Описания комбинаторных алгоритмов", 19941995.

73. Александр Каленюк, "Нестандартные алгоритмы сортировки".

74. Б.Керниган, Д.Ритчи. Язык программирования Си (пер. с англ.). -М.: Финансы и статистика, 1992.

75. Подбельский В.В. Язык Си++. М.: Финансы и статистика, 2000. -560с.

76. Проблемы субмикронной технологии. /Под ред. Орликовского А.А. М.: Наука, 1993. - 112с. - (Тр. ФТИАН: т.6).

77. Валиев К.А., Орликовский А.А. Технологии СБИС. Основные тенденции развития. Электроника: наука, технология , бизнес, №5-6,1996, стр.3.

78. Тодуа П.А., Быков В.А., Волк Ч.П. Метрологическое обеспечение измерений длины в микрометровом и нанометровом диапазонах и их внедрение в микроэлектронику и нанотехнологию-Микросистемная техника, Ч.1., 2004, №1. с. 38-46. Ч.2., 2004, №2. -с. 24-39.

79. Тарлыков В.А. Лазерная дифрактометрия микрообъектов типовой формы. Автореферат на соискание ученой степени доктора технических наук, 2000.

80. Глудкин О.П., Густов А.е. Устройства и методы фотометрического контроля в технологии производства ИС-М.: Радио и связь, 1981. -112с.

81. Виноградова Г.Н., Вознесенский Н.Б. Дифракционные методы контроля геометрических параметров. Оптический журнал. 2002. т.69, №2, с. 76-81.

82. Азарова В.В. и др. Измерение шероховатостей прецезионных кварцевых и лазерных зеркал методом дифференциального рассевания. Оптический журнал. 2000, т.69, №2, с. 71-75.

83. Новиков Ю.А., Раков А.В. Метрология критических размеров элементов СБИС. Измерительная техника. 1999, №1, с. 14-18.

84. Новиков Ю.А., Раков А.В. Высокоточные измерения периода дифракционной решетки интерференционным дифрактометром и исследование качества дифракционной решетки. Оптика и спектроскопия. 1994, т.77, №1, с. 145-151.

85. Волков В.В., Герасимов JI.JL, Капаев В.В., Ларионов Ю.В. Оптические методы измерения размеров БИС и СБИС. -Микроэлектроника, 1980, т.9. вып.6, с. 554-563.

86. Ping Sheng. Theoretical Consideration of Optical Diffraction from RCA Vidio Disc Signals. RCA Revew, 1978, v.39, №9, p. 513-543.

87. Poger A., Maystre D. Inverse scattering method in electromagnetic Optics Application. J Opt Soc Am, 1980, v.70, №12, p. 1483-1494.

88. Nagvi S. and other. Scatterometry applied to microelectronics processing. Solid State Technol., 1993, v.36, №3-4.

89. Истомина Н.Л., Спыну M.B., Моделирование и компьютерная обработка геометрических параметров элементов топологии ИМС на основе дифрактометрии в микро- и наноэлектроники, Успехи современного естествознания, 2/2005 , с.72

90. Макс К. Гофф. Сетевые распределенные вычисления: достижения и проблемы. 2005, с.320

91. Э. Таненбаум, М. ван Стеен, Распределенные системы. Принципы и парадигмы. 2003, с. 8 80

92. Ириков В.А., Тренев В.Н., Распределенные системы принятия решений: Теория и приложения. 1999, с.288

93. В. В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. 2002, с.600

94. Корнеев В. В., Параллельные вычислительные системы. 1999, с.320

95. Р. Лафоре, Объектно-ориентированное программирование в С++. 2003, с. 928

96. Роберт Седжвик, Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах. 2002, с.496

97. Уолтер Савич, Программирование на С++. 2003, с.784

98. Б. С. Хусаинов, Структуры и алгоритмы обработки данных. Примеры на языке Си. 2004, с.464