Оптимальные по точности алгоритмы решения некоторых многоэкстремальных задач оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение • ••••*•••»•••••••••••».

Глава I. ПАССИВНЫЕ И ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ

ПОИСКА ГЛОБАЛЬНОГО МИНИМАКСА . 14

§ I.I. Пассивные алгоритмы для негладких функций

§ 1.2. Последовательные алгоритмы для негладких функций . . о

§ 1.3. Пассивные алгоритмы для дифференцируемых функций

§ 1.4. Последовательные алгоритмы для дифференцируемых функций • . ••••.•

Глава II. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ГЛОБАЛЬНОГО ЭКСТРЕМУМА .34-

§ 2.1* Краткий обзор проблемы • •.••••••••«.

§ 2.2. Исследование вспомогательной задачи минимизации

§ 2.3. Экономичный алгоритм минимизации •••••••••

§ 2.4. Изучение свойств разбиений для двумерного случая

§ 2.5. Линейная сходимость алгоритма на подклассе функций

Глава III. ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ ПОИСКА ГЛОБАЛЬНОГО

МИНИМАКСА.57

§ 3.1. Краткий обзор проблемы и описание алгоритма

§ 3.2. Сходимость алгоритма ••••••••••.•»

§ 3,3. Исследование вспомогательных задач

§ 3.4. Линейная сходимость алгоритма на подклассе функций

Глава 1У. АЛГОРИТМЫ ПОИСКА ЭКСТРЕМУМА, ОПТИМАЛЬНЫЕ В

СПЕЦИАЛЬНОМ СМЫСЛЕ . 80

§ 4.1. Поиск экстремума функций из вероятностного класса

§ 4,2. Нахождение экстремума дифференцируемой функции при известном наборе ее значений . . . . •

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

Ряд прикладных задач оптимизации отражает эту глобальную проблему в конкретных областях трудовой деятельности людей. В качестве примеров можно привести задачи оптимального проек тирования технических систем [44,46,49 ] , управления производственно-технологическими процессами [ 2 ] , минимизации веса тех или иных конструкций [1,48,89 J , принятия решений в экономике и экологии [ 90,96 ] .

Математически такие задачи часто сводятся к поиску экстремумов функций или функционалов. Большая часть работ, относящихся к этой тематике, посвящена отысканию локальных экстремумов [ 7,8,27,33,55,51,66,67 ] . В то же время в указанных практических задачах обычно главный интерес представляет глобальный экстремум, а условия совпадения обоих типов экстремумов далеко не всегда выполняются ( см., например, f 3,53 ] ).

Построению и исследованию эффективных и оптимальных алгоритмов решения задач многоэкстремальной оптимизации посвящены работы Д.И.Батищева, Г.С.Ганшина, Ю.Б.Гермейера, Ю.М.Данилина, Ю.Г.Евтушенко. А.Г.Жилинскаса, В.В.Иванова, В.В.Леонова, В.С.Михалевича, Н.Н.Моисеева, И.^.Моцкуса, Ю.И.Неймарка, А.С.Немировского, С.А.Пиявского, Б.Н.Пшеничного, Л.А.Растри-гина, Р.Г.Стронгина, А.Г.Сухарева, В.В.Федорова, В.К.Чичинад-зе, Д.Б.Кйшна и других математиков.

Основные подходы к решению задач многоэкстремальной оптимизации включают в себя обобщение на многоэкстремальный случай методов локальной оптимизации [ 4,53 J , случайный поиск [ 79 ] , создание оптимальных алгоритмов нахождения экстремума [ 30,39,61,84 ] . Оценки оптимальных алгоритмов решения многоэкстремальных задач в многомерном случае на широких классах функций демонстрируют необходимость огромных вычислительных ресурсов для достижения приемлемой точности. Поэтому представляется важным выделение таких практически используемых подклассов функций, для которых эффективность рассматриваемых алгоритмов является более высокой.

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

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

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

2. Разработан последовательный алгоритм поиска глобального минимакса негладких функций, доказана его сходимость. Исследован также алгоритм последовательного поиска экстремума [20,61].

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

3. Построены оптимальные по точности алгоритмы глобальной минимизации функций следующих специальных классов: а) класс функций с вероятностными ограничениями на производные; б) класс дифференцируемых функций с известными значениями в фиксированном числе точек.

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

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

