Построение численных методов решения оптимизационных задач на ЭВМ с векторно-конвейерной архитектурой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЙ НАУК СССР ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ АН СССР

На правах рукописи

ХОТЕЕВ Сергей Валентинович

УДК 519.6

ПОСТРОЕНИЕ ЧИСЛЕННЫХ МЕТОДОВ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ НА ЭВМ С ВЕКТОРНО-КОНБЕЙЕРНОЙ АРХИТЕКТУРОЙ

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1991

Работа выполнена в Институте проблем кибернетики Академик Наук СССР.

Научный руководитель

Официальные оппоненты-

Ведущая организация

доктор физико-математических наук, профессор В.Г.Карманов

доктор физико-математических наук доцент Ю.А.Флеров

кандидат физико-математических наук В. А.Семенов

Московский Государственный Университет им. М.В.Ломоносова

Защита диссертации состоится "_и_1991 г.

в_час. _мш. на заседании Специализированного Совета

К 003.78.01 при Институте проблем кибернетики АН СССР по адресу: 117312, Москва, ул.Вавилова, 37.

С диссертацией можно ознакомиться в библиотеке Института

Автореферат разослан "31" ЛЛ&ЛЧ 1991 г.

Учешй секретарь Специализированного Совета■ к.ф.-м.н. ' А.З.Ишмухаметов

^ I

, ; ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

' Актуальность темы. На современном этапе развития науки и £]^;'^т}зхники параллельные и векторные суперкомпьютеры становятся важным исследовательским инструментом в научных и инженерных областях человеческой деятельности. С ж помощью можно моделировать слокные явления и анализировать гипотезы, не прибегая к часто дорогостоящим и требующих большое время экспериментам. Влияние высокопроизводительных компьютеров в области крупномасштабных научных вычислений не обошло стороной сферу численной оптимизации и ее приложений в задачах исследования операций и управления. В связи с этим возникло направление исследований по разработка новых программных комплексов, адаптированных для суперкомпьютеров,обеспечивающих наиболее эффективное использование их вычислительных возможностей.

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

Существует■множество методов решения квадратичной задачи. К наиболее известным методам относятся методы Данцига, Била, Вольфа, Гилдрета и другиэ. Существенные трудности в реализации на суперкомпьютере этих методов состоят в необходимости прибегать к сложной, изощренной технике программирования с целью полностью использовать возможности векторно-конвейерной ЭВМ. В работе рассматривается подход, основанный на использовании модифицированных функций Лагранжа. Наряду с эффективностью решения большого числа задач квадратичного программирования, этот подход обеспечивает высокую загруженность вычислительных рессурсов векторноконвейерной ЭВМ.

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

Методика исследования состоит в изучении многошаговых градиентных схем по прямым и двойственным переменным для метода модифицированных функций Лагранка в задачах условной

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

Научная новизна диссертационной работы состоит в том, что

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

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

- создана единая методика изучения многошаговых градиентных методов;

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

- в случае сильной выпуклости целевой функции установлена глобальная сходимость 2-х шаговых методов и получена оченка скорости сходимости;

Практическая значимость. Библиотека алгоритмов, предложенная в диссертации, написана на языке ассемблера векторно-конвейерной ЭВМ и может быть исполь'зована для широкого круга задач квадратичного программирования: на всем пространстве, на положительном ортанте или на простом допустимом множестве типа параллелепипеда, с линейными ограничениями типа равенства и/или неравенства. В подпрограммах библиотеки алгоритмов использованы стандартные соглашения о связях, поэтому эти подпрограммы могут быть непосредственно использованы в программах, написанных на языке высокого уровня Фортран или ПЛ/1. Теоретические результаты работы могут быть использованы при построении новых многошаговых вычислительных методов.

Аппробация работы. Материалы диссертации обсуждались на семинаре отдела прикладной математики Института проблем кибернетики АН СССР, на Всесоюзной конференции "Современные проблемы информатики, вычислительной техники и автоматизации" (1988г. .Москва), 1П-й иколе-семинаре "Численные методы для

- 5 -

высокопроизводительных систем" (1988г.,Фрунзе).

Публикации. По теме диссертации опубликовано 4 работы.

Структура я объем диссертации. Работа состоит из введения, двух глав, объединяющих 7 параграфов, заключения и списка литературы из 60 названий, содержит 100 страниц машинописного текста, I рисунок и 2 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОГЫ

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

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

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

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

