Содержание к диссертации
Введение
1 Принципы построения алгоритмов с аппроксимацией допустимого множества в методе центров. 15
1.1 Постановка задачи, исходные положения и основные обозначения. 15
1.2 Свойства вспомогательной функции. 17
1.3 Условия получения точек из множества є -оптимальных решений 22
1.4 Алгоритмы получения є -оптимальных решений в методе внутренних центров 30
1.5 Алгоритмы получения s -оптимальных решений в методе внешних центров 35
1.6 Вычислительные приемы реализации алгоритмов в методе внешних центров с аппроксимацией допустимого множества 40
2 Использование неполной минимизации вспомогательной функции при построении алгоритмов в методе центров с аппроксимацией допустимого множества 46
2.1 Условия получения точек из множества є -оптимальных решений при неполной минимизации вспомогательной функции 47
2.2 Алгоритмы в методе центров с аппроксимацией допустимого множества и неполной минимизацией вспомогательной функции 58
2.3 Применение аппроксимации допустимого множества в методе центров на основе наискорейшего спуска 67
3 Управление процессом минимизации посредством мультипликативной параметризации в методе центров 84
3.1 Роль мультипликативного параметра в методе центров сточной- минимизацией вспомогательной функции 85
3.2 Использование мультипликативного параметра в методе внутренних центров с точной минимизацией вспомогательной функции 88
3.3 Использование мультипликативного параметра в методе внешних центров с точной минимизацией вспомогательной функции 94
3.4 Мультипликативная параметризация в алгоритмах в методе центров с неполной минимизацией вспомогательной функции 100
4 Решение тестовых задач 108
Заключение 123
- Свойства вспомогательной функции.
- Алгоритмы получения s -оптимальных решений в методе внешних центров
- Алгоритмы в методе центров с аппроксимацией допустимого множества и неполной минимизацией вспомогательной функции
- Использование мультипликативного параметра в методе внутренних центров с точной минимизацией вспомогательной функции
Введение к работе
Актуальность темы. При применении большинства существующих на данный момент методов нелинейного программирования, решающих задачу вида
m\n{f{x),xD}, (1)
где D = {х : х R„,g(x) < 0}, д(х) = max{/;(x)ft = l..m}, специалисты сталкиваются с проблемой обеспечения остановки вычислительного процесса в точке, которая является приближенным решением задачи, удовлетворяющим заданному уровню точности. Конечно, большинство методов нелинейного программирования имеют критерий оптимальности, позволяющий определить, что полученная итерационная точка является решением задачи (1). Однако условия такого критерия выполняются только в искомой точке оптимума, которую можно достичь в общем случае только в пределе. Поэтому для эффективного использования методов оптимизации на практике требуется иметь не только критерии оптимальности, но и легко проверяемые условия, выполнение которых гарантирует получение приближенного решения задачи (1) с заданной точностью е > 0. Если таких условий нет, то приходится останавливать вычислительный процесс на основании эвристических соображений, что может привести к точке, далекой от оптимального решения задачи (1). Поэтому разработка алгоритмов в рамках того или иного метода нелинейного программирования, имеющих практически реализуемый критерий получения е-решения задачи (1), является актуальной проблемой с точки зрения практического применения методов.
Данная диссертационная работа посвящена разработке алгоритмов в методе центров, получающих -решение задачи (1) за конечное число итераций.
Большой вклад в исследование вопросов построения алгоритмов и получения условий достижения точного или е-решения задачи (1) в методе центров и в методе штрафных функций в разное время внесли такие отечественные ученые, как Голыптейн Е.Г.,Евтушенко Ю.Г., Еремин И.П., Жадан В.Г., Заботин Я.П., Ижуткин B.C., Каплан А.А., Князев Е.А., Коткин Г.Г., Сухарев А.Г., Федоров В.В. и другие. В данной работе в качестве вспомогательной функции в методе
центров строится функция максимума. Методы минимизации таких функций разрабатывались Демьяновым В.Ф., Заботиным Я.И., Ко-раблевым А.И., Крейниным М.И., Фазыловым В.Р. Методами последовательной безусловной минимизации, включая метод центров, занимались такие зарубежные ученые, как Бертсекас Д., Гроссман К., Мак-Кормик Г., Мангасариан О.Л., Морисон Д., Фиакко А., Хьюард П.и другие.
Цель работы. Целью работы является разработка алгоритмов в параметризованных вариантах метода внутренних и внешних центров, гарантирующих получение е-решения задачи (1) за конечное число итераций. Основным инструментом при построении алгоритмов является аппроксимация допустимого множества решений.
Методы исследования. При формулировке и доказательстве результатов используется теория выпуклого анализа и математического программирования. Достоверность результатов подтверждается приведенными доказательствами всех лемм и теорем, сформулированных в работе.
Научная новизна Для параметризованных вариантов методов внутренних и внешних центров, использующих в качестве вспомогательной функции функцию максимума, разработаны и обоснованы новые алгоритмы. Основным инструментом в этих алгоритмах является аппроксимация множества допустимых решений, использование которой позволило не только гарантировать получение е-решения задачи (1) за конечное число итераций, проделанных по разработанным алгоритмам, но и получить практически реализуемые правила задания управляющих параметров, применение которых дало возможность получения е-решения задачи (1) не более чем за заданное число процессов минимизации вспомогательной функции метода центров.
Таким образом, на защиту выносятся следующие, полученные автором результаты:
1. Необходимые и достаточные условия задания управляющих параметров для получения е-решения задачи (1) при условии нахождения точного минимума вспомогательной функции, а также при минимизации вспомогательной функции до выполнения заданной точности Ж > 0.
-
Практически реализуемые правила фиксации параметров для получения е-решения задачи (1) за один процесс минимизации вспомогательной функции метода центров, проводимый как до получения абсолютного минимума, так и до достижения заданного уровня точности е > 0.
-
Принципиальные алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров, обеспечивающие получение е-решения задачи (1) за конечное число итераций.
-
Реализуемые алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров, гарантирующие получение е- решения задачи (1) за конечное число итераций при условии минимизации вспомогательной функции до достижения точности ё > 0.
-
Алгоритм в методе внутренних центров, который осуществляет изменение параметров вспомогательной функции после каждой итерации ее минимизации по алгоритму типа наискорейшего спуска и гарантирует получение е-решения задачи (1) за конечное число итераций.
-
Алгоритмы в методах внутренних и внешних центров, которые гарантируют получение е-решения задачи (1) не более чем за N > 0 процессов минимизации вспомогательной функции.
Теоретическая и практическая значимость. Алгоритмы, предложенные и обоснованные в диссертации, обладают важным свойством, которое заключается в гарантии получения приближенного решения с заданной точностью за конечное число процессов минимизации вспомогательной функции метода центров и использовании для прекращения вычислительного процесса практически реализуемых и легко проверяемых критериев остановки. На практике при применении эвристических методов остановки вычислений такие гарантии, как правило, отсутствуют. Это свойство алгоритмов позволяет эффективно применять их для решения практических задач.
Основные подходы к построению и реализации алгоритмов с аппроксимацией допустимого множества в методе центров, используемые в диссертации, могут быть использованы для построения алгоритмов в рамках других методов последовательной безусловной минимизации и при применении других видов вспомогательной функции
в алгоритмах в методе центров.
Апробация работы. Результаты диссертационной работы докладывались и обсуждались на: семинарах Воронежской весенней математической школы «Понтрягинские чтения XIII» (3-9 мая 2002 г.), XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 27-31 мая 2002 г.), Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 24-28 июня 2002 г.), XIII Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 24-28 февраля 2003 г.), Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 1-5 июля 2003 г.), Всероссийской конференции «Алгоритмический анализ неустойчивых задач»(Екатеринбург, 2-6 февраля 2004 г.), ежегодных научных конференциях КГУ в 2001-2004 гг.
Публикации, Основные результаты изложены в 10 работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения. Библиография включает 89 наименований. Общий объем диссертации составляет 132 страницы.
Свойства вспомогательной функции.
В данном параграфе приводятся некоторые свойства вспомогательной функции вида F(x,t,y,p) для задачи (1.1) и множества Z(t,y,p). Основное внимание уделяется условиям, выполнение которых обеспечивает, что пересечение множества Z(t,y,p) с множеством допустимых решений D не является пустым множеством. Вначале приведем лемму, утверждение которой неоднократно будет использовано при дальнейшем изложении. Лемма 1.1. Пусть функции p(x),i/s(x) определены и непрерывны в Rn, Ф(х) = тзх{ф(х),іу(х)}, точка z является точкой локального минимума функции Ф(х), причем имеет место неравенство р(г ) y/{z ). Тогда z является точкой локального минимума функции р{х). Доказательство. В силу непрерывности функций (х) и у/(х) существует окрестность сО\(г ) такая, что р{х) yf(x) для всех хєсох(х ). Кроме того, так как z является точкой локального минимума функции Ф(х), существует окрестность a 2(z ), для которой J (z ) Ф(х) для всех точек xeo 2(z ). Таким образом, для всех точек х из окрестности, Ф = сох о й 2 выполняется неравенство # (У) = Ф(г ) Ф(х) = $?(х). Отсюда следует, что z - точка локального минимума функции р{х). Лемма доказана. Далее в этом параграфе предполагается, что задача (1.1) удовлетворяет условию А.: Лемма 1.2, Пусть geM и параметры p Q,t,y зафиксированы так, что существует точка z GZ(t,y,p), z iD . Тогда f(z) — fZ.pg{z)-y. Доказательство. Предположим, что справедливо неравенство f(z) -1 р g(z) - у, В этом случае согласно лемме 1.1 z является точкой локального, а так как g є М, то и абсолютного минимума функции g(x). Однако g(z) 0, тогда как согласно условию А У 0, и, следовательно, существует точка х, для которой g(x) 0. Получено противоречие. Следовательно, f(z) t pg{z) — у. Лемма доказана. Лемма .1.3. Пусть g є М и параметры р 0, t,y зафиксированы так, что существует точка z Z{t, ytp), z &D. Тогда f(z) f . Доказательство. Докажем сначала, что, если точка z &Z(t,y,p) такова, что Z&D, то выполняется неравенство f(x) pg(x) - у для всех х є D. Допустим, что существует точка y D, для которой выполняется неравенство f(y) tupg(y)-y. Тогда, так как g(y) 0, имеем F(y,t,y,p) = pg(y)-y .-у. С другой стороны, из определения функции F(xJ,ytp) следует, что F(z,t,y,p) pg(z)-y, а так как по условиям леммы g(z) 0, то F(ztt,ytp) -y. Кроме того, z eZ(t,ytp), а, следовательно, справедливо неравенство F(z,t,y,p)F(xJ,y,p) для любых хєЛ„, в том числе и для точки у. Из указанных неравенств вытекает противоречивое неравенство — у F{2tt,y,p) ,F{y,t,y,p)-u-y.
Следовательно, f(x)-1 pg(x) — у для всех xeD. Из полученного неравенства следует, что для любых точек хеО,в том числе, для которых f(x) = f , выполняется f(z) — t F{z,t,y,p)-uF(x,t,y,p) = f{x) t. Лемма доказана. Лемма 1.4. Пусть /єМ, Yr\D = 0 и пусть параметры p Q,y,t зафиксированы так, что существует точка z =Z(t,y,p), zeD. Тогда f{z) pg(z)-y. Доказательство. Предположим, что выполняется неравенство f(z) t p g(z) -у .В этом случае согласно лемме 1.1 z. является точкой локального минимума функции /(х), но так как / є М, то z є Y. С другой стороны, по условиям леммы zєD. Таким образом, zefnD, что противоречит условию Y п D = 0. Лемма доказана. Лемма 1.5. Если параметры p 0,y,t зафиксированы так, что F{z,t,y,p) —y, где z є Z(f, у, р), то Z(t, у, p)czD\ Доказательство. Доказательство очевидным образом следует из определения функции максимума. Действительно, если для зафиксированных значений параметров. F(z, t, у, р) —у, то для любой точки z є Z(t, у, р) выполняется pg(z) у . F(z, t,y, р) -у, или g(z) 0. Следовательно, Z(t,y, р) с . Лемма доказана. Далее в этом параграфе будем считать, что параметр р О зафиксирован произвольным образом. Лемма 1.6. Если параметры t,y зафиксированы так, что y t-f , то Z(t,y,p) zD. Доказательство. Предположим, что существует точка z eZ(t,y,p) такая, что z D. Для этой точки рg(z) — у -у, поэтому из определения функции максимума вытекает, что F(zyt, ytp) p g{z) -у -у. При этом для произвольной точки х є Хй имеем, во-первых, pg(x ) y -yt так как g(x ) 0, во-вторых, fix )-/-/ по условиям леммы. Следовательно, F(x ,t,y,p)—у. Следовательно, имеет место цепочка неравенств F(x ,t,y,р) —у F(z,t,y, р), из которой следует противоречие с тем, что z є Z(t,ytp). Таким образом, для любых точек z є Z(t,y}p) выполняется z є D, или Z(/, y,p)cD. Лемма доказана. Из утверждения леммы 1.6 вытекает Следствие. Если Z(t,ytp)\D 0t то параметры зафиксированы так, что Лемма 1.7. Пусть /єМ. Если Yr\D = 0 и:2(ґ, ,/?)п 0, то параметры зафиксированы так, что у - Доказательство. Зафиксируем произвольно точку геZ(t,у,p)r\D: Так как ze , для этой точки выполняется, во-первых, pg(z) 0, во-вторых, f(z) f . Поэтому в силу леммы 1.4 имеет место цепочка неравенств f , f[z) t р g(z) - у -у, из которой следует, что y t-f . Лемма доказана. Сформулируем следствие из утверждения леммы 1.7. Следствие. Пусть / є М. Если параметры зафиксированы так, что у t - / , то Yr\D 0 или Z(t,y,p)nD = 0. Лемма 1.8. Если Yr\D 0 и параметры зафиксированы так, что / — / , то Z(tty}p)ntD=0,причем Xо сZ{tiyiр) и Z(/j,p)cK. Доказательство. Зафиксируем произвольно точку л: є Х0. Так как Y п D Ф 0, X Q с Y. Поскольку х eDt имеет место неравенство pg{x) 0. Поэтому согласно условиям леммы справедливо f(x ) -y pg(x)-y. Следовательно, F(x ,t,yip) = f(x ). Так как х zY, для любых точек xeRn выполняются неравенства f(x )й/(х) и, следовательно, F(x ,t,ytp) = f(x ) f(x) , F(x,t,y,p). Таким образом, х Z{t,ytp).
Поскольку точка х ЕХ$ была зафиксирована произвольным образом, Х0 zZ(t,y,p) и Z(t,y,p)r\D 0, так как для задачи (1.1) согласно условию А Х0 0. При этом для любых точек z eZ(t,ytp) имеет место цепочка неравенств f{z) — t F{zttiy p) ,F{x ,t,Y,p) = f{x ),z.Ta.K как х єУ, все неравенства в этой цепочке выполняются как равенства, т.е. f(z) = f для всех z є Z(t,y,p). Таким образом, Z(t,y, p) zY. Лемма доказана. Лемма 1.9.Пусть / єМ и Y r\D = 0. Справедливы утверждения: 1. Для того чтобы Z(t,y,p) с D, необходимо и достаточно, чтобы параметры t,y были зафиксированы так, что у t-f . 2. Для того чтобы Z(t,y,p)r\D = 0, необходимо и достаточно, чтобы параметры t, у были зафиксированы так, что у t — f „ і 3. Невозможно одновременное выполнение условий Z(tiyip)r\D 0 и Z(t,y,p)\D 0. Доказательство. Достаточность в утверждении 1 леммы следует из леммы 1.6. Докажем необходимость. Пусть параметры были выбраны так, что Z(t, y,p) Dt или Z(t,y,p)r\D&0. Тогда согласно лемме 1.7 имеет место неравенство y t-f .. Утверждение 1 леммы доказано. Докажем теперь утверждение 2. Необходимость. Пусть Z(t,y,p)r\D = 0. Следовательно, Z(t,y,p) \ D = Z(t,y,p) & 0. Поэтому в силу следствия к лемме 1.6 имеет место неравенство y t — f. Пусть теперь y t — f .Так как Кп = 0, согласно следствию к лемме 1.7 должно выполняться Z(t,y,p)r\D = 0. Таким образом, утверждение 2 доказано. Предположим, что утверждение 3 леммы неверно. Тогда получим, что согласно первому условию по лемме 1,7 у t — f ,вто время как согласно второму условию в силу следствия из леммы 1.6 y t-f . Полученное противоречие доказывает утверждение 3 леммы. Лемма 1.10. Если Тп 0, то Z(t,y,p)nD 0 при любых фиксированных значениях параметров t, Доказательство. Действительно, если параметры t, у зафиксированы так, что у t- f , то согласно лемме 1.6 Z(t y, p) zD и утверждение леммы справедливо. Если же параметры зафиксированы таким образом, что у t f , то так как У г\ D Ф 0, в силу леммы 1.8 Z(t,y,p) г\ D Ф 0, Лемма доказана. Лемма 1.11. Для того чтобы Z{f,7,/?)nD=0, необходимо и достаточно, чтобы У г\ D = 0 и параметры t,y были зафиксированы так, что у t — f . Доказательство. Пусть Z(t,у,р)пD = 0, т.е. Z(t,y,p)\D = Z(t,y,p) 0. Тогда согласно следствию из леммы 1.6 параметры зафиксированы так, что y t f . Если теперь предположить, что У n D ф 0, то согласно лемме 1.8 Z(t,y,p)r\D 0, а это невозможно. Таким образом, Уr\D = 0 и необходимость доказана. Если же YnD = 0 и у t — / , то согласно следствию из леммы 1.7 Z(t,y p)r\D = 0.. Лемма доказана. 1.3 Условия получения точек из множества є -оптимальных решений В данном параграфе доказаны необходимые и достаточные условия получения решения задачи (1.1) с заданной точностью по функционалу.
Алгоритмы получения s -оптимальных решений в методе внешних центров
Данный параграф посвящен построению принципиальных алгоритмов в методе внешних центров с аппроксимацией допустимого множества, на основе которых в дальнейшем строятся реализуемые алгоритмы в главе II. Как и в алгоритмах в методе внутренних центров, предложенных в параграфе 1.4, здесь используется критерий остановки, условия которого гарантировано выполняются за конечное число итераций в точке, являющейся решением задачи (1.1) с заданной точностью є 0. Алгоритмы в методе внешних центров укладываются в схему, аналогичную схеме алгоритмов в методе внутренних центров. Определяются правила фиксации; параметров tk,ук,рк (к 2:0), при этом правила фиксации параметра tk выбираются таким образом, чтобы организовать приближение извне допустимого множества. Для; каждого номера к 0 точка хк+х определяется по правилу хк+1 є Z(tk,-ук,рк). При построении алгоритмов в методе внешних центров аппроксимация допустимого множества осуществляется путем использования множеств вида D(p,-у), где у 0,р 0. Для указанных множеств допустимое множество D является окрестностью. Критерий остановки, применяемый в алгоритмах данного параграфа, определен условиями теоремы 1.3. Согласно этим условиям вычислительный процесс, проводимый по предложенным алгоритмам, продолжается до тех пор, пока не будет получена итерационная точка, принадлежащая множеству допустимых решений. Полученная таким образом точка является є -оптимальным решением задачи (1.1). В [19] для функции расстояния вида F(x,t,0,\) были предложены правила изменения параметра tk в методе внешних центров. По своей форме они совпадают с правилами фиксации параметра tк в методе внутренних центров. Правила изменения параметра tk{ki.O). Используем эти правила для построения алгоритмов в методе внешних центров с аппроксимацией допустимого множества. Алгоритм 1.4. (алгоритм в методе внешних центров, основанный на правиле 1 изменения параметра tk). Фиксируются точка xQ Dt для которой /(х0) , f , точностью 0, число Se(0;s]. Если найдена точка хк ( 0), переход к точке хк+1 осуществляется по следующей схеме. 1. Выбираются значения параметров рк 0, ук = [S;s - рк m\n{g{x\x ЕХ Є}]. 2. Находится точка хы е Z(f(xk),-ук ,рк), 3. Если хк+1 є D, то хк+1 є ХЕ. Процесс решения завершен. 4. Осуществляется переход к п. 1 при к, замененном на к +1.. Следующая теорема обосновывает алгоритм 1.4, Теорема 1.9.
Пусть задача (1.1) удовлетворяет условию A, f,geM, для є 0 множество Хе ограничено и последовательность {хк} вырабатывается по алгоритму 1.4. Тогда найдется такой номер N2.0, что для точки xN+l выполнятся условия п.З алгоритма и xN+l eJr Доказательство. Докажем, что существует номер N 0 такой, что Предположим, что xk+i D для любого номера к 0. Тогда в силу леммы 1.2 и леммы 1.3 для любых номеров к 0 справедливы соотношения В силу (1.21) числовая последовательность {f(xk}} ограничена сверху. Так как jCjt+i ), то g(xk+i) 0. Следовательно, поскольку ук #, из (1.20) получаем, что для любого номера й0 вьшолняется неравенство f(xk+\) — f(xk) $, что противоречит ограниченности сверху последовательности {/()}. Следовательно, существует номер N 0, для которого выполняются включения (1.19). Поскольку согласно (1.19) xN D, по лемме 1.3 при N 0 или в силу правила фиксации начальной точки при N = 0 выполняется неравенство f(xN) Lf. Кроме того, согласно пункту 1 алгоритма имеет место соотношение yN s-pN mm{g{x\x є X }.. Следовательно, выполняются условия теоремы 1.3 при 7 = 0. Таким образом, для полученной точки xN+l є D имеет место xN+i є Хє. Теорема доказана. Покажем, что при построении алгоритмов в методе внешних центров правило 2 изменения параметра tk эквивалентно правилу 1. Лемма 1.16. Пусть задача (1.1) удовлетворяет условию A, f,g є М, для є 0 множество Хе ограничено, t0 f , 5 є (0;] и последовательность {хк} строится по схеме хк+1 є Z(tk ,-ук,рк), где для любого номера к 0 принимается рк 0, Ги {S\s-pk min{g(x),xe ДГ }], fi+1 =tk + F(xk+utk,-yk,pk). Тогда справедливы утверждения; 1. последовательность {хк} может быть построена по алгоритму 1.4. 2. найдется такой номер N 0, что точка xN+l є D, причем xN+\ є Х. Доказательство. Допустим, что найдена точка хк (к 0) и значение tk f . Если xfc+] е , то согласно правилам фиксации параметров по теореме 1.3 при fj-0 получим, что хм еХе, и вычислительный процесс может быть закончен. Если же хк+1 ё D, тогда, во-первых, согласно лемме 1.2 справедливо F(xk+l,tk, yk,pk) = f(xk+l) tk, и, следовательно, по правилу фиксации параметра h+\ к+ F(xk+i h їкіРк) = /(хы)» во-вторых, в силу леммы 1.3 выполняется неравенство tk+l = f(xk+l) f , Следовательно, для любых номеров к 0 В силу условий леммы правила фиксации параметров ук, рк совпадают с правилами, которые используются в алгоритме 1.4 . Отсюда и из включения (1.22) следует справедливость утверждения 1 леммы. Утверждение 2 леммы непосредственно следует из утверждения 1 и теоремы 1.9. Лемма доказана. Алгоритм 1.5. (алгоритм в методе внешних центров, основанный на правиле 3 изменения параметра tk ). Фиксируются точностью 0, числа гє(0;1), Se(0;s] и tQ й f S. Если найдено значение tk (к 0), переход к значению tk+l осуществляется по следующей схеме, 1. Выбираются значения рк 0, ук e[S;e- рк mm{g(x\ xeXe} + S]. 2. Находится точка хк+1 є Z(tk , ук ,рк). 3. Если хк+х є D, то хк+ї є Х. Процесс решения завершен. 4. Вычисляется tM = т/(хм ) + (1- r)tk. 5. Осуществляется переход к п.1 при к, замененном на к +1. Факт получения є -оптимального решения задачи (1.1) за конечное число итераций, проделанных по алгоритму 1.5, обосновывает Теорема 1.10. Пусть задача (1.1) удовлетворяет условию A, f,g =M, для є 0 множество Хе ограничено и последовательность {хк} вырабатывается по алгоритму 1.5. Тогда найдется такой номер N 0, что для точки xN+l выполнятся условия п.З алгоритма 1.5 и х +1 є Хе.
Доказательство. Пусть номер к 0 таков, что хк+х D. Тогда, поскольку g(xk+i) 0 и yhtd, в силу леммы 1.2 для этого номера имеет место цепочка неравенств /(хм) к Рк8Іхк+0 + Ук 7к - Отсюда согласно правилу фиксации параметра tk получаем ы - h = f{xk+])k) х5 . (1.23) Кроме того, в силу следствия к лемме 1.6, так как хы &D, параметры (к,ук зафиксированы так, что выполняется -ук tk- f . Следовательно, так как ук 5, имеет место / / -у Ґ 5. (1.24) Допустим, что для любого номера к Ї: О имеет место хк+[ D. Тогда неравенства (1.23) и (1.24) справедливы для любого к 0. Однако из соотношения (1.23) следует, что числовая последовательность {tk} неограниченно возрастает, в то время как согласно (1.24) данная последовательность ограничена сверху конечной величиной f -S. Получено противоречие, которое доказывает, что существует такой номер N 0, xN+l є D. Поскольку условия пункта 3 алгоритма впервые выполняются для номера N 0, xN ). Тогда tN , f -S в силу (1.24) при N 0 или согласно правилу фиксации начального значения t0 при N - 0. Кроме того, согласно пункту 1 алгоритма имеет место соотношение yN Е-рн mm{g{x),x є Хе} + 5. Таким образом, для номера N 0 выполняются условия теоремы 1.3 при ц = д и, следовательно, имеет место xN+i є ХЕ. Теорема доказана. 1.6 Вычислительные приемы реализации алгоритмов в методе внешних центров с аппроксимацией допустимого множества Непосредственное применение на практике алгоритмов, предложенных в параграфе 1.5 данной главы, требует конкретизации трех моментов. Во-первых, требуется указать способ фиксации точки начального приближения: x0&Dt удовлетворяющей неравенству /(х0) / , для алгоритма 1.4 и значения /0 / —5 для алгоритма 1.5. Во-вторых, правила фиксации параметра ук пункта 1 алгоритмов используют неизвестную величину min{g(x),x =Xe), которую для применения алгоритмов для решения практических задач необходимо оценить. Одним из очевидных способов решения этой проблемы является выбор в алгоритме 1.4 параметра по правилу ук е[S;s], а в алгоритме 1.5 - ук s[S;s + S]. Однако, так как min{g(x),x єХє} 0 и рк 0, такой способ может существенно сократить интервал возможных значений ук. Чтобы избежать подобного сокращения, целесообразнее получить более точную оценку величины min{g(x),xeХе} В-третьих, при выполнении пункта 2 алгоритмов требуется найти точку абсолютного минимума функции вида F{x, t, у,р), что можно осуществить в общем случае только за бесконечное число итераций.
Алгоритмы в методе центров с аппроксимацией допустимого множества и неполной минимизацией вспомогательной функции
В данном параграфе для получения решения с заданной точностью є 0 задачи (1.1), удовлетворяющей условию С, предлагаются алгоритмы в методах внутренних и внешних центров с аппроксимацией допустимого множества и неполной минимизацией вспомогательной функции до выполнения заданного уровня точности є 0. Эти алгоритмы являются- реализацией принципиальных алгоритмов, предложенных в главе I диссертации. Как и принципиальные алгоритмы главы I, предложенные здесь алгоритмы используют в качестве критериев остановки получение итерационной, точки, попадающей в множество, которое является разностью допустимого множества и множества, которое является аппроксимацией последнего. Доказано, что за конечное число итераций, проделанных по алгоритмам данного параграфа, выполняются условия критериев остановки, и полученное таким образом приближенное решение задачи (1.1) удовлетворяет заданной точности s 0. Алгоритм 2.1. (реализация алгоритма 1.1 в методе внутренних центров). Фиксируются точка jt0 є D , числа є О, є 0, для которых є 4є+ L 2. Выбирается хш є Z(f(xk),ук,рк,г). 3. Если хк+і є. ІУ, то xk є Xe. Процесе решения завершен. 4. Осуществляется переход к п.1 при к, замененном на к +1. Для каждого номера к 0 поставим в соответствие точке jcft+i є Z(/(jfк ),ук,рк,є) произвольно фиксированную точку zk+l є Z(f{xk),ук,рк). Обосновывают алгоритм 2.1 следующие утверждения. Лемма 2.5. Пусть задача (1.1) удовлетворяет условию A, f,g&Mt для зафиксированного є 0 имеет место Го)(1, ) = 0, зафиксировано є 0, для которого выполняется неравенство є 2є , 0 - 2 , значение f0 / удовлетворяет условию f(x) tQ g(x)-S для любых xe{x;xeR„,g(x) = min{g(x),xeR„}}, S + e у є-є , p \f зафиксирована точка у є D\ zeZ(f(y),y,p), xeZ(f(y),y,p,s ) и / , max{l;—-=-;/ } Пусть выполняются условия Тогда справедливы утверждения: Доказательство. Согласно лемме 2.3 в силу второго соотношения (2.17) получим, что Тогда согласно лемме 1.1 имеет место Кроме того, так как геД {р,-), выполняется неравенство pg(z) + e 0. Следовательно, для точки xeZ(f(y)ty,p}) согласно определению функции максимума и (2.19) получаем или g(x) 0. Отсюда следует, что число рх определить можно и рх =-. Следовательно, х є D (plr s ). Утверждение 1 доказано.
Докажем утверждение 2. Согласно теореме 2.2 в силу (2.18) существуют числа Ъх, Ь2 є [0; є ], для которых имеет место равенство f{x) = /(г) - +. Отсюда, так каку $ + є ,ивсилу(2Л9)следует f(x)-f(y) = pg(z) y+Ь Ь2 : у + є -S, или f(x) . f(y) - 8. Лемма доказана. Теорема 2.4. Пусть задача (1.1) удовлетворяет условию С, є 0, множество Хє является ограниченным, функция f(x) удовлетворяет условию Липшица с константой L на множестве Д FoD(l,#) = 0, min{g(x)txeХє) min{g(x\x eR„), p = тт{ ,i є H} f для зафиксированного є 0 имеет место D (\t—e ) 0, точка д:0 D удовлетворяет условию /(л) - f(xQ ) g(;c) для любых х є {х: х є Я„, g(x) = min (g(jc), x є Я„}} и последовательность {хА} построена по алгоритму 2.1. Тогда существует номер N 0, для которого выполняются условия п.З алгоритма, и є Хє. Доказательство. Пусть г0 = х0, 0 = Го Тогда г, є Z(/(z0), 0, / ), где 0 є[ У;-2 -I,—]. Пусть Z] є (Л е)- По правилу фиксации параметра р0 If/ jc0 є D (Po -) Тогда для номера к = 0 выполняется zk+l є D (pk-e ) и Следовательно, в силу леммы 2.5 JCJ eD (plt-e ) и f(xl)f(x0)-S f(x0), т.е. (2.20) выполняется и для номера fc = 1. Пусть для некоторого номера к 0 имеют место соотношения (2.20) и Тогда по лемме 2.5 для номера к +1 выполняются соотношения (2.20). Учитывая далее, что согласно определению zk eZ(/{ _), „],pw) и xkGZ(f(xk Xyk ltpk_u)f в силу теоремы 2.2 и леммы 2.3 получим, что существуют числа b b є[0;є ] такие, что Z(f(xk\yk,pk)= Z(f(zk),yk,pk), где У к - У к + ЬЇ 2- Теперь, так как по определению zk+l є Z(f(xk \ук,Рк), имеем zk+x eZ(f(zk),yk,pk). Так как ук 2.6 + є, получаем, что yk=yk+b\ -Ъ\ъ. к + l выполняется(2.20) и zk+l eZ(f(zk),yk,pk) при yk е[8\є-2є -LA— ]. Таким образом, методом математической индукции доказано, что пока для номеров АйО выполняется гк+1єП(ркз-є), для номера к+l имеют место соотношения(2.20)и zk+l є Z{f{zk\yk,pk) при ук є[8,є-2є -LA—]. Пусть єj = є - є - LA—. \М Заметим, что очевидным образом множество Z{f{zk\yktpk) для любого номера к 2: 0 является множеством точек абсолютного минимума функции F(x,f(zk),ak) = mw.{f(x)-f(zk),pkg(x) + -ak}, где ак=ук+є , причем, если ук e[S;e-2s -Li—], то ак є[5 + є ;є{\. Функция F(x,f(zk\ak) является вспомогательной функцией для задачи тіп{/(л:)гл; є D(pk —є)}. Так как для номеров к 0, для которых zk+1 еІУ(рк) є), имеет место zk+1 &Z(f(zk),yk,pk), получим, что zk+i точка абсолютного минимума функции F(x,f(zk),ak).
Заметим также, что согласно утверждению 2 леммы 2.2 для всех к 0 множество X (pkt-e) является ограниченным. Допустим, что для любого номера к 0 имеет место неравенство Поскольку D(l,-) zD(pk-)czD имеют место соотношения min{g(x),x єХ (рк-є)}0 и D (pk,-e ) 0. Поэтому, а также так как v є , для любого номера к2.0 выполняется ак f(zk)-f (pk-). Поскольку zk+i є Z(f(zk\yk pk) является также точкой абсолютного минимума функции F(x,f(zk)tak), построенной для задачи минимизации функции f(x) на множестве D(pkt-e), согласно лемме 1.6 zk+l є D(pkr-e). Более того, zk+l є П(рк, є). Действительно, согласно лемме 1.4 имеет место неравенство ДгА+])-/(гА) , pkg(zk+i ) + е -ак. Теперь, если предположить, что zt+l ч П (pk t-e ), т.е. pkg(zk+i)+s =0, то F(zk+l,/(гк),ак) = -ак. Отсюда, так как из (2.21), в частности,, следует неравенство f (%%) / (Pt s) согласно теореме 1.4, получим f(zk ) й / (рк —є ) + ак. Однако из (2.21) также следует, что f{zk ) / (рк ,-) + ак.. Получено противоречие. Следовательно, zk+l є ІУ(рк-є) для любого номера к й 0. Выше было доказано, что, если zk+i є ІУ(рк,-є ) для номера к 1 0, выполняется (2.20). Следовательно, так как D(pk,-e)cD, в силу утверждения 1 леммы 2.5 для любого номера к; 0 выполняется неравенство f{xk+i) f , откуда вытекает, что числовая последовательность {/(хк)} является ограниченной снизу. С другой стороны, согласно утверждению 2 леммы 2.5 для любого к 0 выполняется f(xk+i) f(xk) $ Ч1 означает неограниченное убывание последовательности {/(хк)}. Полученное противоречие доказывает, что существует номер К2.0, для которого выполняется неравенство pKmm{g(x),xbX\pK -7)) + 7-6 Zf (pK 7) + аК -/(). (2.22) в частности, неравенство (2.22) может выполняться в силу фиксации начальных значений при К = 0. Если, к тому же, выполняется / (РК,-Є) + ХК -f(zK) 0, то согласно теореме 1.1. zK+leX (pK-). А поскольку zK+leZ(f(zK),yK,pK)t где уК=аК-е, согласно теореме 2.2 по построению получим, что хк+1 є Z(f(zK\yKtpKts ). Тогда в силу теоремы 2.3 хк+1 є Х , Пусть / (рк -є ) + ак- f(zK) 0. Докажем, что zK є D(pK ,s). Если К = 0, то Zjr є (/?,—) в силу начальной фиксации точки z0=x9. Если if 0, то поскольку неравенство (2.22) выполняется впервые для номера /Г, для номера К-1 имеет место (2.21) и, следовательно, zK є &(рк_ъ-е) и хк є П(рк-є ). Тогда, так как Рк Рк-і, имеем / ry(zjr) + ff РАТ-ІЯО ) или 2кеГ (Рк-) Следовательно, поскольку 5 ,. для точки zK еЩр -е) выполняется неравенство f{zK) f {pK-s)+eit т.е. Zjf є X (рх,-). Кроме того, так как / (Рк Ё ) / Рк Ь согласно лемме 2,1 получим Теперь заметим, что в; силу теоремы 2.2 f(xK) = f(zK) — 6j + &2 » ГДС bf ,Ь% є[0;]- Следовательно, f(xK) /(zK) + / +є-є +е =/ + є Отсюда, так как хк еП {рк s )cD, имеет место хк є Xff. Таким образом, существует номер Г 0, для которого хк єХе. Докажем далее, что существует номер N ї К, для которого будут выполнены условия пункта 3 алгоритма. Допустим, что для любого к К имеет место хк+1 є ГУ.
Использование мультипликативного параметра в методе внутренних центров с точной минимизацией вспомогательной функции
Оценки параметров (3.1) и (3.2), полученные в предыдущем параграфе, имеют принципиальный, теоретический характер, поскольку содержат неизвестные величины. В данном параграфе будет показано, что для задач, удовлетворяющих условию С или условию D, можно получить более грубые, но практически реализуемые варианты этих оценок. На основании полученных результатов будут построены алгоритмы в методе внутренних центров, главной особенностью которых является получение решения задачи-(1.1) с заданной точностью s 0 не более чем за заданное число N 0 процессов минимизации функции вида F{xJ,y,р). Эти алгоритмы будут также использовать критерий остановки, сигнализирующий о том, что є -оптимальное решение задачи (1.1) получено на итерации с номером, меньшим N 0. Для алгоритмов в методе внутренних центров таким критерием, как ив алгоритмах параграфа 1.4, является получение итерационной точки, не принадлежащей множеству П. В этом случае гарантируется, что предыдущая итерационная точка является решением задачи (1.1) с точностью 0. Построенные в этом параграфе алгоритмы все еще будут носить принципиальный характер, поскольку минимизацию вспомогательной функции в них предполагается производить до получения точного минимума. Для построения практически реализуемых вариантов оценок (3.1) и (3.2) нам требуются оценить сверху и снизу величину f , а также оценить сверху значение mm{g(x),x є Хе}. Последнюю оценку в случаях, когда задача (1.1) удовлетворяет условию С или условию D, мы получаем из результатов лемм 1.20 и 1.21 соответственно. Для получения оценки значения / сверху достаточно, к примеру, выбрать точку z є D. Тогда f(z) Один из известных способов построения оценки снизу величины / указан в параграфе 1.6 диссертации. Строится функция Ц (х) = max{/(х) + d,g(x)}, где d-константа, выбранная так, что f(x) + d g(x) для всех х є D. Если произвольно фиксированная точка ysArgmin xXxєRn] такова, что у&D, то f(y) f , В противном случае точка у является точным решением задачи (1.1). Далее числа, оценивающие значение / сверху и снизу, будем обозначать / и f соответственно. Лемма 3.3. Пусть задача (1.1) удовлетворяет условию В, є 0, Хе - ограниченное множество и известно число Л 0 такое, что min{g(x),x є Хє) , -Л. Если параметры p 0ty,t зафиксированы таким образом, что Доказательство.
Умножим третье неравенство (3.4) на величину -А 0. Отсюда и из оценки f ,f получим цепочку неравенств — Арйе + 5 + f e + S + f . Принимая теперь во внимание, что min{g(x),xХе) й—А и р 0, получим соотношениярmin{g(x),x є Хе} —Ар ,s + S + f , что в свою очередь в силу леммы 1.17 приводит к неравенству (3.1), которое вместе с соотношениями (3.4) согласно лемме 3.1 означает, что Z(t,y,p) с Хе. Лемма доказана. Для задач (1.1), удовлетворяющих условию С или D, условия леммы 3.3 принимают более конкретный вид. Теорема 3.1. Пусть задача (1Л) удовлетворяет условию С, 0, Х - ограниченное множество, функция f(x) удовлетворяет на Xs условию Липшица с константой и min{g(x),jc є Х є} т\ъ\%{х\х є R„}.. Если параметры р 0,y,t зафиксированы так, что где fi = min{# ,і є Я}, то Z(t,r,p) с Х е. Доказательство. Согласно лемме 1.20 в качестве числа А 0 в неравенствах №2 (3.4) может быть использовано значение - 0. Отсюда получаем, что соотношения (3.4) эквивалентны соотношениям (3.5). Следовательно, согласно лемме 3.3 справедливо включение Z(tty,p) а Хє. Теорема доказана. Теорема 3.2. Пусть задача (1.1) удовлетворяет условию D, 0, Хе -ограниченное множество, функция fix) удовлетворяет на множестве Хе условию Липшица с константой L и r {g(x\x є Xе} Ф mm{g(x),x є Rn}, Если параметры p 0,y,t зафиксированы так, что Доказательство. Соотношения (3.4) эквивалентны соотношениям (3.6), поскольку в силу леммы 1.21 значение Ф(ут) 0 может быть принято за число А 0 в третьем из неравенств (3.4). Поэтому согласно лемме 3.3 имеет место включение Z(t,y,p) с Хе. Теорема доказана. Правила фиксации параметров, определенные соотношениями (3.5) и (3.6) для задач, удовлетворяющих условиям С и D соответственно, являются уже практически реализуемыми и позволяют получить є -оптимальное решение задачи (1.1) с помощью одного процесса минимизации функции вида F(x,t,y,p). Однако значение параметра р, используемое при этом, может оказаться достаточно большим, что может привести к овражному характеру минимизируемой функции F xJ , р) и трудностям при ее минимизации. Для уменьшения влияния больших значений параметра р построим алгоритмы в методе внутренних центров, гарантирующие получение є -оптимального решения задачи (1.1) не более чем за заданное количество N 0 процессов минимизации вспомогательной функции вида F(x,t,y,p). Алгоритмы будут построены отдельно для решения задач, удовлетворяющих условию С, и для решения задач, удовлетворяющих условию D. Алгоритм 3.1. (алгоритм в методе внутренних центров для решения задач, удовлетворяющих условию С). Фиксируются точка х0 є D, точность є О, число 8 є (0; є], Л/ 0 - число итераций, за которое должно быть получено є -оптимальное решение задачи (1.1), р_!=0. Задается возрастающая функция р(и), для которой (1) 0, (ЛГ) 1. Определяются правила фиксации параметра tk=T(tk_uxk), фиксируется значение /0 = Т0(х0): Полагается А = 0. 1.. Вычисляется значение Ск г= , принимается рк=тах{ р(к + 1)Ск рк }. 2. Фиксируется число у к є [S;e].. 3 Выбирается точка хк+1 є 2{tk,ук,рк). 4. Если k = N-l и хкі.і є ГУ, то хк+1 є Xs. Процесс решения завершен. 5. Если хк+1 & D\ то хк єХє.
Процесс решения завершен. 6. Определяется значение tk+l = T(tk,xk+l). 7. Осуществляется переход к п. 1 при к, замененном на к +1.. Алгоритм 3.2. (алгоритм в методе внутренних центров для решения задач, удовлетворяющих условию D). Фиксируются точка i0eD, точностью 0, число Зєф е], N 0 - число итераций, за которое должно быть получено є -оптимальное решение задачи (1.1), р_1=0. Задается возрастающая функция р(и), для которой р(ї) 0, p(N)2.1. Определяются правила фиксации параметра tk = 1(tk_uxk)t фиксируется значение t0 = Т0 (х0).. Полагается к = 0. 1. Вычисляется значение Ct = =f , принимается рк = тах{ р(к + ї)Ск Рк-\} 2. Фиксируется число Yk е\$\\- 3. Выбирается точка хкя є Z(tkiyk,pk). 4. Если k = N l и xk+l є 0,то xk+l є Xs. Процесе решения завершен. 5. Если хк+і . П, то хк є Хе. Процесс решения завершен. 6. Определяется значение /t+1 = T(tksxk+1). 7. Осуществляется переход к пункту 1 при к, замененном на к +1. Замечание 1. Перед началом вычислений по алгоритмам 3.1 и 3.2 необходимо задать возрастающую функцию р(и), удовлетворяющую условиям )(1) 0,q (N) 1. Аналогичный прием был применен в [41] применительно к методу сдвига штрафов. Самым простым примером функции, удовлетворяющей указанным условиям, является функция (и) = —. Другим примером могут служить функции вида р{и) = — , где q 1 - целое число. \N) Замечание 2. В алгоритмах 3.1 и 3.2 требуется конкретизировать, каким образом задаются правила фиксации параметра tk=T(tk ,xk) и фиксируется значение /0=Т0(л0). Соответственно правилам изменения параметра tk, используемым в параграфе 1.4 диссертации, в алгоритмах 3.1 и 3.2 возможно использование трех правил: алгоритмов 3.1 и 3.2. Теорема 3.3. Пусть задача (1.1) удовлетворяет условию С, о О, Хє — ограниченное множество, функция f{x) удовлетворяет на Хе условию Липшица с константой i, YrtD = 0, min{g(x),xe Xe} mm{g(x\xG Rn}, і = т\п{(іі7ієН\. Тогда условия пунктов 4 или 5 алгоритма 3.1 вьшолняются при некотором к N — 1 и будет получено є -оптимальное решение задачи (1.1). Доказательство. Пусть для некоторого номера k ,N — \ выполняются условия пункта 5 алгоритма 3.1, т.е. xk+iD . Из этого в силу леммы 1.2 следует, что Р(хк+і к Ук Рк) Ук- Поэтому алгоритм 3.1 укладывается в схему алгоритма 1.1, если используется правило 1 фиксации параметра tkt алгоритма 1.2, если используется правило 2, и алгоритма 1.3, если используется правило 3 фиксации параметра tk.