Введем основные понятия и определения, используемые в диссертации.

В работе рассматриваются алгоритмы поиска глобального экстремума

Х6Х/ а также поиска глобального минимакса

B.I)

В.2)

Здесь Х€ Е » » ^ ~ компакт евклидова пространства.

Пусть ^(Atf, /) - результат обработки алгоритмом Ад/ функции ^ , получаемый на основе значений frfUj) или

Обозначим через V fA^/, ^) точность решения алгоритмом задачи (B.I) или (В.2),

Тогда

V(A,,Fh«4> v(A„f) №

- показатель качества алгоритма Ад/ на некотором классе функций F , а величина

W (QtJ)-'<4 WA„,n отражает сложность класса функций г по отношению к некоторому классу алгоритмов Йд/ .

Согласно [39] будем называть алгоритм оптимальным, асимптотически оптимальным или оптимальным по порядку в классе Qл/ по отношению к классу функций F , если выполняются, соответственно, следующие соотношения:

V(Ah, F)-W(QH, F), шт.* где С - константа, не зависшая от Л/ .

Обозначим через VI £ информацию об исследуемой функции , полученную к t - му шагу алгоритма A N

В частности, для задачи (B.I) И для задачи (В.2) лу*

По аналогии с С 39 J введем Л/л/ - класс последовательных алгоритмов A n » вычисляющих на у - м шаге значения функции ^ соответственно в точках

-^ ГА; J т (Х},4, У/Л), •

Здесь ^ - некоторые функции, отображающие пространство своих аргументов в Xе Е или 0 е Е соответственно.

Выбор первых точек или (X/, £ $ произволен.

На последнем шаге производится вычисление результата

Алгоритм A n полностью задается совокупностью

Те алгоритш, для которых функции Jn-i тождественно равны константам, называются пассивными. Класс таких алгоритмов обозначим Рд/ • Пассивные алгоритмы применяются, к примеру, в тех случаях, когда все требуемые значения исследуемой функции могут быть вычислены одновременно. или

Пусть алгоритм AN выполнил t шагов. Зафиксируем полученную при этом информацию У1г . Тогда алгоритм А определяемый совокупностью или

Хен,#£+<)> У&-Н, выполняет завершающую часть вычислений алгоритма An « Введем обозначение

F (Ад) для сужения класса F с учетом полученной информации Л I . Так, для задачи (B.I) для задачи (В.2)

Согласно f 81,82 j назовем алгоритм /4N £ Q/v последовательно-оптимальным в классе по отношению к классу функций F , если для любого t-i'N-i соответствующий ему алгоритм An-i является оптимальным в классе по отношению к классу функций F[A. ё)» то есть выполняется условие v(AM.t)F(Ae))-W(Q^e>F(Ae}).

Введем в рассмотрение следующие классы функций: Си класс Функций ^ , удовлетворяющих условию

Липшица где^норма евклидова, L - константа. Сц [ 8) - класс функций ^ , удовлетворяющих условию

Хд, Х2 //rx#)-/rxf)/ 'UXi-XJU .

Здесь -константа, MWfftlOM IX Х=- fx'xf., x"jt

Л л Сг Я

CJB), С sl (Ю) - классы 5 раз дифференцируемых функций ^ , для которых функция обладает свойством fS) js; vъ, га i ft,?,<г<)-^fx,^ tji при условии II ^ II для Г и // ^ Ч4 = { для . Здесь ^ - вектор, ST - скалярная величина, L константа.

N. f ti

CjB)- /fm.yj, n г Л Л П i(x)^i\b => min ilx-Xiii