Не менее обширен класс итеративных методов. Многие методы этого класса также основаны на решении задачи линейной дополнительности. В этом случае решенье осуществляется, например, с помощью метода Гаусса-Зейделя или метода последовательной вершей релаксации (SOR). У этого подхода есть определенные достоинства и недостатки. С одной стороны, известно, что при определенных условиях такой подход обладает сверхлинейной скоростью сходимости к решению. Имеются также работы по реализации метода Гаусса-Зейделя на супер-ЭВМ. С другой стороны, не ко всякой задаче линейной дополнительности, полученной с помощью условия Куна-Таккера, могут быть непосредственно применены метода Гаусса-Зейделя или SOR, так как матрица задачи линейной дополнительности должна быть строго положительно определена и все числа на главной диагонали должны быть больше нуля. Имеются трудности в реализации алгоритмов Гаусса-Зейделя и S0E метода на векторно-конвейерной ЭВМ связанные с недостаточной однородностью самих алгоритмов.

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

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

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

Предлагаемый подход лишен некоторых недостатков методов, основанных на решении задачи линейной дополнительности. Размерность задач на безусловный минимум не выше размерности исходной задачи. Используемая техника доказательства позволяет исследовать сходимость итеративных последовательностей в выпуклом случае. Подход обеспечивает высокую однородность алгоритма и хорошо отображается на архитектуру векторно-конвейерной ЭВМ. "Прогнозный" метод модифицированной функции Лагранка позволяет сохранять структуру данных исходной задачи, что особенно важно для задач большой размерности со слабо заложенными матрицами.

Задача минимизации квадратичной функции на всем пространстве эквивалентна решению системы уравнений

Их = I. (1)

с неотрицательно определенной матрицей if. Одним из основных методов решения больших практических задач вида (1) является метод сопряженных градиентов. В случае плохой обусловленности матрицы М сходимость метода сопряженных градиентов не всегда удовлетворяет пользователей. Было предложено много способов ускорямцих сходимость. В приложениях для супер-ЭВМ широко применяется метод сопряженных градиентов .с первобуславлива-нием. Однако, следует заметить, что удачный выбор матрицы переобуславливания сильно связан с особенностями решаемой задачи и дать какой-либо рецепт выбора матрицы переобуслав-ливаниия в общем случав не представляется возможным.

Рассмотрим задачу минимизации квадратичной функции с линейными ограничениями типа неравенства 2<Аг,х) + (ci.z) - mill,

Сх 4 ъ, х € Q. (2)

где А - положительно определенная NxN матрица, С - МхМ матрица, d и b - соответственно, У и М векторы, Q - выпуклое множество. Модифицированную функцию Лагранка возьмем в виде:

Ы(х,у) = ^(Аг.х) + (d,x) + jjgl (к + ЫСх - Ь)) + |2 - ||у|2, где k - некоторое положительное число, (.)+ - операция

проектирования на положительный ортант. Используя функцию Mix, у), поставим задаче (2) в соответствие следующую задачу f1*1 = argpiin{äix.tf1 : х i Q)), (За)

y"+1 = (j/1 + - b)) + . (36)

Известно, что последовательность {Л сходится к решению х* задачи (6) в смысле - г*| - 0 при п -» <». Метод сопряженных градиентов непосредственно к задаче (За) не применим из-за наличия в Six,у) оператора проектирования.Применим другой (прогнозный) подход, который позволяет перенести методы решения задачи квадратичного программирования с ограничениями типа равенства на задачу с ограничениями типа неравенства. Рассмотрим задачу

fix) - min, Ox s: b, (4)

Ax = d, x e Q. Здесь f(x) - выпуклая функция ,0 - УхК,-матрица, А - NxMz~ матрица, bad- вектора размерностью И, и соответственно, Q - выпуклое множество. Задаче (4) поставим в соответствие следующую задачу

ff1 - (у11 + - Ь))\ 2" = z" + ¿(Лг11 г d),

= argmlnCi' (i.JP.z11) : л: e Q>, (5) S™1 = (j/1 + й«й»+1 - d))\

2nf1 = 2" + fe(iüP+1 - d). где fe - некоторое положительное число, у - М^-вектор двойственных переменных, соответствующий ограничениям типа неравенства, z - й2~вектор двойственных переменных, соответствующий ограничениям типа равенства, 'йодифшйровавная функция Лаграя-ssa Ы (х,у,z) тлеет следущий вид

Hnix,y,z) = ¿¡¿Ix - X^f + fix) + (у,Gr - b). + (z.Ax - d). В диссертации доказывается следущая

