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

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

Крутиков Владимир Николаевич

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени доктора технических наук

Томск 2005

Работа выполнена в ГОУ ВПО «Кемеровский государственный университет»

Официальные оппоненты: доктор технических наук, профессор Смагин Валерий Иванович

доктор технических наук, профессор Антамошкин Александр Николаевич;

доктор физико-математических наук, профессор Либерзон Марк Романович.

Ведущая организация: Институт вычислительного моделирования СО РАН (г. Красноярск).

Защита состоится 14 апреля 2005 г. в 14 час. 30 мин. на заседании диссертационного совета Д 212.267.08 при Томском государственном университете (634050, г. Томск, пр. Ленина, 36)

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

Ваш отзыв на автореферат (2 экз.), заверенный печатью, просьба направлять по адресу: 634050, г. Томск, пр. Ленина, 36, Томский государственный университет, ученому секретарю ТГУ.

Автореферат разослан марта 2005 г.

Ученый секретарь диссертационного совета, доктор технических наук

Общая характеристика работы

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

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

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

Развитие области численных методов безусловной оптимизации связано с именами отечественных ученых Л. В. Канторовича, Н. Н. Моисеева, В. Ф. Демьянова, Е. Г. Гольштейна, Ю. Г. Евтушенко, Ю. М. Ермольева, В. С. Михалевича, В.

Г. Карманова, Б. Т. Поляка, Б. Н. Пшеничного, Ю. М. Данилина, А. С. Немиров-ского, Д. Б. Юдина, Ф. П. Васильева, Н. 3. Шора, Ю. Е. Нестерова и многих других авторов. РМО, в зависимости от используемой информации о функции, можно подразделить на градиентные, субградиентные и прямого поиска.

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

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

Методы сопряженных градиентов и квазиньютоновские методы (КНМ) изучались в работах Ю. Г. Евтушенко, В. Г. Карманова, Б. Т. Поляка, Б. Н. Пшеничного, Ю. М. Данилина, О. П. Бурдакова, Хестенса, Штифеля, Девидона, Флет-чера, Ривза, Пауэлла, Бройдена, Денниса, Шнабеля, Морэ и многих других. В результате исследований выявлено значительное число формул пересчета матриц,

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

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

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

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

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

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

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

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

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

Задачи исследований:

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

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

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

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

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

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

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

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

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

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

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

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

метода Вульфа.

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

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

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

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

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

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

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

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

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

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

оптимизационного инструментария в задачах структурно-параметрического моделирования.

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и были одобрены на 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 научных работы, список которых приведен в конце автореферата.

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

Основное содержание работы

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

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

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

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

(1.1)

Алгоритмы минимизации при N=1 и N=2 в (1.1) будем называть соответственно одношаговым (алгоритм Качмажа) и двухшаговым алгоритмами обучения. Для реализации обучения в субградиентных методах, в результате модификации итерационного метода наименьших квадратов, разработан одношаговый алгоритм

обучения срастяжением пространства:

(1.2)

Отмеченные алгоритмы обеспечивают выполнение последнего обучающего соотношения ук = (гк,ск+]). На их основе в диссертации строятся эффективные методы минимизации.

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

Обоснование скорости сходимости класса методов минимизации вдоль векторов линейно независимой системы р, еЛ",/ = 1,2 ...,п:

х, =*,-1 + Р,Р„ Р, =аг§ттДх,_1+Рр,), ¡=\2...,п. (2.1)

Условие 2.1. Пусть / (х), х е 1С, сильновыпуклая функция с константой р, а ее градиент /'(*) удовлетворяет условию Липшица с константой L.

Обозначим Р - матрицу, столбцы которой />,, 1 = 1,...,п, |Л и М— минимальное и максимальное собственные значения матрицы - точку минимума функции. В теоремах 2.1, 2.2 приведены оценки скорости сходимости процесса (2.1) в зависимости от свойств системы векторов.

Теорема 2.1. Пусть / (х) удовлетворяет условию 2.1, для каждого цикла процесса (2.1) \\ р, ||=1, 1 = 1,...,п, матрица Р удовлетворяет ограничению

!!>.р.0>0, а точка хт получена применением т циклов процесса (2.1) Тогда для оценки скорости сходимости имеет место неравенство:

Дхт)-Дх*)<[Г(х0)-/(**)]ехр

2 2 тр ур

' 21? п3

(2.2)

Теорема 2.2. Пусть / (х) удовлетворяет условию 2.1, для каждого цикла процесса (21) ||/?,||=1, / = 1,...,п, матрица Р удовлетворяет ограничению а точка хт получена применением т циклов процесса (2.1). Тогда для оценки скорости сходимости имеет место неравенство:

/(хт)-Г(х*)1[/(х0)-/(х*)]ехр

трУ

2Пп

2„2п-1

(2.3)

Алгоритмы случайного поиска. Изучается скорость сходимости методов случайного поиска хк+/ = хк + Ик\к (к = 0,1,...) с фиксированным шагом Ик в точке хк (без одномерного спуска). Доказано, что при условии 2.1 и специальном выборе шага в точке такие методы имеют скорость сходимости, эквивалентную скорости сходимости метода скорейшего спуска, что определяет возможность создания эффективных алгоритмов случайного поиска при наличии эффективных про-

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

Минимум квадратичной функция f(x)=(х,Ах)/2 + (Ь,х) + с, где матрица А>0, т. е. симметричная и строго положительно определенная, х, belC , с - скаляр, может быть найден процессом (2.1) за цикл минимизации вдоль сопряженных относительно матрицы А векторов (А-ортогональных), т. е. при Р'АР =I. Для создания метода СП с варьированием метрики разработан процесс построения матрицы Р, удовлетворяющей соотношению РТАР = /:

Здесь £ 6 R" - вектор, равномерно распределенный на единичной сфере (РРЕС); А, Р, I - n x n матрицы, А>0. Обозначая через Wk k-ю реализацию случайной ортогональной системой векторов (СОСВ) и объединяя п шагов процесса (2.4) для ортогональных векторов из системы , получаем новый процесс:

Ро~1> Рк+1 ~~ Р/с

i-

a,k=l¿kP¡AP¿,k, * = 0.U...

МЗ. В (2.5) ограничим alk :alk =

(р>1).

Модифицируем процесс (2.5) следующим образом. Ml. Пусть в (2.5) вместо А используется А,к, причем:

I А-А,к \<Ак(к = 0,1,2..,1 = Гп)Л\У\\2 m<yTAy<\\Y\\2 М, ¿Д* с®.

к=0

М2. Положим Рк=1, если после (2.5): \d<¿t{Pk)\<,\l(zaM)nl1 =8Х, или | Рк Ц> (nza / m)°5 = S2 (а > 1), где г = 2пМ/т.

E;=pnA/5j, при a¡k>z¡, ег = mb]при а,к < z¡,

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

Теорема 2.3. Процесс (2.5), модифицированный в соответствии с М1-МЗ, задает последовательность {Рк} такую, что последовательность матриц

\вк = РкАРк | сходится к I п н.

Алгоритм случайного поиска с варьированием метрики (СПВМО). Задаем h0 >0, x0eR", 0<е<0.5, S¡IS2,£¡Í е2 >0. Пусть Р0 = /, xk_¡, hk_h Pk_, уже получены, k-e приближение имеет следующий вид.

1. hkl : = hk_¡, Pkl: = Pt_¡, xk¡: = xk_¡.

Для i = 1,n выполняем n.2-4.

2. aa =argminf{xk¡-ash), где sb = Pkfch, f,,. - вектор из Wk. xh+l = xh .

3. аь я -ь), где / = /(хк, + \/],\<с1Ч„] = ],21,

111,-12, 12,-Уз,) 11

ограничим аи по формуле из МЗ.

5. Положить Рк=Рк^,. Хк = хк^„ й4=й*„+/.

6. Если )!<<?, или || Рк\>Зг,то Гк = /.

7. Положить к = к+1, перейти к выполнению п.1.

Свойства сходимости алгоритма отражены в теоремах 2.4 и 2.5. Теорема 2.4. Пусть / (х) удовлетворяет условию 2.1. Тогда последовательность хк, построенная алгоритмом СПВМО, сходится к точке минимума х*, для оценки сходимости имеют место неравенства

Г(хк)-/(х*)^[/(х0)-Г(х*)]ехр{-с,к), 1> с,> 0.

Теорема 2.5. Пусть/ (х) удовлетворяет условию 2.1 и трижды непрерывно дифференцируема, собственные значения матрицы /"(х *) принадлежатотрез-ку [т, М]. Пусть Ь^Ьноырнцявыбраны, как в выражениях из М2-М3. То-

гда при достаточно больших к хк -ьх, п.н. сверхлинейно.

На основе СПВМО получены реализации СПВМ1, СПВМ2, СПВМ3. Вычисления в алгоритмах организованы так, что они работоспособны при минимизации кусочно-линейных функций. Результаты численного исследования свидетельствуют, что алгоритмы СПВМ1 и СПВМ2 превосходят по скорости методы Розенброка, Хука-Дживса, деформируемого многогранника и обычные методы СП, а методы СПВМ2, СПВМ3 эффективны при минимизации сложных негладких задач. Основное назначение разработанных методов СП - это решение задач минимизации, где нет возможности вычислить градиент или субградиент и нельзя применить для решения по условиям гладкости некоторый метод сопряженных направлений.

Метод минимизации без вычисления производных на основе рассредоточенной схемы А-ортогонализации (МСН). Матрицу Р назовем А-нормированной, если (р^Ар,) = ], I = /,...,«. Для А-нормированной матрицы Р определим преобразование в виде:

где (Р) = аЦ =(р,, ApJ, Ар})(р,,'ар,)]° \ а щ выбирается по правилу:

Матрица также А-нормированная. Формула (2.7) задает шаг неполной

релаксации алгоритма обучения (2.6) в случае подозрительно больших значениях (аЦ)2. Лемма 2.1 определяет свойство сходимости процесса (2.6) при ограниченной релаксации (2.7), что следует из ограниченности модуля определителя мат-

риц при его росте (2.8).

Лемма 2.1. Преобразование (2 6)увеличивает значение определителя:

Множество различных пар {(¡ь]^, ¡к >У*}> расположенных в некотором порядке, общее число которых равно М=п(п-1)/2), будем называть полной последовательностью различных пар. Множество полных последовательностей различных пар, таких, что {(¡ь1)„(]ъ)к-1)}¿{Оь]*).....0Ш)> к=1,...,п(п-1)/2, будем обозначать Ьр. Если пары берутся из £ сЬр , то применительно к процессу

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

Глобальные свойства сходимости процесса (2.6) определяются ниже.

Теорема 2.6. Пусть матрица Р А-нормирована и \Р'\*0. Тогда за конечное число итераций N процесса (2.9) для пар из последовательности пар {(?/с ¿л ^л •••} будет получена матрица Р^*', столбцы которой сопряженные векторы.

Рассмотрим последовательность пар индексов, удобную для получения алгоритма минимизации. Обозначим £/=(7, ...и/ Е1=(1,1+1,...,п, 1,...,1-1), 1=2,...,п.

Элементы Тц последовательности Т(=(1, 1-1, /+7, 1-2, 1+2,...) получим поочередным выбором первого и последнего элементов из Б). Последовательность пар П/ = ([1,1 -1],[1 -1,1+1 ],[1 +1,1-2],...) получим расстановкой скобок в Т|. Перестановкой индексов в парах П( получим последовательность П/, где первый индекс в паре больше второго.

Теорема 2.7. Пусть матрица Р А-нормирована и \Р'\*0 Тогда за конечное число итераций Ыпроцесса (2.9) для пар (¡^ь) из /77/, 77^, ...,77„, /7/, II2, ...,ПК...} будет получена матрица Р^*', столбцы которой сопряженные векторы.

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

Теорема 2.8. Пусть в алгоритме МСН производится точный одномерный спуск Тогда, если минимизируемая функция квадратичная с невырожденной матрицей Гессе, то ее минимум будет найден за конечное число итераций

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

Теорема 2.9. Пусть/(х) удовлетворяет условию 2.1. Тогда для последовательности Хь к=1, 2,..., генерируемой алгоритмом МСН при точном одномерном спуске, имеет место линейная скорость сходимости

Теорема 2.10. Пусть / (х) удовлетворяет условию 2.1, дважды непрерывно

дифференцируема, а ее матрица вторых производных/"(х) удовлетворяет уело-виям: т\\г\\2<(гЛх)2)^М\\2\\2 УгеРГ, \\Г(х)-ГЬ)\\* Ф-у\\ ^х.уеГС (Ь>0).

Тогда последовательность {я*}, генерируемая алгоритмом МСН при точном одномерном спуске, сходится точке к х* сверхлинейно.

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

В третьей главе: на основе формализма теории обучения дается анализ схем обучения матриц в квазиньютоновских методах (КНМ); обосновываются их ускоряющие свойства; разрабатывается КНМ с двухшаговым алгоритмом обучения матриц.

Вывод и анализ на основе формализма теории обучения симметричных формул пересчета матриц. В схеме КНМ метода:

((33..12))

рассчитываются матрицы Вк или Нк - приближения матриц А или Н* = А~'. Формулы перерасчета обозначим или Например,

формула БРС8: Нф^-Н-*^^" ^ + (3-3)

На квадратичных функциях выполняются соотношения:

у = АЬх или Дх=Н*у, где у = У/(х + Ах)-'У/(х), Н* = А-'. (3-4)

Векторные равенства (3.4) образуют п обучающих соотношений для строк матриц (в силу симметрии - и для столбцов), для каждой из которых можно применить алгоритмы обучения, основанные на минимизации показателя качества (1.1). Доказано, что одношаговый алгоритм обучения для минимизации показателя (1.1) при N=1 в форме невязок гк+, = Ш(гк)гк, где гк=ск-с, №(г) = ¡-гг1 /(г,г), применяемый к строкам, либо последовательно к строкам и столбцам матриц, приводит к известным формулам пересчета матриц, записанным в форме невязок:

1) - второй метод Бройдена;

2) - первый метод Бройдена;

