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

• Фукин, Игорь Анатольевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Фукин, Игорь Анатольевич

Введение

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

Список литературы диссертационного исследования кандидат физико-математических наук Фукин, Игорь Анатольевич, 2004 год

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.