Теорема I. Если fix) - выпуклая непрерывно дифференцируемая функция, Q - выпуклое множество, тогда последовательность {г"}, генерируемая задачей (5), сильно сходятся к решении х* задачи (4), го есть Jr" - - О при п - со.

Прогнозный метод, примененный к линеаризованной задаче

- 9 -

Я(хк) - min, х. е Q, (6)

где И (х) = - ^J2 + a(vf(x),x-a^), а > О,

Q = { х : + (vg1(iJt),x-iJC) $0,1 = 1 ,m},

в предположении, что Q - выпуклое замкнутое множество из Rn, m - число оганичений, функции f(x) и gt(x) е С1(Q), имеет следующий еид

yMyVy (g(xicHvglxli){xrl-xk))\

(7)

У4» (J^+T (g & bvg &) 1))f. где 7c(.) - операция проектирования на множество Q. В методе (7) проводятся итерации по индексу п. Последовательность (аРУ сходится к решению ¿г*""1 задачи (6)при условии, что параметр 7 удовлетворяет неравенству 72<1/2I, где-Ъ - максимальное собственное число матрицы vg^rr^vgi:^) Прогнозный метод для задачи поиска проекции точки на выпуклый многогранник есть частный случай процесса (7) без целевой функции fix). Запишем прогнозный метод для задачи поиска возможного направления спуска, представленной в виде

<sk,sk) - min, i £ О

(v^Cr*)^) + 1 < О, (8)

(S7/(kx),Sk) + 1 sä О,

где функции f(x) и g^x) t С1 (Q).Имеем следующий прогнозный метод

lT= (¡Л-7 (vg (а*) )+1))+, 1 (yir(br^+^-u'V/)-vg )] ? (9)

u'Vyüvfiz11).^ Vi ),

где %(.) - операция проектирования на множество Q. Примечательно, что метод (9) одинаково просто реализуется как на положительном ортанте, так и на простом множестве типа параллелепида, в то время, как метод, основанный на задаче, двой твешюй к (8), справедлив ллзь при Q = Rn.

В § 1.3 обсуздавтся з-ааговые метода в задачах безусловной г.итетз8Ц1Ш как один из способов получения Солее бистро®

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

Естественным обобщением метода тяжелого шарика является следующая итеративная процедура

л»4"' = г^-а^/и*1)«^ (10)

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

= zn-a0v/(zn)+.. .+as (vfia?-3^ )). (11)

Имеют место следующие теоремы. Теорема 2. Если

1. функция /(х) - выпуклая и непрерывно дифференцируемая,

2. Q. - выпуклое множество,

3. X - множество минимумов функции fix) не пусто (X * О),

4. последовательность {¿Л построена согласно соотношению

а?"1 = argminil^x), х е Q),

5. с^» 0, 1= 0,в,

7. 1 - ajj аавг > О,

тогда ¡¿"-г*!2 - 0 при п «о (х* е X). Теорема 3. Если

1. функция f{x) - выпуклая и непрерывно дифференцируемая,

2. Q - выпуклое множество,

3. 1 - множество минимумов функции f(x) не пусто (X * 0),

4. последовательность fx11} построена согласно соотношению

= argrain{Fn(x), х с Q),

5. а^ ад> О,

7. > О,

тогда l^-r*!2 - о при п - га (z'. e X).

Одно из следствий Теоремы 2 и 3 состоит в том, что па практике при вычислениях по формулам (10) и (11), видимо, целесообразно ограничиться з-шаговыми схемами с з порядка 2 или 3.

Для сильно выпуклой целевой функции с константой Липшица L имеет место следующая

Теорема 4. Если fix) - сильно выпуклая непрерывно дифференцируемая функция на всем пространстве Rn, последовательность iz") построена согласно соотношению

= зР- - av/(z*') + - v/(an"')),

а и ß удовлетворяют условию

1) 0 < ß < a,

2) a < 2/1,

тогда ¡я*1 - x*\ - 0 с геометрической скоростью при п - со.

В § 1.4 рассматриваются многошаговые метода в задачах условной минимизации. Пусть задана задача минимизации выпуклой функции с линейными ограничениями типа равенства

fix) -> min, (12)

Сх - Ь = 0, х е Q. Здесь F(x) - выпуклая непрерывно дифференцируемая функция, С - NzM-матрица, Q - выпуклое множество. Модифицированную, функцию Лагранва запишем в следующем виде