3) - формула Дж. Гринстадта;

4) - симметричная формула Пауэлла. Формулы БР08 и ББР выводятся применением преобразований 3) и 4) в

системе координат с единичной матрицей Гессе квадратичной функции. Анализ процессов обучения в методах БР08 и ББР позволяет сделать вывод о более вы-

сокой степени ортогональности векторов спуска и обучения матриц в методе BFGS, что объясняет его преимущества.

Ускоряющие свойства квазиньютоновских методов. Обозначим х* -точку минимума функции, р значение функции в ней. В системе координат х = Рх ггооцесс (3.1)-(3.2) эквивалентен минимизации функции $?(•*) = /(л), которая удовлетворяет условию 2.1 с константами рр и 1р

Определим преобразование х = Ух, где V— невырожденная матрица, такое, что ру/!у>рр/Ьр для всякой невырожденной (п х п) - матрицы Р.

Теорема 3.1. Пусть функция /(х) удовлетворяет условию 2.1, Но - симметричная и строго положительно определенная (пхп) - матрица. Тогда для последовательности /(хк), к=0,1,2,..., заданной процессом (3.1)-(3.3), при точном одномерном спуске, имеет место оценка:

пМ пру

/к-ГМ/о-/*)ехр

Р3у

54Ц,

к-3-

т

(3.5)

где т и М - соответственно минимальное и максимальное собственные значения матрицы Р'^АЦ'Р'1.

Оценка (3.5) получена без предположения существования вторых производных функции и свидетельствует о наличии ускоряющих свойств КНМ в области минимизации в случае, когда существует преобразование координат, обеспечивающее неравенство ру/1%-»р/Ь, где отношение р/£ определяет скорость сходимости метода скорейшего спуска.

Квазиньютоновский метод на основе двухшагового алгоритма обучения (КНМР). Определим условия на выбор шага ук в (3.1):

Условие 3.1. (3.6)

Рб(а,1), (3.7)

причем выбирается ук = 1, если для него выполнены условия (3.8), (3.9).

Алгоритм КНМР основан на преобразованиях матриц в (3.2) для пары векторов , предварительно преобразованных в сопряженные:

Преобразования (3.8), (3.9) определяют итерацию двухшагового алгоритма обучения в квазиньютоновских методах.

Алгоритм КНМР.

1. Задать матрицу Н0 >0, ее(0,1/6). Положить к = О, ц0-0. Вычислить /0' = /'(х0).

2. Найти новое приближение минимума = хк -УкНк/к, где шаг у* удовлетворяет условию 3.1. Положить qм = qk■^rl.

3. Вычислить = /'(хк),£як = хк+1~хк, ук = -/к. Если ¡/¿+| ||=0, то

останов.

4. Если ды>2, и | ) | /[(Ах*.,, ук_, )(Лх, < 1-е2, (ЗЛО) то перейти на п. 5, иначе положить Нм = Н(Нк,Ьхк,ук) и перейти на п. б.

5. Положить = 0 и провести преобразования (3.8), (3.9).

6. Положить к = к +1. Если выполнен критерий останова, то закончить вычисления, иначе перейти на п. 2.

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

1. Размерность подпространства минимизации сокращается по мере роста размерности подпространства выполнения квазиньютоновского соотношения пкс, причем пм <п + 1-пкс.

2. Размерность подпространства выполнения квазиньютоновского соотношения в процессе работы КНМ не убывает.

3. Отдельные итерации с точным одномерным спуском повышают на единицу размерность подпространства квазиньютоновского соотношения.

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

Следствия отмеченных свойств изложены в теоремах 3.2,3.3. Теорема 3.2. Для решения задачи минимизации квадратичной функции за конечное число итераций процесса (3.1)-(3.3), при условии 3.1 на одномерный спуск, достаточно не более (п-1) — го включения пар последовательных итераций {(3.1)-(3.3)} и {(3.1), (3.8), (3.9)}, причем решение, если оно не получено ранее, обязательно будет получено на следующей итерации после (п-1) —го включения.

Теорема 3.3. Для решения задачи минимизации квадратичной функции за конечное число итераций процесса(ЗА) - (3.3), при условии 3.1 на одномерный спуск, достаточно не более (п-1)-го включения итераций {(3.1) -(3.3)} с точным одномерным спуском, причем решение, если оно не получено ранее, обязательно будет получено на второй итерации после (п-1) -го включения.

Результаты теорем 3.2, 3.3 свидетельствуют о возможности применения приемов увеличения размерности подпространства выполнения КНС в произвольные моменты, что позволяет разработать устойчивые к ошибкам методы.

В § 3.6 дается обоснование квазиньютоновского метода на основе двухша-говых схем обучения матриц.

Теорема 3.4. Алгоритм КИМР с параметром е - 0 позволяет решить задачу минимизации квадратичной функции с невырожденной матрицей вторых производных за число итераций, не превосходящее [2(п-1)+1].

Теорема 3.5. Пусть алгоритмом КИМР решается задача минимизации квадратичной функции с невырожденной матрицей вторых производных. Тогда решение будет найдено за конечное число итераций.

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

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

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

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

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

направление выбирают из множества S(G) решений неравенств:

(s,g)>0, VgeG, гдеG=St/(*,). (4/1)

В диссертации направления спуска в РСМ выбирается как одно из решений неравенств (4.1). Если множество GcR" принадлежит некоторой гиперплоскости, тогда решение системы неравенств можно получить, решая равенства (s,g) = 1 (VgeG) методами теории обучения. В работе для этих целей используются одношаговый и двухшаговый алгоритмы минимизации показателя (1.1) и одношаговый алгоритм обучения с растяжением пространства. Для построения новых методов негладкой минимизации на их основе создано несколько методов решения неравенств, обладающих конечной сходимостью на отделимых множествах, изложение которых приводится ниже. К числу подобных методов принадлежит и одноранговое семейство РСМ, частным случаем которого является известный эвристический г - алгоритм Н.З.Шора.

Одношаговый алгоритм обучения с растяжением пространства (ОАОР) - это алгоритм обучения (1.2), записанный в виде:

М^У = (4.2)

(Я„н*,) ' "' а2' Сг„Я|Л)

Задача 4.1. По данным е Л"ей1 ,¡ = 0,1,2,. ., процесса У! =(s',g|) + ¿;l,

где - ошибка, найти вектор неизвестных параметров л* еЯ".

Предположение 4.1. Пусть для ^ей" векторы gl и значения уI = + задачи 4.1 удовлетворяют соотношениям:

Я/ = (^.^/¡(ЬАХёЛ)*Ч2>0, где Д, = ^ (4.3)

Л? <1,где X, (4.4)

Сформулируем свойства сходимости процесса (4.2).

Теорема 4.1. Пусть последовательность {л,} -результат процесса (4.2), для »' = 0,1,2,—, 50еЯ",Н0=1. Тогда, если выполнены условия (4.3),

то имеет место оценка:

4 ¿>1. 1 1 qn(a -1)

os/s/-i

(4.5)

Получим оценку скорости сходимости одношагового алгоритма обучения (ОАО):

на основе которого будет получен метод решения неравенств (ОАОН) и метод минимизации (РСМК).

Теорема 4.2. Пусть последовательность {.$,} -результат процесса (4.6)

решения задачи 4.1, для 1 = 0,1,2,еЛ". Тогда, если выполнены усло-

вия (4 3), (4.4), имеет место оценка' (Д^Д^^До.ДдХ! — д2(1 -Я1))'.

Результаты теорем 4.1, 4.2 устанавливают преимущество в скорости сходимости алгоритма ОАОР сравнительно с алгоритмом ОАО.

Одношаговый алгоритм обучения с растяжением пространства для решения множества неравенств (ОАОРН) является распространением алгоритма ОАОР на задачу решения неравенств (4.1). Обозначим: т|(С?) - вектор минимальной длины из С, Рс ^РС^ЩпГОЯЬ RG = R(G) = max\\g\\, Ио=т/(7Ур0,

RssRs(G) = max(\aa,g),

get?

r(G) = pa/Rs, v(G) = pc/RG,

Ss(x) = {zGRn\l\z-x{\zS}.

Предположение 4.2. Множество G выпуклое, замкнутое, ограниченное (Rq <<х>) и удовлетворяет условию отделимости, то есть ра>0.

Следующая теорема позволяет свести задачу нахождения j б 5(G) кзадаче 4.1 и обосновать применимость алгоритмов ОАО и ОАОР для ее решения.

Теорема 43. Пусть для множества G выполнено предположение 4.2 и известно некоторое приближение s, eS&o(s') искомого вектора s' =(%/рс- Тогда

для текущего приближения S, вектор g, eG и величина y,=J в задаче 4.1 с искомым вектором s* удовлетворяютусловиям(4.3), (4.4):

1) {есщ)<0, причемсправедлтьюценшч2 Я2 =(l-pG/ÄS)J;

2) если($,, g,)< 1, причем справедливы оценки q2=0, Я2=1.

Алгоритм ОАОРНдля решения неравенств.

1. Положить i=0. Задать s0eR", а>1, Н0=1,

2. Найти g, eG удовлетворяющий условию {s,,g,)i 0, если такого вектора не существует, то s, 6 5(G), закончить работу алгоритма.

3. Получить новое приближение где

V(s,g, H) = s + I!g{\ - (s,g)V(g,Hg), H(g,H) = Я - (1 - IIa2)HggTHT Kg,Hg).

4. Положить i=i+L Перейти на пункт 2.

Приведем оценку скорости сходимости алгоритма ОАОРН. Теорема 4.4. Пусть множество G удовлетворяет предположению 4.2, а последовательность {.$,} генерируется алгоритмом ОАОРН при условии:

1<а2 <I/(1-/?G/ÄS)2 =1/Я2. Тогда вектор steS{G) будет получен за конечное число итераций, причем пока st iS(G): а) для величин qt и Xt выполнены условия

(4.3), (4.4) с параметрами д2и Травными: q2 =1/||Д0||2/?3 , Я2 =(l-/>G /Ä$)2,' б)

для сходимости s, имеет место оценка (4.5).

РСМсрастяжением пространства в направлении субградиента (МРП)

основан на методе решения неравенств ОАОРН. Алгоритм МРП (rg).

1. Задать начальное приближение На = /, еЛ", =0, целые

k = i=q0=Q, параметр а >\. Вычислить g0sdf{x0). Задать последовательности Ej>0, crj>0,j-0, 1,....

2. Если g,=0, то закончить вычисления.

3. Если (gl,H,gi)<tl или (g^l^g^/fg^gj^al, то произвести обновление

4. Получить новое приближение:

5. Вычислить новое приближение: х-y,i1+/, У, = arg mm f(x, -ysl+/).

г

б Вычислить субградиент gm е^Хц-i), исходя изусловия (gm, 5,»i)<0.

7. Положить /=;+./_ перейти на пункт 2.

Свойства сходимости алгоритма определены в теоремах 4.5-4.7. Обозначим: d(x) = p(df(x)), х, - точку минимума функции, х' - предельные точки последовательности {zk = хЧк }"_], генерируемой алгоритмом rg . Определим свойства сходимости алгоритма в окрестность минимума.

Теорема 4.5. Пусть функция f(x) строго выпукла на R", множество

D(xg) ограничено, на D(x0) при хфх,, r(df(x))2.r0>0, параметр а алгоритма rg удовлетворяет соотношению: l<a = ï/(l-ra)<l/(l-r0). Тогда, если то

На основе теоремы 4.5 формулируются условия сходимости алгоритма. Теорема 4.6. Пусть выполнены предположения теоремы 4 5, и функция f(x) на множестве £>(хв), х*х* удовлетворяет условию v(Sf(x))tv0>0. Тогда, если е £ = 0, ak =£ 0<v0/4, то любая предельная точка последовательности {zявляется точкой минимума на R".

Теорема 4.7. Пусть выполнены предположения теоремы 4.5. Тогда, если Ek~*0, ак —>0, то любая предельная точка последовательности {гк} являет-

ся точкой минимума на

Связь алгоритма МРП с методом сопряженных градиентов (Mil). Теорема 4.8. Пусть функция f(x) квадратичная и в МРП Н0 = I,a Í.I.' Тогда, если начальные точки алгоритмов МРП и МСГ совпадают, то, при n>k>0, до тех пор, пока gk*0, оба процесса генерируют совпадающие последовательные приближения.

Метод решения неравенств на основе одношагового алгоритма обучения (ОАОН):

/. Положить i = 0.Задать s0eR".

9.Haümung$ieG уел o(s¡ л и такого вектора не существует, то S, 6 5(G), закончить работу алгоритма.

10. Получить sl+l по формуле (1.1) при y¡ =1.' J,+| =s, + g, ÍL_Í£ií£l2_

1. Положить i = i + l. Перейти на пункт 2.

Дадим оценку скорости сходимости s, —ï s'.

Теорема 4.9. Пусть множество Gудовлетворяет предположению 4.2. Тогда для оценки скорости сходимости к точке последовательности генерируемой алгоритмом А1 до момента останова, справедливо соотношение:

а при некотором значении удовлетворяющем неравенству будет получен вектор

Алгоритм минимизации (РСМК) на основе алгоритма ОАОН: Задать начальное приближение x0bR", целые k = i = 0.

1. Положить

2. Задать гк, тк.

1. Вычислить g¡£Óf(x,) такой,что (g,,s,)¿ О.Если g/ = 0, тоостанов.

2. Найти новое приближение направления спуска: sl+/ = slJrg,[l-(sl,g,)]/(gl,gl)

3. Вычислить новое приближение критерия: £(+| = Е, + (g,,g,)4.

4. Вычислить: = х,-ТЛ+/» fi=arSminf(xi~ysi-i)-

7. Положить i = i +1. Если l/< ек или i — qк >тто перейти на пункт 1.

8. Перейти на пункт 3.

Определим свойства сходимости алгоритма в окрестность минимума. Теорема 4.10. Пусть функция /(х) строго выпукла на множество Z)(jc0) ограничено и параметры sk, mk, задаваемые в пункте 2 алгоритма РСМК, фиксированы: zk = E0>0, mk=M0. Тогда, если х'- предельная точка последовательности {Xqk)t=i' генерируемой алгоритмом РСМК, то d(x')£maxfE0,R(x0)/} = d0, где R(x0)= max max ||v||. В частности,

если M0 ä R2(xg)Eg2, mo d(x) й E„.

На основе теоремы 4.10 формулируются условия сходимости алгоритма. Теорема 4.11. Пусть функция f{x) строго выпукла, множество О(х0)ог-раничено и zk 0, mk -> оо. Тогда любая предельная точка последовательности (xqk}> генерируемая алгоритмом РСМК, является точкой минимума функции f(x)Ha R".

Связь алгоритмов РСМК и сопряженных градиентов. Теорема 4.13. Пустьмножество D(x0) = {x^RP\f(x)<, f(x0)} ограничено ифункция f(x) строго выпукла и непрерывно дифференцируема в

FT. Тогда, если

начальные точки алгоритмов РСМК и МСГ совпадают, то при riikhO оба процесса генерируют совпадающиепоследовательныеприближения.

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

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

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

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

Метод сопряженных субградиентов с растяжением пространства (AWM(a)). Для множества в и вектора g введем подмножество и(Р>ё) - {" 6 О | «) ^ 0}. Для векторов g и и определим вектор:

где > = Р = ~(УЯ)/(У.У)- (5.1)

Если иеЩв^), то принадлежит оболочке векторов g и и.

Из алгоритма минимизации Ф. Вульфа выделим метод решения неравенств (ЛШ): g0 еб. Найти gl =go(g|-|.щ), покаЗи, еЩв^,.,), 1-0,1,...

Теорема 5.1 Пусть множество О удовлетворяет предположению 4.2. Тогда алгоритм Л Шнаходит решение gleS(G) неравенств (4.1) за конечное число итераций, которое не превосходит минимального целого г, удовлетворяющего неравенству: I > 1п{р2/Я!)/1п{1-р2 /(р2 + Я2)).

Алгоритм обучения (4.2) применим к модифицированной системе равенств

полученной из равенств и распространим на решение неравенств. В результате придем к алгоритму решения неравенств (АЯ(а)), содержащемуся в схеме г-алгоритма:

(5.2)

т,,г

Н,и = Н,-(1-1/а2)

ч,у,у, и

(У,.4,У,)

(5.3)

Теорема 5.2. Пусть множество О удовлетворяет предположению 4.2 и Я$=Р(}.Тогда при а2>1 алгоритм АЩа) находит решение ^ неравенств(4.1) за конечное число итераций.

Алгоритм решения неравенств на основе выбора ближайшего к началу координат вектора в текущей метрике (АУУ(а)) получим,объединяяалгорит-мы А\¥ и АЯ(а):

3. Положить 1=0. Задать а>1, Яо = ¡.Выбрать произвольно goeG.

4. Найти и1 ей, такой, что (Н^^^йО.Если такого вектора не существует, то закончить работу алгоритма.

5. Вычислить У|=u¡-glu получить приближение матрицы по формуле (5.3):

6. Выбрать 8м = Л,,«/), где (¿"(^.у,) = + Р,у„ р, =

7. Положить ¡=¡+1. Перейти на пункт 2.

Теорема 5.3. Пусть множество О удовлетворяет предположению 4.2 и =Ро. Тогда при а2 >1 алгоритм А1У(а) находит решение неравенств (4.1) за

конечное число итераций.

Метод сопряженных субградиентов с растяжением пространства

A WM(a) получим, используя алгоритм решения неравенств AW(a),:

1. Задать начальное приближение //„ = /, х0 € R", параметра >1. Вычислить go^Sf(xg) .Если go~0, то Хо точкаминимума, закончить вычисления.

2. Для i -0,1,2, ..., выполнить действия:

2.2.Найтисубградиент е 8f{xt+x) такой,что i() < 0.

2.3. Если i не кратно т, то вычислить: yi-^^-g,, gltl = gw(g,,y,), и выполнить(5.3),впротивномслучае: Hq — I, g,+\ = m,+j.

Теорема 5.4 На квадратичной функции алгоритм AWM(a), a^I, и метод сопряженных градиентов, при равенстве их начальных точек и циклов обновления т^п, генерируют одинаковые приближения минимума для i <т.

Одноранговое семейство релаксационных субградиентных методов с растяжением пространства (ARWM(a, Д)). Обозначим А(а) - общий алгоритм решения неравенств, получаемый из А W(a) заме не ной пункта 4: {4. Выбрать произвольно g1+i е G }.

Обозначим: 0 = 0(г) = [(l-rG)/(l + rG)]2 и Q = Q(ct,0) = 1 + (а2-1)0 . В следующей теореме дается обоснование сходимости алгоритма А(а).

Теорема 5.5. Пусть множество G удовлетворяет предположению 4.2 и в <1/п. Тогдапри 1<а2 ¿1/лб алгоритм А(а) находит решение неравенств (4.1) за конечное число итераций, которое не превосходит минимального целого i,

удовлетворяющегонеравенству

^ 4i/?g(a2 -\)Q' лр^а2""-!)'

Введем зависимости: 6(са) = (1-а)2/(1+ а)2, а(в) = (1-в'/2 )/(1+ в1/2 ).

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

Теорема 5.6. Пусть множество О удовлетворяет предположению 4.2, 0(га)<-1/п и задано некоторое в*, удовлетворяющеенеравенству: 0(гд) < 0* < 1/и.

Тогда при 1<а2£1/я0*, е£е*=РсД/2, где Л= гд —г*, г*= <о(в*), алгоритм А(а) находит решение неравенств (4.1) на множестве 5((С)за конечное число итераций, которое не превосходит минимального целого i, удовлетворяющего неравенству: ¡^'(ь'-'тъуг.щаг-'тъъг,

пра (а2'/п-1) т,Ла2"п-1)

Алгоритмы решения неравенств АЩа), AW(а) отличаются от А(а) конкретизацией пункта 4. В АЯ(а) он имеет следующий вид: {4. Зад е -мейство алгоритмов решения неравенств АШУ((х,А) получим из алгоритма А(а), заменив в нем пункт 4:

{4. Задать А^" (е„и,) + (1-А)-и, (0<А<1)}. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства А1?№М(а,Д) на основе алгоритм А1Ш(а,Д):

1. Задать Нд = 1, х0 еЯ", целые /'=0, т0=О, А'-период обновления, а>1, 0<Л <1. Bычucлumьg0 е8/(х0). Если go=0, то хо точка минимума, останов.

2. ^,+1 = л,г/=агвтт/(лг,-у5,+1).

г

3. Вычислить и,едЦхо1), (и„ S|+\)< 0. Если и,=0, то *,+/ - точка минимума, останов.

4. Если I - т, >И, то: /и,+/ = gl+^ = ы,, Я,+1 = I; перейти на пункт 7.

5. Вычислить: у,=и,-ё„ £,+1 = g, + ■ Если =0, то: произвести обновление { /я,+/ = /, gl+l = и,, =1}и перейти на пункт 7.

6. Положить т,-ц = т,, вычислить:

„тит

gnl=A-glrl+i+[l-A)-ui, Н„

1+1 = Я,-( ,-1/а2)^^-.

(.У„Н,у,)

7. Положить /=/+/, перейти на пункт 2.

Обозначим (ц , к=0,1.....- индексы I, при которых происходит обновление в

пунктах 4 или 5. Обозначим - точки х,к, х, - точку минимума функции, х'

дельные точки последовательности

Теорема 5.7. Пусть множество Р(х0) ограничено, функция /(х) строго выпуклая на Я", и на О(хо) при х*х., ее характеристики удовлетворяют соотношениям: %(г(с%'(х)))'£,§0<1/п, у(д[(х})^уд>0, где вц и \>о некоторые константы. Пусть задано некоторое в*, такое, что 0О <6*<1/и. Тогда при параметрах алгоритма минимизации АЯШМ(а, Л)'. 1 < аг 2 1/яб *, N >2 К(\>о,в*), где N(^0*) - минимальное целое i, удовлетворяющее неравенству

1>

36i(a2-l)[Q(aß*)]'

, любая предельная точка последовательности {zk} яв-

nvi(a""-l)

ляется точкой минимума.

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

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

Xk4=xk+Ykrh П = -Щ Ш yk = arg min f(xk+yrk), (5.4)

26

нкукуткнтк

Ук=ГЬш)~Пч\ Дб(ОД). (5.5)

(Нкук,ук)'

где Хо - заданная начальная точка, Нд > 0. Обозначим через х* - точку минимума фуиюи\\\/(х),/. =/(х*), и =/*-/„ /*'=/Т-**)-

В системе координат х - Рх процесс (5.4)-(5.5) эквивалентен минимизации функции = /{р~'х)= /(х), которая удовлетворяет условию 2.1 с константами рр , Ьр. Определим преобразование х = Ух, где V - невырожденная матрица, такое, что ру/Цг*рр/Ьр для всякой невырожденной (пхп) - матрицы Р. В следующей теореме обосновываются ускоряющие свойства г-алгоритма.

Теорема 5.8. Пусть функцияудовлетворяет условию А. Тогда для по-следовательности¿/У, к = 0,1,2,..., заданной процессом (5.4) - (5.5) с матрицей Но, удовлетворяющей условию т0й(Н0г,2)/(г,г)<.Мд УгеЛ", имеет место оценка:

^¡¿\х0ехр

{-I

I Чг

к1п(1 + а) | 1п(т/М)1 па <

(5.6)

где т и М- соответственно минимальное и максимальное собственные значения гТ

матрицы

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

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

Программный комплекс ПКРМО включает прямые методы (СПО (§ 2.4) -алгоритм случайного поиска с оптимизацией параметров адаптации шага; СПМ (§ 2.4) - алгоритм СП с пространственной адаптацией шага; СПВМ1, СПВМ2, СПВМЗ (§ 2.5) - методы СП с варьированием метрики; МСН (§ 2.6) - метод минимизации без вычисления производных на основе рассредоточенной схемы А-ортогонализации), градиентные методы (КНМ -квазиньютоновский метод минимизации с формулой BFGS; КНМР (§ 3.6) - квазиньютоновский метод минимизации на основе двухшагового алгоритма обучения; МСГ - метод сопряженных градиентов; МСГП - модификация метода сопряженных градиентов, предложенная Б. Т. Поляком), субградиентные методы (РСМК (гл. 4) - метод сопряженных субградиентов для минимизации негладких функций высокой размерности; МРП (§4.8) - метод с растяжением пространства в направлении субградиента;

АЕ^Мом(и, Д) (гл. 5) - одноранговое семейство релаксационных субградиентных методов; Гом(к) (гл. 5) - г-алгоритм, который является частным случаем семейства алгоритмов А1^М(а, Д) при Д=0).

Среди представленных методов для решения задач минимизации большой размерности применимы методы сопряженных градиентов (МСГ, МСГП) и метод сопряженных субградиентов РСМК. Отмеченные методы не всегда справляются с задачами в случае высокой степени вырожденности функции. С целью испытания возможностей методов с изменением метрики пространства на сложных задачах высокой размерности были решены известные тестовые задачи при размерности п=1000 квазиньютоновскими (КНМ, КИМР) и субградиентными (МРП, Г0М(а)) методами. Во всех методах в каждой точке функция и субградиент вычислялись одновременно. В табл. 6.1 приведено количество затраченных методом вычислений функции и субградиента, которое соответствует моменту выполнения условия

Таблица 6.1.

Функции (п= 1 ООО) Точность е гом(а) МРП КНМ КИМР

/М 10-'° 921 1688 3059 1792

/2(*) 10° 2179 541 2116 1234

Ш 10"4 40738 18088 - -

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

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

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

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

важную практическую задачу, которая не поддается решению аналитическими методами. Поэтому возникает необходимость проведения ускоренных испытаний в условиях повышенной интенсивности облучения с последующей их интерпретацией с помощью методов математического моделирования. В этой связи возникает необходимость разработки комплекса математических моделей (ММ) оптической деградации ТРП, учитывающих возможные закономерности деградации широкого класса ТРП. Изменение коэффициента поглощения а8 необходимо представить в виде модели Д, где х - вектор неизвестных параметров, /,У,Г - соответственно время, интенсивность и температура облучения.

В результате анализа существующих моделей прогнозирования оптической деградации ТРП КЛА, экспериментальных наблюдений за образованием радиационных дефектов и центрами оптического поглощения и многолетнего опыта разработки математических моделей для конкретных покрытий сформировано множество альтернативных моделей для описания изменений КПСР ТРП, каждая из моделей которого включает в себя определенное число составляющих двух видов ¡ = 1, ..6, /-!,...4.

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

Модели вида (6.1) представляют множество для поиска эффективной модели для прогнозирования.

Схема долгосрочного прогнозирования изменений КПСР ТРП космических летательных аппаратов (КЛА) по данным лабораторных испытаний. Задача долгосрочного прогнозирования состоит в предсказании значения при заданном постоянном режиме облучения для заданного времени облучения. Комплекс ММ может быть использован для прогнозирования оптической деградации ТРП на реальных орбитах. Для этого необходимо проведение наземных испытаний и определение изменений коэффициента поглощения а$ в условиях, имитирующих условия орбиты, расчет коэффициентов комплекса математических моделей, выбор «наилучшей» модели. Коэффициенты моделей х определяем по методу наименьших квадратов, посредством минимизации суммы квадратов:

(6.2)

где т - количество экспериментальных данных по измерению Аая х - вектор неизвестных параметров. При этом должны выполняться ограничения:

где п - количество неизвестных параметров модели; Даот - предельное значение Аа3 при 1—><хг, а,0 - исходное значение интегральной отражательной способности; Ь - время облучения, Ла^х,^, Т) - изменение значения КПСР ТРП при облучении за время I. Значение а„ -а5а+Ддот = t соответствует КПСР абсолютно черного

тела.

На основе алгоритмов из ПКРМО были разработаны методы оценки параметров моделей (6.1) посредством минимизации (6.2) при ограничениях (6.3), по данным наземных испытаний. Построение моделей осуществляется в два этапа. На первом этапе строится полное множество моделей (6.1). После этого вычисляется осредненное значение верхнего предела как некоторое среднее пределов полученных моделей. На втором этапе верхний предел всех моделей фиксируется в виде ограничения 2) из (6.3), с использованием осредненного предела, и заново строится полное множество моделей. Полученное множество моделей анализируется.

Критериев оценки качества моделей может быть несколько. От их количества и от того, насколько полно они отражают процессы деградации ТРП, будет зависеть точность выбора модели и точность долгосрочного прогноза. В качестве критериев использовались: критерий минимума остаточной дисперсии; критерий сравнения моделей для отдельных режимов, где худшим условиям функционирования ТРП должны соответствовать и большие изменения КПСР ТРП; критерий правдоподобности предельного значения Да5 при . Для прогнозирования оптической деградации ТРП из множества моделей по критериям дискриминации выбираем наиболее оптимальную для данного ТРП и условий эксплуатации модель.

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

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

В диссертации обосновывается эффективность применения для оценивания параметров нейросетевых моделей релаксационных субградиентных методов. В § 6.7 при решении задачи построения искусственной нейронной сети минимальной сложности используются идеи негладкой регуляризации для целей построения рангового упорядочения переменных по их значимости и последующего удаления малозначимых. Здесь возникают серии невыпуклых негладких задач оптимизации, которые в состоянии решать развитые в работе субградиентные методы. В результате исследований §§ 6,6, 6.1 выявлено, что субградиентные методы МРП, и РСМК являются эффективным средством решения задач оценивания параметров нейросетевых приближений и построения нейронной сети минимальной сложности.

Изучение систем многопродуктового производства на основании матема-

тических моделей приводит к необходимости решения задач нелинейного программирования высокой размерности. В § 6.8 сформулированы условия оптимальности плана в задаче оптимизации прибыли многопродуктового производства, дана их интерпретация и разработан метод декомпозиции по ограничениям получения оптимального решения, который заключается в решении двойственной задачи негладкой оптимизации малой размерности с последующим получением оптимального решения прямой. Задачи негладкой оптимизации схем декомпозиции могут быть решены субградиентными методами программного комплекса ПКРМО.

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

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

Основные результаты диссертации:

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

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

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

жествах и субградиентный метод (РСМК) на его основе.

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

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

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

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

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

1. Крутиков, В. Н. Релаксационный метод минимизации с растяжением пространства в направлении субградиента / В. Н. Крутиков, Т. В. Петрова // Экономика и мат. методы. - 2003. - Т. 39. - Вып. 1. - С 106-119.

2. Крутиков, В. Н. О скорости сходимости методов минимизации вдоль векторов линейно-независимой системы / В. Н. Крутиков // Журнал вычислительной математики и метематической физики. -1983. -Т.23, №1. - С.218-220.

3. Крутиков, В. Н. Статистический метод вычисления сопряженных направлений /

B. В. Захаров, В. Н. Крутиков // Кибернетика (СССР: Киев). - 1984. - №6. - С.95-100.

4. Крутиков, В. Н. Разработка комплекса математических моделей оптической деградации терморегулирующих покрытий космических летательных аппаратов / М. М. Михайлов, В. Н. Крутиков // Перспективные материалы. - 1997. - № 1. -

C.21-27.

5. Крутиков, В. Н. Прогнозирование оптической деградации терморегулирующих покрытий космических летательных аппаратов по результатам наземных испытаний / М. М. Михайлов, В. Н. Крутиков // Перспективные материалы. - 1997. - № 2.-С.18-25.

6. Крутиков, В Н. «Спецтема 1» / М. М. Михайлов, М. И.Дворецкий, Л. Г. Косицин, В. Н. Крутиков, Г. Г. Савельев, Б. И Кузнецов // Вопросы оборонной техники. -Серия 10, выпуск 151. Ленинград: ГОИ им. Вавилова. -1980.

7. Крутиков, В. Н. «Спецтема 2» / М. М. Михайлов, М. И.Дворецкий, Л. Г. Косицин, В. Н. Крутиков // Вопросы оборонной техники. - Серия 10, выпуск 151. Ленинград: ГОИ им. Вавилова. -1980.

8. Крутиков, В. Н. Алгоритм случайного поиска с адаптивной метрикой («SPM») / В. Н. Крутиков // Свидетельство об официальной регистрации программ № 2003612566. - М: РОСПАТЕНТ. Зарегистрировано в реестре программ для ЭВМ. - Москва, 25 ноября 2003г. - 2003.

9. Крутиков, В. Н. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента («RSM») / В. Н. Крутиков // Свидетельство об официальной регистрации программ № 2003612567. - М: РОСПАТЕНТ. Зарегистрировано в реестре программ для ЭВМ. - Москва, 25 ноября 2003 г. - 2003.

10.Крутиков, В. Н. Релаксационные методы безусловной оптимизации, основанные на принципах обучения: Учебное пособие / В. Н. Крутиков. - ГОУ ВПО «Кемеровский государственный университет». - Кемерово: Кузбассвузиздат. -2004. -171с.

11.Крутиков, В. Н. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства / В. Н. Крутиков // Электронный журнал "Исследовано в России". - 209. -2003. -С 2450-2459. http: // zhurnal.ape.relarn.ru / articles /2003/209.pdf.

12.Крутиков, В. Н. Метод сопряженных субградиентов с растяжением пространства / В. Н. Крутиков, Д. В. Арышев // Электронный журнал "Исследовано в России" -208. -2003. -С 2439-2449. -http: / zhurnal.ape.relarn.ru / articles / 2003 / 208.pdf.

13.Крутиков, В. Н. Реализация алгоритмов однорангового семейства субградиентных методов / В. Н. Крутиков, Д. В. Арышев //Электронный журнал "Исследовано в России" - 43. -2004. -С. 464-473. http: // zhurnal.ape.relarn.ru / articles /2004 / 043.pdf.

14.Krutikov, V.N. Predicting the optical degradation of thermoregulating coatings of flying space systems on the basis of the results of tests carried out on earth / M. M. Mik-hailov and V.N. Krutikov // Journal of Advanced Materials (Cambridge interscience publishing). -1996. -v.3. -№2. -pp. 106-113.

15. Krutikov, V.N. Method of examining the thermal adjusting coatings of space apparatus / M. M. Mikhailov and V.N. Krutikov // Journal ofAdvanced Materials (Cambridge interscience publishing). -1996. -v.3.-№l. -pp. 21-28.

16. Крутиков, В. Н. Метод определения коэффициента поглощения терморегули-руюшцх покрытий в зависимости от времени, интенсивности излучения и температуры // М. М. Михайлов, М. И.Дворецкий, Л. Г. Косицин, В. Н. Крутиков // Космическая технология и материаловедение. - М.: Наука, 1982. - С. 95-100 .

17.Крутиков, В. Н. Методы минимизации на основе частной модели субградиентных множеств / В. Н. Крутиков // Методы оптимизации и их приложения / Труды 11-й Международной Байкальской школы-семинара. - Иркутск. 1998. - Том 1. -С.101-104.

18.Крутиков, В. Н. Исследование субградиентных методов обучения нейронных сетей / В. Н. Крутиков, Д. В. Арышев // Вестник КемГУ. - Кемерово. -2004. -№1 (17).-С. 119-124.

19. Крутиков, В. Н. Алгоритм последовательного отсева неинформативных переменных линейной модели / В. Н. Крутиков, Д. В. Арышев // Вестник КемГУ. - Ке-

мерово .-2004 .-№1 (17).-С. 124-129.

20. Крутиков, В. Н. Новый релаксационный субградиентный метод с изменением метрики / В. Н. Крутиков // Вестник КемГУ. - Кемерово. -2001. - Вып. 4. - С. 16-22.

21. Крутиков, В. Н. Новый метод решения задач минимизации большой размерности / В. Н. Крутиков, Т. В. Петрова // Вестник КемГУ. - Кемерово. -2001. - Вып. 4. -С.65-71.

22. Крутиков, В. Н. Новый метод решения неравенств с растяжением пространства и субградиентные методы на его основе / В. Н. Крутиков, Н. Ю. Комаров // Вестник КемГУ. - Кемерово. - 2001. - №3(7). - С. 73-78.

23.Крутиков, В. Н. Субградиентный метод с неточным одномерным спуском / В. Н. Крутиков, Т. В. Петрова // Вестник КемГУ. - Кемерово. - 2001. -№3(7). -С. 8591.

24. Крутиков, В. Н. Алгоритмы распознавания складок поверхности / В. Н. Крутиков, Е. Н. Глушко // Вестник КемГУ. - Кемерово. - 2001. -Вып. 4. - С. 60-65.

25. Крутиков, В. Н. Методы построения линейной функции полезности сложных объектов / В. Н. Крутиков, Я. С Ворошилов // Вестник КемГУ. - Кемерово. -2001. Вып. 4. - С. 71-76.

26. Крутиков, В. Н. Оптимизационные задачи моделирования межотраслевого комплекса и методы их решения / В. Н. Крутиков // Вестник КемГУ. -Кемерово. -2001. -№3(7).- С. 20-25.

27. Крутиков, В. Н. Метод восстановления метрики по упорядоченным расстояниям /

B. Н. Крутиков, Н. Б. Пушкина // Вестник КемГУ. - Кемерово. - 2001. -Вып. 4. -

C. 35-39.

28. Крутиков, В. Н. Абсолютные оценки скорости сходимости г-алгоритма и метода Ньютона / В. Н. Крутиков // Якутск: Матем. заметки ЯГУ. - 1997. - Т.4. - № 1. -С. 38-50.

29. Крутиков, В. Н. Новый релаксационный метод недифференцируемой минимизации / В. Н. Крутиков, Т. В. Петрова // Мат. заметки ЯГУ. - 2001. - Т.8. Вып. 1. -С.50-60.

30.Крутиков, В. Н. Анализ динамики сходимости квазиньютоновских методов / В. Н. Крутиков // Матем. заметки ЯГУ. - Якутск. - 1994. - Т.1. Вып. 2. - С. 40 - 48.

31. Крутиков, В. Н. Квазиньютоновские методы на основе рассредоточенных способов восстановления Гессиана / В. Н. Крутиков // Мат. заметки ЯГУ. - 2000. -Т.7. -Вып. 2.-С. 62-81.

32.Крутиков, В. Н. Быстросходящийся метод решения задач безусловной минимизации, не требующий вычисления производных / В. Н. Крутиков // Газовая динамика. - Томск: ТГУ. - 1987. - С.85-99.

33. Крутиков, В. Н. Методы обнаружения тектонических нарушений / В. Н. Крутиков, Е. Н. Глушко // ТЭК и ресурсы Кузбасса: Вестник ТЭК Кузбасса. - 2001. -№3.-С. 22-23.

34. Крутиков, В. Н. Использование математического моделирования в задачах оптимизации межотраслевых связей в структуре регионального ТЭК / В. Н. Крутиков, В. Н. Вылегжанин // ТЭК и ресурсы Кузбасса. - 2001. - №4. - С.62-64.

35.Крутиков, В. Н. Алгоритмы аппроксимации поверхности, заданной значениями в узлах нерегулярной сетки / В. Н. Крутиков, С. Л. Злобина, Н. Ф. Бувальцев // Ма-

тем. заметки. ЯГУ. -1995. -Т.2, № 2. -С. 110-120.

36.Крутиков, В. Н. Повышение эффективности алгоритмов случайного поиска посредством включения в схему экстраполяции / В. Н. Крутиков, В. В. Захаров // Проблемы случайного поиска. - Рига: Зинатне. -1978. - Вып.7. - С. 207-213.

37.Крутиков, В. Н. Теоретическое и экспериментальное исследование скорости сходимости двух алгоритмов случайного поиска / В. Н. Крутиков, В. В. Захаров // Вопросы разработки территориальных автоматизированных систем управления. -Кемерово: КемГУ. -1984. - С. 65-70.

38. Крутиков, В. Н. Сравнение оценок скорости сходимости случайного покоординатного и циклического покоординатного спусков / В. Н. Крутиков // Применения случайного поиска при решении прикладных задач. - Кемерово: КемГУ. -1981.-С.71-75.

39.Крутиков, В. Н. Новые адаптивные алгоритмы случайного поиска и численные эксперименты с ними / В. Н. Крутиков, В. В. Захаров // Оптимизация динамических систем. - Минск: изд.-во БГУ. -1978. - С. 51-55 .

40. Крутиков, В. Н. Релаксационный субградиентный метод недифференцируемой минимизации с растяжением пространства / В. Н. Крутиков, Т. В. Петрова // Деп. в ВИНИТИ. - М. - 2000. - №3222-В00. - 28с.

41.Крутиков, В. Н. Методы распознавания разрывных форм пластовых месторождений / В. Н. Крутиков, Е. Н. Глушко // Деп. в ВИНИТИ. - 2000. - 191-В00. -31с.

42. Крутиков, В. Н. Методы распознавания складчатых форм пластовых месторождений / В. Н. Крутиков, Е. Н. Глушко // Деп. в ВИНИТИ. - 2000. - 190-В00. -38с.

43.Крутиков, В. Н. Модифицированный алгоритм Качмажа для решения задачи построения разделяющей поверхности / В. Н. Крутиков, Т. В. Петрова // Деп. в ВИНИТИ. - М. -1999. - 3940-В99. -11с.

44. Крутиков, В. Н. Алгоритм Качмажа с изменением метрики / В. Н. Крутиков, Т. В. Петрова // Деп. в ВИНИТИ. - М. -1999. - 3941-В99. - 9с.

45.Крутиков, В. Н. Экспериментальная оценка множества методов аппроксимации поверхности / В. Н. Крутиков, В. П. Потапов, Е. Н. Глушко // Деп. в ВИНИТИ. -М.-1999.-1401-В99.-13с.

46.Крутиков, В. Н. Новый метод аппроксимации поверхности / В. Н. Крутиков, Е. Н. Глушко // Деп. в ВИНИТИ. - М. -1999. - 1400-В99. -11с.

47. Крутиков, В. Н. Метод негладкой регуляризации в задачах контрастирования / В. Н. Крутиков, Д. В. Арышев // Нейроинформатика и ее приложения: материалы XII Всероссийского семинара 1-3 октября 2004г. - Красноярск: ИВМ СО РАН, 2004.-С.80-81.

48.Крутиков, В. Н. Об определении нестационарных законов горения пороха на основе манометрических испытаний / Ю. П. Хоменко, В. М. Широков, В. Н. Крутиков // Материалы четвертой Международной школы-семинара: Внутрикамерные процессы, горение и газовая динамика дисперсных систем: сборник материалов. Том 1. - Санкт-Петербург, Россия, 2004г. - С 86-90.

49. Крутиков, В. Н. Релаксационные субградиентные методы на основе двухшаговых алгоритмов обучения / В. Н. Крутиков, Д. В. Арышев // Материалы Всероссийской научно-практической конференции «Наука и практика: диалоги нового века». - Часть 3. Информационные технологии и математическое моделирование. -

Томск: Твердыня. - 2003. - С. 125-127.

50. Крутиков, В. Н. Алгоритм построения нейронной сети с минимальным числом нейронов / В. Н. Крутиков, Д. В. Арышев // Наука и образование: Материалы Всероссийской научной конференции (20-21 февраля 2003 г.): Белово: БИ(Ф) КемГУ, 2003.-С 440-445.

51. Крутиков, В. Н. Об одной схеме анализа системы угольных предприятий / В. Н. Крутиков. // Наука и образование: Материалы Всероссийской научной конференции (12-13 апреля 2002 г.). - Ч2. - Белово: БИ(Ф) КемГУ, 2002. - С 332-336.

52. Крутиков, В. Н, Об одном методе выделения информативной системы признаков / В. Н. Крутиков, Д. В. Арышев // Материалы Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» - Томск: Твердыня, 2002. - С 194-196.

53.Крутиков, В. Н. Минимизация негладких функций методом случайного поиска/

B. Н. Крутиков, Я. С. Ворошилов // Тез. докл. Второй научно-практической конференции «Наука и образование». -Белово: БФ КемГУ, 2001. - С 290-292.

54. Крутиков, В. Н. Методы регуляризации решения задачи обучения нейронной сети / В. Н. Крутиков, Д. И. Филинов // Нейроинформатика и ее приложения: Материалы VIII Всероссийского семинара, 6-8 октября 2000 г. - Красноярск.' ИПЦ КГТУ,2000.-С.91.

55. Крутиков, В. Н. Основные подходы к проектированию информационной модели углегазового месторождения / В. Т. Преслер, В. Н. Крутиков, А. В. Гарнага // Труды научно-технической конференции: Опыт и перспективы наукоемких технологий в угольной промышленности Кузбасса. - Кемерово: ИУ СО РАН, 1998. -

C. 173-178.

56. Крутиков, В. Н. Построение математической модели метановыделения из пластов спутников / В. Н. Крутиков, С. К. Тризно, Г. Я. Полевшиков // Труды научно-технической конференции: Опыт и перспективы наукоемких технологий в угольной промышленности Кузбасса.- Кемерово: ИУ СО РАН. -1998. - С.173-178.

57.Крутиков, В. Н. Квазиньютоновские методы с попарной А-ортоганализацией / В. Н. Крутиков // Тез. докл. 10-й Байкальской школы-семинара: Методы оптимизации и их приложения. - Иркутск: СЭИ, 1995. -С.88-89.

58.Крутиков, В. Н. Методы приближения поверхности по данным на хаотической сетке на основе алгоритма сдвига штрафов / В. Н. Крутиков, С. Л. Злобина // Тез. докл. 10-й Байкальской школы-семинара: Методы оптимизации и их приложения. - Иркутск: СЭИ, 1995. - С.196-197.

59.Крутиков, В. Н. Методы математического моделирования пластовых месторождений / В. Н. Крутиков, С. Л. Злобина // Тез. докл. Международной конференции по математическому моделированию. -Якутск. -1994. - С.144.

60. Крутиков, В. Н. Прогноз особенностей пластовых месторождений / В. Н. Крутиков, С. Л. Злобина // Тез. докл. Международной конференции по математическому моделированию. - Якутск. - 1994. - С. 143.

61. Крутиков, В. Н. Прогноз тектонической нарушенности угольных месторождений / В. Н. Вылегжанин, Э. И. Витковский, В. Н. Крутиков, В. П. Потапов // Горное давление в очистных и подготовительных выработках. - Новосибирск: ИГД,

1990.-С.42-45.

62. Крутиков, В. Н. О скорости сходимости метода ВБ8 и его модификаций / В. Н.

Крутиков //Тез. докл. Международной школы-семинара по методам оптимизации и их приложениям. - Иркутск: СЭИ, 1989. - С. 114-115.

63. Крутиков, В. Н. О свойствах модификаций алгоритма с растяжением пространства вдоль разности градиентов / В. Н. Крутиков, Г. Б. Кацэба // Тез. докл. Международной школы-семинара по методам оптимизации и их приложениям. - Иркутск: СЭИ, 1989.-С. 116-117.

64. Крутиков, В. Н. Сравнение оценок скорости сходимости г-алгоритма , метода Ньютона и DFP / В. Н. Крутиков // Тез. докл. десятого всесоюзного симпозиума: Системы программного обеспечения решения задач оптимального планирования. - М: АН СССР, ЦЭМИ, 1988. - С.45-46.

65. Крутиков, В. Н. Методы пространственного моделирования геомеханической обстановки шахтных полей средствами горной информатики / В. Н. Вылегжанин, Э. И. Витковский, В. Н. Крутиков, В. П. Потапов // Доклады VII международного конгресса по маркшейдерскому делу, - Ленинград. -1988. - Т6. - С.83-90.

66.Крутиков, В. Н. Управление метрикой окрестностей в алгоритмах дискретной оптимизации / В. Н. Крутиков, Корсакова О. Н. //Тез. докл.: Дискретная оптимизация и компьютеры. -М: ЦЭМИ-КемГУ, 1987. - С. 127-128.

67.Крутиков, В. Н. Алгоритмы случайного поиска с переменной метрикой / В. Н. Крутиков, В. В. Захаров //Тезисы докладов Всесоюзного семинара: Случайный поиск и системы автоматизированного проектирования в электротехнике. - Ере-ван.-1979.-С.7-8 .

68.Крутиков, В. Н. Об одной методике построения методов сопряженных направлений / В. Н. Крутиков //Тезисы докладов Всесоюзного научно-технического семинара (г. Харьков): Численные методы нелинейного программирования. - Москва. -1979.-С.43-45.

69. Крутиков, В. Н. Управление распределением испытаний в алгоритмах случайного поиска / В. Н. Крутиков. // Тезисы докладов 4 Всесоюзного совещания: Статистические методы теории управления. - М.: Наука. -1978. - С.27-28.

70. Крутиков, В. Н. Алгоритмы случайного поиска с изменением метрики пространства испытаний / В. Н. Крутиков, В. В. Захаров //Системы управления. - Томск: изд.-воТГУ, 1978.-С.131-135.

71.Крутиков, В. Н. Новые идеи и методы моделирования поверхностей пластов угля / В. Н. Крутиков, А. В. Паначев // Тез. докл. II Всесоюзного семинара: Информатика недр. - Кемерово: ИУ, 1989. - С.41.

72.Крутиков, В. Н. Оценка и сравнение двух методов аппроксимации поверхностей пластовых месторождений / В. Н. Крутиков, А. В. Паначев, В. П. Потапов // Тез. докл. II Всесоюзного семинара: Информатика недр. - Кемерово: ИУ, 1989. - С.47.

ГОУ ВПО «Кемеровский государственный университет». 650043, г. Кемерово, ул. Красная, 6, Отпечатано в издательстве «Кузбассвузиздат.» 650043, г. Кемерово, ул. Ермака, 7

Подписано к печати 2.03.2005. Печать офсетная. Печ.л 2,25. Тираж 120 экз Заказ № /

05.1Z-OSJ3

г

f

у. »

tu .*. г

* V J

V V ч /

V \ _

2 2 КАР 2005 113 С

ВВЕДЕНИЕ.

ГЛАВА 1. УСЛОВИЯ ОБУЧЕНИЯ В РЕЛАКСАЦИОННЫХ МЕТОДАХ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ И ИТЕРАТИВНЫЕ АЛГОРИТМЫ ОБУЧЕНИЯ.

§ 1.1. Типы сложности задач безусловной оптимизации.

§ 1.2. Базовые схемы релаксационных методов безусловной оптимизации с обучением. Условия обучения.

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

ГЛАВА 2. РАЗРАБОТКА И ОБОСНОВАНИЕ РЕЛАКСАЦИОННЫХ МЕТОДОВ ПРЯМОГО ПОИСКА С ИЗМЕНЕНИЕМ МЕТРИКИ, ОСНОВАННЫХ НА ИТЕРАТИВНЫХ АЛГОРИТМАХ ОБУЧЕНИЯ.

§ 2.1. Схемы алгоритмов изменения метрики в методах случайного поиска и покоординатной релаксации, основанные на квадратичной модели функции

§ 2.2. Обоснование скорости сходимости класса методов минимизации вдоль векторов линейно-независимой системы.

§ 2.3. Обоснование скорости сходимости шаговых методов случайного поиска.

§ 2.4. Алгоритмы адаптации шага в методах случайного поиска и оптимизация их параметров.

§ 2.5. Метод случайного поиска с варьированием метрики.

§ 2.6. Метод минимизации без вычисления производных на основе рассредоточенной схемы А-ортогонализации.

§ 2.7. Выводы.

ГЛАВА 3. РАЗРАБОТКА И ОБОСНОВАНИЕ КВАЗИНЬЮТОНОВСКИХ МЕТОДОВ, ОСНОВАННЫХ НА ИТЕРАТИВНЫХ АЛГОРИТМАХ ОБУЧЕНИЯ.

§ 3.1. Квазиньютоновские методы.

§ 3.2. Вывод и анализ на основе формализма теории обучения известных формул пересчета матриц квазиньютоновских методов.

§ 3.3. Глобальная скорость сходимости и ускоряющие свойства квазиньютоновских методов.

§ 3.4. Квазиньютоновский метод минимизации на основе двухшагового алгоритма обучения.

§ 3.5. Способы наращивания размерности подпространства квазиньютоновского соотношения.

§ 3.6. Обоснование сходимости квазиньютоновского метода минимизации на основе двухшагового алгоритма обучения.

§ 3.7. Результаты вычислительного эксперимента.

§ 3.8. Выводы.

ГЛАВА 4. РАЗРАБОТКА И ОБОСНОВАНИЕ РЕЛАКСАЦИОННЫХ СУБГРАДИЕНТНЫХ МЕТОДОВ, ОСНОВАННЫХ НА

ИТЕРАТИВНЫХ АЛГОРИТМАХ ОБУЧЕНИЯ.

§4.1. Подход построения эффективных алгоритмов обучения в методах сопряженных субградиентов.

§ 4.2. Алгоритм обучения с растяжением пространства для решения множества равенств.

§ 4.3. Алгоритм обучения с растяжением пространства для решения множества неравенств.

§ 4.4. Релаксационный субградиентный метод с растяжением пространства в направлении субградиента.

§ 4.5. Связь релаксационного субградиентного метода с растяжением пространства с методом сопряженных градиентов.

§ 4.6. Реализация релаксационного субградиентного метода с растяжением пространства в направлении субградиента.

§ 4.7. Итерационный метод решения множества неравенств на основе одношагового алгоритма обучения.

§ 4.8. Алгоритм минимизации на основе одношагового алгоритма обучения для решения множества неравенств.

§ 4.9. Связь с методом сопряженных градиентов.

§ 4.10. Реализация алгоритма минимизации на основе одношагового алгоритма обучения для решения множества неравенств.

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

§ 4.12. Выводы.

ГЛАВА 5. РАЗРАБОТКА И ОБОСНОВАНИЕ ОДНОРАНГОВОГО СЕМЕЙСТВА СУБГРАДИЕНТНЫХ МЕТОДОВ С РАСТЯЖЕНИЕМ ПРОСТРАНСТВА, ОСНОВАННЫХ НА ИТЕРАТИВНЫХ АЛГОРИТМАХ ОБУЧЕНИЯ.

§ 5.1. Метод сопряженных субградиентов с растяжением пространства.

§ 5.2. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства.

§ 5.3. Реализация алгоритмов однорангового семейства субградиентных методов

§ 5.4. Анализ глобальной скорости сходимости алгоритма с растяжением пространства в направлении разности последовательных субградиентов.

§ 5.5. Выводы.

ГЛАВА 6. ПРОГРАММНЫЙ КОМПЛЕКС РЕЛАКСАЦИОННЫХ

МЕТОДОВ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИЯМ (ПКРМО)

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

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

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

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

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

Во многих задачах минимизации функция задается алгоритмически, а доступной информацией о функции являются только значения функции. Методы, использующие только эту информацию, называют прямыми методами, методами поиска или методами без вычисления производных. Прямые методы развивались в работах Ф.Л. Черноусько, В.Г. Карманова, Б.Н. Пшеничного, О.П. Бурдакова, М.М. Потапова, Л.А. Растригина, Пауэлла, Брента, Бродли и др. Им посвящена обширная литература (см., например [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 из предложенного множества многомерных негладких задач. Более предпочтительным для этих целей является метод случайного поиска (СП), поскольку он сходится линейно [60, 61] (В.Г. Карманов), а адаптация шага Л. А. Расстригина, Г.С. Тарасенко [169, 179] обеспечивает его сходимость на негладких функциях, но он имеет медленную скорость сходимости на овражных функциях. Отмеченные обстоятельства определяют актуальность исследований диссертации по созданию алгоритмов обучения метрики в методах СП для ускорения их сходимости и расширения области решаемых ими гладких и негладких задач оптимизации.

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

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

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

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

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

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

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

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

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

Развитие численных методов негладкой оптимизации связано с именами ученых И.И. Астафьева, В.П. Булатова, Ф.П. Васильева, Е. Г. Голыитейна, А. М. Гупала, В. Ф. Демьянова, Ю. М. Ермольева, И. И. Еремина, Ю.А. Левина, В.Н. Малоземова, А. С. Немировского, Е. А. Нурминского, Ю. Е. Нестерова, Б. Т. Поляка, Н. 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] известных методов негладкой оптимизации: метода эллипсоидов (МЭ - А.С. Немировский, Д.Б. Юдин.) [146], r-алгоритма (МШ - Н.З. Шор) [195, 196], метода ортогонального спуска (МОС -В.А. Скоков, М.Б. Щепакин) [177, 197], и разработанного в последние годы, метода уровней (МУ - Е.Г. Голынтейн, А.С. Немировский, Ю.Е. Нестеров) [29, 217], с одной стороны - демонстрируют высокую эффективность метода МУ относительно других методов по критерию числа вычислений функции и субградиента, а с другой - выявляют необходимость создания эффективных по критерию времени счета, надежных методов негладкой оптимизации. Среди исследуемых методов реализации методов МЭ, МШ и МУ не используют каких либо дополнительных свойств функции, кроме выпуклости, т.е. являются методами общего назначения. Алгоритмы МШ и МУ справляются с задачами высокой размерности, хотя и не со всеми, а их совершенствование может привести к возможности решения задач порядка 1000 переменных, поскольку современные ЭВМ обладают значительным быстродействием и оперативной памятью. При прочих достоинствах, МШ среди исследуемых методов, единственный пригодный для решения невыпуклых задач оптимизации. Сегодня существует проблема создания универсальных, надежных методов негладкой оптимизации, эффективных при решении гладких и негладких, в том числе и невыпуклых, задач, конкурирующих по свойствам скорости сходимости с методами, основанными на квадратичной, либо кусочно-линейной моделях функции, на классах функций, промежуточных отмеченным базовым классам.

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

Исследования диссертации направлены на решение поставленных актуальных задач с привлечением формализма теории обучения. В [72, 118] определяющее соотношение нахождения вектора спуска, как решения задачи нахождения ближайшего к началу координат вектора отделимого множества, заменено на решение задачи множества неравенств, которая, в свою очередь, представлена в виде задачи решения множества равенств с ошибками. Это дало возможность получить несколько алгоритмов обучения для решения неравенств и создать на их основе эффективные релаксационные субградиентные методы [75, 80, 82, 83, 92-94, 109, 114-120, ]: метод сопряженных субградиентов [72, 82, 116, 117, 120], в основу которого положен одноша-говый алгоритм обучения, и субградиентные методы с растяжением пространства [80, 82, 118, 119], алгоритмы обучения которых созданы на основе алгоритма обучения с растяжением пространства. В частности, на основе алгоритма обучения с растяжением пространства разработано семейство матричных методов обучения [80, 82, 118], отдельным случаем которого является алгоритм обучения, вычлененный из г-алгоритма. На этой основе разработано одноранговое семейство релаксационных субградиентных методов [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-33121); с программой «Университеты России» (код проекта УР.04.01.044); договорной тематикой с угольными компаниями Кузбасса, НТЦ «Кузбассуглетехнология» и с корпорацией «Кузбассинвест-уголь»; с Комплексной региональной программой научных исследований и внедрения совместных работ СО АН СССР и Министерства угольной промышленности СССР, «Программа "Сибирь"», раздел «Уголь Кузбасса», и приказами Министерства угольной промышленности СССР от 16.11.79, и №315 от 24.06.80.

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

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

Задачи исследований:

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

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

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

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

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

Методы исследований:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 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 страницах.

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Айвазян С.А. и др. Прикладная статистика: основы моделирования и первичная обработка данных. - М.: Финансы и статистика. - 1983.

2. Антамошкин А.Н. Оптимизация процессов автоматизированного синтеза управления космическими аппаратами: Дисс. на сиск. уч. степени доктора техн. наук. -Красноярск: ССА, 1996. -265с.

3. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. -Томск: ТГУ. 1986. -129с.

4. Ануфриев В.Е., Крутиков В.Н., Тризно С.К. Математическое моделирование грузоподъёмности мягких оболочек прямоугольного типа // Горное давление в очистных и подготовительных выработках. -Новосибирск: ИГД. -1988. -С.75-79.

5. Аоки М. Введение в методы оптимизации. М.: Наука. — 1977. - 343с.

6. Бакушинский А.Б., Трушниеов В.Н. Методы численного анализа линейных и нелинейных операторных методов с необратимыми операторами: Учеб. пособие. -Кемеровский гос. ун-тю. 2000. - 56с.

7. Банди Б. Методы оптимизации. Вводный курс/ Пер. с англ. М.: Радио и связь. -1968. -128с.

8. Баничук Н.В., Петров В.М., Черноусько Ф.Л. Численное решение вариационных и краевых задач методом локальных вариаций// Жури, вычисл. матем. и матем. физ. -1966.-Т.6.-С. 947-961.

9. Бахвалов Н.С Численные методы. T.l. -М: Наука, 1973 г. 631с.

10. Бенерджи П., Баттерфилд Р. Методы граничных элементов в прикладных науках. -М.: Мир, 1984.

11. Букринский В.А. Геометрия недр. М: Недра, 1985. -526с.

12. Бурдаков О.П. Методы типа сопряженных направлений для решения систем уравнений и поиска седловых точек. Г//Изв. АН СССР. Техн. кибернет. -1982. -№3. -С 17-24.

13. Бурдаков О.П. Методы типа сопряженных направлений для решения систем уравнений и поиска седловых точек. П.//Изв. АН СССР. Техн. кибернет. -1982. №4. -С 26-33.

14. Вазан М. Стохастическая аппроксимация. -М: Мир. 1971. -295с.

15. Васильев Л. В. О связи релаксационного метода обобщенного градиента с методом сопряженных градиентов// Тез. докл. 3-го Всесоюзного семинара (Харьков): Численные методы нелинейного программирования. 4.1. -Москва. -1979. -С.45-49.

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

17. Ворошилов Я.С., Крутиков В.Н.Минимизация негладких функций методом случайного поиска // Тез. докл. Второй научно-практической конференции «Наука и образование». -Белово, БФ КемГУ. -2001. -С 290-292.

18. Вылегжанин В.Н., Витковский Э.И., Крутиков В.Н., Потапов В.П. Прогноз тектонической нарушенности угольных месторождений // Горное давление в очистных и подготовительных выработках. -Новосибирск: ИГД. -1990. -С.42-45.

19. Вылегжанин В.Н., Витковский Э.И., Потапов В.П. Адаптивное управление подземной технологией добычи угля Новосибирск: Наука. -1987. -232с.

20. Вылегжанин В.Н., Крутиков В.Н. Использование математического моделирования в задачах оптимизации межотраслевых связей в структуре регионального ТЭК // ТЭК и ресурсы Кузбасса. -2001. -№4. -С.62-64.

21. Вылегжанин, В.Н., Крутиков В.Н., Тризно С.К. Моделирование технологических процессов в очистном забое // -Кемерово: ЦНТИ. -1990.

22. Вылегжанин, В.Н., Крутиков В.Н., Тризно С.К. Оценка эффективности параметров многомашинных очистных забоев // Горное давление в очистных и подготовительных выработках. -Новосибирск: ИГД. -1989. -С.9-16.

23. Галушкин А.И. Синтез многослойных схем распознавания образов. -Москва: Энергия. 1974.

24. Галушкин А.И. Теория нейронных сетей. -М: ИПРЖР. 2000.

25. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир. - 1985. -509с.

26. Голыитейн Е.Г., Немировский А.С., Нестеров Ю.Е. Метод уровней, его обобщения и приложения// Экономика и мат. методы. -1995. -Т.31. №3.

27. Гольштейн Е.Г., Юдин Д. Б. Новые направления в линейном программировании. -Сов. радио. 1966. -524с.

28. Гонсалес А.В. Принципы распознавания образов/ А. В. Гонсалес, X. Ту. -М.: Мир. 1977.

29. Горбань А.Н. Обучение нейронных сетей. М.: ПараГраф, 1990. - 159с.

30. Горбань А.Н., Миркес Е.М. Логически прозрачные нейронные сети // Изв. ВУЗов. Приборостроение. -1996. -Т. 39, № 1. -С.64-67.

31. Горбань А.Н., Россиев Д.А. Нейронные сети на персональном компьютере -Новосибирск: Наука. 1996.

32. Гранберг А.Г. Математические модели социалистической экономики. -М.:Экономика, 1978. -487с.

33. Гупал A.M. Стохастические методы решения негладких экстремальных задач. -Киев: Наукова думка, 1979. 148с.

34. Дамбраускас А.П. Симплекс поиск. -М.: Энергия. 1979.

35. Данилин Ю.М. Об одном классе алгоритмов минимизации со сверхлинейной сходимостью// Журн. вычисл. матем. и матем. физ. -1974. -Т. 14, №3. -С.598-609 .

36. Данилов Н.Н. Курс математической экономики. Части I -III / Учебное пособие. -Кемерово: Юнити. 2000.

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

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

39. Денис Дж. Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. М.: Мир,- 1988. - 440с.

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

41. Еремин И.И. О методе штрафов в выпуклом программировании// Кибернетика. -1967,-№4.-С. 63-67.

42. Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976. -240с.

43. Завьялов Ю.С., Квасов Б.Н., Мирошниченко В.Л. Методы сплайн-функций. -М.: Наука,- 1980.47.3ангвилл У.И. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973.-311с.

44. Захаров В.В Стандартные условия тестирования и исследования методов поиска минимума функциий многих переменных// Автоматика и вычисл. техника. -1980. -№5. Деп. 11.02.80, №493-80.-31с.

45. Захаров В.В., Крутиков В.Н. Алгоритм случайного поиска с адаптацией весов при векторах памяти //Тезисы докладов совещания: Применение случайного поиска при решении прикладных задач. Кемерово: КемГУ. -1979. -С.20-21.

46. Захаров В.В., Крутиков В.Н. Алгоритмы случайного поиска с изменением метрики пространства испытаний //Системы управления. -Томск: изд. ТГУ- 1978. -С.131

47. Захаров В.В., Крутиков В.Н. Алгоритмы случайного поиска с переменной метрикой //Тезисы докладов Всесоюзного семинара: Случайный поиск и системы автоматизированного проектирования в электротехнике. -Ереван. -1979. -С.7-8 .

48. Захаров В.В., Крутиков В.Н. Новые адаптивные алгоритмы случайного поиска и численные эксперименты с ними// Оптимизация динамических систем. -Минск: изд. БГУ.-1978.-С. 51-55 .

49. Захаров В.В., Крутиков В.Н. Повышение эффективности алгоритмов случайного поиска посредством включения в схему экстраполяции //Проблемы случайного поиска. -Рига: Зинатне. -1978. -Вып.7. -С. 207-213.

50. Захаров В.В., Крутиков В.Н. Статистический метод вычисления сопряженных направлений // Кибернетика (Кев). -1984. -№6. -С.95-100.

51. Захаров В.В., Крутиков В.Н. Теоретическое и экспериментальное исследование скорости сходимости двух алгоритмов случайного поиска //Вопросы разработки территориальных автоматизированных систем управления. Кемерово: КемГУ. -1984. -С.65-70.

52. Зельдович Я.Б. Горение пороха при переменном давлении// Теория горения поро-хов и взрывчатых веществ. -М.: Наука. -1982. -С. 278 300.

53. Ивахненко А.Г. Индуктивный метод самоорганизации моделей сложных систем. -Киев: Наукова думка. -1981.

54. Карманов В.Г. Математическое программирование. -М.: Наука 1980. - 256с.

55. Карманов В.Г. О сходимости метода случайного поиска в выпуклых задачах минимизации// Теория вероятностей и ее применения. -1974. -Т. 19, №3. -С.817-824.

56. Карманов В.Г. Оценки сходимости итерационных методов минимизации// Жур. вычисл. матем. и матем. физ. -1974. -Т. 14, №1. -С.3-14.

57. Компьютеры и системы управления в горном деле за рубежом/ Ю. П. Астафьев, А. С. Зеленский, Н. И. Горлов и др. М.:Недра. -1989. -264с.

58. Круглов В.В., Дли М.И., Годунов Р.Ю. Нечеткая логика и искусственные нейронные сети: Учеб. пособие. М.: Издательство Физико-математической литературы.- 2001.-224с.

59. Крутиков В.Н. Абсолютные оценки скорости сходимости r-алгоритма и метода Ньютона// Якутск: Матем. заметки ЯГУ. -1997. -Т.4. № 1. -С. 38-50.

60. Крутиков В.Н. Алгоритм случайного поиска с адаптивной метрикой («SPM») // Свидетельство об официальной регистрации программ № 2003612566. -М: РОС

61. ПАТЕНТ. Зарегистрировано в реестре программ для ЭВМ, г. Москва, 25 ноября 2003 г.-2003.

62. Крутиков В.Н. Анализ динамики сходимости квазиньютоновских методов// Матем. заметки ЯГУ. -Якутск. -1994. -Т.1. Вып. 2. -С. 40 48.

63. Крутиков В.Н. Быстросходящийся метод решения задач безусловной минимизации, не требующий вычисления произволных//Газовая динамика. -Томск: ТГУ. -1987. -С.85-99.

64. Крутиков В.Н. Идентификация квадратичного объекта по данным текущих изме-рений//Тезисы докладов совещания: Применение случайного поиска при решении прикладных задач. -Кемерово. -1979. -С. 14-16.

65. Крутиков В.Н. Квазиньютоновские методы на основе рассредоточенных способов восстановления Гессиана// Матем. заметки ЯГУ. -2000. -Т.7. Вып. 2. -С. 62-81.

66. Крутиков В.Н. Квазиньютоновские методы с попарной А-ортоганализацией// Тез. докл. 10-й Байкальской школы-семинара: Методы оптимизации и их приложения. Иркутск: СЭИ. -1995. -С.88-89.

67. Крутиков В.Н. Методы минимизации на основе частной модели субградиентных множеств// Методы оптимизации и их приложения/Труды 11-й Международной Байкальской школы-семинара. Иркутск-1998. -Том 1. -С. 101-104.

68. Крутиков В.Н. Методы оптимизации. Часть I: Учебн.-метод. пособие. -Кемерово: КемГУ.-1999.-50с.

69. Крутиков В.Н. Методы оптимизации. Часть II: Учебн.-метод. пособие. -Кемерово: КемГУ. -2002. -56с.

70. Крутиков В.Н. Новый релаксационный субградиентный метод с изменением метрики // Вестник КемГУ. Кемерово. -2001. -Вып. 4. -С. 16-22.

71. Крутиков В.Н. О скорости сходимости метода BFS и его модификаций// Тез. докл. Международной школы-семинара по методам оптимизации и их приложениям. -Иркутск: СЭИ. -1989. -С.114-115.

72. Крутиков В.Н. О скорости сходимости методов минимизации вдоль векторов линейно-независимой системы//Жур. вычисл. матем. и метем, физ. -1983. -Т.23, №1. -С.218-220.

73. Крутиков В.Н. Об одной методике построения методов сопряженных направле-ний//Тезисы докладов Всесоюзного научно-технического семинара (г. Харьков): Численные методы нелинейного программирования. Москва. -1979. -С.43-45 .

74. Крутиков В.Н. Об одной схеме анализа системы угольных предприятий// Наука и образование: Материалы Всероссийской научной конференции (12-13 апреля 2002 г.): ч2. Белово: БИ(Ф) КемГУ. -2002. -С 332-336.

75. Крутиков В.Н. Одноранговое семейство релаксационных субградиентных методов с растяжением пространства П Электронный журнал "Исследовано в России".209. -2003. -С 2450-2459. http: //zhurnal.ape.relarn.ru/articles/2003/ 209. pdf.

76. Крутиков B.H. Оптимизационные задачи моделирования межотраслевого комплекса и методы их решения // Вестник КемГУ. -Кемерово. -2001. -№3(7). -С. 2025.

77. Крутиков В.Н. Релаксационные методы безусловной оптимизации, основанные на принципах обучения: Учебное пособие/ ГОУ ВПО «Кемеровский государственный университет». Кемерово: «Кузбассвузиздат». -2004. -171с.

78. Крутиков В.Н. Сравнение оценок скорости сходимости г-алгоритма , метода Ньютона и DFP// Тез. докл. десятого всесоюзного симпозиума: Системы программного обеспечения решения задач оптимального планирования. -М: АН СССР, ЦЭМИ. -1988. -С.45-46.

79. Крутиков В.Н. Сравнение оценок скорости сходимости случайного покоординатного и циклического покоординатного спусков//Применения случайного поиска при решении прикладных задач. Кемерово: КемГУ. -1981. -С.71-75.

80. Крутиков В.Н. Управление распределением испытаний в алгоритмах случайного поиска// Тезисы докладов 4 Всесоюзного совещания: Статистические методы теории управления. -М.: Наука. -1978. -С.27-28.

81. Крутиков В,Н. Численные методы нелинейного программирования: Учебн.-метод. пособие. -Кемерово: КемГУ, 1994. -32с.

82. Крутиков В.Н., Арышев Д.В. Алгоритм последовательного отсева неинформативных переменных линейной модели // Вестник КемГУ. -Кемерово. -2004. -№1 (17). -С. 124-129.

83. Крутиков В.Н., Арышев Д.В. Алгоритм построения нейронной сети с минимальным числом нейронов // Наука и образование: Материалы Всероссийской научной конференции (20-21 февраля 2003 г.): Белово: БИ(Ф) КемГУ, 2003. С 440-445.

84. Крутиков В.Н., Арышев Д.В. Исследование субградиентных методов обучения нейронных сетей // Вестник КемГУ. -Кемерово. -2004. -№1 (17). -С. 119-124 .

85. Крутиков В.Н., Арышев Д.В. Метод негладкой регуляризации в задачах контрастирования //Нейроинформатика и ее приложения: Материалы XII Всероссийского семинара 1-3 октября 2004г/ Красноярск: ИВМ СО РАН, 2004. С.80-81.

86. Крутиков В.Н., Арышев Д.В. Метод сопряженных субградиентов с растяжением пространства // Электронный журнал "Исследовано в России" 208. -2003. -С 2439-2449. -http:/zhurnal.ape.relarn.ru/ articles/2003/208.pdf.

87. Крутиков В.Н., Арышев Д.В. Реализация алгоритмов однорангового семействасубградиентных методов //Электронный журнал "Исследовано в России" 43. -2004. -С. 464-473. http: //zhurnal.ape.relarn.ru/ articles/2004/ 043.pdf.

88. Крутиков В.Н., Арышев Д.В.Об одном методе выделения информативной системы признаков // Материалы Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» Томск: «Твердыня».-2002.-С 194-196.

89. Крутиков В.Н., Ворошилов Я.С. Методы построения линейной функции полезности сложных объектов // Вестник КемГУ. -Кемерово. -2001. Вып. 4. -С. 71-76.

90. Крутиков В.Н., Глушко Е.Н. Алгоритмы распознавания складок поверхности // Вестник КемГУ. -Кемерово. -2001. -Вып. 4. -С. 60-65.

91. Крутиков В.Н., Глушко Е.Н. Методы обнаружения тектонических нарушений // ТЭК и ресурсы Кузбасса: Вестник ТЭК Кузбасса. -2001. -№3. -С. 22-23.

92. Крутиков В.Н., Глушко Е.Н. Методы распознавания разрывных форм пластовых месторождений //Деп. в ВИНИТИ. -2000. -191-В00. -31с.

93. Крутиков В.Н., Глушко Е.Н. Методы распознавания складчатых форм пластовых месторождений // Деп. в ВИНИТИ. -2000. -190-В00. -38с.

94. Крутиков В.Н., Глушко Е.Н. Новый метод аппроксимации поверхности // Деп. в ВИНИТИ. 1999. -1400-В99. -11с.

95. Крутиков В.Н., Захаров В.В. Модифицированный алгоритм случайного поиска с изменением метрики пространства //Тез. докл.: Статистические методы в горнорудной промышленности. Кемерово: НТО. -1985. -С. 101-102.

96. Крутиков В.Н., Злобина C.JI. Методы математического моделирования пластовых месторождений // Тез. докл. Международной конференции по математическому моделированию. -Якутск. -1994. -С. 144.

97. Крутиков В.Н., Злобина СЛ. Методы приближения поверхности по данным на хаотической сетке на основе алгоритма сдвига штрафов/ // Тез. докл. 10-й Байкальской школы-семинара: Методы оптимизации и их приложения. -Иркутск. -1995. -С. 196-197.

98. Крутиков В.Н., Злобина C.JI. Прогноз особенностей пластовых месторождений // Тез. докл. Международной конференции по математическому моделированию. -Якутск.-1994.-С. 143.

99. Крутиков В.Н., Злобина СЛ., Бувальцев Н.Ф. Алгоритмы аппроксимации поверхности, заданной значениями в узлах нерегулярной сетки // Матем. заметки.

100. ЯГУ. -1995. -Т.2, № 2. -С. 110-120.

101. Крутиков В.Н., Кацэба Г.Б. Методы локальной оптимизации сетевых моделей при ограничениях на ресурсы // Тез. докл. II Всесоюзного семинара: Информатика недр. -Кемерово: ИУ. 1989. -С.39.

102. Крутиков В.Н., Кацэба Г.Б. О свойствах модификаций алгоритма с растяжением пространства вдоль разности градиентов// Тез. докл. Международной школы-семинара по методам оптимизации и их приложениям. -Иркутск: СЭИ. -1989. -С. 116-117.

103. Крутиков В.Н., Комаров Н.Ю. Новый метод решения неравенств с растяжением пространства и субградиентные методы на его основе // Вестник КемГУ. -Кемерово. -2001. -№3(7). -С. 73-78.

104. Крутиков В.Н., Корсакова О.Н. Управление метрикой окрестностей в алгоритмах дискретной оптимизации //Тез. докл.: Дискретная оптимизация и компьютеры. -М: ЦЭМИ-КемГУ. -1987. -С.127-128.

105. Крутиков В.Н., Паначев А.В. Алгоритмы прогноза нарушенности пластовых месторождений // Тез. докл. II Всесоюзного семинара: Информатика недр. -Кемерово: ИУ. -1989. -С.83.

106. Крутиков В.Н., Паначев А.В. Новые идеи и методы моделирования поверхностей пластов угля // Тез. докл. II Всесоюзного семинара: Информатика недр. -Кемерово: ИУ. -1989. -С.41.

107. Крутиков В.Н., Паначев А.В., Потапов В.П. Оценка и сравнение двух методов аппроксимации поверхностей пластовых месторождений // Тез. докл. II Всесоюзного семинара: Информатика недр. Кемерово: ИУ. 1989. -С.47.

108. Крутиков В.Н., Петрова Т.В. Алгоритм Качмажа с изменением метрики / Деп. в ВИНИТИ. -М. -1999. -3941-В99. -9с.

109. Крутиков В.Н., Петрова Т.В. Модифицированный алгоритм Качмажа для решения задачи построения разделяющей поверхности //Деп. в ВИНИТИ. -М. -1999. -3940-В99. -11с.

110. Крутиков В.Н., Петрова Т.В. Новый метод решения задач минимизации большой размерности // Вестник КемГУ. Кемерово. -2001. -Вып. 4. -С.65-71.

111. Крутиков В.Н., Петрова Т.В. Новый релаксационный метод недифференцируе-мой минимизации // Мат. заметки ЯГУ. -2001. -Т.8. Вып. 1. -С. 50-60.

112. Крутиков В.Н., Петрова Т.В. Релаксационный метод минимизации с растяжением пространства в направлении субградиента // Экономика и мат. методы. -2003. -Т. 39. Вып. 1. -С 106-119.

113. Крутиков В.Н., Петрова Т.В. Релаксационный субградиентный метод недиффе-ренцируемой минимизации с растяжением пространства // Деп. в ВИНИТИ. -М. -2000. -№3222-В00. -28с.

114. Крутиков В.Н., Петрова Т.В. Субградиентный метод с неточным одномерным спуском // Вестник КемГУ. Кемерово. -2001. -№3(7). -С. 85-91.

115. Крутиков В.Н., Потапов В.П., Глушко Е.Н. Экспериментальная оценка множества методов аппроксимации поверхности // Деп. в ВИНИТИ. -М. -1999. -1401 В99. -13с.

116. Крутиков В.Н., Пушкина Н.Б. Метод восстановления метрики по упорядоченным расстояниям // Вестник КемГУ. -Кемерово. -2001. -Вып. 4. -С. 35-39.

117. Крутиков В.Н., Филинов Д.И. Методы регуляризации решения задачи обучения нейронной сети//Нейроинформатика и ее приложения: Материалы VIII Всероссийского семинара 6-8 октября 2000г/ Красноярск: ИПЦ КГТУ, 2000. С.91.

118. Крутиков, В. Н., Кацэба Г.Б. Система оценки параметров и структуры математических моделей // Тез. докл. II Всесоюзного семинара: Информатика недр. -Кемерово: ИУ. -1989. -С.40.

119. Лавров С.С. Применение барицентрических координат для решения некоторых вычислительных задач//Журн. вычисл. матем. и матем. физ. -1964. -Т.4, №5. -С.905-911.

120. Лангольф ЭЛ., Вылегжанина И.И., Мазикин В.П. Проблемы эффективности реструктуризации угольной промышленности Кузбасса. -Кемерово: Кузбассвуз-издат,- 1997. -248с.

121. Лбов Г.С. Выбор эффективной системы зависимых признаков// Вычислительные системы. -1965. -Вып 15. -С. 21-34.

122. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. -Новосибирск: Наука 1981. -160с.

123. Левин Ю.А. Об одном алгоритме минимизаций выпуклых функций//Докл. АН СССР. -1965. -Т. 160. № 6. -С. 1244-1247.

124. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений// Журн. вычисл. матем. и матем. физ. -1966. -т. 6, № 5. С 787-823.

125. Макаров И.М., Виноградская Т.М., Рубчинский А.А. Теория выбора и принятия решений: Учебное пособие. -М.: Наука.- 1982. -328с.

126. Маленво Э. Лекции по микроэкономическому анализу. -М.: Наука,- 1985. -390с.

127. Марчук Г.И. Методы вычислительной математики. -М: Наука. -1980. 534с.

128. Марчук Г.И., Кузнецов Ю.А. Итерационные методы и квадратичные функционалы. -Новосибирск: Наука,- 1972.

129. Математические методы и модели планирования и управления горным производством: Учеб. пособие для вузов/ А. Г. Протосеня, С.А. Кулиш, Е.И. Азбель и др. -М.:Наука. 1985. -288с.

130. Михайлов М.М., Дворецкий М.И., Косицин Л.Г., Крутиков В.Н, и др.// Вопросы оборонной техники. Серия 10, выпуск 151. - Ленинград: ГОИ им. Вавилова. -1980.

131. Михайлов М.М., Дворецкий М.И., Косицин Л.Г., Крутиков В.Н.// Вопросы оборонной техники. Серия 10, выпуск 151- Ленинград: ГОИ им. Вавилова. -1980.

132. Михайлов М.М., Крутиков В.Н. Прогнозирование оптической деградации терморегулирующих покрытий космических летательных аппаратов по результатам наземных испытаний // Перспективные материалы. -1997. -№ 2. -С. 18-25.

133. Михайлов М.М., Крутиков В.Н.Разработка комплекса математических моделей оптической деградации терморегулирующих покрытий космических летательных аппаратов // Перспективные материалы. -1997. —№ 1. -С.21-27.

134. Михалевич B.C., Трубин В.А., Шор Н. 3. Оптимизационные задачи производственно-транспортного планирования. М.: Наука.- 1986. - 260с.

135. Моисеев Н.Н. Численные методы в теории оптимальных систем. — М.: Наука, 1971.-424с.

136. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука.-1975.-351с.

137. Мудров В.И., Кушко В.Л. Методы обработки измерений. М.: Сов. радио. -1976.

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

139. Нестеров Ю.Е., Пурмаль Е.И. Анализ эффективности методов негладкой оптимизации. -М.: ЦЭМИ АН СССР. -1984. -31с.

140. Нестеров Ю.Е., Скоков В.А. Методы первого порядка нелинейной безусловной минимизации// Численные методы математического программирования. М.: ЦЭМИ,- 1980. С.6-60.

141. Нестерова С.И., Скоков В.А. Численный анализ программ негладкой безусловной оптимизации // Экономика и математические методы. -1994. -Т.30. -№2.

142. Ортега Д., Рейнболдт В. Итерационные методы решения нелинейных системуравнений со многими неизвестными. М.: Мир,- 1975. - 553с.

143. Пападимитру X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир. - 1985. - 512с.

144. Перельман И.И. Текущий регрессионный анализ и его применение в некоторых задачах автоматического управления// Изв. АН СССР, Энергетика и автоматика. -1960. -Т. XXIII, №2. -С. 122-131.

145. Полак Э. Численные методы оптимизации. М: Мир. - 1974. - 376 с.

146. Поляк Б.Т. Введение в оптимизацию. М.: Наука. - 1983.-384с.

147. Потапов В.П. Математическое и информационное моделирование геосистем угольных предприятий. Новосибирск: Изд. СО РАН. - 1999. -180с.

148. Преслер В.Т. Информационно-математическая среда прогноза газопроявлений в угольных шахтах. Кемерово: Кузбассвузиздат. - 2000. -228с.

149. Прикладная статистика. Классификация и снижение размерности / С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, JI. Д Мешалкин. -М.: Финансы и статистика. 1989.-607с.

150. Примак М.Е. О сходимости модифицированного метода чебышевских центров решения задач выпуклого программирования// Кибернетика. -1977. -№ 5. -С 100102.

151. Пшеничный Б.Н. Метод минимизации функций без вычисления производных// Докл. АН СССР. -1977. -Т. 235, №5. -С. 1026-1029.

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

153. Пшеничный Б.Н., Редковский Н.Н. Некоторые методы безусловной минимизации//Журн. вычисл. матем. и матем. физ. -1979. -Т. 19, №5. -С. 1127-1133.

154. Пшеничный Б.Н., Редковский Н.Н. О методе минимизации вдоль собственных векторов матрицы, близкой к матрице Гессе //Кибернетика. -1977. -№5. -С.68-74.

155. Пшеничный Б.Н., Редковский Н.Н. Об одном численном методе минимизации без вычисления производных // Журн. вычисл. матем. и матем. физ. -1976. -Т. 16, N6.-С. 1388-1396.

156. Растригин JI.A. Системы экстремального управления. -М.:Наука. 1974-632с.

157. Растригин JI.A. Случайный поиск в задачах оптимизации многопараметрических систем. -Рига: Зинатне. 1965. -211с.

158. Растригин JI.А. Современные принципы управления сложными системами. -Сов. радио. 1980. -232с.

159. Растригин Л.А. Статистические методы поиска. -М: Наука. 1968. -376с.

160. Растригин, Л. А., Тарасенко Г.С. Об одном адаптивном алгоритме случайного поиска / Л. А. Растригин//Проблемы случайного поиска. Рига: Зинатне. -1974. -Вып.З. -С.108-112.

161. Резниченко С.С. Математическое моделирование в горной промышленности. Учеб. пособие для вузов. М.:Недра. - 1981. -216с.

162. Руководство по проектированию вентиляции угольных шахт. -М.: Недра. -1975.-237с.

163. Семенкин Е.С., Семенкина О.Е., Терсков В.А. Методы оптимизации в управлении сложными системами: Учебное пособие. Красноярск: Сибирский юридический институт МВД России. - 2000. -254 с.

164. Семенкин Е.С., Семенкина О.Э., Коробейников. Адаптивные поисковые методы оптимизации сложных систем / Под общ. ред. Семенкина Е.С. Красноярск: СИБУП. - 1996.-358с.

165. Серебряков М.Е. Внутренняя баллистика ствольных систем и пороховых ракет. -М.: Оборонгиз. 1962. -703 с.

166. Скоков В.А. Варианты метода уровней для минимизации негладких выпуклых функций и их численное исследование // Экономика и математические методы. -1997. -Т.ЗЗ. №1.

167. Скоков В.А. Замечание к методам минимизации, использующим операцию растяжения пространства// Кибернетика. -1974. -№ 4. -С. 115-117.

168. Скоков В.А., Щепакин М.Б. Численный анализ одного варианта метода ортогонального спуска // Кибернетика и системный анализ. -1994. -№2.

169. Справочник по рудничной вентиляции / Под ред. К.З. Ушакова. -М.: Недра. -1977. -328с.

170. Тарасенко Г.С Сходимость адаптивного алгоритма случайного поис-ка//Кибернетика. -1977. -№5. -С.88-90.

171. Тарасенко Г.С. Исследование адаптивного алгоритма случайного поиска// Проблемы случайного поиска. -Рига: Зинатне. -1976. -вып.5. -С.119-124

172. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука. - 1979.

173. Трофимов А.А. Основы маркшейдерского дела и геометризации недр. -М.:Недра. 1985.-336с.

174. Фадеев Д.К., Фадеева В.Н. Вычислительные методы линейной алгебры. -М: Физматгиз. -1960 г. 656с.

175. Федоров В. В. Теория оптимального эксперимента. М: Наука. - 1981.

176. Фукунага К. Введение в теорию распознавания образов. -М.: Наука. 1979.

177. Химмельблау Д. Прикладное нелинейное программирование. М.: Мир. -1975.-596с.

178. Хоменко Ю.П., Ищенко А.Н., Касимов В.З. Математическое моделирование внутрибаллистических процессов в ствольных системах. Новосибирск: Изд-во СО РАН. - 1999. -256с.

179. Хоменко Ю.П., Ищенко А.Н., Саморокова Н.М. Интегродифференциальный метод определения законов горения конденсированных систем в условиях постоянного объема // Физика горения и взрыва. -1999. -Т.35, №1. -С.67-71.

180. Хоменко Ю.П., Широков В.М. Об учете тепловых потерь при обработке результатов манометрических испытаний // Фундаментальные и прикладные проблемы современной механики: Докл. II Всерос. науч. конф. -Томск: Изд-во Том. ун-та.-2000.-С.171-172.

181. Цыпкин Я. 3. Основы теории обучающихся систем. М.: Наука. - 1981. -251с.

182. Цыпкин Я.З. Адаптация и обучение в автоматических системах. М.: Наука. -1968. -400с.

183. Цыпкин Я.З. Информационная теория идентификации. -М.: Наука: Физматлит. 1995.-336с.

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

185. Шор Н.З., Журбенко Н. Г. Метод оптимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов// Кибернетика. -1971. -№ 3. -С.51 59.

186. Щепакин М.Б. О методе ортогонального спуска//Кибернетика. -1987. -№1.

187. Юдин Д.Б. Вычислительные методы теории принятия решений. -М.: Наука. -1989. -320с.

188. Biggs М.С. Minimization algorithms making use of non-quadratic properties of the objective function// J. Inst. Math, and Applic. -1971. -V.8. -Pp.315-327 .

189. Brent R.P. Algorithms for minimization without derivatives. New Jersey. -Prentice -Hall Inc., Englewood Cliffs. 1973. -195 p.

190. Brodlie K.W. A new direction set method for minimization without evaluating derivatives// J.Inst. Math, and Applic. -1975. -v.15. -Pp.385-396 .

191. Brodlie K.W. An assement of two approaches to variable metric methods// Math. Programming. -1972. -V. 7. №12.

192. Broyden C.G. The convergence of a class of double-rank minimization algorithms// J.Inst.Maths.Applies. -1970. -№6. -Pp. 76-79.

193. Damon A. Dynamical System Perspective of Structural Learning with Forgetting/ A. Damon, Miller, M. Jacek Zurada. // IEEE Transactions on Neural Networks, -may 1998,-vol. 9. -pp. 505-551.

194. Davidon W.C. Variable metric methods for minimization//A.E.C. Res. and Develop. Report ANL-5990. Argonne National Laboratory. -Argonne; Illinois. -1959. -P.21.

195. Davidon, W. C. Optimally conditioned optimization algorithms without line searches// Math. Prog. -1975. -№9. -Pp. 1-30.

196. Dixon L.C. Quasi-Newton algorithms generate identical points // Math. Programming. -1972. -V.2. -Pp. 383-387.

197. Elkin R. Convergence theorems for Gauss-Seidel and other minimization algorithms: Ph.D. Diss.// Univ. Of Maryland. College Park.Maryland. 1968.

198. Fletcher R. A new approach to variable metric algorithms// Computer Journal. -1970.-№13.-Pp. 317-322.

199. Fletcher R., Powell M.J.D. A rapidly convergent descent method for minimization // Comput.J. -1963. -V.6. №2. -Pp. 163-168.

200. Fletcher R., Reeves C.M. Function minimization by conjugate gradients // Comput. J. -1964. -V.7. N2. -Pp. 149-154.

201. Goldfarb D.A family of variable metric methods derived by variational means// Mathematics of Computation. -1970. -№24. -Pp. 23-26.

202. Hooke R., Jeeves I. Direkt search solution of numerical and statically problems // J.A.C.M. -1961. -Pp. 212-229 .

203. Kelley J. E. The cutting plane method for solving convex programs// J. SIAM. -1960. -V. 8. №4. -Pp. 703-712.

204. Koza J. R. Genetic Programming: On the Programming of Computers by means of Natural Selections. Mit Pres. - 1992.

205. Lemarechal C. An algorithm for minimizing convex functions// Proc. IFIP Congress-74. Amsterdam, North-Holland. -1974. -Pp.552-556.

206. Lemarechal C. New Variants of Bundle Methods / C. Lemarechal, A. C. Nemirovski, Yu. E. Nesterov // Match. Program. Ser. B. -1995. -V.69.№1.

207. Lemarechal С. Numerical experiments in nonsmoth optimization//Progress in nondif-ferentiable optimization. -1982. -Pp 61-84.

208. Lemarechal C. On extension of Davidon methods to nondifferentiable problems// Math. Programming. Amsterdam: North-Hol-land. -1975. -№3. -Pp. 95-109.

209. Mikhailov M.M. and Krutikov V.N. Method of examining the thermal adjusting coatings of space apparatus // Journal of Advanced Materials (Cambridge interscience publishing). -1996. -v.3, №1,- pp. 21-28.

210. Oren S.S. Self-scaling variable metric (SSVM) algorithms I: Criteria and sufficient conditions for scaling a class of algorithms / S. S. Oren, D. G. Luenberger // Management Science. -1974. -№20. -Pp. 845-862.

211. Oren S.S. Self-scaling variable metric (SSVM) algorithms II: Implementation and experiments//Management Science. -1974. -№20. -Pp. 863-874.

212. Ortega J., Rockoff M. Non linear difference equations and Gauss-Seidel type iterative methods// SIAM J. Numer. Analys. -1966. -v.3. -Pp. 497-513.

213. Powell M.J.D. An efficient method of finding the minimum of function of several variables without calculating derivatives// Comput. J. -1964. -v.7, N2. -Pp. 155-162.

214. Powell M.J.D. Convergence properties of a class of minimization algorithms // Nonlinear Programming. -1975. -V.2. -Pp. 1-27.

215. Rosenbrock H.M. An automatic Method for finding the greatest or least value of a function// Comput. J. -1960. v.3 , N2. -Pp. 175-184 .

216. Saito K.R. and Nakano R. Second-order learning algorithm with squared penalty term. // In Advances in Neural Information Processing Systems 9. -Denver, CO. -1997, -pp.627-633.

217. Schechter S. Iteration methods for nonlinear problems// Trans. Amer. Math. Soc. -1962. v.104. -Pp. 179-189.

218. Schumer M.A. Steiglitz K. Adaptive step size random search // IEEE Trans. Automat. Control. -1968. -v. 13, N3. -Pp. 270-276.

219. Wolfe P. Note on a method of conjugate subgradients for minimizing nondifferentiable functions// Math. Programming. -1974. -V.7. № 3. -Pp. 380-383.