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

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

Фукин Игорь Анатольевич

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

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

Автореферат

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

Казань — 2004

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

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

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

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

Жадан Виталий Григорьевич

доктор технических наук, профессор Галиев Шамиль Ибрагимович

Ведущая организация: Московский государственный университет им. М.В. Ломоносова

Защита диссертации состоится "23" сршпаЛря 2004 г. в И^Рчасаъ на заседании диссертационного совета К-212.081.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Казанском государственном университете (420008, г. Казань, ул. Кремлевская, 18, корпус , ауд. 1В)

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

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

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

доцент Агачев Ю.Р.

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

Актуальность темы.

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

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

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

Существенный вклад в исследование вопросов построения алгоритмов и получения условий достижения точного или приближенного решения задачи (1)-(2) в методе штрафных функций в разное время внесли такие отечественные ученые, как Васильев Ф.П., Гольштейн Е.Г., Евтушенко Ю.Г., Еремин И.И., Жадан В.Г., Поляк Б.Т. Скарин В.Д., Федоров В.В., и другие.

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

Дат) -> гпш, Д(аг) < 0, г € /

(1) (2)

РОС. НАЦИОНАЛЬНА! БИБЛИОТЕКА

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

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

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

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

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

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

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

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

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

ритмический анализ неустойчивых задач"(Екатеринбург, 26 февраля - 2 марта 2001 года и 2-6 февраля 2004 года), на XII весенней математической школе "Понтрягинские чтения"(Воронеж, 3-9 мая 2001 года), международном семинаре, посвященном 90-летию со дня рождения С.Н.Черникова (Екатеринбург, 1-5 июня 2002 года), на российской конференции "Дискретный анализ и исследование операций"(24-28 июня 2002 года), на XII международной конференции "Проблемы теоретической кибернетики" (Казань, 27-31 мая 2002 года), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 1-5 июля 2003), XII Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, 24-28 февраля 2003 года), научной конференции "Актуальные проблемы математического моделирования и информатики" (Казань, 30 января-6 февраля 2003 года), на итоговых научных конференциях Казанского государственного университета и научных семинарах кафедры экономической кибернетики Казанского государственного университета за 2000 - 2003 годы.

Публикации. Основные результаты изложены в 16 работах.

Структура и объем работы. Диссертация состоит из введения, трех глав и заключения. Библиография включает 143 наименования. Общий объем диссертации составляет 123 страницы.

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

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

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

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

Пусть функции f(x),fi(x), для ¿£/ = {1,2... тп} определены, непрерывны и выпуклы в n-мерном евклидовом пространстве R„. Для любого числа р определим множество D(p) = {х G Rn,g(x) +р < 0}, где д[х) — max{/,-(x), I & I}. Считается, что минимум функции f(x) намно-жестве D(0) достигается, то есть множество X* = Argmin{/(x),x G R„} не пусто. Положим

Г = тш{/(1),1бОД}. (3)

Требуется по заданному числу е > 0 найти точку х' 6 X* = {х G -D(O) : /(х) — /* < £}. Точку х' будем называть е- решением задачи отыскания (3). Считается, что множество D>(0)удовлетворяет условию Слейтера, то есть {х 6 R,g(x) < 0} ф 0.

Определение 1. Множество А будем называть погруженным в В, если множество В является окрестностью А, то есть В содержит открытое множество, содержащее А.

Очевидно, множество D(p) погружено в D(0) при р > 0. Пусть выпуклая функция штрафа V(x) = 0 при х £ D{p) и V (x) > 0 при х £ D(p), р > 0. Обозначим Л(а) = {х 6 Rn : V(x) < а, а > 0}. Если а = тах{а : Л (а) С D( 0)}, то D(0) является окрестностью множества A(ia) при 7 6 [0,1).

Определение 2. Множество A("fa),j 6 [0,1) будем называть аппроксимацией допустимого множества.

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

М(А) = {х : х € Rn, ф) < А} ф 0,

G - заданное в Rn множество, AÍ(A)flG 0 и р(х, М(А)) = inf |

геМ(А)

Определение 3. Функцию