й„(х,у) = ^¡-ix-ap^ivfijp) ,x-jp)i-iy,Cx-b)^lCx-bf, где у - некоторый положительный параметр, у - вектор двойственных переменных. Будем рассматривать следующий з-шаговый прогнозный метод по двойственным переменным

1НЛР, (гЛ-у*-1 )+...+ß3(2/n-s+1-</n-3),

^^argmini^Cr.y) : х « Q), (13)

*/"+'=1Л-7 (С^-Ъ). Имеет место следущая' Теорема 6. Если

1. fix) € 4й,

2. Q - выпуклое мнокество,

3. X - множество репений задачи (12) нэ пусто (Я ? О),

4. последовательность (Л генерируется задачей (13),

5. заданы начальные условия t/n"s=yn"s<'1 = ...=y"1=tJ/0,

- 12 -

6. О < а0 < | и 1-а)71-...-ад+17д+) > о, где а1 = а0р,/7,

<х, = а0(р2-р, )/т,

= ^о^-

и 7± = (1-1)г+2, если а± £ 0, 1 = 1.....э+1,

"7± = -(1-1 )2, если < О, 1 = 1.....э+1.

тогда последовательность {г*1} сходится к решению х* еХ: ¡зР-х*1 - О при п <о.

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

В Главе 2 основное внимание уделено созданию библиотеки методов решения задач квадратичного программирования. Векторно-конвейерная ЭВМ служит для быстрого и эффективного решения крупномасштабных задач. Быстрая обработка данных возможна только на основе учета архитектурных особенностей векторного компьютера. Современные компиляторы с языков высокого уровня не в состоянии генерировать высокоэффективный код для ЭВМ со сложной векторно-конвейерной архитектурой. Программирование на языке ассемблера в настоящее время является единственным средством, обеспечивающим максимальную загруженность функциональных устройств и их параллельную работу. Даже для не очень большой задачи программирование на языке ассемблера сопрянено с большой кропотливой работой по отладке программы. Целесообразно большую программу разбить на повторяющиеся группы операций и их программировать в виде отдельных базовых операций или модулей. К выбранным базовам операциям естественно предъявить следующие требования. Набор базовых операций должен быть полон, то есть должна существовать возможность реализовать алгоритм решения любой задачи из заданного класса . с помощью этого набора базовых операций. При этом главная часть общего числа арифметических операций алгоритма должна прийтись на базовые операции. Базовые операции должны быть функционально законченными, простыми и долхшы обеспечивать максимальную загруженность функциональных устройств.

Дня решения задач квадратичного программирования из главы I достаточно введения следующих базовых операций

- 13 -

у = Ах - Ь, г = у + ох, г = (у + от)*, 0 = (х,у), В = р! + А, В = С + аАТ/1, у = Ъ + аЛг, (14)

Здесь х, у, г, Ъ - вектора, А, В. С- матрицы, Е - единичная матрица, а,- вещественные числа, т- операция транспонирования, (.)+- операция проектирования на положительный ортавт, (.,.) - операция скалярного произведения векторов. Использование операции (14) позволяет избежать транспонирования матрицы, так как операция транспонирования не может быть достаточно .эффективно реализована на векторно-конвей-ерной ЭВМ.

