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

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

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

Введение.

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

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

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

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

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

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

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

Глава II Использование неполной минимизации вспомогательной функции при построении алгоритмов в методе центров с аппроксимацией допустимого множества.

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

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

§ 2.3 Применение аппроксимации допустимого множества в методе центров на основе наискорейшего спуска.

Глава III Управление процессом минимизации посредством мультипликативной параметризации в методе центров.

§3.1 Роль мультипликативного параметра в методе центров сточной минимизацией вспомогательной функции.

§ 3.2 Использование мультипликативного параметра в методе внутренних центров с точной минимизацией вспомогательной функции.

§ 3.3 Использование мультипликативного параметра в методе внешних центров с точной минимизацией вспомогательной функции.

§3.4 Мультипликативная параметризация в алгоритмах в методе центров с неполной минимизацией вспомогательной функции.

Глава IV Решение тестовых задач.

Введение диссертации (часть автореферата) на тему «Алгоритмы с аппроксимацией допустимого множества в методе центров»

Применение методов математического программирования для решения практических задач сопряжено с возникновением ряда вычислительных проблем, которые требуется решить вычислителям для обеспечения эффективной работы методов. Большинство известных на данный момент методов математического программирования ([8, 10, 12, 16, 25, 29, 31, 42, 43, 47, 58, 60, 61, 62, 64, 69, 70]), решают задачу следующего вида: тш{/(х),хе£>}, (1) где £> = {х: х е Яп, £(х) < 0}, g(<x) = тах^ (х), / е {1,2.т} }.

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

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

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

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

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

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

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

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

Ц*^ ~ ХК II - £ •

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15

Заключение диссертации по теме «Вычислительная математика», Андрианова, Анастасия Александровна

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

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

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

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

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

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

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

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

125

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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