Алгоритмы с аппроксимацией допустимого множества в методе центров тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

На правах рукописи УДК 519.853

Андрианова Анастасия Александровна

АЛГОРИТМЫ С АППРОКСИМАЦИЕЙ ДОПУСТИМОГО МНОЖЕСТВА В МЕТОДЕ ЦЕНТРОВ

01.01.07 — вычислительная математика

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

Автореферат

Казань — 2004

Работа выполнена на кафедре экономической кибернетики Государственного образовательного учреждения высшего профессионального образования «Казанский государственный университет им. В. И. Ульянова - Ленина».

Научный руководитель: доктор физико-математических наук,

профессор Заботин Ярослав Иванович

Официальные оппоненты: доктор физико-математических наук,

профессор Ижуткин Виктор Сергеевич

доктор технических наук,

профессор Галиев Шамиль Ибрагимович

Ведущая организация: Вычислительный центр РАН, г.Москва

Защита диссертации состоится "17" июня 2004 г. в 1430 часов на заседании диссертационного совета К-212.081.07 по защите диссертаций на соискание ученой степени кандидата физико- математических наук при Казанском государственном университете (420008, г. Казань, ул. Кремлевская,18, корпус 2 , ауд. 217).

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

Автореферат разослан п 10" __ 2004 г.

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

Агачев Ю.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

