Алгоритмы с аппроксимацией допустимого множества в методе центров

• Автор: Андрианова, Анастасия Александровна
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Казань
• Количество страниц: 132 с.

Глава I Принципы построения алгоритмов с аппроксимацией допустимого

множества в методе центров

§ 1.1 Постановка задачи, исходные положения и основные обозначения

§ 1.2 Свойства вспомогательной функции

§ 1.3 Условия получения точек из множества е -оптимальных решений

§ 1.4 Алгоритмы получения е -оптимальных решений в методе

внутренних центров

§1.5 Алгоритмы получения е -оптимальных решений в методе внешних

центров

§ 1.6 Вычислительные приемы реализации алгоритмов в методе внешних

центров с аппроксимацией допустимого множества

Глава II Использование неполной минимизации вспомогательной функции при построении алгоритмов в методе центров с аппроксимацией
допустимого множества
§ 2.1 Условия получения точек из множества £ -оптимальных решений при
неполной минимизации вспомогательной функции
§ 2.2 Алгоритмы в методе центров с аппроксимацией допустимого
множества и неполной минимизацией вспомогательной функции
§ 2.3 Применение аппроксимации допустимого множества в методе центров
на основе наискорейшего спуска
Глава III Управление процессом минимизации посредством мультипликативной
параметризации в методе центров
§3.1 Роль мультипликативного параметра в методе центров сточной
минимизацией вспомогательной функции
§ 3.2 Использование мультипликативного параметра в методе внутренних
центров с точной минимизацией вспомогательной функции
§ 3.3 Использование мультипликативного параметра в методе внешних
центров с точной минимизацией вспомогательной функции
§3.4 Мультипликативная параметризация в алгоритмах в методе центров
с неполной минимизацией вспомогательной функции
Глава IV Решение тестовых задач
Заключение
Список литературы
Применение методов математического программирования для решения практических задач сопряжено с возникновением ряда вычислительных проблем, которые требуется решить вычислителям для обеспечения эффективной работы методов. Большинство известных на данный момент методов математического программирования ([8, 10, 12, 16, 25, 29, 31, 42, 43, 47, 58, 60, 61, 62, 64, 69, 70]), решают задачу следующего вида:
шш{/(4х£0}, (1)
где £> - {х: X е Яп, #(х) < 0}, я(х) = тах{у; (х), / е {1,2...т)}.
Все методы математического программирования имеют теоретический критерий оптимальности, позволяющий определить, что полученная итерационная точка является решением задачи (1). Однако выполнение условий критерия оптимальности за конечное число итераций гарантируют только методы решения задач линейного ([10, 12, 29, 47]) и квадратичного ([10, 12, 64]) программирования. Но даже эти методы не всегда можно считать эффективными. При решении задач большой размерности они считаются достаточно трудоемкими с точки зрения объема проводимых вычислений.
Методы решения задачи нелинейного программирования обеспечивают сходимость последовательности итерационных точек к решению задачи (1). Однако достижение точки оптимума возможно только в пределе за бесконечное число итераций. Поэтому для практического применения методов важно иметь не только критерий оптимальности, условия которого выполнятся при достижении решения задачи, но и легко проверяемые условия, при выполнении которых гарантируется достижение за конечное число итераций приближенного решения, удовлетворяющего заданной точности е > 0.
Согласно условной классификации, введенной в [19], методы нелинейного программирования можно разделить на две группы. Характерными представителями первой группы являются методы возможных направлений ([43]), методы проекции градиента ([12,42,47]), методы линеаризации ([12,60]) и многие другие. В этих

Z{t,y,p) с X* Отсюда для любых точек z е Z(t,y,p,£ ) в силу соотношения (2.2) выполняются неравенства pg(z)-y й/ +е-е —t + е , или /(г) Оценим разницу между оптимальными значениями целевой функции задачи (1.1) и задачи минимизации функции f(x) на множестве D(p, - а), где ег > 0.
Лемма 2Л. Пусть задача (1.1) удовлетворяет условию С, е>0, функция f{x) удовлетворяет на множестве D условию Липшица с константой L, р>О,ГпД = 0. Пусть число 0 <сг<е зафиксировано так, что П'{р,-а)ф 0. Тогда имеет место неравенство
fp-cr)-f' I 1 рр
где р = min^,1'еЯ}.
Доказательство. Зафиксируем произвольно точку
у" е Argmin{f(x),xe D(p,-a)}. Построим множество U = {x:xeD, f(x) Предположим, что это не так, т.е. существует точка yeU, для которой g(y) < g(y’). Согласно лемме 1.18 выполняется равенство pg(y') + cr = 0, или
g(y*) = . Поэтому

g(y)<~. (2.7)

Из определения множества U для точки у выполняется f(y)£f*(p,-a).
Согласно неравенству (2.7) у е D(p,~ сг) и, следовательно, f(y) > f’(py-cr). Таким