Численные методы безусловной оптимизации с итеративным обучением и их применение

Актуальность работы. Релаксационные методы безусловной оптимизации (РМО) относятся к средствам численного моделирования (моделирования с применением ЭВМ) и используются при изучении явлении действительности. Па их основе конструируются более общие численные методы нелинейного программирования (НЛП). Распространенным приложением РМО являются оптимизационные задачи оценивания параметров математических моделей в схемах структурно-параметрического моделирования, т. е. при конструировании модели, когда требуется определип, такие ее структуру и параметры, которые обеспечивали бы наилучшее согласование с реальностью (см., например, [154]), к числу которых относятся рассматриваемые в работе актуальные задачи: прогнозирования свойств терморегулнрующих покрытии на основе результатов ускоренных испытанийопределения нестационарных законов горения пороха на основе манометрических испытаниипостроения исй-росе1евых приближений и выбора модели минимальной сложности при аппроксимации иейросетямиэкономико-математического анализа деятельности предприятииоценивания параметров и структуры поверхности при аппроксимации горногеологических объектов. Задачи структурно-параметрического моделирования сопряжены с многократным решением задач оптимизации с различными степенями и типами сложности (высокая степень вырожденностиотсутствие гладкости, выпуклостиалгоритмическое заданиевысокая размерность), что предполагает наличие спектра надежных, быстросходящихся, е высокой степенью универсальности РМО.

Итерация иекоюрого РМО включает расчет направления спуска, спуск и пересчет параметров метода на основе поступающей информации о характеристиках функции. Эффективные РМО основываются на некоторой конечной многошаговой стратегии {глобальной стратегии) минимизации определенного класса функций (например, квадратичных) и содержат параметры аппроксимативной модели функции и средства ее обучения. Схемы обучения в методах оптимизации различаются формой обучающей информации, на основе которой производится итерация алгоритма обучения, функционалом качества обучения, на основе которого строится алгоритм обучения, свойствами сходимости и свойствами устойчивости алгоритма обучения, т. е. его способностью сохранять сходимость в сложных, изменяющихся условиях. Например, обучение в методе сопряженных градиентов направлено па получение сопряженных векторов спуска. Схема обучения существенно опирается на сопряженность построенных прежде векторов спуска, что свидетельствует о неустойчивости алгоритма построения сопряженных векторов. Значительные отклонения от сопряженности ранее построенных векторов разрушают сходимосиь процесса обучения. С другой стороны, релаксационные субграднептшле методы [40, 82] также реализуют многошаговую стратегию обучения метода сопряженных градиентов, по в них дополнительно определена локальная цель обучения и алгоритм обучения, который обладает сходимостью независимо от сопряженности построенных ранее векторов [40, 82]. В алгоритмах этого тина большие возмущения не разрушают локальных свойств сходимости алгоритмов обучения.

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

В работах Я. З. Цынкипа [191, 192] применительно к различным областям знания развиты концепция и единообразный подход к решению проблем построения обучающихся систем и принципы построения алгоритмов обучения, как алгоритмов оптимизации заданного показателя качества. Как выясняется, этот подход эффективен и при создании алгоритмов обучения в РМО, что определяет актуальность его использования при конструировании обучающихся методов оптимизации. В диссертации отмеченный подход используется как унифицированное средство построения и анализа устойчивых алгоритмов обучения — итеративных алгоритмов изменения метрики пространства в схемах РМО, обладающих локальными и глобальными свойствами сходимости. Термин «изменение метрики пространства» используется для обозначения линейною преобразования пространства переменных задачи минимизации, предназначенного для уменьшения вытяпутости поверхностей равного уровня минимизируемой функции.

