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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