В § 2.2 рассматривают вопросы реализации базовых операций на векторно-хонвейерной ЭВМ. Для оценки качества выбранных базовых операций введены количественные характеристики. Критерий качества алгоритмов реализации базовых операций, зависящий только от алгоритма, (7 = где т -число операций над векторами, И = У1+Ио, Ы - число входных векторов, Мо - число выходных векторов, показывает на сколько эффективно используется быстрая регистровая память ЭВМ. Чем больше ¡V, тем больше полезной вычислительной работы выполняют функциональные устройства на одно обращение к памяти. Введем критерий качества алгоритма базовой операции, зависящий от способа реализации на ЭВМ ге = где т - число арифметических операций над векторами, Т - время выполнения базовой операции в векторных тактах, т.е. за единицу времени берется время выполнения операции с плавающей запятой над целым вектором размерность» Н. Таблица I.

1Г х Т

у = Ь + аЛг г = у + ах г = (у + аг) + а = (х,у) у = Ъ + аА^х В = ^Е + А С = А + а£тВ г = ъ{х + 'ау) гы - 1 И + 3 2/3 1 1 ги - 1 № + "3 1/2 2Я - 1 N + 3 4/7 '¿И - 1 ы + а 2/3 2 <1 2У - 1 77 + 3 1/2 2Я - 1 N + 3 4/7 N + 3 3 4 >2 И + 3 2 Я«? + 3) 7

- 14 -

•Приведенные критерии качества теоретически оценены для' основных базовых операций, что огранено в Таблице I.

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

Для построения базовых одераций первого и второго уровня использовался широкий набор макросредств, 'имеющихся в языке ассемблера. Одним из основных назначений макросредств является расширение языка программирования путем введения новых операций, удобных для частных применений. Совмещение возможностей условного ассемблирования с шрокши возможностями макросредств позволяет реализовать макромодули, которые в отличающихся контекстах будут выполнять различные функции. Такие функции, как г = х + айу, г = оМу - х, г = х - Ну и другие мошо представить в виде одного макроопределения с параметрами. В зависимости от выбора параметров в исходный текст будет подставляться соответствующая для заданной функции последовательность команд. При этом исключаются лишние условные перехода, использование которых ненелательно в циклах с векторными опёрациями. Дополнительно макроопределения позволяют гибко использовать регистровую память основной машины, сокращая число обращений к основной памяти.

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

- 15 -

написанных на языках высокого уровня таких, как Фортран или ШТ. В подпрограммах соблюдаются стандартные соглашения о связях с внешними подпрограммами.

В § 2.3 рассматриваются результата тестирования библиотечных модулей и подпрограмм. Тестирование и отладка осуществлялись с помощью имитационного комплекса на персональном компьютере IBM PC AT и ЭВМ БЭСМ-6.

В Таблице 2 приводится производительность Р базовых операций при длине вектора N=64. Величина производительность выражается в миллионах операций с плавающей точкой с секунду (Milops). Высокая производительность матрично-векторных операций позволяет организовывать эффективные вычислительные процессы. Например, производительность на одном итерационном цикле в методе скорейшего спуска составляет 154 Milops и 152 Milops в методе сопряженных градиентов. Таблица 2.

Базовые .операции Ч Р (Mflopa)

у = b + аАх 4693 176

у = b + аАтх 4693 176

z = у + <хх 193 66

z = (у + ау)* 263 49

а = (х.у) 275 46

В - У? + А 9150 7

С = А + В 14106 29

С = А*В 284612 177

В качестве примера был выполнен тестовый расчет по минимизации 5-мерной квадратичной функции с линейными ограничениями типа равенства. На этом тесте была получена производительность 14 ИПорз. Минимизация проводилась с псмощыо библиотечной подпрограммы ЮШ£Ш. На задачах с большей размерностью ожидается существенно большая производительность.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ 1) Построена библиотека базовых операций (модулей)¿учитывающих архитектурные особенности векторно-коявайерной ЭВМ. В состав- библиотеки входят 58 ютдулей для матрично-векторвда

- 16 -

операция, а также метода сопряженных градиентов и скорейшего спуска.

2) Построена библиотека алгоритмов решения задач квадратичного программирования в общем виде и задач линеаризации, поиска возможного направления спуска, проекции точки на многогранное множество.

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

4) Установлены условия сходимости s-шаговнх градиентных методов типа "тяжелого шарика" и методов, использующих градиенты, вычисленные на предыдущих итерациях, для-задач безусловной и условной оптимизации;

5) Для случая сильной выпуклости целевой функции установлена глобальная сходимость 2-х шаговых методов и получена оченка линейной скорости сходимости для задачи безусловной минимизации.

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

Материалы диссертационной работы содержатся в следующих

публикациях

1. Хотеев C.B. Решение задач оптимизации на векторно-конве-йерной ЭВМ. В сб."Современные проблемы информатики, вычислительной техники и автоматизации", Тезисы докладов Всесоюзной конференции, Москва,1988г.

2. Хотеев C.B. Реализация алгоритмов оптимизации на супер ЭВМ. В сб.:"Численные метода для высокопроизводительных систем", Тезисы докладов III школы-семинара, Фрунзе, сентябрь, 1988

3. Хотеев C.B. Реализация алгоритмов оптимизации на вехторно-конвейерной ЭВМ.- В сб.¡"Вопросы кибернетики. Вычислительные вопросы анализа больших систем",М.:1989,стр. 157-163.

4. Хотеев C.B. Исследование свойств сходимости и оценок скорости сходимости двухшаговых градиентных методов для задач оптимизации. В сб."Вопросы кибернетики",М.:1990г. '/""V-^

Подписано в печать 23.C6.9I г. Формат 60x84/16, Объём 1,0 п.л.

Тираж 100 экз. Заказ Л 34. Беоллагно._

Ротапринт ЕИВЦ МГУ