Развитие области численных методов безусловной оптимизации связано с именами отечественных ученых JI.B. Канторовича, H.H. Моисеева, В. Ф. Демьянова, Ю. Г. Евтушенко, Ю. М. Ермольева, B.C. Михалевича, В. Г. Кармапова, Б. Т. Поляка, Б. П. Пшеничного, Ю. М. Данилина, Е. Г. Голыптейпа, A.C. Пемпровского, Д. Б. Юдина, Ф. Г1. Васильева, П. З. Шора, 10.Е. Нестерова и многих других авторов. Релаксационные методы безусловной оптимизации, в зависимости от используемой информации о функции, можно подразделить па градиентные, субградиешные и прямого поиска.

Во многих задачах минимизации функция задается алгоритмически, а доступпои информацией о функции являются только значения функции. Методы, использующие только эту информацию, называют прямыми методами, методами поиска пли методами без вычисления производных. Прямые методы развивались в работах Ф. Л. Черноусько, В. Г. Карманова, Б.II. Пшеничного, О. П. Бурда кома, М. М. Потапома, Л. А. Растригнпа, Пауэлла, Брента, Бродлн и др. Им поснящена обширная литература (см., например [13, 16, 28, 60, 150, 154, 160−164, 168, 200]). Прямые методы можно подраздели п> на методы минимизации гладких и негладких функций.

Одно из слабых месг релаксационных методов прямого поиска — это отсутстние эффективных методов минимизации сложных негладких функций. К релаксационным методам минимизации негладких функций относят метод деформируемого многогранника (МД) (см., например, [28, 37, 154]) и методы случайного поиска (СП) [165, 166, 168], различные модификации которых исследовались в работах [3, 18, 50, 51, 54, 55, 60, 62, 85, 110, 169, 172]. Исследования С. И. Нестеровой и В. Л. Скокова [149] показали, что МД в состоянии решить лишь часть задач размерности 2 из предложенного множества многомерных негладких задач. Более предпочтительным для этих целей является метод случайного поиска (СГ1), поскольку он сходится линейно [60, 61] (В.Г. Карманов), а адаптация шага Л. А. Расстригина, Г. С. Тарасспко [169, 179] обеспечивает его сходимость па негладких функциях, по оп имеет медленную скорость сходимости па овражных функциях. Отмеченные обстоятельства определяют актуальность исследований диссертации по созданию алгоритмом обучения метрики в методах СП для ускорения их сходимости и расширения области решаемых ими гладких и негладких задач оптимизации.

В этой связи м качесте задач работы являются: разработка и исследование механизмов обучения в процедурах адаптации шага методов СП (т.е. формулировка функционала обучения и построение градиентного алгоритма обучения) и создание на этой основе алгоритмом пространственной адаптации шагаразработка и исследование устойчивых схем обучения метрики пространства в методах СП па оспоме квадратичной модели функции. В рамках этих задач в диссертации исследуется скорость сходимости методов СП без одномерного спуска, изучаются алгоритмы обучения процедур адаптации шага и способы опшмизации их параметров [52], обобщение которых приводит к алгоршму с пространственной адаптация шага, реализуемого с номощыо операторов растяжения пространства [195] в виде мафицы метрики [50]. В работе теоретически и численно исследуется подход изменения плотности испытаний в методах СП, который состоит в итерационном отыскании повой метрики пространства в предположении квадратичной модели функции [18, 51, 54, 66, 69, 86, 102]. В алгоритмах подобного рода вычисления функции используются в процессе оптимизации и в процессе построения сопряжённых векторов алгоритмами обучения, а процеес обучения обладает локальными свойствами сходимости. Отмеченные алгоритмы организованы таким образом, что они работоспособны и эффективны при минимизации сложных негладких функции, в том числе и кусочпо-липейпых [18]. Разработанные методы случайного поиска с изменением метрики охватывают спектр задач применимости алгоритмов Розепброка, деформируемого многогранника и его модификаций и превосходят их, но скорости сходимости при минимизации сложных гладких и негладких функции [18, 54, 55, 86, 102]. В заключение следует отметить, что алгоритмы СГ1 с изменением метрики пространства получены в результате использования формализма теории обучения па стадии их создания.