Каждая функция класса ^ «у t эй т может принимать значения, близкие к экстремуму, лишь в окрестностях некоторых t точек. Радиус этих окрестностей линейно уменьшается по мере приближения указанных значений к экстремуму. г/

3i Jsibt U-h\\±X>l, iWifcxtf.

Классы ( oC//, LsLVxi&J) являются пустшли, если

Перейдем к краткому изложению содержания работы. Глава I посвяшена построению и исследованию оптимальных в том или ином смысле^алгоритмов решения задачи (В.2). Так, для класса функций L l fin где fin , - кубы

С п Г к соответственно в пространствах С , с » построен алгоритм, оптимальный среди всех пассивных алгоритмов, использующих отдельные сетки в !ftn и Sf^ ( именно такие алгоритмы наиболее удобны в реализации). ^ Для класса функций

С I В) при условии 0-0* «Я* Гп /л Г *

Х/х С с tJy с L р показано, что асимптотически оптимальный алгоритм строится на основе оптимальных покрытий областей

Д , Ви Если же не накладывать на область TJ такого условия, то аналогичный результат получен для алгоритма, оптимального по порядку как среди пассивных, так и среди последовательных алгоритмов.

Способы построения оптимальных по порядку пассивных и последовательных алгоритмов приводятся также и для классов дифференцируемых функций u sl

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

O(NkN) , где /v - количество шагов. Для случая Л=1,2 получена точная оценка.

Введен класс негладких функций Q ( jQ ), для которого рассматриваемый алгоритм обладает линейной сходимостью, то есть /У-0/#2$,где £ - достигаемая точность, jfl считается фиксированным.

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