^ = {/?/>(*. Af(А)) + A Vx G G \ М(А), ¡3 > 0

будем называть (р, /3, А)-аппроксимирующей снизу заданную функцию а функцию -аппроксимируемой снизу на множестве

G? если

■ф(х) < tp(x) Vx € G. (5)

(4)

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

Параграф 1.3 посвящен оценке величины \f{x(C)) — /*|, где х(С) -точка безусловного минимума вспомогательной функции F(x,C) = = f(x) + CV(x). Доказано, что для любого е > 0 найдется р > 0 такое, что неравенство

| f{x[C))-r\<e (6)

выполняется при всех С > О таких, что х(С) £ .D(O). Для оценки подобного р = р(е) накладываются следующие дополнительные условия.

Условие а) Функция д(х) является равномерно выпуклой на множестве D(0) с неубывающим модулем выпуклости S(t).

Условие Ь) Существуют числа pf € (Oif0> где р € (0, — inf{<7(£),

такие, что множество ограни-

чено, где Q(t) = {xERn: f(x) < t}.

Условие с) Существует число р € (0, — inf{g(x),a: € -ßn}) такое, что функция цели /(я) удовлетворяет на множестве D(0) П Q(fp)l условию Липшица с константой L, где fß = min^/(i).

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

Лемма 1. Пусть выполнено условие 6). Тогда для числа рГ найдется ß = ßfef) > 0 такое, что функция q(x) будет (р, ß, —р)-аппроксимируемой снизу на множестве Q(f) при всех р

Всюду далее ß > 0 - параметр, при котором функция q(x) является (p,ß, —р) аппроксимируемой снизу на множестве Q(f)-

Получены оценки параметра р.

Теорема 1. Пусть выполняются условия а) и с), число р 6 (О, min{J(e/L),p}). Тогда |/(х) — /*| < е, для любой точки х £ Q, где Q = {х G Rn : № < min f(x)} П Д(0).

x£D(p)

Следствие. Если для некоторого С > 0 выполняется х(С) € -D(O), то If(x(C))-r\<e.

Замечание. В теореме оценка решения не зависит от способа нахо-

ждения х £С}.

Теорема 2. Пусть выполняются условия Ь) и с), число р £ (О, тш{^,р?,р}]. Тогда любая точка х(С) £ -0(0] является е - решением задачи (1)-(2).

Оценку штрафного параметра С > 0 сверху дают следующие теоремы.

Теорема 3. Пусть выполняются условия о) и с), функции /(х), У(х) - дифференцируемы, существует <£-1(*) - функция, обратная к модулю выпуклости и Тогда неравенство

У{г{С))' (7)

С <

выполняется для всех С > 0 таких, что х(С) 6 -О(О).

Следствие. Включение х(С) £ -О(О) выполняется при всех С >

Теорема 4. Пусть выполняются условия Ь) и с), функции /(х), \(х) дифференцируемы, . Тогда неравенство

с<

1р

(8)

выполняется для всех С > 0 таких, что х(С) 6 -О(О).

Следствие. Включение х(С) £ £>(0) выполняется при всех С > Щ.

Теоремы 1 и 2 дают легко проверяемый критерий остановки в методе штрафов, а следствия к теоремам 3 и 4 указывают значение штрафного параметра С > 0, при котором условие критерия выполняется.

Далее даны оценки величины и параметров

р и 7, при которых неравенство (6) выполняется при всех С > О таких, что х[С) £ £(0) \ А{7а).

В диссертации также использованы штрафные функции Уу(х) = = (У(х) — 75)5., в > 1, = 7пах{0, 4}, построенные по аппроксимации допустимого множества. То есть Т^(х) = 0 при х £ А{7а), > О

при х $ Л (7а). Оценены значения параметров р и-д р и которых включение точки безусловного минимума х7(С) вспомогательной функции Р7(х, С) = /(х) + СУ-г(х) в В(0) обеспечивает ее £■-оптимальность.

Оценено значение штрафного параметра С > 0, при котором включение достигается.

Теорема 4. Пусть выполняются условия теоремы 3. Тогда при

Ь8-1(р)

С>

5(1 - 7)«-1а*

выполняется включение я7(С) 6 -<4(а).

Теорема 5. Пусть выполняются условия теоремы 4. Тогда при

(10)

выполняется включение

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

В параграфе 2.1 приведена следующая вычислительная

Общая схема. Задается требуемая точность решения е. Выбирается Со > 0,г > 1, число р > 0 такое, что |/(х(С)) — /*| < £, при всех х(С) 6 £>(0). Полагается к = 0.

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

2. Методом Ак находим точку х(С*) € Аг^ршп-^^.С*),:!; € -Я»,}.

3. Если х{Ск) £ -0(0)| то процесс окончен и х(Ск) является е- решением задачи (1)-(2).

4. Выбираем Ск+1 > тСк-

5. Переходим к пункту 1 при к, замененном на к + 1.

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

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

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

Алгоритм 1. Задается требуемая точность решения £. Выбираются числа р 6 и натуральное число N. Задается точка

и возрастающая функция такая, что Полагается к = 1

1. Вычисляется

2. Выбирается метод Ак, обеспечивающий нахождение безусловного минимума функции •?(£,(?*).

3. Методом Ак находим точку Хк = х(Ск)-

4.Если Хк € -О(О), то процесс окончен и Хк является е- решением задачи (1)-(2). Иначе переходим к пункту 1 при к, замененном на к + 1.

В этом алгоритме на итерации с номером к > 1 штрафной параметр Ск задается по формуле С* = <р(к), где <р(к) - положительная возрастающая функция. Если С - величина штрафного параметра, обеспечивающего включение х(С) 6 Л>(0), то при выборе функции ф{к) таким образом, что > С, приближенное решение с заданной точностью можно получить за один этап минимизации вспомогательной функции С1). Однако, для расчета величины С в параграфе 1.3 используются оценки константы Липшица, модуля равномерной выпуклости и параметра р-аппроксимируемости, вследствие чего она может быть сильно завышена.

Использовать завышенное значение С следует лишь в крайнем случае, так как увеличение параметра С ведет к ухудшению дифференциальных свойств вспомогательной функции. Но включение х(С) 6 И(0) будет достигаться и при С < С. Поэтому целесообразно увеличивать штрафной коэффициент постепенно так, чтобы через заданное количество итераций N>0 алгоритма он достиг величины С. В этом случае остановка счета произойдет, скорее всего, по критерию попадания точки минимума вспомогательной функции в разность допустимого множества и его аппроксимации.

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

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

(11)

Как и в параграфе 2.1, штрафной параметр изменяется в зависимости от номера итерации к по такому правилу <р(к), что > С, где С -значение штрафного коэффициента, при котором гарантируется вклю-

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

Параграф 2.3 посвящен разработке алгоритмов, осуществляющих двустороннее приближение к решению задачи (1)-(2): изнутри множества А(7<5) и снаружи В(0).

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

Алгоритм 2. Подготовительный шаг. Задается требуемая точность решения Выбираются числа

С0 > Со = 0,0<А<Л<1. Полагаем к = 0.

1. Находим Ск = АкСк + (1 — А*) С*, где А < А» < А.

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

3. Методом Ак отыскиваем х(Ск) € Х(Ск).

4. Если а'(Ск) £ .0(0) \Л(7а), то процесс окончен и х(Ск) является е-решением задачи (1)-(2).

5. Если х(Ск) 6 А(уа), то полагаем Ск+1 = Ск,С*+1 = Ск. Иначе Ск+1 = - Ск.

6. Переходим к пункту 1 при к, замененном на к+1.

Разработан также подобный алгоритм, применимый при выполнении условия Ь) вместо условия а).

На подготовительном этапе этих алгоритмов выбираются параметры Сц иСо таким образом, что х(Сц) £)(0), а:(Со) £ А{7а). Согласнооцен-кам параграфа 1.3, величина Со достаточно велика и вспомогательная функция Р(х, Со) будет очень овражной. Поэтому предложены также алгоритмы с постепенным увеличением С до тех пор, пока не выполнится включение Если окажется, что то х(С) - искомая точка. В противном случае текущее значение параметра С принимается за Со, предыдущее значение С, при котором х(С) £(0) принимается за и начинается двустороннее приближение к множеству

0(0)\Л(7а).

Для штрафных функций

(12)

где Ж(г) - возрастающая по г функция и И^(£) = 0 при t <0, И^) > 0

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

Алгоритм 3. Подготовительный шаг. Выбираем р > 0, Со, Cq > О такие, что x(C0)jE D{ 0), ж(Со) £ D( 0), 0 < \ <\<1,к = 0_

1. Если |/(x(Cjfe))—/(i(Cjt))| < е, то процесс окончен шя®^ я е т с я £ - решением задачи (3).

2. Находим Ск = А*С* + (1 - Ak)Qk> где А < А* < А.

3. Если x(Cfc) € £>(0), то См = Ci,C¿+1 = С*. Иначе C*+i = С*, = С*.

4. Переходим к п.1 при к, замененном на к + 1.

Алгоритм 3 осуществляет двусторонние, изнутри множества D(0) и снаружи, приближения к границе D(0). Доказано, что условия пункта 1 выполнятся через конечное число итераций.

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

Алгоритм 4 . Задается требуемая точность решения е > 0,X(¡ £ Rn, натуральное число N, число 5 6 (0,£). Выбирается 0 < р < < min{^(£ — 6),р',р}, возрастающая функция <р(-) такая, что ip( 1) > 0, ¡p(N) = =|. Полагается к = 1.

1.Вычисляется Ск = <р(к).

2. Если к < N, то находится приближенное решение задачи нахождения Переход к шагу 1 при к, замененном на К+1.

3.Если к = N, то находится точка хм £ А(а), являющаяся ¿-оптимальным по функционалу решением задачи minF(x, Си). Точка хц

ХвЯп

принимается в качестве - решения задачи (1)-(2).

Данный алгоритм позволяет найти е - решение задачи (1)-(2) при выполнении условий теоремы 4. Подобный алгоритм предложен при выполнении условия а) вместо 6).

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

Алгоритм 5. Задается требуемая точность решения е > 0,xq G Rn, числа 5 € (0, s), 7 6 (0,1), натуральное число N. Выбирается 0 < р < < ^{¿(«Kif-bl^-i-H)) 'Р'-РЬ гДе х* 6 Х*> возрастающая функция <р(-) такая, что <р( 1) > 0, <p(N) = Выбирается функция штрафа

Vy(x) = (У(х) — 7ä)+ при s > 1. Полагается к = 1.

1.Вычисляется С* = <р(к).

2. Если к < N, то находится приближенное решение задачи нахождения miii{F(i,Cjfc),x G i2n}. Переход к шагу 1 при к, замененном на к+1.

3.Если к = ÍV, то находится точка xn € являющаяся i-оптимальным по функционалу решением задачи min F~(x, Сц). Точка хк

zeRn

принимается в качестве £ - решения задачи (3).

Таким образом, алгоритмы 4 и 5 позволяют найти е - решение задачи (1)-(2) за заданное число N итераций.

В алгоритмах 4 и 5 не задается точность решения вспомогательных задач при номерах итерации к < N, так как расположение точки х^ не зависит от Xjv_i и, тем более, о тп р и к < N — 1. Решение вспомогательных задач в пунктах 2 этих алгоритмов необходимо лишь для постепенного приближения к точке

В главе 3 «Реализация алгоритмов и анализ вычислительных экспериментов» для проверки работоспособности и эффективности предложенных алгоритмов проводится их анализ на основе вычислительного эксперимента.

В первом параграфе уточняются некоторые аспекты реализации алгоритмов на ЭВМ. Здесь обсуждается выбор функции f(k), задающей штрафной параметр С* в зависимости от номера итерации к, доказываются практически применимые оценки величин а и конкретизируются оценки значений р и используемых в алгоритмах.

В данном параграфе диссертации также предлагается такой способ изменения штрафного коэффициента в алгоритмах с двусторонним приближением, что их можно трактовать как алгоритмы решения уравнения V(x(C)) = с точностью ■^а по функционалу V(x).

Алгоритмы с неполной минимизацией вспомогательной функции несколько модифицированы для гарантии выполнения критерия остановки за конечное число шагов процесса минимизации N-ой вспомогательной функции.

В следующем параграфе приводятся некоторые из тех задач, что использовались в эксперименте. Объясняются способы получения априорной информации о задачах, на основании которой в алгоритмах задаются параметры построения множеств D(p) и А(7а), штрафных функций и функции (р(к).

Анализ результатов решения с заданной точностью этих задач разработанными алгоритмами приводится в последнем параграфе главы 3. Для этого вычислительный эксперимент проводился для различных значений заданной точности £ > 0, заданной верхней границы числа итераций N, параметра 7. Результаты вычислений сравнивались между собой и с классическим методом штрафных функций. Для остановки вычислительного процесса, проводимого по методу штрафов, использовался эвристический критерий - вычисления прекращались, если при некотором номере к >0 имело место неравенство \f(xk+i) — ^ £-

По результатам исследования сделаны следующие выводы.

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

2. При решении задач алгоритмами с неполной минимизацией вспомогательной функции заданная точность достигается за заданное число N итераций алгоритма.

3. В алгоритмах, предложенных в параграфах 2.1-2.2 диссертации выполнение критерия остановки происходило не более, чем через заданное число N итераций. Вычисления зачастую останавливались менее, чем через N итераций, что говорит о целесообразности использования разработанного в диссертации критерия остановки (включение итерационной точки в D(0)).

4. В отличие от метода штрафных функций предложенные алгоритмы дают допустимое решение.

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

6. В алгоритмах, предложенных в параграфах 2.1-2.3 диссертации вычислительные затраты на решение задачи велики при очень больших,

либо очень малых N. В эксперименте лучшим для большинства задач оказывался выбор

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

8. Показатели точности, трудоемкости и скорости вычислений алгоритмов с использованием множества Б(р) примерно равны таким же показателям алгоритмов с аппроксимацией допустимого множества.

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

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

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

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

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

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

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

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

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

2. Заботин Я.И. Критерий останова в методе штрафов /Я.И. Заботин, И.А. Фукин// Современные методы в теории краевых задач "Понтря-гинские чтения".Тезисы докладов. - Воронеж, ВГУ, 2001, - С. 72.

3. Заботин Я.И. Модификация метода сдвига штрафов /Я.И. Заботин, И.А. Фукин// Алгоритмический анализ неустойчивых задач: Тез. Докл. Всерос. Науч. Конф., Екатеринбург, 26 февр/- 2 марта 2001 года. Екатеринбург:Изд-во Урал.ун-та, 2001. - С. 217-218.

4. Заботин Я.И. Алгоритм метода штрафов с аппроксимацией допустимого множества /Я.И. Заботин, И.А. Фукин//"Понтрягинские чтения - XIII". Сборник материалов - Воронеж, ВГУ, 2002. - С. 58-59.

5. Заботин Я.И. Алгоритм с погружением в допустимое множество /Я.И. Заботин, И.А. Фукин//Проблемы теоретической кибернетики. Тезисы докладов XIII международной конференции (Казань, 27-31 мая 2002 г.), Часть I / Под редакцией О.Б.Лупанова. - М.:Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С. 66.

6. Заботин Я.И. Критерий остановки, гарантирующий заданную точность в методе штрафов /Я.И. Заботин, И.А. Фукин// Материалы российской конференции "Дискретный анализ и исследование операций", 24-28 июня 2002 г. - Новосибирск, 2002. - С. 164.

7. Заботин Я.И. Конечные алгоритмы в методе штрафных функций с погружением в допустимое множество /Я.И. Заботин, И.А. Фукин// Актуальные проблемы математического моделирования и информатики (математическая научная конференция. Казань. 30 января 2002 г. - 6 февраля 2002 г.) Изд. Казанского математического общества. Казань, 2002. - С. 43-45.

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

9. Заботин Я.И. Аппроксимация допустимого множества в методе штрафов /Я.И. Заботин, И.А. Фукин// Информационный бюллетень ассоциации математического программирования. №10. Научное издание. Екатеринбург: УрО РАН, 2003. - с.110-111.

10. Заботин Я.И. Алгоритмы в методе штрафов с аппроксимацией допустимого множества /Я.И. Заботин, И.А. Фукин// Изв.вузов.Матем.

- 2004. - №1. - С.36-47.

11. Фукин И.А. Метод сдвига штрафов в решении задач экономического планирования /И.А. Фукин// Проблемы реформирования российской экономики: основные тенденции и направления. Материалы межвузовской научно-практической конференции. - Казань: Издательство "Таглимат", 2001. - С. 136-137.

12. Фукин И.А. Решение задачи линейного программирования с заданной точностью методом штрафов /И.А. Фукин// Алгебра и линейная оптимизация: Труды международного семинара, посвященного 90-летию со дня рождения С.Н. Черникова. Екатеринбург: УрО РАН, 2002.

- С.309-313.

13. Фукин И.А. Приближенное решение вспомогательных задач в методе штрафов /И.А. Фукин//Современные методы теории краевых задач: Материалы Воронежской весенней математической школы "Понт-рягинские чтения - XIV". - Воронеж, Воронежский государственный университет, 2003. - С. 144-145.

14. Фукин И.А. Вычислительный опыт решения с заданной точностью задачи выпуклого программирования алгоритмами метода штрафов с аппроксимацией допустимого множества /И.А. Фукин ; Казан, ун-т. -Казань, 2004. - 58 с: Библ. 24 назв. - Рус. - Деп. в ВИНИТИ 20.05.04 № 869-В2004.

15. Фукин И.А. Сведение решения задачи выпуклого программирования к решению уравнения /И.А. Фукин//Современные методы теории краевых задач. Материалы Воронежской весенней математической школы "Понтрягинские чтения - XV". Воронеж, ВГУ, 2004. - С.222.

16. Фукин И.А. - аппроксимируемость выпуклых функций /И.А. Фу-кин//Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. конф., Екатеринбург, 2-6 февр. 2004 г. - Екатеринбург: Изд-во Урал. унта, 2004. - С. 306-307.

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

»13613

Введение

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

1.1 Постановка задачи-и основные понятия.

1.2 Аппроксимация допустимого множества. Условие р - аппроксимируемости функции.

1.3 Оценки параметров аппроксимации.

2 Алгоритмы заданной точности в методе штрафов

2.1 Алгоритмы с использованием множества, погруженного в допустимое

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

2.3 Алгоритмы, осуществляющие двустороннее приближение к решению.

2.4 Алгоритмы с неполной минимизацией вспомогательных функций.

3 Реализация алгоритмов и анализ вычислительных экспериментов

3.1 Процедуры реализации принципиальных алгоритмов. Вычислительные аспекты.

3.2 Тестовые задачи.

3.3 Результаты вычислений.

В связи с повсеместным использованием вычислительной техники не вызывает сомнение необходимость перехода во всех сферах человеческой деятельности с интуитивных методов принятия решений на новые, более эффективные методы. В их основе, как известно, лежит количественное обоснование выбора того или иного варианта действий при определенных условиях. Эта проблема решается, в частности, методами математического программирования, разработке и описанию которых к настоящему моменту посвящено очень большое число работ (см., например, [8, 9, 17, 43, 40, 41, 55, 59, 84, 89, 94, 95, 123] и библиографию в них).

Одним из наиболее исследованных на сегодняшний день разделов математического программирования можно считать теорию линейной оптимизации [18, 52, 50, 125]. Основными направлениями развития этой области в настоящее время являются теория двойственности [53], параметризация задачи линейного программирования [27], проблемы некорректности ее постановки и нестационарного моделирования [52, 54].

Для более сложных задач квадратичного программирования, также как и для линейных, имеются конечные методы их решения [23, 74, 99, 100, 109, 121].

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

Большой интерес представляют методы последовательной безусловной минимизации [33, 114], сводящие исходную задачу с ограничениями к последовательности безусловных задач, для которых аппарат минимизации разработан достаточно хорошо, создано много методов. Здесь искомое решение определяется как предел последовательности безусловных минимумов вспомогательных задач. В зависимости от способа сведения задачи с ограничениями к семейству вспомогательных задач различают методы центров, штрафных функций, модифицированных функций Лагранжа и другие. Свое развитие этот раздел оптимизации получил благодаря работам И.И. Еремина [46], Ю.Г. Евтушенко [41, 43], В.Г. Жадана [58], Ф.П. Васильева [16], В.В. Федорова [112], Д. Бертсекаса [12]. Обзор иностранных работ по этой тематике дан в [114] и [126].

Одним из первых методов последовательной безусловной минимизации был метод штрафных функций, общая идея которого заключается в следующем. Для нахождения минимума функции f(x) на множестве D строится семейство вспомогательных функций где {ifk(x), к = 0,1.} - последовательность определенных и неотрицательных в Rn функций, удовлетворяющих условию

Алгоритм состоит в минимизации вспомогательной функции (1) при различных к £ {0,1. }, где к —оо.

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

Принято считать ([114],с.20), что впервые подобный подход был преме-нен еще в 1943 году Р. Курантом [129], но получил свое развитие лишь в конце 50 - начале 60 годов. В этот период была доказана его сходимость

Fk(x) = f(x) + <pk(x)

1)

2)

130], применимость для задачи со многими ограничениями [140], предложена обратная штрафная функция [128], используемая в методе внутренних штрафов [114].

Строгая формулировка идеи Куранта появилась лишь в 1962 году в [127]. В то же время [138] доказана сходимость метода для задач выпуклого программирования с.ограничениями в форме неравенств.

Для задачи математического программирования общего вида У.Зангвилл [143] изучил метод для вспомогательной функции

F(x1CTj = f(x)^C-V(x)i (3) где V(x) = 0 при х 6 D, V(x) > 0 при х 0 D, в которой условие (2) достигается за счет введения штрафного коэффициента. Там же было показано, что существуют вспомогательные функции типа (3), безусловный минимум которых совпадает с решением исходной задачи выпуклого программирования при достаточно большом значении параметра С. Удовлетворяющие этому условию функции штрафа названы "точными штрафными функциями".

Подобная идея высказывалась и Петшиковским [138].

Важным этапом в развитии рассматриваемых методов являются работы Еремина И.И. [46, 48, 47]. В них впервые осуществлен оценочный подход к установлению связей между исходной и вспомогательной задачами, а именно между их решениями и оценено значение коэффициента С, при котором эти решения совпадают. Впоследствии точные штрафные функции исследовались во многих работах, например, [1, 19, 35, 38, 57, 105, 110, 131, 133, 141]. В [44] было доказано, что точными штрафными функциями при определенных условиях могут быть и внутренние штрафы.

Сходство некоторых негладких штрафов с вспомогательными функциями в методе центров [135] выявлено в [26]. Отметим работу [45], в которой введено понятие точной вспомогательной функции, являющееся обобщением точных штрафов.

В [87] оценено значение штрафного коэффициента, при котором решение вспомогательной задачи существует.

Для улучшения сходимости метода штрафов независимо и почти одновременно в целом ряде работ была предложена аддитивная параметризация штрафной функции. В них для решения задачи f(x) тгп, (4)

9i{x) = 0, г = 1,т (5) строится последовательность {хк}, где хк - точка безусловного минимума функции $(x,t\ С) = f(x) + - ]Г(тах{<ф) + if, О})2, (6) z i=i tk = (if,., i^), величины if пересчитываются по формуле if+1 = i^+^a^). Метод представляет собой такой способ решения задачи (4)-(5), при котором сходимость последовательности достигается за счет итерационного уточнения сдвигов tk при фиксированном значении С, а не за счет неограниченного увеличения С как в классическом методе штрафов, оснот ванном на вспомогательной функции F(x, С) = /(ж) + С gf(x). г—1

Четкая формулировка метода для задачи (4)-(5) появилась в [132, 139]. Независимо от этого аналогичная идея для задач выпуклого программирования была высказана в [32, 136, 142]. В несколько иной форме метод был предложен также в [134]. Здесь вспомогательная функция представлена в виде т /-itu

Щх,у, С) = f(x) + + jY^SiM М i=1 i=1

Точка xk отыскивается из условия

Ч?(х\ук,С) = min Ъ(х,ук,С). (8) x&Rn т

Легко заметить, что Ф(®, у, С) = Ф(ж, i, С) ~ ^ ^ у? при уi = CU. i=1

Функцию (7) можно трактовать как модификацию [124, с.255] известной функции Лагранжа, полученную добавлением штрафа за 1 нарушение ограничений (5). В методе [134] приближение для множителей Лагранжа пересчитывается по формулам: уf+1 = у\ + Сфк) (9)

В [98] хорошо изучены свойства функции (7), исследована скорость сход-мости метода (8)-(9) и рассмотрены некоторые вопросы, связанные с его численной реализацией. Здесь же предложено называть процедуру (8)-(9) методом "штрафных оценок", так как в экономической интерпретации метод описывает процесс планирования с помощью цен, в которые включены штрафы за нарушения ограничений на ресурсы (член J2 9%(х))- В [139] 1 дана вычислительная схема метода, в которой параметр С подбирается в процессе счета так, чтобы обеспечивалась наперед заданная скорость убывания величин \gi(xk)\. Для задач выпуклого программирования с ограничениями в форме неравенств метод обоснован в [111]. Показано, что при условиях регулярности решения исходной задачи метод сходится в окрестности седловой точки не медленнее убывающей геометрической прогрессии, причем ее знаменатель может быть сделан сколько угодно малым за счет выбора достаточно большого штрафного коэффициента С.

На основании идеи метода штрафных оценок в [20] для решения задачи (4)-(5) предложен метод ослабления ограничений хк+1 = argmin{/(z) : \\д(х) = г}, (10) fc+i = Afe + 0(sjfe+i), (11) где д(х) = (gi(x),дт(х)), г > 0. Алгоритм (10)-(11) отличается от схемы (8)-(9) тем, что на каждом шаге фиксируется не вектор двойственных переменных у^ а вектор сдвига ограничений /3&, подобно [139].

Для минимизации функции f(x) при ограничениях gi{x) > 0, г = 1.т в

39] использовалась вспомогательная функция т

F(x:e) = f(x) + e®p(-iy ■ + е)), в > 0, w = гу(е) > 0, (12) г=1 тахЙ/(®)}, Г>-5>-оо. (13)

Доказана сходимость последовательности при lira = 0, где х^ оо точка минимума вспомогательной функции F(x,£k)

Естественная физическая природа метода штрафов оказалась очень плодотворной для построения многих новых методов на его основе. Так в 1964 году Хьюардом предложен метод центров [135], параметризация которого рассмотрена в [2, 60, 62, 85]. Обобщение вспомогательной функции привело к появлению метода модифицированных функций Лагранжа [28], всесторонне исследованного в [7, 12, 25, 29, 30, 31, 42, 56]. В [83, 122] описаны непрерывные аналоги метода штрафов. Хорошие результаты дало комбинирование метода штрафов с градиентными методами минимизации [86], линеаризация ограничений [36, 90, 91], параметризация вспомогательных функций [24,102], регуляризация некорректных задач с помощью штрафов [14, 15, 49, 107], применение точных интегральных штрафов для нахождения минимаксов [21] и минимаксиминов [22], использование внутренних [78] и внешних [77] штрафных функций в методе приведенных направлений [79].

Современные исследования в этой области посвящены свойствам множеств точек минимумов вспомогательных функций [4, 5, 6, 10, 11], обобщению метода точных штрафов [51, 58], созданию многометодной технологии решения задач математического программирования [80], включающей в себя метод штрафов и сходные с ним методы.

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

В данной работе задача fix) min, (14) fi(x) <о, iei (15) решается с заданной по f(x) точностью £ > 0. То есть, разрабатываются алгоритмы метода штрафов, позволяющие отыскать точку х' £ X*, где X* = {х е D{0) : fix) - f* < e},Dip) = {x 6 Rn : /»(®) + p < 0,

Элементарный, на первый взгляд, способ оценки разности /* и заключается в следующем. Пусть - проекция на множество -D(O) итерационной точки Xk метода штрафов, которая является точкой минимума вспомогательной функции F(x,Ck) вида (3) . Тогда ([113], с. 38) неравенство /* > f(xk), выполняется при любом к — 0,1. и f(x®J—f{xk) > f*—f(xk)-Так как p(xk,D(0)) -У 0, то при непрерывности целевой функции fix) k-too увеличением С& можно добиться любой заданной близости значений /(&£) и fixk). Основной недостаток, препятствующий практическому использованию подобного' подхода, • заключается в необходимости нахождения на каждом шаге метода штрафов проекции итерационной точки на допустимое множество, что сопоставимо по сложности с исходной задачей математического программирования. Более того, процесс проектирования приходится останавливать эвристически. Поэтому в практике заданная точность может не достигаться.

Другой способ был предложен в [47]. Здесь разность между решениями исходной и вспомогательной задачами оценивается через оптимальные значения двойственных переменных. На основе подобных оценок в [97] и [104] исследована скорость сходимости метода с квадратичным штрафом, в [105] - с модифицированным штрафом, в [106] - метода барьерных функций. В методе точных штрафов с помощью двойственных переменных в

57] оценен штрафной коэффициент, при котором итерационная точка метода является решением исходной задачи. Оценки связи решений исходной и вспомогательной задач проводились также в [44] и [104].

В практике оптимизации решение двойственной задачи бывает известно крайне редко, поэтому описанный подход сложно реализовать в численных экспериментах для оценки близости значения целевой функции в итерационной точке к искомому решению. В этом смысле хороший результат дают оценки, основанные на априорной информации о функционалах, составляющих задачу. Так, в [81] вводится условие равномерной непрерывности через границу множества D(0) и параметры, характеризующие свойства функции f(x) и множества D{0). В [82] они используются для оценки расстояния p(xk,D(0)) = sup \\х - г/|| в задачах с функцией цели, удовлеyeD( о) творяющей условию Липшица и штрафной функцией, оцениваемой расстоянием до множества D(0). Величина |/(ж*-) — /*| оценена для задач с полиномиальной целевой функцией.

При довольно слабых предположениях в [75] по заданному числу р < 0 вычисляется значение штрафного параметра С > 0, гарантирующего попадание точки минимума вспомогательной функции в множество D(p),p < 0. Для этого используется значение f(x{), где х\ G D(0), и значение mf{f(x), х е S}, где S - некоторое множество простой структуры, содержащее D(0). Однако, полученное решение будет недопустимым. Более того, задачи нахождения точки х\ Е D(0) и величины inf{f(x),x 6 S} могут быть сопоставимы по сложности с исходной задачей.

Следует отметить также работу [76], в которой задача математического программирования с ограничениями в форме равенств и неравенств решается с заданной точностью методом параметризации целевой функции [43],[137]. Используемая в этом методе вспомогательная функция имеет вид

F(x, ц) = (max{f(x) - ^ 0}1+s + У(я), (16) где fj, - числовой параметр, s 6 {0,1,., s}, V(х) - функция штрафа, удовлетворяющая условиям V(x) — 0 при х Е D и V(x) > 0 при х ^ D. Параметр /л уточняется на каждой итерации, приближаясь к /*. Здесь обоснован метод в приближенной постановке, оценена близость решения вспомогательной задачи к /* и количество итераций, которое необходимо сделать для достижения заданной точности. Предложенный метод последовательной безусловной минимизации, в отличие от метода штрафов, является одношаговым, значения вспомогательной функции в итерационных точках стремятся к нулю (в методе штрафов - к /*). Эти принципиальные отличия не позволяют воспользоваться при решении задачи математического программирования методом штрафных функций результами из [76].

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

В данной диссертации предлагается подход, отличный от рассмотренных выше. Он заключается в использовании штрафных функций, построенных для некоторого множества, погруженного в допустимое. Если в качестве такого множества принять D(p),p > 0, то функция штрафа может иметь, например, следующий вид

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

Независимо и одновременно с данной работой идея использования пор > 0.

17) груженного множества, предложенная Я.И. Заботиным в [63], была также применена в [66] для решения с заданной точностью задачи (14)-(15) методом центров.

Диссертация состоит из трех глав. Первая глава посвящена оценке величины |f(x(C)) — f*где /* = min{/(ж),ж G -D(O)}, х(С) - решение вспомогательной задачи

Вспомогательные функции F(x, С) = f(x) + CV(х) используют штраф V(x) = 0 при х Е D' и V(x) > 0 при х ^ D', где множество D' с D{0) такое, что допустимое множество является его окрестностью. То есть, согласно определению ([13], с. 27), D(0) содержит открытое множество, содержащее D'.

Предлагается два способа построения множества D'. В первом случае положено D' = D(p),p > 0. Так как D(p) С &(0), то В(р) при р > 0 названо погруженным множеством. Доказано, что для любого е > 0 найдется р > 0 такое, что неравенство выполняется при всех С > 0 таких, что х{С) Е D(0). Оценено подобное Р — р{£) Для задач с функцией цели, удовлетворяющей условию Липшица, и равномерно выпуклой функцией д{х) = max{fi(x),i = l.m}.

Во втором случае за D' принимается лебегово множество А(а) = = {х Е Rn : V(x) < а, а > 0}. Если а = тах{а : А(о>) С £>(0)}, то D(0) является окрестностью множества А(-уа) при у Е [0,1). Множество А(уа), 7 Е (0,1) называется в работе аппроксимацией допустимого множества. Здесь даны оценки величины min{/(a;), х Е А(уа)} — f* и параметров р и 7, при которых неравенство (20) выполняется при всех С > 0 таких,

F(x,C) — mm, х Е Rn

18) (19) f(x(C)) -ГI < е

20) что х(С) е D{0) \ /Ц'/О).

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

Определение /^-аппроксимируемости функции вводится в параграфе 1.2 на основе известного ([109], с. 245) понятия ^-регулярности ограничений задачи математического программирования. Там же приведены достаточные условия ^-аппроксимируемости снизу выпуклой функции, более слабые и универсальные, чем подобные условия для понятия р-регулярности ограничений.

В диссертации также рассмотрены штрафные функции V7(x) построенные по аппроксимации допустимого множества. То есть Уу(х) = 0 при х е А( у a), Vy(x) > 0 при х $ А(уа). В параграфе 1.3 оценены значения параметров р и 7, при которых включение точки безусловного минимума Xj(C) вспомогательной функции Fy(x,C) = f(x) + CVу(х) в D{0) обеспечивает ее е-оптимальность.

Здесь также для различных способов построения D' и условий, накладываемых на функцию <7(ж), оценивается значение штрафного параметра С > 0, при котором включения х(С) (Е D{0) \ D' и ж7(С) G D(0) достигаются.

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

В параграфе 2.1 приведена общая схема вычислений с использованием штрафных функций, построенных для погруженного множества где параметр р выбирается таким образом, чтобы любая точка х(С) Е D(0) являлась е-решением исходной задачи. Факт включения точки х(С) в допустимое множество используется в качестве критерия остановки процесса. На основе этой схемы обоснована сходимость двух алгоритмов, предназначенных для решения с заданной точностью задач, функции ограничений которых удовлетворяют либо условию р-аппроксимируемости снизу (алгоритм 1), либо равномерно выпуклы (алгоритм 2). В этих алгоритмах на итерации с номером к > 1 штрафной параметр С& задается по формуле Ck — <р{к): где ср(к) - положительная возрастающая функция. Если С - величина штрафного параметра, обеспечивающего включение х (С) £ D{0), то при выборе функции ср(к) таким образом, что <^(1) > С, приближенное решение с заданной точностью можно получить за один процесс минимизации вспомогательной функции F(x,C\). Однако, для расчета величины С в параграфе 1.3 используются оценки константы Липшица, модуля равномерной выпуклости и параметра р-аппроксимируемости, вследствие чего она может быть сильно завышена и включение х(С) (Е -D(O) также будет достигаться при С < С. Поэтому целесообразно увеличивать штрафной коэффициент постепенно так, чтобы через заданное количество итераций N>0 алгоритма он достиг величины С.

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

В следующем параграфе приводятся алгоритмы с применением штрафных функций, построенных по аппроксимации допустимого множества. Вычисления останавливаются при выполнении условия х7(С) е D(0). (21)

Как и в параграфе 2.1, штрафной параметр изменяется в зависимости от номера итерации к>0 по такому правилу <р(к), что <p(N) > С, где С -значение штрафного коэффициента, при котором гарантируется включение (21), N - верхняя граница числа итераций, за которое требуется найти допустимое е-оптимальное решение задачи (14)-(15).

Параграф 2.3 посвящен разработке алгоритмов, осуществляющих двустороннее приближение к решению задачи (14)-(15): изнутри множества А(jа) и снаружи D(0). Решение останавливается при выполнении х(С) 6 D(0) \ А(уа). При выборе величин р и 7 на основе оценок главы 1 такая точка х(С) будет не только допустимым, но и е-оптимальным решением задачи (14)-(15).

На подготовительном этапе этих алгоритмов выбираются параметры С0 и Со таким образом, что ж (Со) 0 D{0), ж (Со) Е А(уа). Соглано оценкам параграфа 1.3, величина Со достаточно велика и вспомогательная функция Fix., Со) будет очень овражной. Поэтому предложены также алгоритмы с постепенным увеличением С до тех пор, пока не выполнится включение ж (С) Е D{0). Если окажется, что ж (С) ^ A (ja), то х (С) - искомая точка. В противном случае текущее значение параметра С принимается за Со, предыдущее значение С, при'котором х(С) ^ D(0) принимается за С0 и начинается двустороннее приближение к множеству D(Q) \ А{уа).

Для штрафных функций

V(x) = W(0(x)+p)1 (22) где Wit) - возрастающая по t функция и Wit) = 0 при t < 0, Wit) > 0 при t > 0, предложен алгоритм решения задачи (14)-(15), не использующий оценок главы 1. Доказано, что для штрафа (22) из равенства д(х(С)) = 0 следует оптимальность точки х(С). Алгоритм осуществляет двусторонние, изнутри множества D{0) и снаружи, приближения к границе i?(0). Вычисления останавливаются в том случае, когда разность между значениями функции fix) в итерационных точках алгоритма, принадлежащих D(0) и вне его, уменьшится до величины заданной точности е.

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

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

В первом параграфе уточняются некоторые аспекты реализации алгоритмов на ЭВМ. Здесь обсуждается выбор функции <£>(&), задающей штрафной параметр в зависимости от номера итерации к, доказываются практически применимые оценки величин а и V(х*), конкретизируются оценки значений р и tp(N), используемых в алгоритмах.

В данном параграфе диссертации также предлагается такой способ изменения штрафного коэффициента в алгоритмах с двусторонним приближением, что их можно трактовать как алгоритмы решения уравнения V(x(C)) = ^тра с точностью ^тр-а по функционалу V(x).

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

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

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

В заключении кратко сформулированы основные результаты диссертации.

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

В основном, автор придерживается следующих обозначений:

1) для обозначения вещественных чисел используются строчные греческие буквы;

2) для обозначения векторов используются строчные латинские буквы;

3) для обозначения множеств и пространств используются прописные латинские буквы;

4) символы "(•, ■ )!| и "|| • ||" означают скалярное произведение и норму, порожденную скалярным произведением;

5) для обозначения внутренности и границы множества используются символы "int"H "bd"(например, intD, bdD);

6) символом "□" заканчиваются доказательства теорем и лемм.

Основные результаты диссертации опубликованы в работах [63] - [65],

67] - [73] и [115] - [120]. Результаты диссертации докладывались на Всероссийских научных конференциях "Алгоритмический анализ неустойчивых задач "(Екатеринбург, 26 февраля - 2 марта 2001 года и 2-6 февраля 2004 года), на XII весенней математической школе "Понтрягинские чтения" (Воронеж, 3-9 мая 2001 года), международном семинаре, посвященном 90-летию со дня рождения С.Н.Черникова (Екатеринбург, 1-5 июня

2002 года), на российской конференции "Дискретный анализ и исследование операций"(24-28 июня 2002 года), на XII международной конференции "Проблемы теоретической кибернетики"(Казань, 27-31 мая 2002 года), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 1-5 июля 2003), XII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 24-28 февраля

2003 года), научной конференции "Актуальные проблемы математического моделирования и информатики"(Казань, 30 января-6 февраля 2003 года), на итоговых научных конференциях Казанского государственного университета за 2000 - 2003 годы.

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

Заключение

Кратко сформулируем основные результаты диссертации.

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

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

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

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

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

1. Абанькин А.Е. О точных штрафных функциях /А.Е. Абань-кин//Вест.СпбУ,Сер. 1. 1995. - вып.З. - С.3-8

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

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

4. Андронов В.Г. О сходимости по функционалу метода штрафных функций /В.Г. Андронов, Е.Г. Белоусов// Изв.МГУ, серия 15. 1996. - №2 - С.59-61.

5. Андронов В.Г. О слабой сходимости по аргументу метода штрафных функций /В.Г. Андронов, Е.Г. Белоусов// Ж. вычисл. матем. и матем. физ. 1997, т.37, 4. - С.404-414.

6. Андронов В.Г. О бержевой сходимости метода штрафных функций /В.Г. Андронов, Е.Г. Белоусов// Ж. вычисл. матем. и матем. физ. -1998, т.38, 4. С.575-591.

7. Антипин А.С. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагаранжа /А.С. Антипин. М.:преприцт, 1979. - 74 с.

8. Аоки М. Введение в методы оптимизации. Основы и приложения нелинейного программирования /М. Аоки. М.:Наука, 1977. - 343 с.

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

10. Белоусов Е.Г. О непрерывности функции возмущения задачи выпуклого программирования /Е.Г. Белоусов, В.Г. Андронов// Изв.вузов. Матем. 1994. - №12. С.20-24.

11. Белоусов Е.Г. О сводимости общей задачи выпуклого программирования к задаче на безусловный экстремум /Е.Г. Белоусов, В.Г. Андро-нов//Изв.вузов.Матем. 1995. - №12. С.10-18.

12. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа / Д. Бертсекас. М.:Радио и связь, 1987. - 400 с.

13. Бурбаки Н. Общая топология. Основые структуры /Н. Бурбаки. -М.:Физматгиз, 1958. 324 с.

14. Васильев Ф.П. О регуляризации некорректных экстремальных задач с использованием штрафных и барьерных функций /Ф.П. Васильев, М.О. Ковач// Вест.Московск.ун-та. Сер.ВМК. М.:МГУ, 1980. - №2.1. С.29-35.

15. Васильев Ф.П. Применение негладких штрафных функций в методе регуляризации неустойчивых задач минимизации /Ф.П. Васи-льев//Ж. Вычислит, матем. и математ. физики. 1987. -Т.27, № 10. - С. 1444-1450.

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

17. Васильев Ф.П. Методы оптимизации /Ф.П. Васильев. М.: Изд-во "Факториал Пресс", 2002. - 824 с.

18. Васильев Ф.П. Линейное программирование /Ф.П.Васильев, А.Ю.Иваницкий. М.:Изд-во "Факториал Пресс", 2003. - 352 с.

19. Венец. В.И. Седловая точка функции Лагранжа и негладкие штрафные функции в выпуклом программировании /В.И. Венец//Автом. И телемех. 1974. - №8. - С.109-118.

20. Волынский Э.И. Об одном методе ослабления ограничений в задачах на условный экстремум /Э.И. Волынский, С.И. Касьяненко, М.З. Хен-кин// Ж. Вычислит, матем. и математ. физики. 1980. - т.20. - №2. -С.289-297.

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

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

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

24. Голиков А.И. Об одном классе методов решения задач нелинейного программирования / А.И. Голиков, Ю.Г. Евтушенко//ДАН. 1978. -т.239. - №3. - С.519-522.

25. Голиков А.И. Итеративные методы решения задач нелинейного программирования с использованием модифицированных функций Лагранжа / А.И. Голиков, В.Г. Жадан// Ж. Вычислит, матем. и математ. физики. 1980. - т.20. - №4. - С.874-888.

26. Голиков А.И. Метод внешних центров и негладкие штрафные функции /А.И. Голиков// Системы программного обеспечения решения задач оптимального планирования. VII Всеросс. симпозиум. М., 1982. -С.125-126.

27. Голыптейн Е.Г. Модифицированные функции Лагранжа /Е.Г. Голь-штейн, Н.В. Третьяков// Экон. И матем. методы. 1974. - т.Х. - вып.З. - С.568-591.

28. Голыптейн Е.Г. Градиентный метод минимизации и алгоритмы выпуклого программирования, связанные с модифицированными функциями Лагранжа /Е.Г. Голыптейн, Н.В. Третьяков//Экон. И матем. Методы. 1975. - т.XI. - вып.4. - С.730-742.

29. Голыптейн Е.Г. Слабые модифицированные функции Лагаранжа и связанные с ними теоремы двойственности /Е.Г. Голыптейн, Н.В. Тре-тьяков//Экон. и матем. методы. 1979. - t.XV. - вып.4. - С.1180-1193.

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

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

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

33. Давыдов Э.Г. Исследование операций /Э. Давыдов. М.:Высш.шк., 1990. - 383 с.

34. Данилин Ю.М. Об одной точной штрафной функции для задачи нелинейного программирования /Ю.М. Данилин, В.Н. Ковнир //Кибернетика. 1986. - №5. - С.43-46.

35. Данилин Ю.М. Модификация метода градиентного типа для минимизации негладких штрафных функций /Ю.М. Данилин, Д. Нурназа-ров//Вычисл. и прикл. матем. 1992. - вып.73. - С.108-112.

36. Демидович Б.П. Основы вычислительной математики /Б.П. Демидо-вич, И.А. Марон. М.:Наука, 1966. - 664 с.

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

38. Денисов Д.В. Модификация метода штрафов для решения задач нелинейного программирования /Д.В. Денисов, А.А. Егорушкин// Оптимизация и управление: Практич.пособие. М.-.НИВЦ МГУ, 1985. - с.50-53.

39. Евтушенко Ю.Г. Численные методы нелинейного программирования /Ю.Г. Евтушенко//ДАН. 1975. - т.221. - №5. - С.1016-1019.

40. Евтушенко Ю.Г. Численные методы решения задач нелинейного программирования /Ю.Г. Евтушенко// Ж.вычислит.матем.и математ. физики. 1976. - т.16. - №2. - С.307-324.

41. Евтушенко Ю.Г. Применение модифицированных функций Лагранжа для решения задач нелинейного программирования /Ю.Г. Евтушен-ко//Исслед.операций. 1979. - вып.7. - С.3-24.

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

43. Евтушенко Ю.Г. Оценки точности в методе штрафных функций /Ю.Г. Евтушенко//Пробл.прикл.мат. и информат: Сб.ст. М.:Наука, 1987. -С. 199-208.

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

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

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

47. Еремин И.И. Метод штрафов в линейном программировании и его реализация на ЭВМ /И.И. Еремин, М.А. Костина// Ж.вычислит.матем.и математ. физики. 1967. - т.7. - №6. - С. 1359-1366.

48. Еремин И.И. О задачах выпуклого программирования с противоречивыми ограничениями /И.И. Еремин// Кибернетика. 1971. - №4. -С.124-129.

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

50. Еремин И.И. К методу штрафов в математическом программировании /И.И. Еремин// ДАН. 1996. - т.346. - №4. - С.459-461.

51. Еремин И.И. Теория линейной оптимизации /И.И. Еремин. -Екатеринбург:Изд-во "Екатеринбург", 1999. 312 с.

52. Еремин И.И. Двойственность в линейной оптимизации /И.И. Еремин. Екатеринбург:УРО РАН, 2001. - 180 с.

53. Ермольев Ю.М. Методы решения экстремальных задач /Ю.М. Ермо-льев//Кибернетика. 1966. - №4. - С.1-17.

54. Жадан В.Г. Модифицированные функции Лагаранжа в нелинейном программировании /В.Г. Жадан// Ж.вычислит.матем.и математ. физики. 1982. - т.22. - №2. - С.296-308.

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

56. Жадан В.Г. Общие вспомогательные функции в невыпуклой оптимизации /В.Г. Жадан// Алгоритмический анализ неустойчивых задач: Тез. Докл. Всерос. Науч. Конф., Екатеринбург, 26 февр.- 2 марта 2001 года. Екатеринбург:Изд-во Урал.ун-та, 2001. С.214-215.

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

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

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

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

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

62. Заботин Я.И. Критерий останова в методе штрафов /Я.И. Заботин, И.А. Фукин// Современные методы в теории краевых задач "Понтря-гинские чтения ".Тезисы докладов. Воронеж, ВГУ, 2001, - С. 72.

63. Заботин Я.И. Модификация метода сдвига штрафов /Я.И. Заботин, И.А. Фукин// Алгоритмический анализ неустойчивых задач: Тез. Докл. Всерос. Науч. Конф., Екатеринбург, 26 февр.- 2 марта 2001 года. Екатеринбург:Изд-во Урал.ун-та, 2001. С.217-218.

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

65. Заботин Я.И. Алгоритм метода штрафов с аппроксимацией допустимого множества /Я.И. Заботин, И.А. Фукин//"Понтрягинские чтения ХШ". Сборник материалов - Воронеж, ВГУ, 2002. - С. 58-59.

66. Заботин Я.И. Критерий остановки, гарантирующий заданную точность в методе штрафов /Я.И. Заботин, И.А. Фукин// Материалы российской конференции "Дискретный анализ и исследование операций", 24-28 июня 2002 г. Новосибирск, 2002. - С. 164

67. Заботин Я.И. Конечные алгоритмы в методе штрафных функций с погружением в допустимое множество /Я.И. Заботин, И.А. Фукин//

68. Актуальные проблемы математического моделирования и информатики (математическая научная конферен-ция. Казань. 30 января 2002 г. 6 февраля 2002 г.) Изд. Казанского математического общества. Казань, 2002. - С. 43-45

69. Заботин Я.И. Аппроксимация допустимого множества в методе штрафов /Я.И. Заботин, И.А. Фукин// Информационный бюллетень ассоциации математического программирования. №10. Научное издание. Екатеринбург: УрО РАН, 2003. с.110-111.

70. Заботин Я.И. Алгоритмы в методе штрафов с аппроксимацией допустимого множества /Я.И. Заботин, И.А. Фукин// Изв.вузов.Матем. -2004. №1. - С.36-47.

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

72. Иванов В.В. К методу штрафных функций /В.В. Иванов, В.Е. Тру-тень//Кибернетика. 1968. - №2. - С.67-69.

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

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

75. Ижуткин В:С. Метод центров и барьерных функций с использованием приведенных направлений для задачи нелинейного программирования /B.C. Ижуткин, М.В. Петропавловский, А.В. Бли-нов//Изв.вузов.Матем. 1996. - №2. - С.30-41.

76. Ижуткин B.C. Методы приведенных направлений для решения задачи нелинейного программирования /B.C. Ижуткин, М.Ю. Кокурин// Ж.вычислит.матем.и математ. физики. 1998. - т.12. - №2. - С.1799-1814.

77. Казаров С.А. Сведение общей задачи математического программирования к безусловной экстремальной задаче /С.А. Каза-ров//Изв.вузов.Матем. 1972. - №1. - С.25-32.

78. Казаров С.А. Оценки близости решений экстремальных задач в методе штрафных функций /С.А. Казаров// Изв.вузов.Матем. 1978. - №9. -С.40-48.

79. Казьмин А.И. Непрерывный алгоритм в методе штрафных функций /А.И. Казьмин, М.В. Рыбашов// Автом. и телемех. 1975. - №5. -С.38.-44.

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

81. Князев Е.А. Алгоритмы с адаптацией в методе центров: Дис. . канд. физ.-матем. наук /Е.А. Князев; Казан, гос. ун-т. Казань, 1987. -134 с.

82. Конышева В.М. Сходимость и оценки скорости сходимости алгоритмов условной оптимизации, совмещающих градиентный спуск с методом штрафных функций /В.М. Конышева, С.В. Шильман// Горьк. Ун-т. Горький, 1985. - 17 с.

83. Крутто Н.И. О штрафном коэффициента в методе штрафных функций// Кибернетика /Н.И. Крутто. 1984. - №1. - С. 121-122.

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

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

86. Панин В.М. Методы конечных штрафов с линейной аппроксимацией ограничений. I /В.М. Панин// Кибернетика. 1984. - №2. - С.44-50,55.

87. Панин В.М. Об ассимптотической эквивалентности двух методов конечных штрафов первого порядка /В.М. Панин//Кибернетика. 1986.- №5. С.47-53.

88. Пинягина О.В. Общий метод выпуклого программирования с заданной точностью /О.В. Пинягина, В.Р. Фазылов//Изв.вузов.Матем. -1995. №12. - С.63-73.

89. Пинягина О.В. Метод выпуклого программирования с заданной абсолютно-относительной погрешностью/О.В. Пинягина, В.Р. Фазы-лов //Ж. вычисл. матем. и матем. физ. 1998. - Т.38. - №8. - С. 12471254.

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

91. Поляк Б.Т. Методы минимизации функций многих переменных(обзор) /Б.Т. Поляк// Экон. и матем. методы. 1967. - т.Ш. - №6. - С.881-902.

92. Поляк Б.Т. Метод сопряженных градиентов в задачах на экстремум /Б.Т. Поляк// Ж.вычислит.матем.и математ. физики. 1969. - т.9. -№4. - С.807-821.

93. Поляк Б.Т. О скорости сходимости метода штрафных функций /Б.Т. Поляк// Ж.вычислит.матем.и математ. физики. 1971. - т. 11. - №1. -С.3-11.

94. Поляк Б.Т., Третьяков Н.В. Метод штрафных оценок для задач на условный экстремум /Б.Т. Поляк// Ж.вычислит.матем.и математ. физики. 1973. - т. 13. - Ж. - С.32-46.

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

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

97. Пшеничный Б.Н. Необходимые условия экстремума /Б.Н. Пшеничный. М.Наука, 1982. - 155 с.

98. Рапопорт Л.Б. Двухпараметрический класс штрафных функций и алгоритм нелинейного п рограммирования /Л.Б. Рапопорт//Методы ис-лед.сложных систем, М., 1981. С.3-11

99. Рокафеллар Р.Т. Выпуклый анализ /Р.Т. Рокафеллар. М.:Мир, 1970. 472 с.

100. Скарин В.Д. О методе штрафных функций для задач нелинейного программирования /В.Д. Скарин// Ж.вычислит.матем.и математ. физики. 1973. - т.13. - №5. - С.1186-1199.

101. Скарин В.Д. Об одной модификации метода штрафных функций в выпуклом программировании /В.Д. Скарин//АН СССР, Уральский науч.центр. Труды инст.матем. и мех. 1973. - вып.5. - С.51-62.

102. Скарин В.Д. О скорости сходимости метода барьерных функций /В.Д. Скарин//Методы оптимизации и распознавание образов в задачах планирования, УНЦ АН СССР, 1980. С.27-36.

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

104. Сухарев А.Г; Курс методов оптимизации /А.Г. Сухарев, А.В. Тимохов,

105. B.В. Федоров. М.:Наука, 1986. - 328 с.

106. Тимохов А.В. Об одном точном методе штрафа в вогнутом программировании / А.В. Тимохов// Вестн.МГУ, 1984. сер.ВМК. - №1.1. C.77-78.

107. Третьяков Н.В. Метод штрафных оценок для задач выпуклого программирования /Н.В. Третьяков// Экон. и матем.методы. 1973. -т.IX. - С.526-540.

108. Федоров В.В. О методе штрафных функций в задаче определении максимина /В.В. Федоров// Ж.вычислит.матем.и математ. физики. 1972. - т.12. - №2. - с.321-333.

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

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

111. Фукин И.А. Сведение решения задачи выпуклого программирования к решению уравнения /И.А. Фукин//Современные методы теории краевых задач. Материалы Воронежской весенней математической школы "Понтрягинские чтения XV". Воронеж, ВГУ, 2004. - С.222.

112. Фукин И.А. р аппроксимируемость выпуклых функций /И.А. Фукин//Алгоритмический анализ неустойчивых задач: Тез.докл.Всерос.конф., Екатеринбург, 2-6 февр. 2004 г. - Екатеринбург: Изд-во Урал ун-та, 2004. - С. 306 - 307.

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

114. Шепилов М.А. Непрерывные аналоги метода штрафов для задачи выпуклого программирования//Экономика и матем. методы /М.А. Шепилов. 1975. - т.XI. - вып.4. С.130-136.

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

116. Эрроу К. Исследования по линейному и нелинейному программированию /К. Эрроу, Дж.Л. Гурвиц, Х.Удзава. М., Изд-во ин.лит., 1962. -334 с.

117. Юдин Д.В. Линейное программирования /Д.В. Юдин, Е.Г. Голь-штейн. М.:Наука, 1969. - 424 с.

118. Boukari D. Survey of penalty, Exact-penalty and multiplier methods from 1968 to 1993./D. Boukari, A.V. Fiacco//Optimization. 1995. - V.32. -№4. - P.301-334.

119. Butler T. On a method of Courant for minimizing functionals /Т. Butler, A.V. Martin// J.Math.Phis., 1962. v.41. - P.291-299.

120. Carroll C.W. The created response surface technique for optimizing nonlinear restrained system / C.W. Carroll// Operation Res., 1961. v.9. - P. 169-184.

121. Courant R. Variations methods for the solution of problems of equilibrium and vibrations /R. Courant// Bull. Am. Math. Soc., 1943.-v.49. P. 1-23.

122. Courant R. Calculs of variations and supplimentary notes and exercises (Mimeographed Notes)/ R. Courant//Supplimentary notes by M.Krushkal and H.Rubin, New York University, 1955-1957.

123. Evans J.P. Exact penalty function in nonlinear programming /J.R. Evans, F.J. Could, J.W. Tolle// Math. Program. 1973. V.4.- P.72-97.

124. Haarhoff P.C. A new method for the optimization of a nonlinear constraints /Р.С. Haarhoff, J.D. Buys// Computer J. 1970. - V.13. -№2. - P.178-181.

125. Han S.P. Exact penalty function in nonlinear programming /S.P. Han, O.L. Mangasarian// Math.Program. 1979. - 17,№3. - P.251-269.

126. Hestenes M.R. Multiplier and gradient methods /M.R. Hestenes// J.Opt. theory and appl., 1969. v.4. - №5. - P.303-320.

127. Huard P. Resolution of mathematical programming with nonlinear constraints by the method of centres/P.Huard//Nonlinear Programming. Amsterdam, North Holland. 1967. - P. 207-219.

128. Miele A. Use of the augmented penalty function in the mathematical programming problems /А. Miele, E.E. Gragg, R.R. Lyer, A.V. Leve// J.Opt. theory and appl., 1971. v.8. - №2. - P.115-130.

129. Morrison D.D. Optimization by least squares /D.D. Morrison//SIAM J. Number Analys. 1968! - V.5. - №1. - P. 83-88.

130. Pietrzikowski T. Application of the stepest descent method tj the concave programming /Т. Pietrzikowski//In Proceeding of the IFIPS Congress, Munich, 1962, North-Holland Publishing Company, Amsterdam, 1962. -P.185-189.

131. Powell M.J.D. A method for nonlinear constraints in minimization problems /M.J.D. Powell//Optimization. N.Y.:Acad.Press, 1969. - P.283-298.

132. Rubin H. Motion under a strong constraining force /Н. Rubin, P. Ungar//Common. Pure Appl. Math, 1957. -v.10 P.65-87.

133. Rubinov A.M. Decreasing functions with application to penalization /A.M. Rubinov, B.M. Glover, X.Q Yang //SIAM Journal Optimization, 2000. V. 10. P. 289-313.

134. Wierzbicki A.P. A penalty function shifting method in constrained state optimization and its convergence properties /А.Р. Wierzbicki// Arch.Autom. i Telemech. 1971. - v.16. -№4. - P.395-416.

135. Zangwill W.I. Non-linear programming via penalty function /W.I. Zangwill// Management Sci., 1967. №13(5). - P.344-358.