Известные эффективные методы минимизации гладких функций прямого поиска осиовывакнся либо па конечиоразпостпой аппроксимации метода Ныотоиа [28, 154] или квазиныотоновских методов (КИМ) [28, 154], либо используют схему минимизации вдоль лнпеипо-независимон системы векторов, с одновременным их преобразованием в сонряжеипые векторы относительно матрицы Гсссс [28, 154, 200, 201, 225]. Последнюю группу методов будем называть методами сопряженных направлений (МСП). Методы типа MCII основаны па использовании метода покоординатного спуска в меняющейся метрике (см., например, [12, 13, 60, 150, 154, 160−164, 201, 225]). По результатам вычислительного эксперимента можно выделить несколько наиболее эффективных алгоршмов: Пауэлла [225], Брента [200], Бродлн [201], Пшеничного [160] п Пшеничпою-Редковского [162−164]. Мы попытаемся оцепить локальные свойства сходимости схем построения сопряженных векторов в отмеченных алгоритмах, поскольку они обеспечивают эффективность обучения в условиях больших возмущений.

В методах Пшеничного и Пшеничного — Редковского схема минимизации и схема построения сопряженных векторов реализованы раздельно, т. е. не используется совмещение затрат вычислений функции па обучение и поиск минимума. Для проведения итерации требуется п2 вычислений функции. Для некоторых задач эта величина может оказаться излишне большой. В методе [164] вычисляется конечно разностная аппроксимация матрицы вторых производных в точке. Схемы преобразования векторов в методах [160, 162, 163] основаны па использовании порций информации о матрице вторых производных. Они существенно опираются на сопряженность уже построенных векторов, т. е. не являются устойчивыми к большим ошибкам па стадиях алгоритма, которые возникают вследствие разнесённости обучающей информации в пространстве минимизации и изменчивости свойств характеристик функции.

На одной итерации меюдов Пауэлла, Брента, Бродли затрачивается 3п вычислений функции. В алгоритмах Пауэлла и Брепта требуется точный одномерный спуск и приходится затрачивать значительные вычислительные усилия для борьбы с линейной зависимостью векторов [200], а их схемы обучения чрезмерно зависимы от степени сопряженности уже построенных векторов, т. е. их алгоритмы 'обучения неустойчивы к большим возмущениям па ранних итерациях. По эти причине эффективность эiих методов падает с ростом размерности. Метод Бродлп [201] - один из первых методов типа MCII, в котором используется устойчивая схема обучения и не требуется точный одномерный спуск. В этом методе используются онера юры вращений для преобразования пары смежных векторов спуска, на основе характеристик вторых производных в плоскости двух векторов. По его схема обучения пе позволяет построить за конечное число шагов систему сопряженных векторов, что существенно ограничивает возможности метода при росте размерности.

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

Методы сопряженных градиентов (МСГ) и квазипыотоноьекпе методы (КИМ) изучались в работах 10. Г. Евтушенко, В. Г. Кармапова, Б. Т. Поляка, Б. П. Пшеничного, Ю. М. Данилина, О. П. Бурдакова, Хестенса, Штифеля, Девидона, Флетчера, Рив-за, Пауэлла, Бройдена, Денниса, Шиабеля, Морэ и многих других авторов. Квазпныо-тоновекпе методы (КИМ) (ем., например, [28, 42, 43, 153, 154, 161, 203, 205, 209, 210, 212]) используют итерационную схему метода Пыотона, а необходимую для реализации матрицу Гессе (либо обратную к ней матрицу) восстанавливают на основе градиентов, получаемых в процессе работы алгоритма. При точном одномерном спуске задача минимизации квадратичной функции решается КИМ не более чем за п итераций, а векторы спуска являются сопряженными. Па первом этапе развития КИМ были разработаны формулы восстановления Гессиана или обрашой к нему матрицы [203, 205, 209, 210, 212]. В результате исследований выявлено значительное множество формул пересчета матриц в квазипыотоповскнх методах, проведен экспериментальный и теоретический анализ существующих методов (см., например, [28, 42] и подробный обзор [148]).