0{blk Ю , где /у - количество шагов, размерность пространства фиксирована. Данный алгоритм обладает линейной сходимостью на классе негладких функций C^'g(iD).

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

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

Некоторые из разработанных в диссертации алгоритмов реализованы в виде программ на языке ФОРТРАН, используются как функциональное наполнение в пакете прикладных программ для решения стандартных задач вычислительной математики, создаваемом в Институте кибернетики им. В.М.Глушкова АН УССР, сданы в Республиканский фонд алгоритмов и программ и вне,дрены в НПО "Ленинец".

По результатам диссертации опубликовано 7 работ. Основными являются работы [ 74-78 ] .

Результаты диссертации докладывались на I Всесоюзной школе-семинаре по дискретной оптимизации ( Судак, 1982 ), III Республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе ( Канев, 1982 ), Всесоюзной школе молодых ученых "Современные тенденции развития высокопроизводительных ЭВМ" ( Киев, 1982 ), Научном совете по комплексной проблеме "Кибернетика" ( Киев, 1979, 1981, 1984 ), Научно-исследовательском семинаре кафедры исследования операций МГУ ( Москва, 1984 ), а также на конференциях молодых ученых Института кибернетики АН УССР ( I98I-I984 г.).

Работа выполнена в отделе Теории вычислений Института кибернетики имени В.М.Глушкова АН УССР.

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

ЗАКЛЮЧЕНИЕ.

JTo полученным в диссертации результатам можно сделать следующие выводы:

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

2. Для S раз дифференцируемых функций, S -я производная которых удовлетворяет условию Липшица, оптимальными по порядку пассивными и последовательными алгоритмами поиска глобального минимакса являются алгоритмы, основанные на методах интерполяции. Погрешность этих методов должна составлять

О ( SjK N)b"), где W) - показатель качества некоторого оптимального покрытия /V точками области, в которой ищется минимакс. Здесь Л/ - количество вычислений значений функции.

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

О ( Ьг\ К ) арифметических операций» если размерность пространства фиксирована.

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

0(Ьп К) арифметических операций при фиксированной размерности пространства.

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

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

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

8. Для ряда предложенных алгоритмов получены оценки точности и построены соответствующие программы. Проведенные численные эксперименты подтверждают теоретические результаты.

1. Антуков В.Н., Поздеев А.А. Некоторые минимаксные задачи технологии и прочности конструкций. Изв. АН СССР, сер.Техн. киберн., 1982, В I, с. 47-55.

2. Артамкин В.Н. и др. Оптимальный режим остановки реактора. -Атомная энергия, 1964, т. 17, вып. 3, с. 189-193.

3. Архипова Т.А., Сергиенко И.В. Об условиях совпадения локального и глобального экстремумов в задачах оптимизации. -Кибернетика, 1975, Ji I, с. II3-II5.

4. Батишев Д.И. Поисковые методы оптимального проектирования. -М.: Сов. радио, 1975, 216 с.

5. Брусов B.C., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости. Ж. вычисл. матем. и ма-тематич. физ., 1971, т. II, № 2, с. 304-312.

6. Васильев Л.В., Тарасов В.Н. Об одном методе решения задач на минимакс. В кн.: Оптимизация. - Новосибирск, 1977, вып. 19 (36), с. 53-57.

7. Васильев Ф.П. Численные методы решения экстремальных задач.- М.: Наука, 1980. 520 с.

8. Вопросы теории и элементы программного обеспечения минимаксных задач. Под ред. Демьянова В.Ф., Малоземова В.Н. Л.: Изд-во ЛГУ, 1977. - 191 с.

9. Гамецкий А.Ф. Об оптимальности главной решетки первого типа Вороного среди решеток первого типа любого числа измерений.- Докл. АН СССР, 1963, т. 151, Н 3, с. 482-484.

10. Ганшин Г.С. Оптимальные пассивные алгоритмы вычислениянаибольшего значения функции на отрезке. S. вычисл. матем. и матем. физ.,-1977, т. 17, № 3, с. 562-571.

11. Ганшин Г.С. Вычисление наибольшего значения функций нескольких переменных. Кибернетика, 1983, № 2, с. 61-63.

12. Гермейер Ю.Б. Приближенное сведение с помощью штрафных функций задачи определения максимина к задаче определения максимума. S. вычисл. матем. и матем. физ., 1969, т. 9, & 3, с. 730-731.

13. Гирлин С.К., Ганшин Г.С. Оптимальные алгоритмы поиска наименьшего значения функции. Изв. вузов, сер. Математика, 1983, Л 3, с. 75-77.

14. Глушков В.М., Иванов В.В., Михалевич B.C., Сергиенко И.В., Стогний А.А. Резервы оптимизации вычислений. Препринт -77-67, Киев: Ин-т киберн., 1977, - 54 с.

15. Глушкова О.В., Гупал A.M. Численные методы минимизации функции максимума без вычисления градиентов. Кибернетика, 1980, Ш 5, с. I4I-I43.

16. Горелик В.А. Приближенное нахождение максимина с ограничениями, связывающими переменные. S. вычисл. матем. и матем. физ., 1972, В 2, с. 510-517.

17. Горелик В.А. Максиминные задачи на связанных множествах в банаховых пространствах. Кибернетика, 1983, № I, с.64-67.

18. Грачев Н.И., Евтушенко Ю.Г. Применение метода сингулярных возмущений для решения минимаксных задач. Доклады АН СССР, 1977, т. 233, № 3, с. 277-280.

19. Данилин Ю.М., Панин В.М., Пшеничный Б.Н. Модифицированный метод линеаризации. Кибернетика, 1982, № 5, с. 70-73,87.

20. Данилин Ю.М., Пиявский С.А. Об одном алгоритме отыскания абсолютного минимума. В кн.: Семинар. Теория оптимальных решений. Вып. 2.- Киев: йзд-во ИК АН УССР, 1967, с. 25-37.

21. Данилин Ю.М. Оценка эффективности одного алгоритма отыскания абсолютного минимума. Ж. вычисл. матем. и матем.физ., 1971, т. II, № 4, с. I026-I03I.

22. Данилин Ю.М., Панин В.М. О некоторых методах поиска седло-вых точек. Кибернетика, 1974, № 3, с. II9-I24.

23. Даугавет В.А., ГЛалоземов В.Н. Квадратичная скорость сходимости одного метода линеаризации для решения минимаксных задач. Ж. вычисл. матем. и матем. физ., 1981, т. 21,1. Л 4, с. 835-843.

24. Демьянов В.Ф. Ускорение сходимости при решении минимаксных задач. -Ж.вычисл.матем.и матем.физ.,1972,т.12,№1,с.51-60.

25. Демьянов В.Ф., Певный А.Б. Численные методы разыскания седловых точек. Ж. вычисл. матем. и матем. физ., 1972, т. 12, К 5, с. I099-II27.

26. Демьянов В.Ф., Шомесова В.К. Дифференцируемость по направлениям функции супремума. Вестник ЛГУ, 1978, I 7,с.15-20.

27. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. - 368 с.

28. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981. - 384 с.

29. Евтушенко Ю.Г. Численный метод поиска глобального экстремума. Ж. вычисл. матем. и матем. физ., 1972, т. 12, № 4, с. 888-896.

30. Евтушенко Ю.Г. Численный метод поиска глобального экстремума ( перебор на неравномерной сетке ). Ж. вычисл.матем. и матем. физ., 1971, т. II, Л 6, с. 1390-1403.

31. Евтушенко Ю.Г. Итеративные методы решения минимаксных задач. Ж. вычисл. матем. и матем. физ., 1974, т. 14, Ш 5, с. II38-II49.

32. Евтушенко Ю.Г. Методы поиска глобального экстремума. В кн.: Исследование операций. - М.: ВЦ АН СССР, 1974, вып.4, с. 39-68.

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

34. Емельянова Н.М. Оптимизация процессов поиска экстремума функций с использованием априорных данных. Автоматика и телемеханика, 1967, т. 18, Л 5, с. 160-165.

35. Ермольев Ю.М., Ляшко И.И., Михалевич B.C., Тюптя В.И. Математические методы исследования операций. Киев: Виша школа, 1979, - 312 с.

36. Жилинскас А.Г. Метод одномерной многоэкстремальной минимизации. -Изв. АН СССР, сер. Техн.киберн.,1976, № 4, с.71-74.

37. Зализняк Н.Ф., Лигун А.А. Об оптимальных стратегиях поиска глобального максимума функции. Ж. вычисл. матем. и матем. физ., 1978, т. 18, Л 2, с. 314-321.

38. Иванов В.В. Вопросы точности и эффективности вычислительных алгоритмов.(Обзор достижений в области кибернетики и вычислительной техники.Вып.2). Киев: ИК АН УССР,1969.- 135 с.

39. Иванов В.В. Об оптимальных алгоритмах минимизации функций некоторых классов. Кибернетика, 1972, Л 4, с. 81-94.

40. Иванов В.В., Людвиченко В.А. Об одном методе последовательной безусловной минимизации решения задач математического программирования. Кибернетика, 1977, Л 2, с. 1-8.

41. Иванов В.В., Остапенко В.В., Остапенко О.С. О минимизациип И п пфункций классов у^^ ы и а/д* В кн.: Оптимизациявычислений. Киев: ИК АН УССР, 1977, вып. 3, с. 71-79.

42. Иванов В.В., Людвиченко В.А., Михалевич B.C., Трубин В.А., Шор Н.З. Вопросы повышения эффективности алгоритмов минимизации функций и математического программирования . Препринт 79-59, Киев: Ин-т киберн., 1979, - 54 с.

43. Красношеков П.С., Морозов В.В., Федоров В.В. Проектирование технических систем многоцелевого назначения. Изв.АН СССР, сер. Техн. киберн., 1979, JE 42, с. 5-10.

44. Кузовкин А.И., Тихомиров В.М. О количестве вычислений для нахождения минимума выпуклой функции. Экономика и матем. методы, 1967, т. 3, « I, с. 95-103.

45. Ланнэ А.А., Малоземов В.Н. Оптимальный синтез одного класса нелинейных схем при гармонических воздействиях. Изв.

46. АН СССР, сер. Техн. кибернетика, 1982, № 4, с. 58-66.

47. Леонов В.В. Метод покрытий для отыскания глобального максимума функций от многих переменных. В кн.: Исследования по кибернетике. - М.: Сов. радио, 1970, с. 41-52.

48. Малков В.П., Угодчиков А.Г. Оптимизация упругих систем. -М.: Наука, 1981. 288 с.

49. Малоземова Л.К., Хургин И.М. Об одной задаче оптимизации, связанной с синтезом остронаправленных антенн. Из.АН СССР,сер. Техн. кибернетика, 1982, Л 4, с. 44-50.

50. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. I, II. Кибернетика, 1965, Л I, с. 45-55, № 2, с. 85-89.

51. Михалевич B.C., Сергиенко И.В., Шор Н.З. Исследования методов решения оптимизационных задач и их приложения. -Кибернетика,1981, Л 4, с. 89-113.

52. Моисеев Н.Н. Элементы теории оптимальных систем. М.: Наука, 1975, - 526 с.

53. Моцкус И.Б. Многоэкстремальные задачи в проектировании. -М.: Наука, 1967. 214 с.

54. Неймарк Ю.И., Стронгин Р.Г. Информационный подход к задаче поиска экстремума функций. Изв. АН СССР, сер. Техн. кибернетика, 1966, Л I, с. 17-26.

55. Немировский А.С., К}цин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979, - 384 с.