где D = {¿с : х € R„,g(x) < 0}, (/(¡с) = тах{/,(ж),г = 1..т}, специалисты сталкиваются с проблемой обеспечения остановки вычислительного процесса в точке, которая является приближенным решением задачи, удовлетворяющим заданному уровню точности. Конечно, большинство методов нелинейного программирования имеют критерий оптимальности, позволяющий определить, что полученная итерационная точка является решением задачи (1). Однако условия такого критерия выполняются только в искомой точке оптимума, которую можно достичь в общем случае только в пределе. Поэтому для эффективного использования методов оптимизации на практике требуется иметь не только критерии оптимальности, но и легко проверяемые условия, выполнение которых гарантирует получение приближенного решения задачи (1) с заданной точностью е > 0. Если таких условий нет, то приходится останавливать вычислительный процесс на основании эвристических соображений, что может привести к точке, далекой от оптимального решения задачи (1). Поэтому разработка алгоритмов в рамках того или иного метода нелинейного программирования, имеющих практически реализуемый критерий получения е-решения задачи (1), является актуальной проблемой с точки зрения практического применения методов.

Данная диссертационная работа посвящена разработке алгоритмов в методе центров, получающих е-решение задачи (1) за конечное число итераций.

Большой вклад в исследование вопросов построения алгоритмов и получения условий достижения точного или е-решения задачи (1) в методе центров и в методе штрафных функций в разное время внесли такие отечественные ученые, как Голыптейн Е.Г.,Евтушенко Ю.Г., Еремин И.И., Жадан В.Г., Заботин Я.И., Ижуткин B.C., Каплан А.А., Князев Е.А., Коткин Г.Г., Сухарев А.Г., Федоров В.В. и другие. В данной работе в качестве вспомогательной функции в методе

min{/(x),x € D},

(1)

РОС НАЦИОНАЛЬНАЯ

БИБЛИОТЕКА | С-Пекр Ч 09 ТОО

центров строится функция максимума. Методы минимизации таких функций разрабатывались Демьяновым В.Ф., Заботиным Я.И., Ко-раблевым А.И., Крейниным М.И., Фазыловым В.Р. Методами последовательной безусловной минимизации, включая метод центров, занимались такие зарубежные ученые, как Бертсекас Д., Гроссман К., Мак-Кормик Г., Мангасариан О.Л., Морисон Д., Фиакко А., Хьюард П.и другие.

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

Методы исследования. При формулировке и доказательстве результатов используется теория выпуклого анализа и математического программирования. Достоверность результатов подтверждается приведенными доказательствами всех лемм и теорем, сформулированных в работе.

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

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

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

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

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

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

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

6. Алгоритмы в методах внутренних и внешних центров, которые гарантируют получение е-решения задачи (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 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Пусть Я — {1,2..т}, функции f(x),fi(x),i € Я определены в п-мерном евклидовом пространстве R„, д(х) = max{/,(x),i € Я}, D = {х:х£ Rn,g(x) <0},1У = {х:хе Д„,$(х) < 0}, f* = min{/(x),x e D}, Y = Argmin{f(x),x € K}.

Условие А. Задача (1) удовлетворяет условию А, если она имеет решение, функции f(x),fi(x),i g Я непрерывны в Д, и ГУ ф 0.

Условие В. Задача (1) удовлетворяет условию В, если она удовлетворяет условию А и ТУ = D.

Условие С. Задача (1) удовлетворяет условию С, если она удовлетворяет условию В, функция f(x) является выпуклой на Rn и функции /,(г), i G Я являются сильно выпуклыми на Д, с постоянными СИЛЬНОЙ выпуклости /X,-.

Условие D. Задача (1) удовлетворяет условию D, если она удовлетворяет условию В, функция f(x) является выпуклой на R„ и функции fi(x),i G Я являются равномерно выпуклыми на R„ с неубывающими модулями выпуклости 0,(и)(0 < и < оо).

Обозначим через М множество функций, определенных в Rn, каждый локальный минимум которых является абсолютным, X* = {х : х £ D, /(х) < /* + а} для а > 0 - множество cr-решений задачи (1).

По заданной точности е > 0 требуется найти точку из множества

X;.

Для фиксированных значений t,7,p положим F{x,t,^,p) — maх{/(х) - t,pg(x) - 7}, Z(t,%p) = ^grmm{F(x, t,7,p),x € Я„}. Функцию вида F(x,t,7,p) будем называть вспомогательной функцией для задачи (1). Будем полагать, что Z(t,j, р) ф 0 при любых значениях р > 0, i, 7.

Под термином «аппроксимация» допустимого множества понимается построение множества вида D(p, 7) = {i:z£ Rn,pg(x) —7 < 0}, где р > 0,7 - константы. Обозначим £>'(р, 7) = {х : х € Д„, рд{х)—7 < 0}.

В § 1.2 доказываются новые свойства вспомогательной функции вида F(x,i,7,p) и множества Z(t,j,p).

В § 1.3 получены и доказаны необходимые и достаточные усло-

вия получения е-решения задачи (1) за один процесс минимизации функции вида Р(х, 7, р).

Достаточным условием получения е-решения задачи (1) является

Теорема 1. Пусть задача (1) удовлетворяет условию А, для константы е > 0 множество X* является ограниченным, параметры р > 0, £,7 зафиксированы таким образом, что

ртт{«?(!г),аг€Хе*}-£<Г + 7-*<0. (2)

Тогда г(Ь,ър) С X*.

Если

/,д € М, У П О = 0, тш{<>(х), г € X/} тт{</(х), х € Д„}> (3)

то выполнение для заданных значений параметров р > 0, 7 двойного неравенства (2) является также и необходимым условием того, чтобы 7, р) С X*. Получение точек из множества X* возможно и тогда, когда некоторые из условий (3) не выполняются. Бели задача (1) удовлетворяет условию А, множество X* является ограниченным, то среди точек множества 7, р) существуют точки множества X* в каждом из следующих случаев:

1. / € М, У П £> ^ 0 и параметры р > 0,4,7 зафиксированы так, что рхшп{</(г),г е X*} — е < /* + 7 —

2. д £ М, пип{д(а;),х € X*} = ша{}(г),г е Дп} и параметры р > 0, ¿,7 зафиксированы так, что /* + 7 — £ < 0.

3. € М, Г Л Э ф 0, шт{}(1),г <= Хе*} = тт{5(а;),а: € К} и параметры р > 0, 7 фиксированы произвольным образом.

Двойное неравенство (2) имеет теоретическое значение. При построении алгоритмов используются следующие практически реализуемые условия, эквивалентные выполнению неравенства (2).

Теорема 2. Пусть задача (1) удовлетворяет условию А, / € М, для е > 0 множество X' ограничено, параметры р, 7 функции F(a:,t,-7,p) при некотором т? > 0 зафиксированы так, что р > 0, рпип{з(х),аг е X*} — е < 17 — 7, £</* — »7, и произвольно выбрана точка 2 € —7, р). Тогда, для того чтобы г е X*, необходимо и достаточно, чтобы г £ И.

Теорема 3. Пусть задача (1) удовлетворяет условию А, д € М и параметры функции F(x, 7, р) зафиксированы так, что 4 > /*, 7 > 0,

р > 0. Тогда для того чтобы выбранные значения параметров удовлетворяли неравенству Ь < /* + 7, необходимо и достаточно, чтобы Р&ЛЪР) > ~7. где г 6 £(«,7,р).

В частности, если 1 = /(у), где у € -О, 7 < е, тогда необходимым и достаточным условием того, что у € X*, является выполнение неравенства ^(г,/(у),7,р) > -7 для г € £(/(у),7.р)-

Если в дополнение к условиям теоремы 3 / бЛ/иУГ)1)/ = 0, то для выполнения неравенства £ < /* + 7 необходимо и достаточно, чтобы произвольно фиксированная точка г € 7, р) удовлетворяла условию г £ I)'.

На основе доказанных достаточных условий получения е—решения задачи (1) в § 1.4 и 1.5 построены принципиальные алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров соответственно.

В алгоритмах в методе внутренних центров в качестве аппроксимации допустимого множества используются множества 1)(р, 7) при р > 0,7 > 0. Критерием остановки в алгоритмах в методе внутренних центров является получение итерационной точки, которая не принадлежит множеству ГУ. В этом случае гарантируется, что предыдущая. итерационная точка является е-решением задачи (1).

Алгоритм 1 (в методе внутренних центров). Фиксируются точка Яо € И, точность е > 0, число 6 € (0;е]. Если найдена точка Хк(к > 0), переход к точке осуществляется следующим образом.

1. Выбираются числа 7* € [¿;е], Рк > 0.

2. Находится точка е 2(/(ж*),7ь,р*).

3. Если F(г^+l,/(xt),7J^,pJ^) > -7*, то хк € X*. Процесс решения завершен.

4. Осуществляется переход к п.1 при к, замененном на /г + 1.

Доказано, что если задача (1) удовлетворяет условию А, д € М и

последовательность {х*} вырабатывается по алгоритму 1, найдется такой номер N > 0, что для точки хдм-1 будут выполнены условия пункта 3 алгоритма и хдг € X*.

Если для задачи (1) известно, что / €МиУпР' = 0, то пункт 3 алгоритма 1 может принять следующий вид:

3'. Если £ 1У, то ж» е X*. Процесс решения завершен.

При построении алгоритмов в методе внешних центров в качестве аппроксимации допустимого множества используются множества

£)(р, 7) при р > 0, 7 < 0. Остановка вычислительного процесса производится при получении итерационной точки, которая принадлежит множеству Б. Именно эта точка и является е—решением задачи (1).

Алгоритм 2 (в методе внешних центров). Фиксируются точка го $ I), для которой /(го) < /*» точность е > 0, число 5 е (0; е]. Если найдена точка > 0), переход к точке осуществляется по следующей схеме.

1. Выбираются рк > 0, 7* € — р*тш{р(:г),ж € X*}].

2. Находится точка г*+х € ъ,Рк)>

3. Если хц-1 € О, то х*+1 € X*. Процесс решения завершен.

4. Осуществляется переход к п.1 при к, замененном на к +1.

Доказано, что если задача (1) удовлетворяет условию А, /,д €

М, для е > 0 множество X* ограничено и последовательность {г*} вырабатывается по алгоритму 2, найдется такой номер N > 0, что для точки хдг+1 выполнятся условия пункта 3 алгоритма и хдг+1 е X*.

Алгоритмы в методах внутренних и внешних центров, аналогичные алгоритмам 1 и 2, построены и для следующих правил изменения параметра > 0) вспомогательной функции.

1. = *к + -Р(а;*+1,*ь7ьР*)-

2. = т/{хк+0 + (1 - т)«ь где т € (0; 1).

В § 1.6 конкретизируется реализация некоторых этапов алгоритмов с аппроксимацией допустимого множества в методе внешних центров. К их числу относится процедура нахождения точки начального приближения х0 Б, для которой /(х0) < /*, и определение допустимого интервала задания параметра 7ъ(к >0) в пункте 1 алгоритма 2 и других алгоритмах в методе внешних центров с аппроксимацией допустимого множества.

Во второй главе диссертации «Использование неполной минимизации вспомогательной функции при построении алгоритмов в методе центров с аппроксимацией допустимого множества» построены реализуемые алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров.

В § 2.1 доказаны достаточные условия получения е- решения задачи (1) за один процесс минимизации вспомогательной функции, проводимый до выполнения заданного заранее уровня точности 1 > 0, а также установлена связь между процессом поиска точного решения и процессом поиска ё—решения задачи минимизации вспомогатель-

ной функции.

Для фиксированных значений р > 0,t,y обозначим F*(£,7,p) = min{F(x,i,7,p),x е R„}, Z(t,i,p,z) = {х : х G fl„,F(x,f,7,p) < F'(t,7,p) + £>, = {* = « € Д^МЛ./») < +

ё,| f(x)-t-pg(x) + 1\<l).

Если среди точек множества Z(t,"f,p) нет точек абсолютного минимума функций /(х) и д(х), то Z(t, 7, р, е) ф 0,4 причем Z(t,f,p) с ~Z(t,y, р,Щ для е > 0.

При фиксированных значениях р > 0,7 поставим вспомогательную задачу

min{/(x),x€D(p,7)}. (4)

Обозначим/*(р, 7) =min{/(x),x € D(p,7)}.

Теорема 4. Пусть задача (1) удовлетворяет условию А, /, д 6 Л/, УГШ = 0, е > 0, множество X* является ограниченным, пип{з(х),х 6 X'} ф min{g(x),x € Л„}, параметры 0 < е < е, р > 0,i,7 зафиксированы так, что D( 1, —г) ф 0 и имеет место двойное неравенство

t -/*-£ + г + pmin{5(x),х <Е Хе*_Г} < 7 < t - f(p, -ё) - ё. (5)

Тогда Z(t,7,p,s) С

Если задача (1) удовлетворяет условию С, функция /(х) удовлетворяет условию Липшица с константой L > 0 на множестве £>, ц — min{/x;,i £ Н} и параметры зафиксированы так, что р > 0, е > 2е + то существуют значения параметров t, 7, для которых будет выполнено неравенство (5).

Связь между правилами фиксации параметров при поиске точного абсолютного минимума и при поиске F—решения задачи минимизации вспомогательной функции устанавливается следующей теоремой.

Теорема 5. Пусть задача (1) удовлетворяет условию A,f,g£ М, заданы х0 е Д,, ро > 0,pi > 0,70,71» ? > 0. Пусть хх € 2Г(/(х0),7о, p0,t) и zi € Z(/(x0),7o,Po). Если £ Y и 5(21) ф min{p(x),x € Д„}, то существуют числа ¿1,62 € [0;?] такие, что 2(/(xj),7i,pi) = Z{f{zi),71 + bj - bjiPi)» ^(/faO.Ti.Pi) = ^(/(zi),7i + bi - 62.p1) и справедливо равенство /(xj) = f{zi) — 61 + 62-

Результаты этой теоремы позволяют интерпретировать процесс решения задачи (1), проводимый с минимизацией вспомогательной функции до выполнения точности г > 0, как процесс решения вспомогательной задачи вида (4) с помощью алгоритма с аппроксимацией

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

В § 2.2 на основании утверждений теорем 4 и 5, построены алгоритмы с аппроксимацией допустимого множества и неполной минимизацией вспомогательной функции в методах внутренних и внешних центров, в пункте 2 которых находится точка ¡ri+x € Эти алгоритмы являются реализуемыми вариантами алгоритмов 1 и 2 соответственно.

Пусть задача (1) удовлетворяет условию С, е > 0, множество X* является ограниченным, функция /(ас) удовлетворяет условию Липшица с константой L на множестве D, Y П D{\, е) = 0, rainez), х € X*} ф min{<?(x),x € Rn}, M = min{/i;,t € Я), для зафиксированного г > 0 имеет место £>'( 1, —г) ф 0 и 2У(1,-г) — D(l,—S). Тогда

1. если точка х0 € D удовлетворяет условию /(х)—/(хо) > д(х) — S, где 0 < S < е, для любых х ç {х : х G Л„,д(х) — min{g(x),x G Яп}} и последовательность {xt} построена по алгоритму, который является реализацией алгоритма 1, то существует номер N > 0, для которого xjv+i $ ГУ, и Xfi € X*.

2. если последовательность {х*} построена по алгоритму, который является реализацией алгоритма 2, то существует такой номер N > О, что хдг+1 € D, причем x^+i G X*.

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

Пусть задача (1) удовлетворяет условию В, функции /(х), /,(х), i € H являются непрерывно-дифференцируемыми и выпуклыми в R„.

Алгоритм 3." Фиксируется точка х0 6 ГУ, числа х € (0; 1), 0,- > 0, i g Яи {0}, последовательности {а,}, {Ьг}, удовлетворяющие следу-

ющим условиям:

оо

От > 0,0,+j < Or г > 0; аг 0, г оо, £ ат = оо

ГШ О

Ьг > 1,Ьг+1 > ьт г > 0; 6Г оо,г оо

Полагается к — 0, zq = уо = ®о> го = 0> 9о = 0, р = 0.

1. Строится функция F(xJ(xk),pk) = max{/(x) - f(xk),pkg(x) -s), где pi = bJk.

2. Если р = 1, то принимается (в*, сг*) = (s*_1(cri_i). Осуществляется переход к п.7.

3. Строится множество H(zk,Sk) = {» : t е ff,F(zk,f(xk),pk) -Sк < pkfi{zk) - е}> где 6к = ркОгк.

4. Решается задача

а — max (6)

№),«) + 9о<т< 0, (7)

№0» + to < 0 € H(zk, 6к) (8)

a eS, (9)

где S -замкнутое ограниченное множество в • пространстве Д,, содержащее нуль пространства в качестве внутренней точки. Задача (6)-(9) является задачей выбора направления убывания для функции F(x, f(xk),pk) в точке zk. Пусть (si, ak) - оптимальное решение задачи (6)-(9).

5. Если ок = 0 и H(zk,Sk) = 0, то хк G X'. Процесс решения завершен.

6. Если сгк = 0, то Xi+j = хк, yk+i = ук, zk+x — zk, qk+i = qk, rt+i = rk + 1, осуществляется переход к п.1 при к, замененном на fc+1.

7. Вычисляется t]k € [*А£;Л£],где AJ = argmin{F(zk+Xsk, f(xk),pk), А > 0} - полный шаг из точки zk по направлению убывания sk для функции F(x,f(xk),pk), и принимается Хк = XVk-

8. Определяется точка у*+1 = zk + Xksk.

9. Если Ук+i G С и /(yi+i) - f(xк) < -е, то хк+г = ук+и zk+i = Ук+и Чк+i — Як, гк+1 = П + 1, р = 0.

10. Если ул+1 g 1У, то ®t+x = хк, zk+i = zk, qk+ï = qk +1, гА+х = rk, p = l.

11. Если yi+l G ГУ И /(y*+l)—/(Xfc) > -£, TO Xjfc+i = Ж*, Zk+1 = IAt+1, qk+1 = Як + 1, ri+i = rk +1, p = 0.

12. Осуществляется переход к n.l при к, замененном на к + 1.

Если начальная точка жо £ ГУ была выбрана так, что множество

{ж : х G D,f(x) < /(жо)} является ограниченным, и не существует номера, для которого выполнены условия пункта 5 алгоритма, то справледливы утверждения:.

1.Иш /ы = л

2.Существует номер N > 0 такой, что для всех номеров к > N не выполняются условия пункта 9 алгоритма, причем iff £ X*.

В третьей главе диссертации «Управление процессом минимизации посредством мультипликативной параметризации в методе центров» основное внимание уделено роли параметра р в управлении процессом минимизации.

В § 3.1 на основании теоремы 1 получены теоретические правила задания параметров для получения ^-решения задачи (1), удовлетворяющей условию В, за один процесс минимизации вспомогательной функции.

В § 3.2 на основе результатов § 3.1 получены практически реализуемые правила фиксации параметров для получения е-решения задачи (1) за один процесс минимизации вспомогательной функции, построенной в методе внутренних центров.

Пусть для е > 0 множество X' является ограниченным, функция /(ж) удовлетворяет на множестве X* условию Липшица с константой L > 0, тш{<;(ж),ж G X*} ф min{</(x),x £ R„} и пусть известно число /, для которого выполняется условие / < /*. Тогда Z(t, 7, р) С X* в каждом из двух случаев:

1. Задача (1) удовлетворяет условию С, ц = min{/2,-, i G Н}, параметры р > 0, t, 7 зафиксированы так, что

*r>s>o,t>r + rp>-L2{£ + 5JL-t). (10)

2. Задача (1) удовлетворяет условию D, ф(и) = min{$,(u),t G #}, параметры р > 0, f, 7 зафиксированы так, что

7 > S > 0,t > Г + ЪР > + (")

Поскольку оценки параметра р, указанные в (10) и (11), оказываются обычно существенно завышенными, построены алгоритмы с аппроксимацией допустимого множества в методе внутренних центров, обладающие следующим свойством. В этих алгоритмах условия (10) или (11) выполняются только на итерации с номером N > 0, гарантируя, что е-решение задачи (1) будет получено не более чем за N итераций. Однако алгоритмы имеют дополнительный критерий остановки, условия которого могут быть выполнены на итерации с номером, меньшим N. Этим критерием остановки является получение точки, не принадлежащей допустимому множеству. Тогда гарантируется, что предыдущая итерационная точка есть е-решение задачи (1).

Сформулируем алгоритм в методе внутренних центров для решения задач, удовлетворяющих условию С.

Алгоритм 4. Фиксируются точка хо 6 £>, точность е > 0, число 6 € (0;е], N > 0 - число итераций, за которое должно быть получено е-решение задачи (1), р_ 1 = 0. Задается возрастающая функция <р(и), для которой ¥>(1) > 0, > 1. Полагается к = 0.

1. Вычисляется С* = принимается р* = шах{^?(Л+

2. Фиксируется число 7* € [<5;е].

3. Выбирается точка 6 2(/(х*),7*,р*).

4. Если к = N — 1 и х*+1 € ГУ, то х*+х € X*. Процесс решения завершен.

5. Если £ £>', то х* 6 X*. Процесс решения завершен.

6. Осуществляется переход к п.1 при к, замененном на к + 1.

Доказано, что если задача (1) удовлетворяет условию С, для е > 0

множество X* является ограниченным, функция /(х) удовлетворяет на множестве X* условию Липшица с константой Ь > 0, тт{<7(х), х € X'} ф тт{д(х),ж € Яп}, тогда условия пунктов 4 или 5 алгоритма будут выполнены при некотором номере к< N — 1 и будет получено е-решение задачи (1).

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

Пусть для е > 0 множество X* является ограниченным, функция /(х) удовлетворяет на множестве X* условию Липшица с константой

Ь > О, тт{д(ж),х € X*} ф тт{<7(х),х € Д,} и пусть известно число 7, для которого выполняется условие 7 > /*■ Тогда ¿?(£,7,р) С X* в каждом из следующих случаев:

1. Задача (1) удовлетворяет условию С, ц = пип{д,-,г € Я}, параметры р > 0, 7 зафиксированы так, что

2. Задача (1) удовлетворяет условию Б, ф(и) = гшп{0;(и),» € Я}, параметры р > 0,7 зафиксировали так, что

Оценки параметра р, указанные в (12) и (13), также оказываются завышенными. Поэтому построены алгоритмы с аппроксимаг цией допустимого множества в методе внешних центров для задач, удовлетворяющих условию С или Б, которые позволяют получить е-решение задачи (1) не более чем за заданное число итераций N > 0. Также, как и алгоритмы в методе внутренних центров, алгоритмы § 3.3 имеют дополнительный критерий остановки вычислений, условия которого могут быть выполнены на итерации с номером, меньшим N - получение допустимой итерационной точки, которая и является е- решением задачи (1).

В § 3.4 алгоритмы в методах внутренних и внешних центров с аппроксимацией допустимого множества, получающие е- решение задачи (1) не более чем за N > 0 итераций, построены из предположения минимизации вспомогательной функции до выполнения точности

Пусть задача (1) удовлетворяет условию С, для е > 0 множество X* является ограниченным, функция /(х) удовлетворяет на множестве В условию Липшица с константой Ь > 0, пип{д(х),х € X*} ф тт{<?(х),х е Я«} и известны числа ¿,7, для которых выполняется условие < /* < /. Тогда 2((,7,р,г) С X* в каждом из следующих случаев:

1. Параметры 0 < е < е, р > 1, зафиксированы так, что 1У(р, —ё) ф 0 и выполняются неравенства

, 7 = Р^Р'- (12)

£> 0.

7 > £ > 0, *>/* +7+ + Р>~

Р(е-г)2

, (14)

2.Параметры £ > 0, (/ > 1, ^ 7 зафиксированы так, что £)'(1, -г) ^ 0, £>'(1,-г) = 1)(1,-ё), с > 2£1 = е — 1-Ь^ и имеют место соотношения

Применение правил (14) и (15) позволяет построить алгоритмы в методах внутренних и внешних центров, получающие е- решение задачи (1) не более чем за N > 0 итераций, аналогичные алгоритмам, построенным в § 3.2 и § 3.3, при условии, что для каждого номера к > О выбирается хк+х € 2Г(/(®*)>7*?Р*»£)-

Четвертая глава диссертации «Решение тестовых задач» посвящена решению задач с помощью алгоритмов, построенных в диссертации, и их сравнению с классическими алгоритмами в методах внутренних и внешних центров и их параметризованными модификациями.

При решении задач полагалось е = Ю-3, 6 = 10~7. Фиксация параметра 71 на каждой итерации проводилась случайным образом из допустимого для соответствующего алгоритма интервала. Минимизация вспомогательной функции проводилась с точностью Т = 10~8. Для остановки вычислительного процесса, проводимого по методам внутренних и внешних центров и их параметризованным вариантам, использовался эвристический критерий - вычисления прекраг щались, если при некотором номере к > 0 имело место неравенство

На основании проведенных экспериментов сделаны следующие выводы.

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

t<r+

£2

|/(х4+1)-/(**)!<*•

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

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

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

5. Теоретическим критерием остановки процесса вычислений алгоритма 3 является тот факт, что начиная с некоторого номера К > О, ни разу не выполняются условия пункта 9 алгоритма. В связи с этим процесс останавливался тогда, когда в течение последних 50 итераций условия пункта 9 алгоритма не имели места. Хотя этот критерий все еще носит эмпирический характер, при решении всех тестовых задач было получено решение, удовлетворяющее заданной точности е — 10~3. Следует заметить, что количество малых итераций (поиск направления убывания вспомогательной функции и шаг по нему), проделанных по алгоритму 3, и время работы алгоритма для задач размерности п 5 уменьшается по сравнению с другими алгоритмами в методе центров.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3. Построены алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров с минимизацией вспомогательной функции до выполнения заданной точности e > 0, которые также за конечное число итераций получают е-решение исходной задачи.

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

5. Построены алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров, получающие е-решение задачи не более, чем за заданное заранее число итераций N>0.

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Заботин Я.И. Алгоритмы в методе центров с аппроксимацией множества допустимых решений/Я.И.Заботин, А.А. Андрианова // Изв. вузов. Математика. - 2001. - N 12. - с.41-45.

2. Андрианова А.А. Конечные алгоритмы в методе центров с аппроксимацией допустимого множества /А.А. Андрианова// Казан, ун-т - Казань, 2002 - 31 с. (деп. в ВИНИТИ 06.05.02, N 791-В2002).

3. Заботил Я.И. Алгоритм в методе центров с использованием множества, вложенного в допустимое /Я.И.Заботин, А.А.Андрианова // Материалы Воронежской весенней математической школы «Понт-рягинские чтения XIII», 3-9 мая 2002 г.- Воронеж, 2002. - с. 58.

4. Андрианова А. А. Метод центров с аппроксимацией допустимого множества /А.А. Андрианова, Я.И. Заботин// Тез. докладов XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 27-31 мая 2002 г.) - Москва , 2002. - ч.1, с. 13.

5. Заботин Я. И. Получение решения с заданной точностью методом центров /Я.И. Заботин, А.А. Андрианова// Тезисы докладов Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 24-28 июня 2002 г.). - Новосибирск: Изд-во ин-та математики, 2002. - с. 163.

6. Андрианова А.А. Управление процессом минимизации в параметризованном методе центров /А.А.Андрианова, Я.И.Заботин// Изв. вузов. Математика. - 2002. - N 12. - с. 3-10.

7. Андрианова А.А. Минимизация с заданной точностью в параметризованном методе центров /А.А.Андрианова, Я.И.Заботин// Информационный бюллетень 10. Тезисы докладов конференции «Математическое программирование и приложения» (Екатеринбург, 2428 февраля 2003 г.) - Екатеринбург, 2003. - с.28-29.

8. Андрианова А.А. Алгоритм с неполной минимизацией вспомогательной функции в методе центров /А.А.Андрианова, Я.И.Заботин// Материалы Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 1-5 июля 2003 г.) - Изд-во Наследие, Диалог Сибирь. - Омск , 2003. - с. 114.

9. Андрианова А.А. Об одном алгоритме в методе центров с аппроксимацией допустимого множества на основе наискорейшего спуска /А.А.Андрианова// Казан, ун-т - Казань, 2003 - 20 с. (деп. в ВИНИТИ 04.12.2003 N 2100-В2003).

10. Андрианова А.А. Алгоритм с неполной минимизацией вспомогательной функции в параметризованном методе центров / А.А. Андрианова, Я.И.Заботин// Тезисы докладов Всероссийской конференции «Алгоритмический анализ неустойчивых задач», Екатеринбург, 2-6 февраля 2004 г. - Изд-во Уральского университета - Екатеринбург, 2004. - с.246-247.

Подписано в печать 04 05.2004 г Заказ Д-26. Усл. печ. л. 1,25. Тираж 100 экз. Бумага офсетная. Печать ризографическая. Отпечатано с готового оригинал-макета. Республиканский некоммерческий фонд делового и общественного развития "ФОРРА" г.Казань, ул. Университетская, 17. тел. 31-53-69

р-90 85

Введение.

Глава 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]), решают задачу следующего вида: тш{/(х),хе£>}, (1) где £> = {х: х е Яп, £(х) < 0}, g(<x) = тах^ (х), / е {1,2.т} }.

Все методы математического программирования имеют теоретический критерий оптимальности, позволяющий определить, что полученная итерационная точка является решением задачи (1). Однако выполнение условий критерия оптимальности за конечное число итераций гарантируют только методы решения задач линейного ([10, 12, 29, 47]) и квадратичного ([10, 12, 64]) программирования. Но даже эти методы не всегда можно считать эффективными. При решении задач большой размерности они считаются достаточно трудоемкими с точки зрения объема проводимых вычислений.

Методы решения задачи нелинейного программирования обеспечивают сходимость последовательности итерационных точек к решению задачи (1). Однако достижение точки оптимума возможно только в пределе за бесконечное число итераций. Поэтому для практического применения методов важно иметь не только критерий оптимальности, условия которого выполнятся при достижении решения задачи, но и легко проверяемые условия, при выполнении которых гарантируется достижение за конечное число итераций приближенного решения, удовлетворяющего заданной точности £ > 0.

Согласно условной классификации, введенной в [19], методы нелинейного программирования можно разделить на две группы. Характерными представителями первой группы являются методы возможных направлений ([43]), методы проекции градиента ([12,42,47]), методы линеаризации ([12,60])и многие другие. В этих методах итерационная последовательность точек определяется в результате решения на каждой итерации одной или нескольких более простых задач оптимизации с ограничениями.

Вторую группу методов образуют методы последовательной безусловной минимизации. Основными методами данной группы являются методы штрафных функций ([19, 26, 28, 30, 31, 46, 64, 61, 67, 68, 73, 74, 77, 78, 82, 84]), модифицированных функций Лагранжа ([16, 17, 19]) и методы центров ([9, 11, 26, 31, 33, 46, 58, 62, 72, 75, 79, 80, 81, 85, 86, 87]). Решение исходной задачи оптимизации в этих методах определяется как предел последовательности абсолютных минимумов определенным образом сконструированных вспомогательных функций. Наиболее полный обзор основных возможностей методов данной группы можно найти в монографиях Гольштейна Е.Г., Третьякова Н.В. ([17]) и Гроссмана К., Каплана А.А. ([19]).

В более поздних публикациях [26, 31, 54] рассматриваются общие принципы построения методов последовательной безусловной минимизации, исследуются свойства основных видов вспомогательных функций, применяемых в этих методах. Много внимания уделяется получению точных вспомогательных функций в методе штрафных функций и в методе центров ([21, 26, 27, 30, 31, 71, 74, 78, 84]). Здесь для ряда видов вспомогательных функций указываются правила фиксации управляющих параметров методов такие, что точка абсолютного минимума вспомогательной функции оказывается решением задачи (1). Однако зачастую при построении таких функций сложной и трудоемкой задачей уже становится осуществление процесса минимизации вспомогательной функции. Идея точных интегральных штрафных функций используется и для решения задачи нахождения минимакса и минимаксимина ([14, 15]).

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

Среди основных видов эвристических критериев остановки вычислительного процесса, общих для большинства методов нелинейного программирования, можно выделить следующие критерии. При заданном значении е > 0 процесс построения итерационной последовательности точек {хк} с помощью какого-либо метода нелинейного программирования прекращается при нахождении такого номера К > 0, для которого выполняется одно из неравенств:

ЯхК+1)-ЯхК)\<£,

Ц*^ ~ ХК II - £ •

В случае, когда целевая функция /(х) является выпуклой и непрерывно-дифференцируемой в Яп,ив задаче оптимизации (1) множество И совпадает со всем пространством Яп, может применяться критерий, согласно которому остановку вычислительного процесса можно производить тогда, когда найден номер К > 0, для которого имеет место

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

Разработке алгоритмов в методе центров, имеющих такие условия, посвящена данная работа.

Метод центров для решения задачи вида (1) был предложен Хьюардом в 1967 году ([80]). Вспомогательная функция, которая строится на каждой итерации метода центров, называется «функцией расстояния». Свое название метод центров получил благодаря следующему свойству функции расстояния. Точка абсолютного минимума функции расстояния является в некотором смысле центральной для пересечения лебегова множества целевой функции, определяемого ее значением в предыдущей итерационной точке, с множеством допустимых решений D задачи (1). Каждая итерационная точка, построенная по методу центров, является допустимой.

Различные виды функций расстояния порождают различные виды алгоритмов в методе центров ([9, 11, 13, 19, 26, 27, 31, 33, 44, 53, 68, 72, 80, 81, 82, 83, 86]). Использование некоторых видов функций расстояния привело к созданию модификации метода центров, называемого методом параметризации целевой функции ([25, 26, 31]).

Важной модификацией метода центров является метод внешних центров ([19, 76, 86]). В этом методе точка абсолютного минимума функции расстояния является в определенном смысле равноудаленной от множества допустимых решений и лебегова множества целевой функции, определенной ее значением в предыдущей итерационной точке. В отличие от метода центров, итерационные точки, построенные по методу внешних центров, не являются допустимыми, однако при выполнении определенных условий гарантируется, что последовательность {/(хЛ)} сходится к минимальному значению целевой функции на множестве D. С появлением метода внешних центров метод центров, предложенный Хьюардом, стали называть методом внутренних центров.

В методах внутренних и внешних центров для решения задачи (1) может быть использована предложенная в [80] функция расстояния

Fk(x) = max{/(x)-/(x*),g(x)}. (2)

В дальнейшем функцию (2) и ее модификации называли вспомогательной функцией максимума.

Согласно классификации методов оптимизации, введенной Полаком в [58], методы внутренних и внешних центров являются «принципиальными», поскольку каждая точка итерационной последовательности отыскивается в результате бесконечного процесса безусловной минимизации вспомогательной функции I максимума. Это еще одна проблема, которую приходится решать вычислителю при применении алгоритмов в методе центров для решения практических задач.

Для решения этой проблемы были разработаны алгоритмы ([19, 72]), в которых при любом номере к £ 0 вспомогательная функция максимума минимизируется до выполнения заданного уровня точности 8к, где Sk> 0 для всех к > 0 и lim Sk = 0. к-* оо

Эта же проблема решалась в [38], где были предложены алгоритмы в методах внутренних и внешних центров, в которых минимизация вспомогательной функции прекращалась при попадании итерационной точки в множество вида Dh = {х: х е D, /(х) - f(xk ) + вk < 0}, где последовательность {г^} выбиралась таким

00 образом, что £к > 0 для всех номеров к > 0, lim £к =0 и V £к = оо. ¿=0

Отдельную группу образуют алгоритмы в методе центров, в которых на основании свойств тех или иных методов минимизации вспомогательной функции максимума удается менять функцию после проведения одной итерации ее минимизации. К этой группе, в частности, можно отнести алгоритмы типа наискорейшего спуска ([32, 50, 56]), в основу которых положены принципы поиска направления наискорейшего спуска, применяемые при решении задачи минимизации дискретной функции максимума ([22, 23, 24, 40, 55]), алгоритмы, основанные на использовании s -субградиентов ([51, 52]) и алгоритмы типа обобщенно-градиентного спуска ([39]). В методе штрафных функций на основе свойств вспомогательной функции также разрабатываются алгоритмы такого типа. В частности, к ним относится алгоритм, использующий методику нахождения приведенных направлений ([45,46]).

Построению алгоритмов в методе центров, получающих решение задачи (1) с заданной точностью за конечное число итераций, также ранее уделялось значительное внимание. В разработке таких алгоритмов условно можно выделить два основных подхода. Первый подход заключался в построении алгоритмов, использующих специальные критерии остановки, условия которых выполняются через конечное число итераций и гарантируют достижение заданной точности £ > 0. Основными представителями этого подхода являются алгоритмы с двусторонним приближением ([20,37]), разработанные Заботиным Я.И. и Даныниным И.Н. В них за счет построения двух итерационных последовательностей точек, одна из которых лежит в множестве допустимых решений, являясь аналогом последовательности, построенной по методу внутренних центров, а другая — вне допустимого множества, таким образом, приближаясь к оптимуму извне, как в методе внешних центров, удается за конечное число итераций гарантировать получение приближенного решения, удовлетворяющего заданной точности е > 0.

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

Рк{х,а,/3) = тах{/?(/(х)-/(хА)),^(х)}, (3) I где а> 0,/? > 0 - некоторым образом зафиксированные числа. В [33] Заботиным Я.И. было доказано, что, в принципе, за счет выбора значений управляющих параметров а,р можно достичь приближенного с заданной точностью решения задачи (1) за один процесс минимизации функции вида (3). Но так как указать такие значения не удалось, в [39, 48, 49, 50, 51] были разработаны алгоритмы с адаптацией параметров, осуществляющие подстройку значений параметров с целью ускорения приближения к оптимуму. Однако теоретически обоснованного критерия остановки, гарантирующего выполнение точности е > 0, в этих алгоритмах все еще не было.

Предметом исследования в данной диссертации является разработка алгоритмов с аппроксимацией допустимого множества' в методах внутренних и внешних центров в рамках обоих указанных подходов, позволяющих получить е -оптимальное решение задачи (1) за конечное число итераций. Основные результаты, представленные в диссертации, были опубликованы в работах [1,2,3,4, 5, 6,7, 34,35,36].

Основным инструментом при построении алгоритмов в диссертации является аппроксимация допустимого множества решений. Термин «аппроксимация» в данном случае означает, что вместо допустимого множества задачи (1) при построении вспомогательной функции максимума будет использоваться окрестность допустимого множества Д т.е. множество, содержащее Д или множество, для которого О является окрестностью.

Идея использования аппроксимации допустимого множества в методах последовательной безусловной минимизации использовалась в методе штрафных функций при разработке метода сдвига штрафов ([18, 88, 89]). На основании связи штрафной функции и модифицированной функции Лагранжа была разработана иная модификация метода, названная методом штрафных оценок ([59, 65, 79]). Главным достоинством этих методов был тот факт, что более не было необходимости неограниченно увеличивать штрафной коэффициент. Однако задачи гарантированного получения решения с заданной точностью s > 0 за конечное число итераций эти модификации метода штрафных функций не решали. Эта задача в рамках метода штрафных функций была решена для задачи выпуклого программирования в [41].

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

F(x, t, у, р) = max{/(x) -1, pg(x) - у}. (4)

В функции (4) параметр р выполняет ту же роль, что и параметры a, ft в алгоритмах в методе центров с адаптацией параметров. Задавая правила изменения параметров t,y,p, удается построить алгоритмы в методах внутренних и внешних центров, осуществляющие односторонний процесс приближения к минимуму и останавливающие этот процесс в точке, являющейся решением задачи (1) с заданной точностью £>0.

Диссертация состоит из четырех глав. В первой главе определяются основные принципы построения алгоритмов с аппроксимацией допустимого множества в методах внутренних и внешних центров с целью получения решения задачи (1) с заданной точностью е>0 за конечное число итераций. Результаты, изложенные в этой главе, опубликованы в работах [1,3,34,35].

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

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

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

В следующих параграфах предлагаются алгоритмы с аппроксимацией допустимого множества для решения задачи (1), в которой множество D удовлетворяет условию регулярности по Слейтеру, и функции /(jc),/)(*),/ е {1,2.т) являются непрерывными в Rn, причем каждый локальный минимум этих функций является абсолютным.

В параграфе 1.4 приводятся принципиальные алгоритмы с аппроксимацией допустимого множества в методе внутренних центров. В качестве аппроксимации допустимого множества в этих алгоритмах используются множества, являющиеся окрестностями допустимого множества. Критерием остановки вычислительного процесса, проводимого по этим алгоритмам, является выполнение для некоторого номера к> 0 неравенства F(xk+l ,tk,yk,pk)>-yk, где хк+х - точка абсолютного минимума функции F(x,tk,yk,pk). В этом случае гарантируется, что предыдущая итерационная точка хк является ¿-оптимальным решением задачи (1). Для задач, в которых абсолютный минимум функции f(x) не совпадает с глобальным минимумом этой функции на множестве D, эквивалентным условием является получение итерационной точки, не принадлежащей множеству

В параграфе 1.5 приводятся алгоритмы с аппроксимацией допустимого множества в методе внешних центров. В отличие от алгоритмов, предложенных в параграфе 1.4, в качестве аппроксимации допустимого множества здесь используются множества, по отношению к которым исходное множество D является окрестностью. Критерием остановки вычислительного процесса в алгоритмах этого параграфа является получение итерационной точки, принадлежащей множеству D. I

В параграфе 1.6 для задач, в которых функция f(x) является выпуклой, а функции /¡(х), i е {l,2.m} являются сильно выпуклыми или равномерно выпуклыми на Яп, конкретизируются процедуры практического выполнения некоторых пунктов алгоритмов, предложенных в параграфе 1.5.

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

В параграфе 2.1 исходя из предположения, что функция вида (4) минимизируется до выполнения заданной точности по функционалу е >0, указываются достаточные условия фиксации управляющих параметров чтобы е -оптимальное решение задачи минимизации функции (4) являлось £ -оптимальным решением задачи (1).

На основании результатов параграфа 2.1 в параграфе 2.2 предлагаются алгоритмы в методах внутренних и внешних центров с аппроксимацией допустимого множества и неполной минимизацией до выполнения точности £ >0 I вспомогательной функции вида (4). Эти алгоритмы позволяют за конечное число итераций находить £ -оптимальное решение задачи вида (1), в которой функция /(х) является выпуклой, функции /}(*),/е {1,2.т) являются сильно выпуклыми, а множество £> удовлетворяет условию регулярности по Слейтеру, причем £)' = £). Критерием остановки, как и в алгоритмах, построенных из предположения минимизации вспомогательной функции до получения ее абсолютного минимума, является получение точки, попавшей в множество, образованное разностью допустимого множества £> и множества, являющегося аппроксимацией множества £), применяемой на данной итерации алгоритмов.

В параграфе 2.3 предложен алгоритм в методе внутренних центров с аппроксимацией допустимого множества, построенный на основании метода типа наискорейшего спуска решения задачи минимизации вспомогательной функции максимума ([24, 40, 55]). Использование аппроксимации допустимого множества позволяет гарантировать получение £ -оптимального решения задачи (1) за конечное число итераций. Однако подстройка управляющих параметров осуществляется не после нахождения точного минимума функции вида (4), а после выполнения каждой итерации ее минимизации. Таким образом, удается избежать бесконечного процесса минимизации вспомогательной функции (4) на каждой итерации алгоритма.

Третья глава диссертации посвящена исследованию роли мультипликативного параметра р в алгоритмах в методах внутренних и внешних центров с аппроксимацией допустимого множества. Роль этого параметра схожа с той ролью, которую играли параметры а,р в алгоритмах с адаптацией параметров в методе центров ([33, 39, 48, 49]), а именно - ускорение приближения к точке оптимума. Результаты этой главы представлены в работах [4, 5, 7, 36].

В параграфе 3.1 приводятся теоретические правила фиксации управляющих параметров позволяющие получить е -оптимальное решение задачи (1) за один процесс минимизации функции вида (4). На основании этих правил в параграфе 3.2 построены практически реализуемые правила фиксации управляющих параметров в случае приближения к оптимуму изнутри допустимого множества, следуя которым можно получить £ -оптимальное решение задачи (1) за один итерационный шаг. Эти правила построены для задачи (1), в которой выпукла функция /(х) и строго выпуклы или равномерно выпуклы на Яп функции /)(*),/е{1 .т). Также в параграфе 3.2 построены алгоритмы в методе внутренних центров, гарантирующие получение е -оптимального решения задачи (1) не более чем за заданное заранее число итераций N > О, проделанных по предложенным алгоритмам.

В параграфе 3.3 аналогичные алгоритмы построены в методе внешних центров. Здесь также гарантируется получение е -оптимального решения задачи (1) не более чем за заданное заранее число итераций N > 0, проделанных по предложенным алгоритмам. Эти алгоритмы разработаны для решения задачи (1), в которой функция /(х) является выпуклой, функции /Дх),/е{1.т} являются строго выпуклыми или равномерно выпуклыми на Лп.

Аналогичные результаты при условии, что вспомогательная функция максимума минимизируется до выполнения заданной точности е > О, получены в параграфе 3.4. Здесь указываются правила фиксации параметров для получения е -оптимального решения задачи (1) за один процесс поиска е -оптимального решения задачи минимизации функции вида (4). На основании полученных правил построены алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров, получающие е -оптимальное решение задачи (1) не более чем за заданное заранее число итераций N > 0.

В четвертой главе диссертации приводятся результаты экспериментов, проделанных для тестирования предложенных в диссертации алгоритмов. В качестве тестовых задач были выбраны задачи, известные из различных публикаций ([10, 19, 58,63,69]), и несколько сгенерированных задач выпуклого программирования.

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

Автор выражает глубокую и искреннюю благодарность своему научному руководителю профессору кафедры экономической кибернетики Казанского государственного университета Заботину Ярославу Ивановичу за постоянное внимание к работе, за предоставление для работы интересной темы и за множество ценных советов и рекомендаций.

15

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

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

2) Доказано достаточное условие фиксации параметров для получения £-оптимального решения задачи (1.1) при минимизации вспомогательной функции до выполнения заданной точности по функционалу £ >0. Для задач (1.1) с выпуклой целевой функцией и сильно выпуклыми функциями-ограничениями указаны практически реализуемые эквиваленты этого условия.

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

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

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

6) Построены алгоритмы с аппроксимацией допустимого множества в методах внутренних и внешних центров, гарантирующие получение е -оптимального решения задачи (1.1) не более чем за заданное число итераций N > 0. Эти алгоритмы также имеют дополнительные критерии остановки, позволяющие остановить вычислительный процесс на итерации с номером, меньшим N. Доказано, что не более чем за заданное N > 0 итераций, проделанных по этим алгоритмам, будут выполнены условия критериев остановки и получено ^-оптимальное решение задачи (1.1).

7) Проведены вычислительные эксперименты по предложенным в диссертации алгоритмам на решении ряда тестовых задач. Проведено сравнение предложенных алгоритмов с известными ранее классическими алгоритмами в методах внутренних и внешних центров.

125

ЗАКЛЮЧЕНИЕ

1. Андрианова A.A. Конечные алгоритмы в методе центров с аппроксимацией допустимого множества / А. А. Андрианова // Казан, ун-т Казань, 2002. — 31 с. (деп. в ВИНИТИ 06.05.02, № 791-В2002).

2. Андрианова A.A. Об одном алгоритме в методе центров с аппроксимацией допустимого множества на основе наискорейшего спуска / A.A. Андрианова // Казан, ун-т Казань, 2003. - 20 с. (деп. В ВИНИТИ 04.12.2003 № 2100-В2003).

3. Андрианова A.A. Метод центров с аппроксимацией допустимого множества / А.А.Андрианова, Я.И. Заботин // Тез. докладов XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 27-31 мая 2002 г.) — Москва, 2002. -ч.1, с. 13.

4. Андрианова A.A. Управление процессом минимизации в параметризованном методе центров / А. А. Андрианова, Я. И. Заботин // Изв.вузов. Математика. 2002. -№12. -с. 3-10.

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

6. Ахметзянов A.B. Основные модификации метода центров Хьюарда /А. В. Ахметзянов // Управление многосвязными системами: Сб. ст. М.: Наука, 1975. -с.42-51.

7. Базара М. Нелинейное программирование. Теория и алгоритмы. / М. Базара, К. Шетги. М.: Мир, 1982. - 584 с.

8. Бирюков С.И. Метод лебего-оптимальных траекторий / С.И. Бирюков // Моделирование процессов обработки информации и управления: Сб. ст. М.: Изд-во Моск. физ.-тех. инст-та, 1990. - с. 4-14.

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

10. Величенко В.В. Способ определения условного минимума функции многих переменных /В.В. Величенко // Автоматика и телемеханика. 1967. - №2 - с. 171-172.

11. Галиев Ш.И. Направления убывания для минимаксных задач / Ш.И. Галиев // Журнал вычисл. математики и матем. физики. 1993. - т.ЗЗ, №1. - с. 22-34.

12. Галиев Ш.И. Направления убывания для минимаксиминных задач / Ш.И. Галиев // Журнал вычисл. математики и матем. физики. 1994. - т.34, №3. — с.323-343.

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

14. Голыптейн Е.Г. Модифицированные функции Лагранжа. Теория и методы оптимизации / Е.Г. Голыптейн, Н.В. Третьяков. М.: Наука, 1989. - 400 с.

15. Горский A.A. Модификация метода штрафных функций для решения задач выпуклого программирования / A.A. Горский // Изв. АН СССР. Серия «Техническая кибернетика». 1971.- №6 - с.25-29.

16. Гроссман К. Нелинейное программирование на основе безусловной минимизации / К. Гроссман, A.A. Каплан. Новосибирск: Наука. - 1981. - 184 с.

17. Даныпин И.Н. Конечные алгоритмы в методе центров / И.Н. Даныпин // Казан.ун-т. Казань, 1999. - 19 с. (Деп. в ВИНИТИ 22.07.99 №2378-В99).

18. Демьянов В.Ф. Точные штрафные функции в задачах негладкой оптимизации / В.Ф. Демьянов // Вестник СПбГУ, Сер. 1.-1994. вып.4 (№ 22). - с. 21-27.

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

20. Демьянов В.Ф. К теории нелинейных минимаксных задач / В.Ф. Демьянов, ВН. Малоземов // УМН.- 1971. т.26, №3 - с.53-104.

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

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

23. Евтушенко Ю.Г. К вопросу о систематизации численных методов нелинейного программирования / Ю.Г. Евтушенко, В.Г. Жадан. М.: ВЦ АН СССР, 1988.-66 с.

24. Евтушенко Ю.Г. Точные вспомогательные функции в задачах оптимизации / Ю.Г. Евтушенко, В.Г. Жадан // Журнал вычисл. математики и матем. физики. — 1990. т.30, №1. - с.43-57.

25. Еремин И.И. Метод «штрафов» в выпуклом программировании / И.И. Еремин // ДАН СССР 1967. - т. 173, №4 - с.748-751.

26. Еремин И.И. Введение в теорию линейного и выпуклого программирования / И.И. Еремин, Н.Н. Астафьев. М.: Наука, 1976. - 190 с.

27. Жадан В.Г. О некоторых оценках коэффициента штрафа в методах точных штрафных функций / В.Г. Жадан // Журнал вычислит.математики и матем.физики. — 1984. т.24, №8.- с. 1164-1171.

28. Жадан В.Г. Численные методы линейного и нелинейного программирования. Вспомогательные функции в условной оптимизации / В.Г. Жадан. М.: Выч.центр им. А.А.Дородницына РАН, 2002. - 160 с.

29. Заботин И.Я. Вариант параметризованного метода центров / И.Я. Заботин, Е.А. Князев // Изв.вузов. Математика. 1995. - №12.- с.26-32.

30. Заботин Я.И. Минимаксный метод решения задачи математического программирования /Я.И. Заботин // Изв.вузов. Математика. 1975. - №6 - с.36-43.

31. Заботин Я.И. Алгоритмы в методе центров с аппроксимацией множества допустимых решений / Я.И. Заботин, А.А. Андрианова // Изв.вузов. Математика. — 2001. -№12.-с.41-45.

32. Заботин Я.И. Алгоритмы с комбинированием, параметризацией и двусторонним приближением в методе центров / Я.И. Заботин, И.Н. Даныпин // Изв.вузов. Математика.-1998. №12, с.40-48.

33. Заботин Я.И. Алгоритмы в методе центров с неполной минимизацией вспомогательной функции максимума / Я.И. Заботин, И.Н. Даныпин // Изв.вузов. Математика. 1999. -№12. - с.53-59.

34. Заботин Я.И. Алгоритмы с адаптацией в параметризованном методе центров / Я.И. Заботин, Е.А. Князев // Исследования по прикладной математике. 1987. - вып. 14.-е. 9-15.

35. Заботин Я.И. К сходимости методов отыскания минимакса / Я.И. Заботин, М.И. Крейнин // Изв.вузов. Математика. 1977. - №10.- с.56-64.

36. Заботин Я.И. Об одной модификации метода сдвига штрафов для задач нелинейного программирования / Я.И. Заботин, И.А. Фукин // Изв.вузов. Математика. 2000. - №12. - с.49-54.

37. Зангвилл У.И. Нелинейное программирование. Единый подход / У.И. Зангвилл. М.: Советское радио, 1973. - 310 с.

38. Зойтендейк Г. Методы возможных направлений / Г. Зойтендейк. — М.г ИЛ, 1963.-176 с.

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

40. Ижуткин B.C. Методы приведенных направлений с допустимыми точками для задачи нелинейного программирования / B.C. Ижуткин, М.Ю. Кокурин // Журнал вычислит, математики и матем. физики. 1990. - т.30, № 2.- с.217-230.

41. Ижуткин B.C. Методы приведенных направлений на основе дифференцируемой штрафной функции для задачи нелинейного программирования / B.C. Ижуткин, М. В. Петропавловский // Изв.вузов. Математика. — 1994. №12. -с. 50-59.

42. Карманов В.Г. Математическое программирование / В.Г. Карманов. — М.: Наука, 1986.-288 с.

43. Князев Е.А. О параметризованной модификации метода центров для решения задачи выпуклого программирования / Е.А. Князев // Казан, ун-т. Казань, 1983. -18 с. (Деп. в ВИНИТИ 18.08.83, № 4553-83).

44. Князев Е.А. Об одной модификации параметризованного метода центров / Е.А. Князев // Исследования по прикладной математике. -1984. — вып. 12. с. 155-162.

45. Князев Е.А. Метод центров с адаптацией параметров на основе наискорейшего спуска / Е.А. Князев // Исследования по прикладной математике. -1988. вып. 15.-с. 13-24.

46. Князев Е.А. в -субградиентные алгоритмы с адаптивным параметрическим управлением в методе центров / Е.А. Князев // Исследования по прикладной математике. 1989. - вып. 16. — с. 108-120.

47. Кораблев А.И. е -субградиентный метод решения нелинейных экстремальных задач / А.И. Кораблев // Исследования по прикладной математике. -1979. вып.7. - с.3-11.

48. Кораблев А.И. Об одном методе отыскания минимакса / А.И. Кораблев // Исследования по прикладной математике. 1979. - вып.7.- с. 19-23.

49. Коткин Г.Г. Класс методов последовательной безусловной минимизации / Г.Г. Коткин. М.: ВЦ АН СССР, 1989. - 64 с.

50. Крейнин М.И. К вопросу о нахождении приближенного минимакса / М.И. Крейнин //Программирование и численные методы: Сб. ст. Казань: Изд-во КГУ, 1978. -с.65-70.

51. Крейнин М.И. О применении минимаксных методов для решения задач оптимизации с ограничениями / М.И. Крейнин // Казан, ун-т. — Казань, 1980. — 20 с. (Деп в ВИНИТИ 18.03.80, № 1057-80).

52. Куликов А.Н. Выпуклая оптимизация с заданной точностью / А.Н. Куликов, В.Р. Фазылов // Журнал вычисл. математики и матем. физики. 1990. - №5. -с. 663-671.

53. Полак Э. Численные методы оптимизации. Единый подход / Э. Полак. -М.:Мир, 1974. 376 с.

54. Поляк Б Л7 Метод штрафных оценок для задач на условный экстремум / Б.Т. Поляк, Н.В. Третьяков // Журнал вычисл. математики и матем. физики. — 1973. — т. 13, №1. -с.34-46.

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

56. Разумихин Б.С. Физические модели и методы теории равновесия в программировании и экономике / Б.С. Разумихин. М.: Наука, 1975. - 297 с.

57. Cea Ж. Оптимизация. Теория и алгоритмы / Ж. Cea.- М.: Мир, 1973. 244 с.

58. Скоков В.А. Некоторый вычислительный опыт решения задач нелинейного программирования / В.А. Скоков // Математические методы решения экономических задач: Сб. ст. М.: Наука, 1977. - вып.7 - с.51-69.

59. Сухарев А.Г. Курс методов оптимизации / А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. М.: Наука, 1986. - 328 с.

60. Третьяков Н.В. Метод штрафных оценок для задач выпуклого программирования / Н.В. Третьяков// Экономика и математические методы. — 1973. -т.9, №3. с.526-540.

61. Фазылов В.Р. Один общий метод отыскания точки выпуклого множества / В.Р. Фазылов // Изв.вузов. Математика. 1983. - №6. - с.44-51.

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

63. Фиакко А. Нелинейное программирование. Методы последовательной безусловной минимизации / А. Фиакко, Г. Мак-Кормик. М.: Мир, 1972. — 240 с.

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

65. Эльстер К.-Х. Введение в нелинейное программирование / К.-Х. Эльстер, Р. Рейнгард, М. Шойбле, Г. Донат. М.: Наука, 1985. - 264 с.

66. Bertsecas D.P. Necessary and sufficient conditions for a penalty method to be exact / D. P. Bertsecas // Math.Programming 1975.-v.9, №1. - p.87-99.

67. Bui Trong Lieu. La methode des centers dans un espace topologique / Bui Trong Lieu, P. Huard // Num.Math. 1966. - v.8, №1. - p.56-67.

68. Charalambous Ch. A negative-positive barrier method for non-linear programming / Ch. Charalambous // IntrnatJ.Systems Sci. 1976. - v.7. - p.557-575.

69. Di Pillo G. Exact penalty functions in cinstrained optimization / G. Di Pillo, L. Grippo // SIAM J.Control Optim. 1989. -v.27. - p. 1333-1360.

70. Elzinga J. A general cutting plane algorithm for the convex programming problem / J. Elzinga, T.G. Moore // Math. Programming. 1975. - v.8, № 2. - p. 134-145.

71. Grobmann Ch. Rates of convergence in methods of exterior centers / Ch. Grobmann // Math.Operationsforschung und Statistik, ser. Optimization. 1978. - v.9, №3. - p.373-388.

72. Fletcher R. A exact penalty function for nonlinear programming with inequalities / R. Fletcher // Math.Programming. -1973. v.5, №5. - p. 129-150.

73. Han S.-P. Exact penalty functions in nonlinear programming / S.-P. Han, O.L. Mangasarian // Mathematical Programming. 1979. - v. 17. - p.251 -269.

74. Hoshipo S. A method of centers algorithm with arbitrary parameter and its application / S. Hoshipo // J.Inst.Maths.Applics. 1973. - №12.

75. Huard P. Resolution of mathematical programming with nonlinear constraints by the method of centers / P. Huard // Nonlinear programming. Amsterdam, North Holland, 1967. -p.207-219.

76. Huard P. A method of centers by upper bounding functions with application / P. Huard //Nonlinear programming, N.Y., Academic Press, 1970. p. 1-30.

77. Iri M. A multiplicative barrier function method for linear programming / M. Iri, H. Imai // Algorithmica. 1986. - №1. - p.455-482.

78. Kowalik J. A new method for constrained optimization problems / J. Kowalik, M.R. Osborn, D.M. Ryan // OperatRes. 1969. - v. 17,- p.973-989.

79. Mangasarian O.L. Sufficincy of exact penalty minimization / O.L. Mangasarian// SIAM J. Contr. and Optim. 1985. - v.23, №1. - p.30-37.

80. Mifflin R. Rates of cinvergence for a method of centers algorithm / R. Mifflin // JOTA. 1976. - v. 18, №2. - p. 199-228.

81. Morrison D. Optimization by least squares / D. Morrison // SIAM J. Numer. Anal. -1968.-v.5, №l.-p.83-88.

82. Mottl J. Description of a program for nonlinear programming: the centroid program / J. Mottl // ComputJ. 1985. - v.2.8, №1. - p.89-94.

83. Powell M.J.D. A method for nonlinear constraints in minimization problems / M.J.D. Powell // Optimization. New York: Acad.Press, 1969. - p.283-298.

84. Wierzbicki A.P. A penalty function shifting method in constrained static optimization and its convergence properties / A.P. Wierzbicki // Arch. Autom I Telemech. -1971. v.16, №4. -p.395-416.