Экспериментально установлено, по не объяснено, что и КИМ наилучшие результаты имеет формула пересчета ВРСБ [42]. Оказывается, что. КИМ без точного одномерного спуска более эффективны, нежели с одномерным спуском (см., например [28, 42]). Предпринятые попытки повысить эффективность КИМ при неточном одномерном спуске, за счет явных или неявных схем последовательного построения сопряженных векторов (см., например, [42, 206]), не увенчались успехом [28, 42]. Такие методы оказались менее эффективными, нежели обычные КИМ с неточным одномерным спуском [42]. Одной из причин подобных неудач является изменчивость матрицы вторых производных в пространстве минимизации, т. е. несоответствие получаемой информации о матрице вторых производных некоторой фиксированной матрице, усиливаемое эффектом практически линейной зависимости векторов спуска, возникающей в силу протекания процесса минимизации на определенном отрезке итераций в некотором подпространстве малой размерности. По этим причинам процесс построения последовательности сопряженных векторов неустойчив, и, как следствие, процедуры восстановления матриц, построенные на этой основе не работоспособны.

Отметим некоторые из актуальных проблем КИМ методов, которые требуют своего разрешения. Сегодня отсутствую!: единообразные, обозримые и легко анализируемые способы вывода формул пересчета матриц п формализация алгоритмов обучения, которая устанавливает обозримую взаимосвязь сходимости алюрнгма обучения и алгоритма минимизации в КИМобъяснение преимуществ формулы пересчета ВРвБобъяснение причин высокой скорости сходимости КИМ при неточном одномерном спускеметоды КИМ с неточным одномерным спуском, конечные па квадратичных функциях, которые позволяют избежать неустойчивой процедуры построения полной системы сопряженных векторовоценки скорости сходимости и анализа ускоряющих свойств методов КИМ в области оптимизации в условиях отсутствия вторых производных. В этой связи является актуальным объяснение установленных экспериментально фактов и создание устойчивых к линейной зависимости векторов спуска алгоритмов обучения метрики, обладающих локальными и глобальными свойствами сходимости при неточном одномерном спуске.

Исследования диссертации направлены па изучение и разрешение этих проблем с привлечением формализма теории обучения. Алгоритмы теории обученияодношаговый (алгоритм Качмажа) и двухшаговын алгоритмы минимизации показателя качества обучения используются для построения одпошагового и двухшагового алгоритмов обучения в квазипыотоповскнх методах. В работе выявлена взаимосвязь одношагового алгоритма обучения, устанавливающего выполнимость одного обучающего соотношения, с формулами пересчета матриц ЭРР и ВРСБ (одношаговыми алгоритмами обучения матриц) [82, 87]. Полученная формализация алгоритмов обучения в случае квадратичных функций устанавливает единство направлении спуска алгоритма обучения п алгоритма минимизации [70, 71, 82, 87] и позволяет дать качественное обоснование преимуществ формулы ВРСБ. Применение на произвольных итерациях включений двухшаговых алгоритмом обучения матриц, т. е. алгоритмом устанавливающих выполнимость двух смежных квазиныотоновских обучающих соотношений, позволяет получить конечный па квадратичных функциях квазипыотопов-екпй метод при неточном одномерном спуске, устойчивый к линейной зависимости векторов спуска [70, 71, 82]. Эю означает возможность, но кусочкам сложить конечный алгоритм обучения матриц, причем, за счет выбора в процессе минимизации нар вектором существенно лнпснпо-пезависимых, процесс обучения становиться устойчивым. Оказывается, включения точного одномерного спуска на произвольных итерациях эквивалентны включению двух’шагового алгоритма обучения матриц, и приводят к конечному окончанию процесса минимизации па квадрашчпых функциях [70, 71, 82]. Поэтому, если в алгоритме одномерного спуска квазииыотоповского метода изредка находится почти точный минимум (например, вследствие использования кубической интерполяции), то такой метод будет иметь высокую скорость сходимости, что обьяспяет эффективность квазиныотоновских методов при неточном одномерном спуске. Кроме отмеченных задач в диссершции изучается глобальная (во всей области минимизации) скорость сходимости КИМ методов в случае. минимизации сильновыпуклых функций, градиент коюрых удовлетворяет условию Липшица, при условии отсутствия вторых производных. Полученные оценки свидетельствуют о наличии ускоряющих свойств у КИМ методов, подобных ускоряющим свойствам па всей области минимизации метода Пыоюна, где необходимо наличие вторых производных [67, 76, 82, 84].

