Введение к работе
, ij:Tr> j
;,:,-!j; \ Актуальность темы. На современном этапе развития науки и Р^і^тізхники параллельные и векторные суперкомпьютеры становятся важным исследовательским инструментом в научных и инженерных областях человеческой деятельности. С их помощью можно моделировать слокные явления и анализировать гипотезы, не прибегая к часто дорогостоящим и требующих большое время экспериментам. Влияние высокопроизводительных компьютеров в области крупномасштабных научных вычислений не обошло стороной сферу численной оптимизации и ее прилокений в задачах исследования операций и управления. В связи с этим возникло направление исследований по разработке новых программных комплексов, адаптированных для суперкомпьютеров,обеспечивающих наиболее эффективное использование их вычислительных возможностей.
В диссертации главным образом исследуются задачи квадратичной оптимизации. Этот важный в практическом применении класс, с одной стороны, является основой многих эффективных методов безусловной и условной оптимизации,а с другой сторони, хорошо отображается на архитектуру векторно-конвейервой ЭВМ,
Существует множество методов решения квадратичной задачи. К наиболее известным методам относятся методы Данцига, Била, Вольфа, Гилдрета и другие. Существенные трудности в реализации на суперкомпьютере этих методов состоят в необходимости прибегать к сложной, изощренной технике программирования с целью полностью использовать возможности векторно-конвейерной ЭВМ. В работе рассматривается подход, основанный на использовании модифицированных функций Лагранжа. Наряду с эффективностью решения большого числа задач квадратичного программирования, этот подход обеспечивает высокую загруженность вычислительных рессурсов векторноконвейерной ЭВМ.
Целью работы является отображение методоз решения задач условной оптимизации на векторно-конвейэрную архитектуру и построение эффективных алгоритмов, учитывающих архитектурные особенности ЭВМ.
Методика исследования состоит в изучении многошаговых градиентных схем по прямым и двойственным переменным для метода модифицированных функций Лагранка в задачах условной
-4-оптимизации и в построении библиотеки базовых операций на основе структурной общности алгоритмов для рассматриваемых методов решения оптимизационных задач. В работе применялись аналитические и вычислительные методы линейной алгебры и методы теории математического программирования.
Научная новизна диссертационной работы состоит в том, что
создана библиотека базовых операций (модулей).учитывающих архитектурные особенности векторно-конвейерной ЭВМ, на основе которой построена библиотека алгоритмов решения задач квадратичного программирования;
предложена методика решения задач условной оптимизации с использованием библиотеки базовых модулей.
создана единая методика изучения многошаговых градиентных методов;
исследованы условия сходимости з-шаговых градиентных методов типа "тяжелого шарика" и методов, использунцих градиенты, вычисленные на предыдущих итерациях, для задач безусловной и условной оптимизации;
в случае сильной выпуклости целевой функции установлена глобальная сходимость 2-х шаговых методов и получена оченка скорости сходимости;
Практическая значимость. Библиотека алгоритмов, предложенная в диссертации, написана на языке ассемблера векторно-конвейерной ЭВМ и может быть исполь'зована для широкого круга задач квадратичного программирования: на всем пространстве, на положительном ортанте или на простом допустимом множестве типа параллелепипеда, с линейными ограничениями типа равенства и/или неравенства. В подпрограммах библиотеки алгоритмов использованы стандартные соглашения о связях, поэтому эти подпрограммы могут быть непосредственно использованы в программах, написанных на языке высокого уровня Фортран или ПЛ/І. Теоретические результаты работы могут быть использованы при построении новых многошаговых вычислительных методов.
Ашгробация работы. Материалы диссертации обсуждались на семинаре отдела прикладной математики Института проблем кибернетики АН СССР, на Всесоюзной конференции "Современные проблемы информатики, вычислительной техники и автоматизации" (1988г..Москва), II1-й школе-семинаре "Численные методы для
- 5 -высокопроизводительных систем" (1988г.,Фрунзе).
Публикации. По теме диссертации опубликовано 4 работы.
Структура и объем диссертации. Работа состоит из введения, двух глав, объединяющих 7 параграфов, заключения и списка литературы из 60 названий, содержит 100 страниц машинописного текста, I рисунок и 2 таблицы.