56. Немировский А.С., КЗдин Д.Б. Информационная сложность математического программирования. Изв. АН СССР, сер. Техн. ки-берн., 1983, Л I, с. 88-117.

57. Нурминский Е.А. Численные методы решения детерминированных и стохастических минимаксных задач. Киев: Наукова думка, 1979, - 157 с.

58. Основные направления экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года. М.: Политиздат, 1981. - 95 с.

59. Панин В.М. Метод линеаризации для задачи непрерывного минимакса. Кибернетика, 1981, Л 2, с. 75-78.

60. Певный А.Б. Скорость сходимости некоторых методов нахождения минимакса и седловых точек. Кибернетика, 1972, Л 4, с. 94-98.

61. Певный А.Б. Об оптимальных стратегиях поиска максимума функции с ограниченной старшей производной. S. вычисл. матем. и матем. физ., 1982, т. 22, Л 5, с. I06I-I066.

62. Пиявский С.А. Алгоритм отыскания абсолютного минимума функций.-В кн.: Семинар.Теория оптимальных решений,вып.2.-Киев:

63. Изд—во Ин-та киберн. АН УССР, 1967, с. 13-24.

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

65. Полякова 1.Н. Об одной задаче негладкой оптимизации. Кибернетика, 1982, № 2, с. II9-I22.