Развитие численных меюдов негладкой оптимизации связано с именами ученых И. И. Астафьева, В. Г1. Булаюва, Ф. П. Васильева, Е. Г. Голыптепна, А. М. Гупала, В. Ф. Демьянова, 10. М. Ермольева, И. II. Еремина, Ю. А. Левина, В.II. Малоземова, А. С. Пемировского, Е. А. Пурмпиского, Ю. Е. Нестерова, Б. Т. Поляка, II. 3, Шора, Д. Б. Юдина, Лемарешаля, Вульфа, Келлн и многих других. Субграднептиые методы предназначены для минимизации недифферепцируемых функций (см., например, [29, 40,41,44, 58, 82, 130, 142, 154, 159, 195, 197, 198, 214, 216, 217]). В области негладкой оптимизации можно наблюдать большое разнообразие подходов построения методов минимизации (см., например, [29, 40, 58, 82, 130, 154, 195, 197]), об эффективности которых можно судить, опираясь па результаты численных исследований (см., например, [29, 147, 149, 175, 195, 218]). В [147, 149] сформирована методика многокритериального численного анализа методов негладкой оптимизации. Результаты числепного исследования С. И. Нестеровой и В. Л. Скокова [149] известных методов негладкой оптимизации: метода эллипсоидов (МЭ — A.C. Пемпровский, Д. Б. Юдин.) [146], r-алгоритма (MUI — II.3. Шор) [195, 196], метода ортогонального спуска (МОСВ.А. Скоков, М.Б. Щепакип) [177, 197], и разработанного в последние юды, метода уровней (МУ — Е. Г. Голынтейн, A.C. Пемпровский, 10.В. Нестеров) [29, 217], с одной стороны — демонстрируют высокую эффективное п. метода МУ относительно других методов по критерию числа вычислений функции и субградиента, а с другой — выявляют необходимость создания эффективных, но критерию времени счета, надежных методов негладкой оптимизации. Среди исследуемых методов реализации методов МЭ, MUI и МУ не используют каких либо дополнительных свойств функции, кроме выпуклости, т. е. являются методами общего назначения. Алгоритмы Mill и МУ справляются с задачами высокой размерности, хотя и не со всеми, а их совершенствование может привести к возможности решения задач порядка 1000 переменных, поскольку современные ЭВМ обладают значительным быстродействием и оперативном памятью. При прочих достоинствах, МШ среди исследуемых методов, единственным пригодный для решения иевыпуклых задач оптимизации. Сегодня существует проблема создания универсальных, падежных методов негладкой оптимизации, эффективных при решении гладких и негладких, в том числе и иевыпуклых, задач, конкурирующих, но свойствам скорости сходимости с методами, основанными на квадратичной, либо кусочно-линейной моделях функции, па классах функций, промежуточных отмеченным базовым классам.

