Содержание к диссертации
Введение
1 Аппроксимация допустимого множества 19
1.1 Постановка задачи к основные понятия 19
1.2 Аппроксимация допустимого множества. Условие р - аппроксимируемости функции 24
1.3 Оценки параметров аппроксимации 33
2 Алгоритмы заданной точности в методе штрафов 47
2.1 Алгоритмы с использованием множества, погруженного в допустимое 48
2.2 Алгоритмы с аппроксимацией допустимого множества . 53
2.3 Алгоритмы, осуществляющие двустороннее приближение к решению 56
2.4 Алгоритмы с неполной минимизацией вспомогательных функций , 64
3 Реализация алгоритмов и анализ вычислительных экспери ментов 71
3.1 Процедуры реализации принципиальных алгоритмов. Вычислительные аспекты 71
3.2 Тестовые задачи 78
3.3 Результаты вычислений 87
Заключение 106
Список литературы 107
- Аппроксимация допустимого множества. Условие р - аппроксимируемости функции
- Алгоритмы с аппроксимацией допустимого множества
- Алгоритмы с неполной минимизацией вспомогательных функций
- Процедуры реализации принципиальных алгоритмов. Вычислительные аспекты
Введение к работе
В связи с повсеместным использованием вычислительной техники не вызывает сомнение необходимость перехода во всех сферах человеческой деятельности с интуитивных методов принятия решений на новые., более эффективные методы. В их основе, как известно, лежит количественное обоснование выбора того или иного варианта действий при определенных условиях. Эта проблема решается, в частности, методами математического программирования, разработке и описанию которых к настоящему моменту посвящено очень большое число работ (см., например, [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].
Одним из первых методов последовательной безусловной минимизации был метод штрафных функций, общая идея которого заключается в следующем. Для нахождения минимума функции /(ж) на множестве D строится семейство вспомогательных функций
Fk{x) = f{x)+(pk(x), (1)
где {<Рк(х), к = О,1... } - последовательность определенных и неотрицательных в Rn функций, удовлетворяющих условию
(о, xD,
lim щ(х) = < (2)
*-* [со, xD.
Алгоритм состоит в минимизации вспомогательной функции (1) при различных к Є {0,1...}, где к -> со.
Очевидно, с ростом номера к приходится "платить" большой штраф за нарушение ограничений.
Принято считать ([114],с.20), что впервые подобный подход был преме-нен еще в 1943 году Р. Курантом [129], но получил свое развитие лишь в конце 50 - начале 60 годов. В этот период была доказана его сходимость
[130], применимость для задачи со многими ограничениями [140], предложена обратная штрафная функция [128], используемая в методе внутренних штрафов [114].
Строгая формулировка идеи Куранта появилась лишь в 1962 году в [127]. В то же время [138] доказана сходимость метода для задач выпуклого программирования с ограничениями в форме неравенств.
Для задачи математического программирования общего вида У.Зангвилл [143] изучил метод для вспомогательной функции
F{x,C) = f{x) + C-V(x), (3)
где V(x) = 0 при х Є D) V(x) > 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) —> min, (4}
gi(x) - 0, i = l,m (5)
строится последовательность {хк}> где хк - точка безусловного минимума
функции
р т
Ф(х, *\ С) = f{x) + - 2(max{ft(a;) + if, О})2, (6)
z i=i
tk = {t\,.., ^J, величины tk пересчитываются но формуле tk+1 = tf+gi(xk). Метод представляет собой такой способ решения задачи (4)-(5), при котором сходимость последовательности {хк} достигается за счет итерационного уточнения сдвигов tk при фиксированном значении С, а не за счет неограниченного увеличения С как в классическом методе штрафов, осно-
ванном на вспомогательной функции F(x} С) = f(x) + С ^2 gf{x)-
Четкая формулировка метода для задачи (4)-(5) появилась в [132, 139]. Независимо от этого аналогичная идея для задач выпуклого программирования была высказана в [32, 136, 142]. В несколько иной форме метод был предложен также в [134]. Здесь вспомогательная функция представлена в виде
Ф(*,3/,С) = f(x) + $>ія(а0 + .-5^) (7)
=1 i~\
Точка хк отыскивается из условия
Ф(я:*,/,а) = тшЩх,ук,С). (8)
Легко заметить, что Ф(ж,г/, С) — $(x,t, С) — ^ J2 Уі пРи Уі = ^-
г=1
Функцию (7) можно трактовать как модификацию [124, с.255] извест-ной функции Лагранжа, полученную добавлением штрафа % ^ 9і(х) за
і=1
нарушение ограничений (5), В методе [134] приближение для множителей Лагранжа пересчитываете^ по формулам:
у^^у' + Сд^) (9)
В [98] хорошо изучены свойства функции (7), исследована скорость сход-мости метода (8)-(9) и рассмотрены некоторые вопросы, связанные с его численной реализацией. Здесь же предложено называть процедуру (8)-(9) методом "штрафных оценок", так как в экономической интерпретации метод описывает процесс планирования с помощью цен, в которые включены штрафы за нарушения ограничений на ресурсы (член % J] 9іІх))- В [139] дана вычислительная схема метода, в которой параметр С подбирается в процессе счета так, чтобы обеспечивалась наперед заданная скорость убывания величин \ді(х )|. Для задач выпуклого программирования с ограничениями в форме неравенств метод обоснован в [111]. Показано, что при условиях регулярности решения исходной задачи метод сходится в окрестности седловой точки не медленнее убывающей геометрической прогрессии, причем ее знаменатель может быть сделан сколько угодно малым за счет выбора достаточно большого штрафного коэффициента С.
На основании идеи метода штрафных оценок в [20] для решения задачи (4)-(5) предложен метод ослабления ограничений
хк+1 = Bxgmm{f(x) : \\д(х) + рк\\2 = г}, (10)
Pk+i = Рк+д(хк+і), (П)
где д(х) = {дг{х)^..,дт(х)),г > 0. Алгоритм (10)-(11) отличается от схемы (8)-(9) тем, что на каждом шаге фиксируется не вектор двойственных переменных г/k, а вектор сдвига ограничений /, подобно [139].
Для минимизации функции f(x) при ограничениях д^х) > 0, г = 1..т в
[39] использовалась вспомогательная функция
F(x,e) = f(x)+^2exp{~w- {ді{х) + є)), є > 0, w = w(s)>0, (12) »=1
f{x)=max{6J{x)}1 f>-S>-oo. (13)
Доказана сходимость последовательности (} при lim. є& = 0, где & -
fe—^оо
точка минимума вспомогательной функции 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}y к = 0,1..., гарантирующего заданную точность приближенного решения.
В данной работе задача
f(x) -тіщ (14)
fi(x)<0, ге I (15)
решается с заданной по f(x) точностью є > 0. То есть, разрабатываются алгоритмы метода штрафов, позволяющие отыскать точку х' Є X*, где X* = {х Є Z?(0) : /(ж) -Г < e},D{p) = {х Є Rn : Л(а;) +р < 0, г є /}, /* = min{/(ж), ж Є >(0)}.
Элементарный, на первый взгляд, способ оценки разности /* и / (ж&) заключается в следующем. Пусть х - проекция на множество D(0) итерационной точки X/. метода штрафов, которая является точкой минимума вспомогательной функции F(x,Ck) вида (3) . Тогда ([113], с. 38) неравенство
/* > f(xk), ВЫПОЛНЯеТСЯ ПрИ ЛЮбоМ к == 0, 1 . . . И f(xJ—f(Xk) > /* —/(ffijfc).
Так как p(xk, -^(0)) > 0, то при непрерывности целевой функции f(x)
к—>оо
увеличением Ck можно добиться любой заданной близости значений Да?) и f(xk). Основной недостаток, препятствующий практическому использованию подобного'подхода,-заключается в необходимости нахождения на каждом шаге метода штрафов проекции итерационной точки на допустимое множество, что сопоставимо по сложности с исходной задачей математического программирования. Более того, процесс проектирования приходится останавливать эвристически. Поэтому в практике заданная точность может не достигаться.
Другой способ был предложен в [47]. Здесь разность между решениями исходной и вспомогательной задачами оценивается через оптимальные значения двойственных переменных. На основе подобных оценок в [97] и [104] исследована скорость сходимости метода с квадратичным штрафом, в [105] - с модифицированным штрафом, в [106] - метода барьерных функций. В методе точных штрафов с помощью двойственных переменных в
[57] оценен штрафной коэффициент, при котором итерационная точка метода является решением исходной задачи. Оценки связи решений исходной и вспомогательной задач проводились также в [44] и [104].
В практике оптимизации решение двойственной задачи бывает известно крайне редко, поэтому описанный подход сложно реализовать в численных экспериментах для оценки близости значения целевой функции в итерационной точке к искомому решению. В этом смысле хороший результат дают оценки, основанные на априорной информации о функционалах, составляющих задачу. Так, в [81] вводится условие равномерной непрерывности через границу множества )(0) и параметры, характеризующие свойства функции f(x) и множества )(0). В [82] они используются для оценки расстояния p(xk,D(0)) ~ sup \\х — у\\ в задачах с функцией цели, удовле-
творяющей условию Липшица и штрафной функцией, оцениваемой расстоянием до множества )(0). Величина |/(ж&) — /*| оценена для задач с полиномиальной целевой функцией.
При довольно слабых предположениях в [75] по заданному числу р < 0 вычисляется значение штрафного параметра С > 0, гарантирующего попадание точки минимума вспомогательной функции в множество D(j>),p < 0. Для этого используется значение f(x{), где х\ Є -D(O), и значение *mf{f(%), х Є S}, где S - некоторое множество простой структуры) содержащее )(0). Однако, полученное решение будет недопустимым. Более того, задачи нахождения точки а?! Є )(0) и величины inf{f(x),x Є 5} могут быть сопоставимы по сложности с исходной задачей.
Следует отметить также работу [76], в которой задача математического программирования с ограничениями в форме равенств и неравенств решается с заданной точностью методом параметризации целевой функции [43],[137]. Используемая в этом методе вспомогательная функция имеет вид
F{x7 у) = (max{/(z) - м, 0}1+s + V(x): (16)
где {J, - числовой параметр, s Є {0,1,..., s}>V(x) - функция штрафа, удо-
влетворяюгцая условиям V(x) = 0 при х Є D и V{x) > 0 при х D. Параметр \i уточняется на каждой итерации, приближаясь к /*. Здесь обоснован метод в приближенной постановке, оценена близость решения вспомогательной задачи к /* и количество итераций, которое необходимо сделать для достижения заданной точности. Предложенный метод последовательной безусловной минимизации, в отличие от метода штрафов, является одношаговым, значения вспомогательной функции в итерационных точках стремятся к нулю (в методе штрафов - к /*). Эти принципиальные отличия не позволяют воспользоваться при решении задачи математического программирования методом штрафных функций результами из [76].
В [88, 93, 92] предложены методы решения с заданной абсолютной, относительной и абсолютно-относительной погрешностью задачи выпуклого программирования. Однако, они сложны в реализации и не обладают некоторыми достоинствами метода штрафов, например, большой областью сходимости.
В данной диссертации предлагается подход, отличный от рассмотренных выше. Он заключается в использовании штрафных функций, построенных для некоторого множества, погруженного в допустимое. Если в качестве такого множества принять D(p)yp > 0, то функция штрафа может иметь, например, следующий вид
У(г)=^(тах{0,Л()+р})2, р > 0. (17)
В отличие от метода модифицированных функций Лагранжа здесь аддитивный параметр р > 0 не пересчитывается на каждой итерации, а фиксирован изначально таким образом, чтобы попадание точки минимума вспомогательной функции в допустимую область гарантировало ее е-оптимальность. В данной работе также предложено для построения штрафных функций использовать аппроксимацию допустимого множества, отличную по структуре от D{p).
Независимо и одновременно с данной работой идея использования по-
груженного множества, предложенная Я.И. Заботиным в [63], была также применена в [66] для решения с заданной точностью задачи (14)-(15) методом центров.
Диссертация состоит из трех глав. Первая глава посвящена оценке величины \f(x(C)) — /*[, где /* = тіп{/(ж),ж Є ^(0)}> х{С) - решение вспомогательной задачи
F(x,C) — тгщ (18)
х Є Rn. (19)
Вспомогательные функции F(x,C) = f(x) -f- GV{x) используют штраф V{x) — 0 при х Є D' и V{x) > 0 при х ^ D\ где множество D' С D(Q) такое, что допустимое множество является его окрестностью. То есть, согласно определению ([13], с. 27), D(0) содержит открытое множество, содержащее D'.
Предлагается два способа построения множества D'. В первом случае положено D' = Dip),р > 0. Так как D(p) с >(0), то D(p) при р > 0 названо погруженным множеством. Доказано, что для любого є > 0 найдется р > 0 такое, что неравенство
1/(*(С0) - Л < є (20)
выполняется при всех С > 0 таких, что х(С) Є -^(0). Оценено подобное р ~ р{е) для задач с функцией цели, удовлетворяющей условию Липшица, и равномерно выпуклой функцией д{х) — max{/j(cc),4 = l..m}.
Во втором случае за D' принимается лебегово множество Л(а) = = {х Є Rn : V(x) < а, а > 0}. Если a = max{a : А{а) С D(0)}, то D(0) является окрестностью множества А(уа) при у Є [0,1). Множество А(7^0,7 Є (О? 1) называется в работе аппроксимацией допустимого множества. Здесь даны оценки величины тіп{/(ж), х Є Л^а)} — /* и параметров р и 7э ПРИ которых неравенство (20) выполняется при всех С > 0 таких, что ж (С) ED(0)\A{ya).
Условие равномерной выпуклости легко проверяемо для некоторых функций, например, квадратичных, но не выполняется для задач с лжнейными ограничениями. Поэтому все оценки сделаны также и для задач, в которых функция д(х) является /^-аппроксимируемой снизу.
Определение р-аппроксимируемости функции вводится в параграфе 1.2 на основе известного (1109], с. 245) понятия р-регулярности ограничений задачи математического программирования. Там же приведены достаточные условия р-аппроксимируемости снизу выпуклой функции, более слабые и универсальные, чем подобные условия для понятия р-регулярности ограничений.
В диссертации также рассмотрены штрафные функции V7(x) построенные по аппроксимации допустимого множества. То есть V7(x) = 0 при х Є Л(707), Vy(x) > 0 при х $ A(ja). В параграфе 1.3 оценены значения параметров р и 7> при которых включение точки безусловного минимума ж7(С) вспомогательной функции F7(x, С) = /(ж) + CVy(x) в D(Q) обеспечивает ее є-оптимальность.
Здесь также для различных способов построения D' и условий, накладываемых на функцию д(х)} оценивается значение штрафного параметра С > 0, при котором включения х(С) Є D(0) \ D' и х7{С) Є -^(0) достигаются.
Во второй главе построены алгоритмы решения с заданной точностью задачи выпуклого программирования.
В параграфе 2.1 приведена общая схема вычислений с использованием штрафных функций, построенных для погруженного множества D{p), где параметр р выбирается таким образом, чтобы любая точка х{С) Є D(0) являлась є-решением исходной задачи. Факт включения точки х(С) в допустимое множество используется в качестве критерия остановки процесса, На основе этой схемы обоснована сходимость двух алгоритмов, предназначенных для решения с заданной точностью задач, функции ограничений которых удовлетворяют либо условию р-аппроксимируемости снизу (алго-
ритм 1), либо равномерно выпуклы (алгоритм 2), В этих алгоритмах на итерации с номером к > 1 штрафной параметр Ck, задается по формуле Ck = {р{к)) где (р(к) - положительная возрастающая функция. Если С - величина штрафного параметра, обеспечивающего включение х(С) D(0), то при выборе функции (р(к) таким образом, что <р(1) > С, приближенное решение с заданной точностью можно получить за один процесс минимизации вспомогательной функции F(x,Ci). Однако, для расчета величины С в параграфе 1,3 используются оценки константы Липшица, модуля равномерной выпуклости и параметра р-аппроксимируемости, вследствие чего она может быть сильно завышена и включение х(С) Є D(0) также будет достигаться при С < С. Поэтому целесообразно увеличивать штрафной коэффициент постепенно так, чтобы через заданное количество итераций N>0 алгоритма он достиг величины С.
В предлагаемых алгоритмах выбирается такая положительная возрастающая функция (р(к), что
В следующем параграфе приводятся алгоритмы с применением штрафных функций, построенных по аппроксимации допустимого множества. Вычисления останавливаются при выполнении условия
s7(C)eD(0). (21)
Как и в параграфе 2.1, штрафной параметр изменяется в зависимости от номера итерации к>0 по такому правилу (р{к), что
Параграф 2.3 посвящен разработке алгоритмов, осуществляющих двустороннее приближение к решению задачи (14)-(15): изнутри множества А("уаі) и снаружи D(0). Решение останавливается при выполнении %(С) Є )(0) \ А(уа). При выборе величин р и j на основе оценок главы 1 такая
точка х(С) будет не только допустимым, но и е-оптимальным решением задачи (14)-(15).
На подготовительном этапе этих алгоритмов выбираются параметры Со и Со таким образом, что ж(С0) >(()), ж (Со) Є А(-уа). Соглано оценкам параграфа 1.3, величина Cq достаточно велика и вспомогательная функция F(x,C<\) будет очень овражной. Поэтому предложены также алгоритмы с постепенным увеличением С до тех пор, пока не выполнится включение х(С) Є D(0). Если окажется, что ж (С) ^ А{/уа)> то х(С) - искомая точка. В противном случае текущее значение параметра С принимается за Со, предыдущее значение С, при'котором х{С) $ D{0) принимается за Cq и начинается двустороннее приближение к множеству D(0) \ A{ja),
Для штрафных функций
V(x) = W(g(x)+p), (22)
где W{t) - возрастающая по і функция B.W(t) = О при і < О, W(t) > 0 при t > О, предложен алгоритм решения задачи (14)-(15), не использующий оценок главы 1. Доказано, что для штрафа (22) из равенства д(х(С)) = О следует оптимальность точки х(С). Алгоритм осуществляет двусторонние, изнутри множества -D(O) и снаружи, приближения к границе D(0). Вычисления останавливаются в том случае, когда разность между значениями функции f{x) в итерационных точках алгоритма, принадлежащих D(0) и вне его, уменьшится до величины заданной точности є.
Предложенные в параграфах 2.1 - 2.3 алгоритмы являются принципиальными, так как нахождение даже одной точки х(С), в общем случае, процесс бесконечный. Поэтому в параграфе 2.4 предлагаются алгоритмы, допускающие неполную минимизацию вспомогательных функций. В них определенный выбор параметра р в зависимости от заданной точности решения вспомогательной задачи гарантирует достижение требуемой точности решения задачи (14)-(15) при выполнении легко проверяемого на практике критерия остановки.
Для проверки работоспособности и эффективности предложенных алгоритмов в главе 3 проводится их анализ на основе вычислительного эксперимента.
В первом параграфе уточняются некоторые аспекты реализации алгоритмов на ЭВМ. Здесь обсуждается выбор функции <р(к), задающей штрафной параметр ( в зависимости от номера итерации к, доказываются практически применимые оценки величин а и V(x*)y конкретизируются оценки значений р и (f(N), используемых в алгоритмах.
В данном параграфе диссертации также предлагается такой способ изменения штрафного коэффициента в алгоритмах с двусторонним приближением, что их можно трактовать как алгоритмы решения уравнения V{x{C)) = Ц1 с точностью - по функционалу V(x).
Алгоритмы с неполной минимизацией вспомогательной функции несколько модифицированы для гарантии выполнения критерия остановки за конечное число шагов процесса минимизации вспомогательной функции.
В следующем параграфе приводятся некоторые из тех задач, что использовались в эксперименте. Объясняются способы получения априорной информации о задачах, на основании которой в алгоритмах задаются параметры построения множества /)', штрафных функций и функции <р(к). Анализ результатов решения с заданной точностью этих задач разработанными алгоритмами приводится в последнем параграфе диссертации. Для этого вычислительный эксперимент проводился для различных значений заданной точности є > 0, заданной верхней границы числа итераций N, параметра 7* Результаты вычислений сравнивались между собой и с классическим методом штрафных функций. По результатам исследования сделаны выводы о реализуемости и вычислительной эффективности предлагаемых алгоритмов, даны рекомендации по выбору различных параметров алгоритмов.
В заключении кратко сформулированы основные результаты диссертации.
В диссертации используется двойная нумерация параграфов, формул, определений, теорем и лемм. Первый номер - номер главы, в которой введены параграф, формула, определение, теорема или лемма. Второй номер указывает на место того или иного объекта внутри главы.
В основном, автор придерживается следующих обозначений:
для обозначения вещественных чисел используются строчные греческие буквы;
для обозначения векторов используются строчные латинские буквы;
для обозначения множеств и пространств используются прописные латинские буквы;
символы "(-,)" и "jj |j" означают скалярное произведение и норму, порожденную скалярным произведением;
для обозначения внутренности и границы множества используются символы "іігЬ"и "bd" (например, inti?, bdD);
6) символом "" заканчиваются доказательства теорем и лемм.
Основные результаты диссертации опубликованы в работах [63] - [65],
[67] - [73] и [115] - [120]. Результаты диссертации докладывались на Всероссийских научных конференциях "Алгоритмический анализ неустойчивых задач "(Екатеринбург, 26 февраля - 2 марта 2001 года и 2-6 февраля 2004 года), на XII весенней математической школе "Понтрягинские чтения" (Воронеж, 3-9 мая 2001 года), международном семинаре, посвященном 90-летию со дня рождения С.Н.Черникова (Екатеринбург, 1-5 июня
года), на российской конференции "Дискретный анализ и исследование операций"(24-28 июня 2002 года), на XII международной конференции "Проблемы теоретической кибернетики"(Казань, 27-31 мая 2002 года), Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, 1-5 июля 2003), XII Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 24-28 февраля
года), научной конференции "Актуальные проблемы математического моделирования и информатики "(Казань, 30 января-6 февраля 2003 года),
на итоговых научных конференциях Казанского государственного университета за 2000 - 2003 годы.
Автор выражает глубокую признательность Ярославу Ивановичу Забо-тину за чуткое руководство данной работой, постоянное внимание, понимание и моральную поддержку, а также благодарит сотрудников кафедры экономической кибернетики за полезное обсуждение результатов диссертации.
Аппроксимация допустимого множества. Условие р - аппроксимируемости функции
Пусть у = {уі,У2, ,Ут)і У Ят, ДТІ - т-мерное евклидово пространство, В,т = {у : уі 0, і = 1,.., m}. Зададим в і? выпуклую функцию .Я (у) О для любого у Є Дт так, что Эквивалентными импликациями будут Обозначим V(z) = Р(/і(ж)+р,..., fm{%)+p),P 0 и множество Л (а;) = = {яг е Rn V{%) а, а 0}. Учитывая (1.7)-(1.8), легко заметить, что V(x) — 0 при х Є А(0) и V(x) 0 при х А(0) и, по определению 1.11, V{%) является штрафной функцией, построенной для множества А(0). Так какр 0 и А(0) = D(p), то множество А(0) является погруженным в -D(O), то есть множество D(0) по определению 1.2 является окрестностью множества А(0). В соответствие задаче (1.1) поставим задачу Очевидно; задача 1.9 поставлена корректно, если множество D(p) не пусто. Лемма 1.2. Для того, чтобы существовало число р 0 такое, что множество D(p) было не пусто, необходимо и достаточно, чтобы множество D(0) удовлетворяло условию Слейтера. Доказательство. Необходимость. Пусть число р такое, что D(p) ф 0. Тогда существует точка у е D(p). По определению множества D(p) выполняется неравенства д(у) + р 0 и д(у) — р 0. Это означает, что существует точка у, в которой д(у) 0, то есть множество D(0) удовлетворяет условию Слейтера. Достаточность.. Так как множество D(0) удовлетворяет условию Слейте-ра, то существует точка у такая, что д(у) 0. Выберем число р = —д(у) О- Тогда д{у) + р 0 и множество Z?( ) ) так как имеет хотя бы одну точку у. Лемма 1.3. Если множество D(0) удовлетворяет условию Слейте-ра7 то множество D{p) не пусто тогда и только тогда, когда р -mf{g(x),x Є Rn]. Доказательство. Необходимость, Пусть точка у Є Rn такая, что д(у) — — —р. Она существует, так как — р in.f-[g(x), х Є Rn}- Тогда из равенства 9 (у) +Р — 0 следует, что D(j ) ф 0, так как множество D{p) содержит точку у. Достаточность. Покажем, что р —ті{д(х),х Є Rn}. Если это не так ир — ті{д(х),х Є Rn}, то д(х) +р 0 для всех х Rn. То есть, D(p) = 0, что невозможно по предположению. Лемма 1.4. Прир — шї{д(х) х Є Rn} множество D(p) удовлетворяет условию Слейтера. Доказательство. Выберем число р Є (p,—m{g(x),x Є Rn})- В силу непрерывности g(x) найдется точка у є D{p) такая, что g{y) —р. Тогда д Замечание. Леммы 1.2 - 1.4 позволяют для множества, удовлетворяющего условию Слейтера, построить непустое погруженное множество, также удовлетворяющее условию Слейтера. Для удобства изложения результатов сформулируем определение (р, /З, А)-аппроксимации функций на основе приведенного в определении 1.10 известного понятия р-регулярности ограничений для задачи математического программирования. В этом определении и последующих леммах будем считать, что функция р(х) определена в Rn, число А таково, что G - заданное в Ra множество, М(Л) Пб/0и, как обычно, р(х, М(Х)) = — inf \\х — г/11.
Определение 1.14. Функцию будем называть (р, /3, А)-аппроксимирующей снизу заданную функцию р(х), а функцию (fi(x) - (р, {3, А)-аппроксимируемой снизу на лтооюестве G, если Замечание. Функция ф(х) может быть определена лишь в тех случаях, когда число А такое, что М(А) ф 0. Как видно на рисунке 1.1, параметр (3 0 такой, что функция ф(х), определенная на множестве G С Rn лежит не выше функции (р(х) при всех х Є G. Заметим, что не для всякой функции (р(х) и любого числа А существует параметр /? 0 такой, что функция ц (х) будет (р,/3,А) -аппроксимируемой снизу на G с Rn. Укажем достаточные условия (p,j3y А)-аппроксимируемости снизу для выпуклой функции р($). Лемма 1.5. Пусть функция р{%) определена, непрерывна и является выпуклой на выпуклом множестве G С Rn, для числа X множество G П М(А) ограничено и существует точка х Є G такая, что р{х) А. Тогда найдется число (3 = /3(A) 0 такое, что для функции ф{х)} определенной условием, (1.10) будет выполнятся неравенство (1.11). Доказательство. В тривиальном случае G С М(Х) существование (р,/5, А)-аппроксимирующей функции очевидно. Пусть G \ М(Х) ф 0 и ж - произвольная точка из G \ М(А). Поскольку G - выпуклое множество, то ах \- (1 — а)х Є G для всех а Є (0,1). Так как р(х) А, то в силу непрерывности функции -р(х) найдется такое а Є (0,1), что в точке у = ах-\-(Х —а?) ж, , выполняется равенство , то при этом из условия выпуклости функции (р(х) на множестве G вытекает неравенство (р(у)- а р(х) .4- (1 — а)(р(х). Отсюда с учетом Поскольку уух Е G П М(А), то выполняется неравенство у — S"J (і, где d- диаметр компакта GflM(A). Кроме того, \\у—х\\ р(х, М(Х)). Положим р = р 0. Тогда из (1.13) неравенство (1.11) следует при функции ф(х), определенной условием (1.10). Следствие 1. Пусть для функции ф{х), множества G С Rn и числа X выполняются условия леммы 1.5. Тогда для любого X X найдется число /? = /З(А ) 0 таков; что функция р(х) будет (р, /З , А )-аппроксимируемой снизу на G. Доказательство. Действительно, так как в силу условий леммы 1.5 существует точка х Є G такая, что р(х) А, то у?(ж) А . В силу ограниченности множества G П М(Х) и выпуклости функции р{%) для любого A А множество GnM(X ) ограничено. Тогда по лемме 1.5 найдется число /? = р(Х ) 0 такое, что ip(x) /З р(ж, М(Х )) + А для х Є G \ М(Х ). Замечание. Здесь была использована схема доказательства известной леммы ([109], с. 246) об условиях р-регулярности ограничений в задаче выпуклого программирования. Но лемма 1.5 может быть использована безотносительно задачи условной оптимизации и множество G может быть неограниченным. Например, G может быть плоскостью любой размерности в Rn или совпадать с Rn. В первом случае лемму 1.5 возможно будет использовать при исследовании задач выпуклого программирования, когда среди ограничений есть линейные уравнения, а во втором - лемма 1.5 дает условия (р, /3, А)-аппроксимируемости снизу выпуклой в Rn функции на всем пространстве Rn. Лемма 1.6. Пусть функция р(х) является непрерывной и выпуклой на Rn. Если функция (р(х) является (р,/3, А) -аппроксимируемой снизу на G С Rn, то функция к{х) = т р(ж),0 г 1 является (р, т/3, А )-аппроксимируемой снизу на G при А А. Доказательство. Пусть А Х,Е(Х ) = {х : х Є В к(х) А }. Если G е М(А ), то существование [р, т/3, А )-анпроксимирующей функции очевидно. В противном случае произвольно выберем точку х! Є G \ Е(Х/). Тогда и х! : М(Х). Пусть Хр - проекция точки х1 на множество М(Х). Тогда Так как х . Е(Х ), то, учитывая (1.15), имеем При т = 1,А = А функция к(х) будет по условиям леммы (р,т/?, А )-аппроксимируемой снизу на G. В противном случае хотя бы одно из нестрогих неравенств в цепочке (1.16) будет выполнятся как строгое и p(x ) — p(xp). Так как p{x) - непрерывная функция, то внутри отрезка, соединяющего точки х ,хР, найдется такая точка у что Это значит, что найдется такое число а Є (О,1), для которого у — ахР -Ь 4-(1 — (У\х . где Так как (p(os) - выпуклая на Rn функция, то (р(у) аир(хр) + (1 — а) р(х ). Отсюда, учитывая (1.15), (1.17) и (1.18), получим По условию леммы ip{x) /Зр(х: M(A))-А для всех х є G\M(A), а в силу (1.14), тем более, это неравенство выполняется для всех х є G\ Е(Х ), то есть В частности, неравенство (1.20) выполняется для х = х . Тогда, усиливая неравенство (1.19) подстановкой вместо f(x ) в правой части числа /?р(ж;, М(Х)) + А, получим В силу (1.17) выполняется включение у Є Е(Х ). Тогда \\х —у\[ р{х , Е(Х )), ж из неравенства (1.21) следует неравенство rtpix ) rj3p(x E{X )) + А . Таким образом, в силу произвольности выбора х Є G\ Е(Х ) можно построить функцию ф(х), аппроксимирующую функцию к(х) по правилам (1.10)-(1.11) параметрами /3,А А. Замечание. Обратим внимание на частный случай т 1 в лемме 1.6. В этом случае Е(Х) М(Х). В отличие от следствия к лемме 1.5 в лемме 1.6 не требуется выполнение условий леммы 1.5. Для спреведли-вости утверждения леммы 1.6 достаточно, чтобы существовала функция,
Алгоритмы с аппроксимацией допустимого множества
Пусть Vy(x) - функция штрафа множества Л(-уа), где 0 j 1. То есть Yy(x) = 0 при ее Є A(YS) И У7(Ж) 0 при х 0 Л(ja). Тогда по определению множества Л(а) функция V7(x) = 0 при V{x) ja, V7(x) О при V(x) 7«. Таким условиям удовлетворяет, например, функция где t+ = max{0,t}. Пусть А(а) = {х Rn: V(x) а}. Тогда A(ya) с A(a) С A{a) с D(0) и D(p) = A(0) С A{ a) С Afya). Отсюда по определению 1.2 множество А(7сё) при 7 Є (0,1) является погруженным в D(0), а множество -D(p) погружено в А{ а). Для решения задачи (1.1) с заданной точностью в данном параграфе используется вспомогательная функция множество Х7(С) Argmm-[F1(x,C),x Є Rn} точки а?7(С) Є Ху(С). Как и в главе 1 будем обозначать С7 - число, при котором V{x{G1)) = у а, С _ число, при котором V(x(C)) а, ДV(x) = v( x) $ число из условия Алгоритм 3. Задается требуемая точность решения є 0. Выбирается р Є (0, mia{дwj/fr )) І р э })) натуральное число JV. Задается хо Є Rn и возрастающая функция {) такая, что ip(N) psnJ%e i& , pO-) 0. Функция штрафа выбирается вида (2.5) при s 1. Полагаем к = 1. 1. Вычисляется Ck = tp{k). 2. Выбирается метод А безусловной минимизации, обеспечивающий нахождение минимума функции F1(x)Ck). 3. Методом Ak находим х Є Xy(Cfc). 4. Если Xk Є D(0), то процесе окончен и жй является допустимым є -решением задачи (1.1). Иначе заменяем к на к-Ы и переходим к п.1. Теорема 2.4. Пусть выполняются условия Ь) и с). Тогда последовательность {#&}, построенная по алгоритму 3, сходится теє- оптимальному решению задачи (1-1) не более, чем за заданное на подготовительном этапе алгоритма количество N итераций. Доказательство. Если при к N условие пункта 4 алгоритма не выполнится, то при к = N штрафной коэффициент Си жттз г - То гда по теореме (-1.9) х& Є А(а) С #(0), что означает остановку алгоритма при к = к N. В силу (1.63) f{xkJ) - / АуИсдЯ. Так как на подготовительном этапе алгоритма выбирается р ду/ , у-; то При выполнении условия а) вместо условия &) предлагается Алгоритм 4. Задается требуемая точность решения є 0. Выбирается р Є (0,тт{ 5"(ду, fg ))g)?ff}); натуральное число /V. Задается жо Є . и возрастающая функция р(-) такая, что p(N) - -i . Функция штрафа выбирается вида (2.5) при s 1. Полагаем к — 1. 1. ВыЧИСЛЯеТСЯ Cfc = (&) 2. Выбирается метод Л/; безусловной минимизации, обеспечивающий нахождение минимума функции Ку(х7С} ). 3. Методом Ак находим ж& Є Х7(Сь). 4.
Если Xk Є (0), то процесс окончен и asfc является допустимым є -решением задачи (1.1). Иначе заменяем к на к+1 и переходим к п.1. Теорема 2.5. Пусть выполняются условия а) и с). Тогда последовательность {%&}, построенная по алгоритму 4? сходится к є- оптимальному решению задачи (1.1) не более} чем за заданное на подготовительном этапе алгоритма количество N итераций. Доказательство. Аналогично доказательству теоремы 2.4 в силу (1.65) имеем f{x k) — / Y(x(cl)(V(x ) - V(x(C1))), где k! - номер шага алгоритма, на котором выполнилось условие пункта 4. Так как р 5(AV{ є(с L) то/) -/ є. В алгоритмах 3 и 4, в отличие от 1 и 2, вспомогательные функции строятся на основе штрафов аппроксимации допустимого множества. Если, при этом, функция V(x) - непрерывно дифференцируемая, то множество А(-уа) имеет довольно простую структуру в силу того, что задается лишь одним ограничением V(x) а. Поэтому в алгоритмах 3 и 4 имеется большой выбор вспомогательных функций Vy(x), обладающих дополнительными свойствами, позволяющими использовать специфические методы для их безусловной минимизации. Для решения с заданной точностью задачи (1.1) построим алгоритмы с критерием остановки, отличным от применяемого в параграфах 2.1 и 2.2. Пусть (77 - число, при котором У (ж(С7)) = уа. В параграфе 1.3 было показано, что при некоторых значениях р = р(є) выполняется f(x(C-y))—f є и ж(С7) X . Так как функция f(x(C)) не убывает по С О, то неравенство \f(x(C)) — / ] є верно для всех С С7 таких, что х(С) є D(0). Поэтому в следующем алгоритме осуществляется двустороннее приближение к множеству -D(O) \ A( ja)) где 7 произвольное число из интервала (0,1). Определенный выбор числа р 0 гарантирует е-оптимальность любой точки х(С) Є і?(0)\Л(7а). При этом предполагается, что выполняются условия Ъ), с) и Argmui{/(a;), х Є Rn} Г\ D{0) = 0, Алгоритм 5. Подготовительный шаг. Задается требуемая точность решения є. Выбираются числа 0 fy li0 p mm{L,v/??_ _.,]/, р}, CQ , G.Q - 0, 0 Л А 1. Полагаем к = 0. 1. Находим Ск = ХкСк + (1 - Afe) 2b где А Хк А. 2. Выбирается метод Ак безусловной минимизации, обеспечивающий нахождение минимума функции F(x, (7). 3. Методом Ak отыскиваем x(Ck) Є Х(Ск) 4. Если х{Си) Є (0) \ A(ja), то процесс окончен и x{Ck) является е-решением задачи (1.1). 5. Если x{Ck) Є А{ уа) то полагаем Ск+і = Ck Ck+1 = Ск. Иначе Ck+i = Cfe, Cfc+1 = С .
Алгоритмы с неполной минимизацией вспомогательных функций
Алгоритмы 1-7, предложенные в параграфах 2.1 - 2.3 являются принципиальными., так как в них необходимо вспомогательные задачи решать точно. В общем случае это означает бесконечный процесс минимизации вспомогательных функций. Если процесс безусловной минимизации вспомогательных функций оста-навливать по эвристическому критерию \F{x C) — F{x}z i)C)\ 5, где 8 - достаточно малое заданное число, (} - последовательность точек приближения к Aigmin{F(x С), ее І }, то даже при включении х Є D(0) нет гарантии выполнения неравенства /() — / є, где є - заданная точность нахождения / . В данном параграфе приводятся алгоритмы, допускающих приближенное решение вспомогательных задач. Определенный выбор параметра р в зависимости от заданной точности решения вспомогательных задач обеспечивает требуемую точность решения задачи (1.1). Алгоритм 8 . Задается требуемая точность решения є 0,ж0 Є Rn натуральное число N, число S Є (0,є). Выбирается 0 р min{ ( — 5),р ,р}, возрастающая функция ip(-) такая, что ip(l) 0, p{N) Ш. Полагается к 1. І.Вьічисляется 0% — как в алгоритме задается CN — =J, то Учитывая, что р (е - 5), получим f(xN) - / 2Х 5) + rf = є. П Так как при вычислении величины CV в практике используются оценки параметров L и /?, то значение (Тдг будет завышенным и х(Ср?) Є ІггЬЛ(а). Тогда найдется число г 0 такое, что все множество ш[х(С ),г) — {ж є . : p(as,X(Cjv)) г} будет лежать в А (а). Так как функция F(K,C) непрерывна по ж Є Rn то для последовательности {yi}, минимизирующей функцию F{x, CN), найдется номер V такой, что неравенство p{yi,X{C )) г выполняется при всех 1 V. Таким образом процесс нахождения точки ж в пункте 3 алгоритма будет в большинстве случаев на практике конечным. Если решение всломогательной задачи единственно при всех С таких, что х{С) Є А(а), то можно теоретически гарантировать сходимость процесса нахождения ждг є А(а) ПХ$(Сх) за конечное число шагов. Для этого достаточно потребовать на подготовительном этапе алгоритма выполнения Тогда аналогично доказательству теоремы 2.10 легко доказывается неравенство /(aijv) — / е. При этом 7дг = - С, где С - параметр штрафа, при котором гарантируется включение х(С) Є А(а). Докажем, что #(Сдг) Є ІІЇЬ4.(СК). Действительно, так как 0 С Cjv, то в силу единственности точек безусловных минимумов функций F(X,CN) И F(X,C) имеем неравенства Складывая неравенства р(к). 2. Если к N, то находится приближенное решение задачи min F(x} Сц). xeRn Переход к шагу 1 при к, замененном на к+1. З.Бсли к N, то находится точка х А (се), являющаяся 5-оптимальным по функционалу решением задачи min F(ж, CV). Точка ж_/у принимается в качестве є - решения задачи (1.1). г Теорема 2.10. Пусть выполняются условия Ъ) и с). Тогда построение точки гсдг при помощи алгоритма 8 возможно. При этом хм Є X Доказательство.
Обозначим Х$(С) — {х Є Rn : F(x C) - F(x(C) C) S}. По теореме 1.8 из (1.62) следует, что при Сщ = = точка ie(CV) Є А(а)- Так как X{G N) Є Xs(G), то пересечение множеств А(а) и Х(С) не пусто. То есть существует точка xjf Є А(а), являющаяся -оптимальным по функционалу задачи mm{F(z, С), х Є Rn}. Так как точка х является 5-оптималъным решением вспомогательной задачи, то F(XN) - F(x(G )) S. То есть, по определению функции F(x) верно неравенство /(XN) — /( (CJV)) - GN{V(X(C )) — V(XN)) & Так как xj-j Є А(а) и x(CN) Є А(а), то V(X{GN)) — V(xN) а. Отсюда Из доказательства теоремы 1.6 видно, что f(x(CN)) — f 4р. Тогда f{xи) - f — hp /(a;jv) — /(ж(Ст\г)). Отсюда и из (2.15) получим неравенство Так как в алгоритме задается CN — =J, то Учитывая, что р (е - 5), получим f(xN) - / 2Х 5) + rf = є. П Так как при вычислении величины CV в практике используются оценки параметров L и /?, то значение (Тдг будет завышенным и х(Ср?) Є ІггЬЛ(а). Тогда найдется число г 0 такое, что все множество ш[х(С ),г) — {ж є . : p(as,X(Cjv)) г} будет лежать в А (а). Так как функция F(K,C) непрерывна по ж Є Rn то для последовательности {yi}, минимизирующей функцию F{x, CN), найдется номер V такой, что неравенство p{yi,X{C )) г выполняется при всех 1 V. Таким образом процесс нахождения точки ж в пункте 3 алгоритма будет в большинстве случаев на практике конечным. Если решение всломогательной задачи единственно при всех С таких, что х{С) Є А(а), то можно теоретически гарантировать сходимость процесса нахождения ждг є А(а) ПХ$(Сх) за конечное число шагов. Для этого достаточно потребовать на подготовительном этапе алгоритма выполнения Тогда аналогично доказательству теоремы 2.10 легко доказывается неравенство /(aijv) — / е. При этом 7дг = - С, где С - параметр штрафа, при котором гарантируется включение х(С) Є А(а). Докажем, что #(Сдг) Є ІІЇЬ4.(СК). Действительно, так как 0 С Cjv, то в силу единственности точек безусловных минимумов функций F(X,CN) И F(X,C) имеем неравенства Складывая неравенства (2.20) и (2.20), получим то есть V(x{CN)) V{x(C)). Так как V{x{C)) а, то V(x{CN)) а и ж(С/у) intA(a). Таким образом, процесс нахождения точки хм в пункте 3 алгоритма гарантированно будет конечным. Алгоритм 9. Задается требуемая точность решения е 0,ж0 Є #„, числа (5 Є (0,є), 7 Є (0ДХ натуральное число N. Выбирается 0 р
Процедуры реализации принципиальных алгоритмов. Вычислительные аспекты
Предложенные в главе 2 алгоритмы решения с заданной точностью задачи выпуклого программирования требуют для численной реализации уточнения некоторых аспектов. В первую очередь, необходимо определить закон изменения штрафного коэффициента, влияющий на скорость сходимости алгоритма. В отечественной литературе [44],[46],[47],[97] неоднократно отмечалось, что отклонение минимума вспомогательной функции от решения исходной задачи обратно пропорционально величине штрафного коэффициента. Поэтому, зачастую, лучшим оказавается мультипликативный закон увеличения параметра С. В алгоритмах 1-4, 6, 8 и 9, приведенных в главе 2, штрафной коэффициент ( задается в зависимости от номера итерации к по формуле С% — f(k), где /?() - неотрицательная возрастающая функция натурального аргумента. Если С - значение штрафного параметра, при котором обеспечивается включение х(С) Є D(0), то, подобрав функцию ( ) таким образом, что ip(l) С, условие критерия остановки будут выполнятся уже на первой итерации применяемого алгоритма. Однако, на практике оценка величины С может быть сильно завышенной и включение будет выполнятся при С С. Более того, при больших значениях параметра G вспомогательные функции F(x,C) являются очень овражными, что значительно затрудняет их минимизацию. Поэтому, в данной работе предложено постепенно увеличивать штрафной коэффициент С до тех пор, пока не выполнится включение ж (С) Є D(0). При этом, можно потребовать, чтобы параметр штрафа достиг значения С не более, чем за заданное количество N 1 итераций. Для этого достаточно подобрать такую функцию /з(-), что p(N) С. Тогда Сдт С, х(См) Є D{0) и условие критерия остановки х(С ) Є D{0) выполнится на итерации с номером к N. Для того, чтобы рост параметра С происходил по мультипликативному закону при проведении вычислений он задавался по правилу к функции (р(-) выполнены. Выбор параметра ц влияет на объем практических вычислений. Если задавать ц « 1, то это приведет к близости значений С и Сі, так как -=ь — С при (л — - 1. Тогда функция F(x, Сі) будет овражной, и, в силу того, что точка XQ Є Rn выбирается произвольно, минимизация функции F(Xj Сі) градиентными методами станет довольно проблематичной. При достаточно большом (і коэффициент С\ будет очень мал в силу того, что -- Ц —» 0 при \х — со. Тогда при малых номерах к все С& окажутся близки MJV-fc к нулю. Более того, разница между С и Cjy_i будет слишком большой. Если при минимизации функции F(x, CN) В качестве точки начального приближения выбрать ж(Слг_і), то процесс нахождения точки ж(Сдг) станет очень продолжительным. Поэтому имеет смысл выбирать параметр JJL в некоторых пределах, далеких от 1 и +оо. При реализации алгоритмов явно задавался начальный коэффициент Сі. Для этого полагалось и, = (-Я-)Й=Ї. Тогда имеем ip(l) = -CN-! = Сі, то есть увеличение штрафного параметра начинается с заданного числа С\. Аналогично рекомендациям по проблеме выбора (і, не следует задавать величину Сі, близкую к С.
На подготовительных этапах алгоритмов 1-6 и 8-9 в условиях, по которым выбирается параметр р и функция (р(к) используются величины а = тах{а : А(а) С D(0)}, V{x ) и AV(x(C7)) = щ )) , неизвестные в практике. Очевидно, они зависят от конкретного вида штрафной функции. Для функций штрафа (2.1) и (2.2) приведем их оценки. Доказательство. 1) Пусть I = {1,2,.., m}, x A{pq)1 то есть ]P(max{/i(a;) + p, 0})g pq. Так как в левой части неравенства сумми ІЄІ руются неотрицательные числа, то (тах{/Дж) +р, О})9 pq для любого индекса іє/и для любого х Є A(pq). Так как q 1 и р 0, то для всех і Є I выполняется fi{x) +р р, что означает попадание точки х в множество D(Q) и включение А(рд) С ?(0). Тогда р5 maxja : Л (а) С JD(0)}. Отсюда по определению а = тах{а : Л (а) С (0)} имеем а pq. Далее Vi(x ) = ХХтах{Жж ) +Р;0})3 mPq Так как /і(ж ) 0, для всех ІЄ/. 2) Выберем произвольно х Є A{pq). При этом У ж) = (max{g(x) + +р, 0})? р5 или, что то же самое, max{max(/t(s) + р, 0)]д} р. То-гда [(Л(ж) + p)+]e pq для любого і є /. Так как р 0 и g 1, то fi(x) + р р при всех г Є I. Отсюда ж Є D(0) и, в силу произвольности точки, выполняется включение A(pq) С D(0). Верны и обратные рассуждения, из которых следует (0) С Л(р3). Тогда A(pq) = )(0) и а — р3. Неравенство (ж ) р? следует из того, что х Е D(0) A(pq). Следствие. ІТри выполнении условий леммы 3.1 верни неравенства где і = m тгри использовании штрафа V(x) вида (2.1) и t — 1 при V(x) вида (2,2). Доказательство. Так как С7 - число, при котором V(x(Cy)) = ja, то по лемме 3.1 V{x(C7)) ypq. Поэтому AV{x(C7)) = ущс)) ----7 -. Используя результаты леммы, сократим дробь на величину pq 0 и получим (3.2). Если в алгоритме 3 выбирать 0 р min{Lffi р7}, где t — т при У (ж) = VI(K) и і = 1 при У(ж) = (ж), то в силу соотношений 2&(ШП)Ь — — rt-7)i: 0 будут выполняться неравенства 0 р min{-A / ))І Р } Обозначим С - число, при котором V(xy(C )) а. В доказательстве теоремы 1.9 было показано, что С (1l-ig- При р щгтл- получим