66. Пшеничный Б.Н. О необходимых условиях экстремума для негладких функций. Кибернетика, 1977, № 6, с. 92-96.

67. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980, - 320 с.

68. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.- М,: Наука, 1975, 320 с.

69. Роджерс К.А. Укладки и покрытия. М,: Мир, 1968, - 134 с.

70. Рышков С.С, Некоторые замечания о типах П мерных параллелоэдров и о плотности решетчатых покрытий пространства с пt равными шарами. Докл. АН СССР, 1965, т.162, В 2, с. 277-280.

71. Сергиенко И.В. Вопросы построения и использования математического обеспечения методов оптимизации. Препринт 79-38, Киев: Ин-т киберн. АН УССР, 1979, - 67 с.

72. Современное состояние теории исследования операций. М.: Наука, 1979, - 464 с.

73. Сорокина Т.Г., Сорокин И.М. Минимизация многоэкстремальных функций.- В кн.: Математические методы оптимизации и управления в сложных системах. Калинин, 1981, с. 60-68.

74. Стригуль О.И. Алгоритмы поиска экстремума и минимакса в некоторых классах функций.- Сборник трудов 1У конф.молодых ученых Ин-та киберн. АН УССР. Киев, 1983. Деп. в ВИНИТИ 5.03.1984, Ж 1290-84 Деп., с. 5-16.