Одна нз возможностей создания подобных методов заключается в совершенствовании класса релаксационных методов ссубфадиентиого типа (РСМ), к числу которых относятся методы Лемарешаля и Вульфа [216, 219, 231]. Методы этого класса, как и r-алюритм, пригодны для решения иевыпуклых гладких и негладких задач оптимизации, генерируют, как и предельный вариант r-алтрнтма, па квадратичных функциях сопряженные направления и находят минимум за конечное число итераций [15, 40, 195, 216, 219, 231], по существенно уступают в скорости сходимости г-алюрнтму. В методах Лемарешаля и Вульфа искомое направление спуска — кратчайший вектор множества, который вычисляется алгоритмами обучения. Недостатком методов Лемарешаля и Вульфа является низкая адаптивность содержащихся в них алгоритмов обучения, и необходимость частых обновлений с потерей накопленной информации. Происхождение r-алгорптма и его определяющие соотношения обучения не определены, а его существующие реализации на сложных задачах имеют либо низкую скорое ib сходимости, либо не позволяют их решить. В этой связи, для создания надежных и эффективных РСМ необходимо создание теории, назначение которой определить удобные определяющие соотношения обучения, разработать эффектнопые алгоритмы обучения и методы оптимизации на их основе, объяснить происхождение r-алгоритма, выявить его обучающие соотношения, ускоряющие свойства при конечных параметрах растяжения пространства и создать эффективные способы реализации РСМ.

Исследования диссертации направлены па решение поставленных актуальных задач с привлечением формализма теории обучения. В [72, 118] определяющее соотношение нахождения вектора спуска, как решения задачи нахождения ближайшего к пачалу координат вектора отделимого множества, заменено на решение задачи множества неравенств, которая, в свою очередь, представлена в виде задачи решения множества равенств с ошибками. Это дало возможность получить несколько алгоритмов обучения для решения неравенств и создать на нх основе эффективные релаксационные субграднеигпые методы [75, 80, 82, 83, 92−94, 109, 114−120, ]: метод сопряженных субградпептов [72, 82, 116, 117, 120], в основу которого положен одпоша-гошлм алгоритм обучения, и субградпепшые методы с растяжением пространства [80, 82, 118, 119], алгоритмы обучения которых созданы па основе алгоритма обучения с растяжением пространства. В частности, па основе алгоритма обучения с растяжением пространства разработано семейство матричных методов обучения [80, 82, 118], отдельным случаем которого япляс1ся алгоритм обучения, вычлененный из г-алгоритма. На этой основе разработано одноранговое семейство релаксационных суб-граднептных методов [80, 82], частым случаем которого является r-алгоритм. Обоснованы ускоряющие свойства r-алгоритма па сплыювыиуклых функциях при конечных значениях параметра растяжения пространства [65, 82], эквивалентные ускоряющим свойствам метода Пыотона в условиях отсутствия стабильности матрицы вторых нронзводпых.

Методы сопряженных градиентов [154] основаны па квадратичной модели минимизируемой функции. Вследствие малых затрат памяти они применимы для решения задач большой размерности, например, при решении задач аинрокснмацнн горпо-гсологических объектов (см., например, [11, 19−22, 97, 99−101, 103−106, 111−113, 121, 136, 155−157, 170, 182]) и нейросетевых приближений [27, 32, 34], где возникают задачи минимизации высокой размерности, связанные с оценкой неизвестных параметров моделей [19−21, 88, 90, 91, 97, 101, 103−106, 111−113, 121, 157, ]. В начале раздела отмечался неустойчивый характер алгоритмов обучеиня в методах сопряженных градиентов. В этой связи одна из целей работы — теоретическое и экспериментальное исследование методов типа сопряженных субградпептов, основанных па принципах обучения. Все отмеченные шлше методы сопряженных субградпептов, в том числе и проективный вариант r-алгоритма при предельных значениях параметра растяжения пространства, эквивалентны метод)' сопряженных градиентов на квадратичных функциях. В работах [72, 82, 116, 117, 120] изложен новый метод сопряженных субградн-ентов, который по затратам памяти эквивалентны методу сопряженных градиентов, а его алгоритм обучения сохраняет работоспособность п условиях потерн сопряженности пеночки построенных векторов спуска. Такие методы эффективны в условиях неточного одномерного спуска при минимизации гладких и негладких функции [82, 116].

Эффективность алгоритма и его полезность подтверждается многими компонентами численного исследования и приложениями. Одним из назначений создаваемых алгоритмов является их применение для реализации схем структурно-параметрического моделирования при решении отмеченных выше актуальных прикладных задач. Созданию конкретной системы построения модели предшествуют предварительные этапы формирования множества моделей, оценки качества моделей, подбора алгоритмов оценивания их параметров и т. д. Для их выполнения необходим комплекс падежных и проверенных алгоритмов оптимизации. Отсутствие падежного и эффективного алгоритма для идентификации модели может привести к неправильным выводам о ее свойствах н отбраковке, как не перспективной. Эти обстоятельства определяют акту альность создания программного комплекса РМО, численного исследования и сравнения с известными методами его алюрнтмов и определения областей их приложений. В рамках поставленной задачи создана модульная система программ, в которой реализованы разработанные алгоритмы. Алгоритмы системы исследованы численно, а на базе ее алгоритмов решен ряд прикладных задач построения и анализа математических моделей: прогнозирования свойств терморегулирующих покрытий па основе результатов ускоренных испытаний [137−141, 220, 221]- определения нестационарных законов горения пороха на основе манометрических испытаний [190]- оценивания неизвестных параметров моделей при аппроксимации горногеологических объектов [19−21, 97−101, 103−106, 111−113, 121, 157]- построения моделей по экспериментальной информации [4, 17, 24, 25, 96, 123, 125]- экономико-математического анализа данных [23, 79, 81]- построения иейросетевых приближений и выбора модели минимальной сложности при аппроксимации пейросетями [88−91, 95, 124].

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

Диссертационная работа выполнена в соответствии: с планами ПНР КемГУ по кафедре математической кибернетики 1991;2004 гг.- с грантом Российского фонда фундаментальных исследований (код проекта 04−03−33 121) — с программой «Университеты России» (код проекта УР.04.01.044) — договорной тематикой с угольными компаниями Кузбасса, ПТЦ «Кузбассуглстехнология» и с корпорацией «Кузбассинвест-уголь" — с Комплексной региональной программой научных исследовании и внедрения совместных работ СО АН СССР и Министерства угольной промышленности СССР, «Программа «Сибирь» «, раздел «Уголь Кузбасса», и приказами Министерства угольной промышленности СССР от 16.11.79, п № 315 от 24.06.80.

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

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

Зад, а ч 11 п ссл сд о ва 1111 п:

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

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

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

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

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

М етод I"! иссл сд о в, а 1111 й:

• методы теории адаптации и обучения для создания алгоритмов обучения;

• методы линейной алгебры, статистики, нелинейного программирования, функционального анализа для разработки и теоретического анализа алгоритмов оптимизации;

• тестирование и сравнение алгоритмов для численного анализа эффективности новых методов минимизации;

• методы анализа данных и закономерности изучаемых явлений для оценивания параметров н структуры математических моделей в разрабатываемых системах математического м одел нр о ва 11 ия.

Научная н практическая новизна работы заключается в том, что в пей:

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

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

3. Впервые формализм теории адаптации п её алгоритмы минимизации показателя качества обучения (одпошаговый и двухшаговый) применены в субгради-ситпых и квазипыотоповских методах для разработки новых алгоритмов обучения, обладающих локальными и глобальными свойствами сходимости. Одпошаговый алгоритм обучения в квазипыотоповских методах приводит к известным формулам преобразования матриц, а двухшаговыйобеспечивают конечную сходимость меюда при неточном одномерном спуске. Одпошаговый алгоритм обучения позволяет разработать новый метод решения неравенств н новый субградиептпый метод (РСМК) на его основе.