75. Стригуль О.И. Быстрое преобразование. - В кн.: Оптимизация вычислений и технология программирования. - Киев: ИК АН УССР, 1978, с. 38-42.

76. Стригуль О.И. Программа быстрого вычисления £ ~ преобразования. РФАЛ, 1980, Л 5491.

77. Стригу ль О.И. Об одном вероятностном подходе к поиску глобального экстремума функций. В кн.: Программное обеспечение ЭВМ. - Киев.: ИК АН УССР, 1982, с. 40-48.

78. Стригуль О.И. Оптимальный по точности алгоритм отыскания глобального минимума в классе ДА ~ Сборник трудов III конф. молодых ученых ИК АН УССР. Киев, 1982.- Деп. в ВИНИТИ 26.01.1983, Л 417-83 Деп., с. 9-18.

79. Стригуль О.И. Оптимальные алгоритмы поиска минимакса для функций некоторых классов. Кибернетика, 1983, Л 5, с. 126.

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

81. Сухарев А.Г. Об оптимальных стратегиях поиска экстремума. -Ж. вычисл. матем. и матем. физ., 1971, Т„ II, Л 4, с. 910924.

82. Сухарев А.Г. Наилучшие стратегии последовательного поиска экстремума. Ж. вычисл. матем. и матем. физ., 1972, т. 12, Л I, с. 35-50.

83. Сухарев А.Г. Оптимальный поиск экстремума. М.: Изд-во Моск. ун-та, 1975, - ПО с.

84. Сухарев А.Г., Федоров В.В. Минимаксные задачи и минимаксные алгоритмы. М.: Изд-во Моск. ун-та, 1979. - 50 с.

85. Сухарев А.Г. Глобальный экстремум и методы его отыскания. -В кн.: Математические методы в исследовании операций. М.: Изд-во Моск. ун-та, 1981, с. 4-37.

86. Сухарев А.Г., Федоров В.В, Об оптимальном отыскании максимума функции минимума при связанных переменных. Вестник МГУ, сер. Вычисл. матем. и киберн., 1981, № I, с. 45-50.

87. Сухарев А.Г. Оптимальные и последовательно-оптимальные алгоритмы в задачах численного анализа. В кн.: Математические методы в исследовании операций. - М.: Изд-во Моск. ун-та, 1981, с. 54-68.

88. Тимонов Л.Н. Алгоритм поиска глобального экстремума. Изв. АН СССР, сер. Техн. киберн., 1977, № 3, с. 53-60.

89. Трауб Д.Дж., Вожьняковский X. Обшая теория оптимальных алгоритмов. М.: Мир, 1983. - 382 с.

90. Уайлд Д. Оптимальное проектирование. М.: Мир, 1981. - 272с.

91. Управление и оптимизация в экологических системах. Вопросы кибернетики, 1979, вып. 52, - III с,91» Федоренко Р.П. О минимизации негладких функций. Ж. вычисл. матем. и матем. физ., 1981, т. 21, I 3, с. 572-584,

92. Федоров В.В» Численные методы максимина. М.: Наука, 1979,- 278 с.

93. Чичинадзе В.К. Решение невыпуклых нелинейных задач оптимизации. М.: Наука, 1983, - 256 с.

94. Шор Н.З., Шабашова Л.П. О решении минимаксных задач методом обобщенного градиентного спуска с растяжением пространства.- Кибернетика, 1972, Л I, с, 82-88.

95. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 199 с.

96. ЙаЛ of Ckuiai. -mamf^hiinyt 49Ц2,vM. p. W-695.