4. Разработаны новые алгоритмы обучения с растяжением пространства: алю-ритм для решения множества равенствалгоритм для решения неравенств на отделимых множествах. Па основе алгоритма решения неравенств разработан новый релаксационный субградиентный метод с растяжением пространства в направлении субградиепта (МРГ1) для решения сложных задач оптимизации.

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

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

7. Впервые разработан комплекс программ релаксационных методов (ПКРМО), значительная часть алгоритмов которою предназначена для решения сложных негладких задач оптимизации, в том числе п певыпуклых, что существенно расширяет возможности решения задач структурно-параметрического моделирования.

Основные положении, выносимые па защиту.

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

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

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

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

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

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

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

Достоверность научных положений и выводов подтверждается:

• строгими теоретическими оценками скорости сходимости созданных алгоритмов обучения;

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

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

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

Личный вклад автора coci опт:

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

• в разработке программного комплекса методов оптимизации с обучением и про-1раммпых средств определения параметров и структуры математических моделей в задачах математического моделирования;

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

Практическая значимость результатов работы.

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

Апробация работы. Основные положения диссертационной работы докладывались и были одобрены па:

• VIII н XII Всероссийских семинарах «Пейронпформатика и ее приложения» (Красноярск, 2000, 2004 гг.);

• Четверюй Международной школе-семинаре «Внутрпкамериые процессы, горение и газовая динамика дисперсных систем» (Санкт-Петербург, Россия, 2004г);

• Всероссийской конференции «Паука и практика: Диалоги нового века» (Апжеро-Суджепск, 2003, 2002 гг.) — Всероссийской научно-практической конференции «Паука и образование» (Белово, 2001, 2002 гг.);

• Международной школе-семипаре по методам оптимизации и их приложениям (Иркутск: СЭИ, 1989, 1995, 1998 гг.);

• Международной конференции по математическому моделированию (Якутск, 1994 г.) — десятом Всесоюзном симпозиуме «Системы программного обеспечения решения задач оптимального планирования» (Москва: АН СССР, ЦЭМИ, 1988 г.);

• I и II Всесоюзных семинарах «Информатика недр» (г. Кемерово, 1987 г., 1989 г.);

• VII Международном конгрессе, но маркшейдерскому делу (г. Ленинград, 1988 г.);

• VII региональной конференции по математике и механике (Томск, 1981 г.);

• Всесоюзном научно-техническом семинаре «Численные методы нелинейного программирования» (Харьков, 1979 г.);

• Всесоюзном совещании «Применение случайного поиска при решении прикладных задач» (Кемерово, 1979 г.);

• симпозиуме «Вероятиост шле вычислительные методы и средства» (Москва, 1978 г.) — Всесоюзном семинаре «Случайный поиск и системы автоматизированного проектирования в электронике» (Цахкадзор, 1978 г.);

• IV Всесоюзном совещании по статистическим методам в теории управления (Фрунзе, 1978 г.);

• Всесоюзной школе-семипаре по оптимизации динамических систем (Минск, 1977 г.).

Публикации. По теме диссертации опубликовано 72 научных работы, список которых приведен в конце авюреферата. По результатам исследований опубликованы работы [4, 17−21, 23−25, 49−55, 65−125, 137−141, 157, 190]. Основные результаты представлены в работах [54, 66, 77, 83, 82, 118, 137, 138, 139, 140, 141].

Структура работы. Диссертация состоит из введения, шести глав, заключения и приложения. Объем диссертации составляет 290 страниц машинописного текста, в том числе содержит 31 таблицу и 6 рисунков.

Список литературы

включает 231 наименование, приложения изложены на 8 страницах.

Основные результаты диссертации заключаются в следующем:

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

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

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

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

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

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

7. Разработан комплекс программ ГЖРМО созданных методов: прямого поиска, квазиньютоновскиих и субградиентных. Алгоритмы комплекса ПКРМО являются надежным и эффективным средством решения сложных задач безусловной оптимизации и реализации оптимизационного инструментария в задачах струкгурно-параметрического моделирования.

ЗАКЛЮЧЕНИЕ

.