Оптимизация численных алгоритмов

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ .............................. 5
Глава 1.
ОБЩИЕ ВОПРОСЫ
НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 13
Глава 2.
РЕЛАКСАЦИОННОЕ УСКОРЕНИЕ ИТЕРАТИВНЫХ ПРОЦЕССОВ 35
§2.1. ОПИСАНИЕ ПРИНЦИПА МИНИМАЛЬНОСТИ........35
§2.2. ТОЧНЫЕ РЕЛАКСАЦИИ
ДЛЯ МЕТОДА ПРОСТЫХ ИТЕРАЦИЙ .............37
§2.3. ТОЧНЫЕ РЕЛАКСАЦИИ
В СКАЛЯРНОМ ПРОСТРАНСТВЕ ................39
§2.4. МНОГОМЕРНЫЙ СЛУЧАЙ (р = 1).............42
§2.5. ОБОБЩАЮЩАЯ СХЕМА.......................47
§2.6. СТАТИСТИЧЕСКИЕ СВОЙСТВА ТОЧНОЙ
РЕЛАКСАЦИИ МЕТОДА ПРОСТОЙ ИТЕРАЦИИ (р=1) 48
§2.7. АСИМПТОТИКА ТОЧНОЙ РЕЛАКСАЦИИ..........54
§2.8. НЕЛИНЕЙНАЯ СХОДИМОСТЬ (р > 1) .........58
§2.9. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ.................79
Глава 3.
ДИФФЕРЕНЦИРОВАНИЕ ПО ИТЕРАЦИИ 88
§3.1. ПОЛУПРОИЗВОДНАЯ И ЕЕ СВОЙСТВА..........88
§3.2. АНАЛИЗ СХОДИМОСТИ
С ПОМОЩЬЮ ДИФФЕРЕНЦИРОВАНИЯ ПО ИТЕРАЦИИ 91
Глава 4.
НЕЛИНЕЙНЫЕ УРАВНЕНИЯ 95
§4.1. СУЩЕСТВОВАНИЕ И ОЦЕНКА РЕШЕНИЯ
НЕЛИНЕЙНОГО УРАВНЕНИЯ....................95
§4.2. СРАВНЕНИЕ С ИЗВЕСТНЫМИ РЕЗУЛЬТАТАМИ 102
§4.3. СХОДИМОСТЬ МЕТОДА НЬЮТОНА.............109
§4.4. РАСХОДИМОСТЬ МЕТОДА НЬЮТОНА...........116
2
Глава 5.
МЕТОД КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ
(МКО) 121
§5.1. ОПИСАНИЕ МЕТОДА......................121
§5.2. ЛОКАЛЬНАЯ СХОДИМОСТЬ.................123
§5.3. ПОЛУГЛОБАЛЬНАЯ СХОДИМОСТЬ............134
§5.4. ВЫБОР НАЧАЛЬНОЙ ТОЧКИ................141
§5.5. МОДИФИКАЦИИ МЕТОДА
КВАДРАТИЧНОЙ ОПТИМИЗАЦИИ ..............150
Глава 6.
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ 154
§6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОСТРОЕНИЮ
КВАДРАТИЧНЫХ ПРОГРАММ-АППРОКСИМАЦИЙ ... 154
§6.2. ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ И АППРОКСИМАЦИЯ . . 155
§6.3. КВАДРАТИЧНЫЕ АГРЕГАТЫ................160
§6.4. ВЫБОР УЗЛОВ ИНТЕРПОЛЯЦИИ.............163
§6.5. ВЫПУКЛОСТЬ ЛИНЕЙНО-КВАДРАТИЧНОГО АГРЕГАТА 166
§6.6. АЛГОРИТМ ТРЕХКООРДИНАТНОГО СПУСКА....168
§6.7. АЛГОРИТМ ЧАСТИЧНОГО ПРОЕКТИРОВАНИЯ...174
§6.8. АЛЬТЕРНАТИВНЫЙ ПОДХОД................184
§6.9. МОДИФИКАЦИЯ МЕТОДА БИЛА..............189
Глава 7.
ДИСКРЕТНЫЕ МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ
И ПОИСКА ЭКСТРЕМУМА 204
§7.1. ДИСКРЕТНЫЙ МЕТОД ЧЕБЫШЕВА.............204
§7.2. МЕТОД МЮЛЛЕРА........................210
§7.3. ПОИСК ОДНОМЕРНОГО МИНИМУМА
НА ОСНОВЕ n-ТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ......212
§7.4. УЧЕТ ПОГРЕШНОСТЕЙ ИЗМЕРЕНИЙ ПРИ МИНИМИЗАЦИИ
МЕТОДОМ ТРЕХТОЧЕЧНОЙ ИНТЕРПОЛЯЦИИ......220
3
Глава 8.
МИНИМИЗАЦИЯ НА КОМБИНАТОРНЫХ ПРОСТРАНСТВАХ 227
§8.1. АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЯ
ДЛЯ ОДНОГО СЕМЕЙСТВА ЗАДАЧ ОБСЛУЖИВАНИЯ . 227 §8.2. КОМБИНАЦИОННОЕ ДОЗИРОВАНИЕ.........234
Глава 9.
МИНИМИЗАЦИЯ СЕПАРАБЕЛЬНЫХ ЦЕЛЕВЫХ ФУНКЦИЙ 242
ЗАКЛЮЧЕНИЕ..........................258
Указатель литературы.......................263
4
ВВЕДЕНИЕ
Как бы не совершенствовалась вычислительная техника, улучшение алгоритмов, закладываемых в нее остается вечно желанным. Всегда будут существовать задачи вычислительного типа, которые окажутся не доступны объединенным усилиям “металла” и математического обеспечения из-за нехватки быстродействия, памяти, несходимости итеративного процесса или просто отсутствия алгоритма решения.
В этой работе рассматриваются численные методы решения нелинейных уравнений и задач нелинейного программирования. Улучшение сходимости численных методов предлагается проводить с помощью принципа минимальности. Для исследования вопросов сходимости развивается аппарат дифференцирования по итерации на основе полупроизводной. Предлагаются новые алгоритмы.
Вводной для глав 5-7 является гл. 1. Основной ее объект — нелинейная программа общего вида:
/(х) —» min, (0.1)
где / — скалярная функция, именуемая целевой] D — именуемое допустимым некоторое множество; во многих важных приложениях оно задается формулой
D := {х\д(х) < 0}; (0.2)
здесь х — n-мерный вектор; д — m-мерная вектор-функция. Программа (0.1) является ключевым элементом большинства задач на оптимизацию.
Исходной задачей в гл. 1, 5-7 является нелинейная программа (0.1) с допустимым множеством (0.2), именуемая здесь для краткости задачей А. В основе многих исследований методов нелинейного программирования лежит функция Лагранжа. Для задачи А она задается формулой
F(s, А) := f(x) + \g(x),
где А — m-мерная строка. Поиск у функции Лагранжа седловой точки (£, Ä), определяемой неравенствами
F(x, Ä) > F(x, Ä) > F(x, A) VA > 0, Vs £ Rn,
(двойственная задача) здесь — задача В. Связь между решением задачи А и т-составляющей решения задачи В описана в теоремах Куна-Таккера [84]. В случае дифференцируемости функций / и д, как известно, седловая точка необходимо удовлетворяет системе
VzF(x, А) = 0 A VAF(x, А)<0 A А>0 A AVaF(x,A) = 0, (0.3)
часто называемой системой Куна-Таккера. Поиск решения системы (0.3) можно рассматривать как самостоятельную задачу, которую далее будем именовать задачей С. Выпуклость функций / и g гарантирует совпадение множества решений задач В и С [79]. Связь между решением задачи А и х-составляющей решения задачи С традиционно устанавливается при помощи посредника — задачи
5
В. В результате суперпозиции двух пар теорем получаются два утверждения, в формулировках которых есть требование выпуклости обеих рассматриваемых функций. Из обычной логики, однако, не следует характера необходимости условий в этих суперпозициях. То есть вопрос о получении более сильных результатов в отношении этих связей был открыт.
Здесь будет исследована прямая взаимосвязь задач А и С.
В гл. 2 для улучшения сходимости итеративных методов, как одноточечных, так и многоточечных, предложен принцип минимальности (ПМ), суть которого не вызывает возражений. В упрощенном виде она такова.
Пусть существует итеративный процесс вида хк+1 = .А(т*), к = 0,1,..., начатый из х°. Может оказаться, что базовый алгоритм А использует не всю доступную на к-шаге информацию. Ею может быть, например, оценка текущей погрешности dk, оценка невязки, или часто используемая оценка погрешности последующей итерации через оценку погрешности текущей
||Л(г4) - «|| < с\\хк - а||р, р>1, ft = 0,1,2,... (0.4)
Здесь {х*}о° — элементы некоторого банахового пространства, порождаемые базовым алгоритмом А, ос — искомая неподвижная точка этого алгоритма: а - А{а).
Г1М: использовать всю доступную информацию, включал А(хк), для определения последующей итерации, как обеспечивающей минимум оценки ее погрешности.
ПМ, конечно, можно сформулировать и для многоточечных методов. Модификацию базового алгоритма с помощью ПМ будем именовать его точной релаксацией.
В гл. 2 с помощью ПМ были получены расчетные формулы точной релаксации однотчечных методов для вещественных гильбертовых и евклидовых пространств с дополнительной информацией, состоящей из оценки текущей погрешности dk и оценки (0.4) при р = 1,2.
Проведены численные эксперименты с точной релаксацией модифицированного метода Ньютона для скалярного уравнения (§2.9).
При обосновании численных методов (да и, вообще, при формулировании теорем) естественно желание предельно ослабить условия и, тем самым, усилить результат. Так, ограниченность производной, по возможности, заменяется на ее липшицевость. Например, в теореме Канторовича (ТК) о сходимости метода Ньютона ([18], гл.ХУШ, § 1, т. 6) решения уравнения д(х) =■ 0 присутствует условие вида ||<?"(х)|| < X V х € 5. Ав теореме Канторовича, приведенной в книге [23] это условие заменяется на липшицевость д* в S.
Одним из ослаблений подобного рода (или иначе расширением класса рассматриваемых функций) является понятие полу производной, введенной в §3.1. Оно активно используется в методе дифференцирования по итерации (§3.2). Суть его состоит в параметризации отрезка, соединяющего решение а с текущей итерацией: xk(t) := а + t[xk - а), и исследовании задачи Коши для y(t) := x*+l(t) - а = .4(x*(£)) - а:
У = F(y, xk, **-<*), у(0) = о
с переходом к дифференциальному неравенству относительно [|у||. Так как
б
2/(1) = хму оценка для \\у(1)\\ позволяет оценить погрешность последующего приближения.
Аппарат дифференцирования по итерации был успешно применен в получении новых результатов по сходимости метода Ньютона и в обосновании метода квадратичной оптимизации.
В гл. 4 понятие полупроизводной использовано в выяснении существования и оценивании удаленности решения нелинейного уравнения в банаховом пространстве
д(х) = 0. (0.5)
Для отображений д, обладающих липшицевой производной (класс С1’1) был получен результат - теорема 4.1, пересекающийся с известными теоремами Канторовича (ТК), Мысовских [58] (т. 1), Гавурина [7] (т. 1) в тех их частях (соответственно, ЧТК, ЧТМ, ЧТГ), где они касаются существования решения и оценки его удаленности от начального приближения.
Теорема 4.1 является расширением ЧТК на случай, когда известна оценка гм > )|(<7'(я))-1||, является усилением ЧТМ в виде ослабления условий и усиления заключения, является усилением ЧТГ в виде ослабления условия.
Для отображения, обладающего полупроизводной (класс П) вначале в теореме 4.2 была получена оценка удаленности, затем найдены достаточные условия сходимости метода Ньютона и оценка скорости сходимости. Эти результаты не вложимы в упомянутые теоремы Канторовича, Мысовских, Гавурина, нет и обратного вложения. Конкретное отображение д, рассматриваемое как элемент из С1,1, может получить согласно этим теоремам гарантии по сходимости метода Ньютона и не получить как элемент из П согласно теоремам, приведенным в гл. 4. Возможно и наоборот. А также возможно получить гарантии при обеих трактовках и не получить ни в одной трактовке.
Большая часть итеративных методов поиска экстремума и решения систем нелинейных уравнений базируется на построении некоторой упрощенной здачи в окрестности итеративной точки. Последующее приближение есть решение этой упрошенной задачи. Наиболее распространенный способ упрощения — линейная экстраполяция (интерполяция) функций исходной задачи. Аппроксимирующая задача имеет тогда вид соответственно линейной программы или линейной системы, решение которых, как правило, несложно в вычислительном аспекте. Однако на шаге итеративного метода требуется рассчитать еще параметры аппроксимации, такие, например, как значения функций и их производных из исходной задачи. И может случиться, что вычислительная стоимость решения аппроксимирующей задачи многократно меньше, чем рассчет параметров. Тогда даже существенное усложнение аппроксимации будет оправдано: лишь бы оно увеличило скорость сходимости, поскольку последнее приводит к уменьшению общего числа шагов, потребных для получения решения заданной точности. Предпосылкой такого усовершенствования служит обладание некоторой информацией о нелинейностях параметров (см. гл. 5,7,9).
Следующей по сложности за линейной, по-видимому, надо признать квадратичную аппроксимацию. Именно она, т.е. квадратичная программа, составляет центральную часть метода квадратичной оптимизации (МКО) для решения задач нелинейного программирования общего вида. На практике этод метод
7
хорошо зарекомендовал себя как составная часть метода последовательной оптимизации движения летательных объектов В. М. Пономарева [64]. Последнее служило, в частности, яркой иллюстрацией того чтб есть трудоемкость собственно метода на шаге и чтб есть затраты на вычисление параметров. Решение квадратичной программы образовывало первое, параметры же представляли собой математические ожидания функционалов от решений систем дифференциальных уравнений, описывающих движение летательного аппарата. Отношение первого к второму было ничтожно.
Здесь будет подробно изложен и обоснован МКО решения нелинейных программ общего вида, использующий на каждом шаге квадратичную аппроксимирующую программу. О проблемах, связанных с обоснованием этого метода говорит уже то, что частным вырожденным вариантом его является метод Ньютона решения системы нелинейных уравнений.
Методу квадратичной оптимизации посвящена глава 5. Его назначение — итеративное решение задачи (0.1) + (0.2), т.е. задачи А.
Пусть х есть текущее приближение. Тогда в соответствии с МКО следующее приближение к решению задачи А получается как решение квадратичной программы относительно параметров х:
/(*,**) := У/(х*)(х - х*) + (х- хк)тН(хк)(х - хк)/2, д(х,хк) := J(xk)(x - хк) + д(хк).
/(х,х*)—» шш. . (0.6)
д(х,хк)<0
Здесь Я — гессиан функции /, т.е. матрица из вторых производных ||/”||; J — матрица из строк-градиентов V#, г = 1, га, т.е.
{^9и-^дтУ =: ^ =: J.
Частные случаи метода квадратичной оптимизации предлагались и исследовались с 60-х годов. Так, для задачи А без ограничений, т.е. при 0 = 7?” были предложены программы, реализующие фактически метод квадратичной оптимизации в чистом виде [96] и его модификацию, когда в качестве функции }(х,хк) берется квадратичный интерполяционный полином, совпадающий в некоторых 1 -I- п + п(п + 1)/2 точках с исходной целевой функцией / [94]. Дж. Ортега и В. Рейнболд этот частный случай называют методом параболоидов. Как составная часть метода последовательной оптимизации В.М. Пономарева, метод квадратичной оптимизации активно использовался при решении большого числа задач управления летательными объектами и другими системами [65], [66]. В [64] был доказан частный случай сходимости, когда система Куна-Таккера (0.3) эквивалентна своей подсистеме
У/(т) + М(х) = 0 А А$(а?)=0. (0.7)
Тогда метод кваратичной оптимизации для задачи А можно сопоставить решению методом Ньютона некоторой системы нелинейных уравнений, являющихся подмножеством системы (0.3), и воспользоваться известными результатами для
8
метода Ньютона. Однако большое количество конкретных задач (0.1) + (0.2) не обладает эквивалентностью систем (0.7) и (0.3), что делает актуальным теоретическое обоснование сходимости метода квадратичной оптимизации в применении к ним (§5.2), а также исследование критериев остановки итератиного процесса (§5.3) и исследование по выбору начальной точки (§5.4).
В §5.5 исследуются возможности модификации МКО по аналогии с модифицированным методом Ньютона. То есть, как сказываются на сходимости погрешности в вычислениях параметров для квадратичной программы на шаге. А именно, параметров У/(х*), J(xk), д(хк), Н(хк). Нельзя ли какие-нибудь из них вычислить только в начальной точке и использовать затем вместо текущих значений, например, Н(х°) вместо Н(хк)? Это дало бы существенное снижение общих вычислительных затрат.
В нелинейной программе, решаемой методом квадратичной оптимизации, целевая функция изначально выпукла. Кроме того, сходимость метода базируется на выпуклости целевой функции. Поэтому важно уметь строить именно выпуклые квадратичные аппроксимации на каждом шаге. В гл. 6 рассмотрены различные способы построения линейных и квадратичных аппроксимаций. В частности, предлагается несколько алгоритмов построения выпуклых квадратичных функций, приближающих в некотором смысле наилучшим образом значения исходной целевой функции в заданных узлах.
Поскольку каждая итерация в МКО есть поиск решения квадратичной программы, то выбор способа решения последней должен производиться с особой тщательностью. В §6.9 предлагается одна модификация метода Била, приспособленная для автоматических вычислений. Метод приведен к табличному виду и дан способ построения начальной таблицы. Даны рекомендации по преодолению теоретически возможного зацикливания.
В гл. 5 использование информации о нелинейном поведении целевой функции ограничилось аппроксимацией ее полиномом второго порядка. Тому было два основания: во-первых, построение многомерной аппроксимации более высокого порядка представляется весьма трудоемкой задачей, и, во-вторых, решать нелинейную программу с целевой функцией в виде полинома, порядка большего двух, значительно труднее в многомерном пространстве, чем квадратичную программу. В одномерном пространстве эти два затруднения существенно слабее, и в гл. 7 исследован ряд способов решения нелинейного уравнения и поиска одномерного экстремума. В §7.1 рассмотрен дискретный аналог метода Чебышева [3], [34] решения скалярного уравнения
Сам Чебышев предложил его решать с использованием обратной экстраполяционной задачи с вычислением производных обратной функции вплоть до порядка п. Здесь предлагается использовать обратную интерполяционную задачу с п последними узлами. Ключевым в исследовании является разностное уравнение
(А/ — величина, связанная с оценками сверху на \Г(х)\ и производную порядка п обратной к / функции), в общем виде достаточно подробно изученное еще
/(х) = 0.
(0.8)
Ък - tk-1 - - - <*-„ = ЬлМ
(0.9)
9
А.М. Островским [61] . Здесь не рассматривается общий случай, это позволило привести иные доказательства сходных утверждений, вполне достаточные для обслуживания дискретного метода Чебышева. Исследуется условие на начальные данные, гарантирующие сходимость и высокую скорость сходимости.
На базе §7.1 получены аналогичные результаты для решения (0.8) методом Мюллера (§7.2).
Те же идеи заложены в исследовании поиска одномерного минимума на основе п-точечной интерполяции (§7.3). Близкий метод был предложен Н.Е. Кириным и С.И. Веденяпиной [4], однако иной способ замещения узлов интерполяции имел последствием иные оценки скорости сходимости.
После получения обоснований итеративного метода, устойчивость его к ошибкам в исходных данных и к ошибкам округления — главное беспокойство для пользователя. В §7.4 исследуется сходимость метода трехточечной интерполяции (частный случай метода §7.3) при наличии погрешности в измерениях целевой функции [87]. Выясняется, нельзя ли повышением точности вычислений от шага к шагу сохранить тип сходимости.
В главах 8,9 вводятся нелинейные модели задач оптимизации, порожденных непосредственно хозяйственной деятельностью, предлагаются и обосновываются алгоритмы решения этих уже первичных моделей. Все они являются важнейшей разновидностью задачи на экстремум — задачей поиска оптимального управления.
Некоторые задачи обслуживания сводятся к дискретному программированию на конечном пространстве. Проблема поиска решения состоит тогда в указании алгоритма, с наименьшими вычислительными затратами приводящего к решению. А какой-либо тривиальный алгоритм перебора очевиден с самого начала исследования, но из-за большого числа элементов исходного допустимого множества он не приемлем, и следует найти тс или иные отсечения, которые сократят пространство перебора.
В §8.1 исследуются алгоритмы поиска оптимального решения задач на обслуживание сеансов связи следующего вида:
Имеется тп заявок на обслуживание. В каждой г-й заявке указывается отрезок времени Тг = [**, £*], г = 1,т, когда она может быть выполнена. Заявки выполняются на фиксированных иепересекающихся участках обслуживания к = №, Л*] во время сеанса связи [В, Е] Э Ц”=1 /г,. На каждом участке может
быть выполнена только одна заявка из числа тех, для которых содержится в некотором Т» . Требуется составить расписание, по которому обслуживается наибольшее число заявок.
Дискретное программирование тесно связано с вопросами порождения пространств при реализации алгоритмов на ЭВМ. Один из наиболее богатых наборов алгоритмов “чистого” порождения можно найти, например, в [26]. Однако конкретный вид целевой функции и наличие отсечений должны тесно соединяться с порождением в эффективном алгоритме, что приводит к совершенно новым конструкциям. Такой случай имел место при исследовании комбинационного дозирования. Суть последнего в следующем.
Имеется п одновременно взвешивающих весов. По их показаниям выбираются некоторые из них так. чтобы сумма их показании была ближайшей к некоторой заданной величине. Выбранные весы опорожняются и наполняются заново, и т.д.
10
Поскольку процесс идет в реальном времени, быстродействие алгоритма выбора имеет существенное значение. Предложен (см. §8.2) названный здесь пачечным алгоритм порождения комбинаторного пространства, обладающий порядком минимального изменения, как и двоично-отраженный п-разрядный код Грея [70], но, в отличие от последнего, позволяющий вводить отсечения.
Один из известных подходов к задаче наилучшего распределения капиталовложений в развитие городского коммунального хозяйства или экономики района, области, страны [16], [88] с помощью математического моделирования примерно таков.
На первом принципиальном шаге выбирается целевой функционал вида
где Ь — время; Т — длительность срока планирования; т» — количественное состояние і-й отрасли; Д — функции вредности, убывающие с ростом А» — веса. Фактически т» зависят не от времени, а от объема финансирования щ і-й отрасли: т* = Хі(щ). Таким образом, задача приобретает вид
где щ — возрастающие функции, = и(Ь) V I € [0,Т], д(£) — заданная
функция общего финансирования.
Сама такая постановка задачи является проблемой: каким должны быть и Лж, чтобы минимайзер для (0.11) воспринимался как оптимальное финансирование? То есть по сути: как добиться адекватности математической модели реалиям жизни? Даже при самом тщательном выборе Д,..., /«, но при А! = ... = Ап = 1 может случиться, что минимайзер для (0.11) вызовет недоумение заказчика. Здесь на помощь приходят веса. Закзчику предлагается количественно их оценить пропорционально важности отраслей. После чего находится новый минимайзер для новых весов. Эту процедуру можно повторять до получения приемлемого результата. Проблема адекватности кажется исчезнувшей, на самом деле всего лишь переместившись в адекватность выражения важности в виде некоторого числа.
В гл. 9 предлагается иной взгляд на проблему. Пусть есть приемлемый некоторым коллективом план и. И пусть существует функционал Ф2(А, и), зависящий от плана и вектора параметров А. При каком значении вектора параметров А минимайзер функционала Фг будет совпадать с таким приемлемым планом? Ответ на этот вопрос дает возможность лучше понять сущность весов и назначать их более обосновано.
Эта обратная экономическая эадача исследована для частного случая. Как приемлемый был взят опорный план — равномерное сокращение дефицита по отраслям, а в качестве целевой функции — функционал вида (0.10) с Д,/п, равными квадратам текущих относительных дефицитов, и линейной зависимостью Х{(у) = Хю Оказалось (т. 9.3), что вектор параметров А, обеспечивающий совпадение опорного плана и минимайзера для (0.10) существует и единствен.
Наряду с обратной экономической задачей исследуется и прямая. Т.е. веса Ах,...,Ап фиксируются и, соответственно, вводятся в (сливаются с) Д,...,/п.
(0.10)
(0.11)
11
Поступление капиталовложений может быть непрерывным по времени и дискретным (т.е. и — разрывна). В предположении выпуклости функций Д, ...,/п и кусочной непрерывности вторых производных /",/" (т.е. целевой функционал — произвольная выпуклая кусочно гладкая сепарабельная целевая функция) предложен алгоритм построения плана. Доказано, что он — минимайзер.
Об обозначениях. Буква Т в верхнем индексе будет означать операцию транспонирования. Знак V — операция нахождения градиента, сам градиент будет пониматься как строка. Слева от знака находится обозначение того,
что стоит справа от него. Справа от знака находится обозначение того,
что стоит слева от него. В конце некоторых логических частей стоит знак ■ . Индекс итерации для векторных величин — верхний.
12
Глава 1. ОБЩИЕ ВОПРОСЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Много практических задач на оптимизации, может быть даже ббльшая их часть, имеют вид задач нелинейного программирования или, в соответствии с распространенным подходом, приводятся к ним. Задачей нелинейного программирования (или просто нелинейной программой) называется задача поиска условного экстремума функции /(я) при ограничениях р(я) < 0, когда / или д нелинейны. Если / — квадратичная функция, а д — линейная, то такая разновидность нелинейной программы называется квадратичной программой. Одна из распространенных записей нелинейной программы имеет следующий вид:
Здесь я — п-мерный вектор; / — функция, д — т-мерная вектор-функция; неравенство понимается покомпонентно. Здесь такую нелинейную программу будем именовать задачей А. Приведем сначала несколько определений.
Определение 1.1. Вектор, удовлетворяющий ограничениям задачи А, называется допустимым.
Определение 1.2. Функция Лагранжа для задачи А определяется формулой
где А — т-мерная строка.
Определение 1.3. Седловая точка функции Лагранжа — это пара (я*, А*), удовлетворяющая неравенствам
Седловая точка функции Лагранжа имеет весьма близкое отношение к решению нелинейной программы. Задача поиска седловой точки функции Лагранжа здесь будет называться задачей В.
Если функции / и д дифференцируемы, то в соответствии с теоремой математического анализа, называемой далее Теорема 1.1. Система Куна-Таккера
является необходимым условием седловой точки.
Можно также рассматривать самостоятельную задачу нахождения решения (я, А) этой системы. В дальнейшем мы ее будем называть задачей С. Допуская
(її)
F(x,A) :=/(х) + Ад(х),
^(х, А*) > ^(х*, А*) > Р(х*, А) УА >0, Ух Є Я".
(1.2)
У^(х,А) = 0, А > 0, Ул^(х,А) < 0, А-У^(х,А) = 0
(1.3)
13
вольность речи, задачи В и С иногда будем обозначать (1.2) и (1.3) соответственно.
Первые п компонент решения как (1.2), так и (1.3) будем называть х-составляющей решения задачи В или задачи С соответственно.
Отобразим соотношения между описанными задачами в виде диаграммы — см. рис. 1.1.
Рис. 1.1.
Здесь связь (1.2) ==> (1.1) означает возможность всегда получить решение задачи А из решения задачи В. Связь (1.2) —> (1.3) означает, что решение задачи В всегда есть решение задачи С при условии существования задачи С (т.е. / и д — дифференцируемы). Знак —> говорит о том, что часть или все решение задачи у начала стрелки есть часть или все решение задачи справа лишь при выполнении определенных условий. Цифрами отмечены номера теорем в первой главе, в которых формулируются эти соотношения.
Теорема 1.2. Первые п компонент решения задачи В есть решение задачи А или, другими словами, х-состаоляющая задачи В есть решение задачи А [79].
Трудоемкость и сложность решения задач нелинейного программирования существенно зависят от класса функций, которые в них входят. Свойство выпуклости функций одно из самых благоприятных для решения нелинейных программ.
Определение 1.4. (классическое). Функция } выпукла, если ее область задания И С К1 выпукла и для любых х,у из Г) выполняется соотношение
а/(х) + (1 - а)/(у) > /(ах + (1 - а)у) Уа в (0,1). (1.4)
Замечание 1. В (1.4) в неявном виде содержится утверждение о том, что / задана в ах + (1 - а)у Уа € (0,1), Ух, у € £>. Таким образом, требование выпуклости И в определении 1.4 избыточно.
Замечание 2. Формально определение 1.4 позволяет выпуклой функции принимать значения ±оо. Здесь, однако, такие крайности не понадобятся. И поскольку наличие бесконечных значений разных знаков делает (1.4) не состоятельным, а -оо потребует еще дополнительных оговорок (см. например, свойство 1.6), будем считать, что выпуклая функция не принимает значения “00.
Введем удобное обозначение:
аЦ,и := аи + (1 - а)и.
14
Используя его, соотношение (1.4) можно записать в виде
> Н°Ц) Уа 6 (0,1). (1.5)
Выпуклая функция имеет следующее свойство.
Свойство 1.1. Для всех а $ (0,1) и для всех х,у 6 О выполняется соотношение
•Дее => аь'$<пч1). (1.6)
Определение 1.5. График С/ функции / — это множество
{(*)| хео Л *=/(*)}.
Определение 1.6. Надграфик в/ функции / — это множество
{(£))*€£ Л »>/(*)}.
Определению 1.4 эквивалентно
Определение 1.7. Функция выпуклая, если ее надграфик выпуклый.
В последнем определении выпуклость надграфика есть обычная выпуклость множества, т. е. возможность соединить любые две его точки отрезком, содержащимся в нем же.
Утверждение 1.1 Определения IЛ и 1.7 эквивалентны.
Действительно.
1. Из выпуклости по определению 1.7 выпуклость по определению 1.4 может быть получена совсем просто. Достаточно взять произвольные точки х, у из графика и соединить их отрезком, принадлежность которого к надграфику, выписанная аналитически, есть не что иное, как соотношение (1.4), т.е. классическая выпуклость.
2. Пусть функция / выпукла по определению 1.4. Докажем выпуклость надграфика. Допустим противное, тогда в силу определения 1.6 найдутся точки х, у € О и числа X, У, такие, что надграфик содержит точки 9 - ©■ но не содержит какую-нибудь точку из отрезка, их соединяющего, т. е.
•ч < /ГД), (1-7)
а 6 (0,1), X > /(г), У >/(»). (1.8)
Из (1.7) и (1.8) следует но это противоречит неравенству
(1.5), соответсвующему определению 1.4. Поэтому определение 1.4 эквивалентно определению 1.7. ш
Определение 1.8. Гиперплоскость Г является опорной к множеству (•?, если она содержит хотя бы одну точку из замыкания С и все точки лежат только в одной из половин пространства ВТ, на которые разделила его гиперплоскость (сама гиперплоскость полагается принадлежащей этой же половине).
15
Утверждение 1.2. Выпуклость множества эквивалентна наличию опорной гиперплоскости в каждой его граничной точке. Иными словами, G С выпукло, если
(V* 6 ÖG)ßu € Ят)(УУ € G)(z' - z)ru > 0. (1.9)
Это утверждение является простым следствием леммы об отделимости выпуклых множеств.
Далее при исследовании некоторых отображений W : D С R” Я™ во внутренних точках области D придется использовать иногда производную Фре-ше, а иногда производную Гато. То есть, соответствено, линенйные операторы 5, в € £(#”, В771), такие, что
Jini II+ А) - W(x) - 5ЛЦ/Ц/1Ц = 0;
rl—tv
lim ||W(x + th) - W{x) - teh\\/t = 0 V/i € Д"
(t — скаляр).
Операторы 5,(6, если существуют, то единственны [18].
Применим утверждение 1.2 к определению 1.7. Согласно определению 1.7,
если Qj =: z € Gf С К1*1, то и любой вектор т!, совпадающий с z по первым
п компонентам и с z'n+l > у, также принадлежит Gf. Поэтому компонента ип+\ вектора и в (1.9) должна быть неотрицательна. Более того, нетрудно показать, что она положительна, если х — внутренняя точка области задания D. Таким образом, не уменьшая общности, можно положить un+1 = 1.
Как известно, если существует опорная гиперплоскость Г к графику функции во внутренней точке области задания, то она совпадает с касательной гиперплоскостью в этой же точке. Поэтому в качестве нормали к Г можно взять нормаль к касательной гиперплоскости вида и = (—Vf(z), 1). Сделав замену в (1.9): G -» G/, z-+ {xQ,f(xo))} z! -»• {x,f(x)), получаем
Свойство 1.2. Для выпуклой по определению 1.7 и дифференцируемой по Гато во внутренней точке xq области задания D функции / справедливо неравенство
f(x) > f(xo) + Vf(x0)(x - т0) Vt 6 D.
Вообще говоря, функция может обладать свойствами 1.1 и 1.2, но не быть выпуклой. Для ее выпуклости необходима еще выпуклость области задания.
Утверждение 1.3. Определение 1.4 эквивалентно совокупности свойства
1.1 и выпуклости области задания функции.
Действительно.
1. Пусть / выпукла в смысле определения 1.4 и пусть не имеет свойства 1.1, т.е. существуют х,у € D и а ф! [0,1], такие, что
> /(«) л и = Щ 6 D. (1.10)
Положим для определенности о < 0, тогда для ß = — а/(1-а) справедливо
у= ßLux= ß (i.il)
16
Так как /? е (0,1), то в соответствии с определением 1.4
> /№) = Ну)- (112)
Поскольку величина (1 — р) положительна, из (1.10) и (1.12), имеем
Рцм«х-«)М > 0Ьт > т (из)
Обратим внимание на то, что соотношение (111) справедливо при выбранном указанным способом Р для любых значений х и у. После замены в (1.11) точек х и у на их образы {[х) и /(у) получаем {{у) = б ^ чт0 про-
тиворечит (1.13). Отсюда — наличие свойства 1.1 у выпуклой по определению 1.4 функции. Выпуклость области задания постулируется в определении 1.4.
2. Пусть функция имеет свойство 1.1, задана на выпуклом множестве Д но не выпукла в смысле определения 1.4. Тогда в силу выпуклости £> существуют х,у,и€ И и а € (0,1), такие, что
и = 41 Л </(«). (1.14)
Как и в п. 1 положим /3 = а/(а - 1). Тогда справедливо соотношение (1.11), и, так как р < 0, в силу свойства 1.1 будет
< Л'Ц) = Ну)- (Ы5)
Поскольку величина (1 - р) положительна, из (1.14) и (1.15) имеем
Аналогичным путем получается противоречие, которое завершает доказательство утверждения 1.2. в
Для дальнейшего будет полезно следующее:
Свойство 1.3. Классически выпуклая функция / непрерывна на любом открытом множестве б, из области задания Т) [60], [72].
На границе области задания П ситуация значительно сложнее.
Контрпример 1.1. Пусть V есть единичный круг {(^1,^2) | Я\+х1< 1}, и /(х) = х\ + х\, если х{ + х\ < 1. На окружности с единичным радиусом функцию / можно задать произвольно, лишь | бы она была, ограничена снизу числом 1.
Определение 1.9. Число г есть односторонний по отношению к множеству О предел функции / в точке х, если
(Че>0)(36>0)уе36х[)П =*► \/(х)-г\<е.
(Б* — замкнутый шар радиусом 8 с центром в точке х).
Из контрпримера 1.1 следует, что на границе области задания выпуклая функция может не иметь одностороннего предела. Может создаться впечатление, что это результат искуственного задания функции на границе. Но это не
так.
17
Контрпример 1.2. Возьмем за основу функцию д(х) = х\ 4- х\ и положим область задания Д = {(зь^з) а?1 < 1}. На окружности, определяемой равенством х\ + х\ = 1, зададим бесконечную последовательность непересекающихся хорд {Л*}?0, монотонно стремящихся к точке (1,0) с одной стороны. То есть меньшая из дуг, стягиваемых хордой из последовательности, не содержит точку (1,0), и все эти меньшие дуги лежат в некоторой односторонней окрестности на рассматриваемой окружности относительно точки (0,1) при достаточно больших индексах к.
Пусть центр каждой хорды удален от центра Ск стягиваемой ею дуги на £к. Проведем в Я3 через Ьк гиперплоскости так, чтобы котангенс наклона их нормалей к плоскости (яь^г) был равен (Ьк > 0). Таким образом, третья координата этих гиперплоскостей в точке Ск примет значение Ьк+1. Найдем пересечение над графиков функции д и линейных функций, соответствующих этим гиперплоскостям. Поставим ему в соответствие функцию /. Выбирая {Ьк}]° монотонно возрастающей, получим
!ш*-»(1,о)/(я) = 1 < 1 + Ит*_>оА < Птх->(1,о)/(х).
Следовательно, односторонний предел в граничной точке (1,0) отсутствует, а верхний предел может в ней равняться +оо. Причем на границе области задания дД функция / вообще не задана.
Заметим, что в контрпримере 1.2 функция / принимает неограниченные значения на любых ограниченных множествах, границы которых содержат 5^0) ПЯД \ {(!>0)} Для какого либо е > 0, даже когда последовательность {&*} ограничена сверху числом Ь < оо. Это следует, например, из того, что если выпуклая функция ограничена на любом ограниченном подмножестве из области задания и область задания есть открытый многогранник, то на замыкании области задания се можно доопределить с сохранением непрерывности [72].
Остается проиллюстрировать, что даже при условии ограниченности выпуклой функции на любом ограниченном подмножестве области задания на непрерывность функции может оказать вредное влияние наличие в границе области задания точки, в любой окрестности которой эта граница не может быть частью границы какого-либо выпуклого многогранника.
Контрпример 1.3. При выборе последовательности {6*}, ограниченной и не стремящейся к нулю, сужение функции из контрпримера
1.2 на множество Д = {(яьл^) \х1 + х% < 1} не имеет предела, когда аргумент стремиться к точке (1,0), хотя это сужение и ограничено.
Заметим, что в любой х 6 #Д нельзя указать е > 0, чтобы пересечение могло бы стать границей многогранника. Однако, контрпример 1.3 легко модифицировать так, чтобы лишь одна точка (1,0) была таковой. Например, обрезать единичный круг хордами, стремящимися к (1,0).
Свойство 1.4. Выпуклая функция / скалярного аргумента имеет односторонний конечный либо бесконечный предел г в произвольной точке х на границе области задания. Причем, если /(х) определено, то верно
ф(х)>У\т/(у)=:г. (1.16)
18
Действительно. Пусть пока г — односторонний верхний предел функции / и {хк}™ — монотонно сходящаяся к х последовательность, реализующая его.
Положим а*(ц) = (п - Хк)/(хг - хк). Очевидно, что V = а*^££{, к = 2,3,4,...
Существование предела будет следовать из равенства нижнего предела верхнему. Пусть последовательность {Ур}™ монотонно стремится к я и реализует нижний предел / в х. Тогда по числу к можно определить Мк так, что для всех тп> Мк будет Ут находиться на отрезке ххк и будет
+ (1 - Ы)/Ы < /(а‘й"")^;) н /(Ут). (1.17)
Так как ут —> х* при к -> оо для всех т > Мк и длины отрезков ххк
растут, имеет место ак(ут) 0 при к -> оо. Поэтому переход к пределу по к
в (1.17) даст
Ш> КщЛШ = г. (1.18)
Таким образом, односторонний предел } ъ х существует.
Очевидно с**(х) <0, к = 2,3,... Поэтому если / задана в х, то в силу свойства 1.1 имеет место
/(*) = / (“<*>!£) > = <*»(*)/(*,) + (1 - «*(*))/(**)• (1.19)
Поскольку ак(х) -» 0 при к -> оо, правая часть (1.19) стремиться к г при к —У оо. Отсюда — (1.16).
Свойство 1.5. Если выпуклая функция имеет односторонний на границе области задания предел г в точке х и задана в этой же точке, то имеет место условие (1.16).
Действительно, сужение функции на произвольный луч, выходящий из х внутрь области задания, имеет также односторонний предел г в точке х, а для одномерного случая (1.16) доказана (свойство 1.4).
Свойство 1.6. Выпуклая функция / ограничена снизу на любом ограниченном подмножестве б области задания В.
Доказательство. Построим выпуклую оболочку соп\б множества д. Найдем некоторое линейное многообразие М минимальной размерности, содержащее ее. Рассмотрим сужение / на пересечение МГ\й Э сопу д. Свойство 1.6 очевидно, когда б состоит из одной точки. Если в б более одной точки, то в сопу б найдется внутренняя точка х (относительно многообразия М). Выберем г > 0 достаточно малым, чтобы замкнутый шар 5^ принадлежал внутренней части множества задания. По свойству 1.3 функция / непрерывна на этом шаре, следовательно и ограничена снизу некоторым числом г. А что вне его?
По построению произвольная точка и многообразия М представима в виде х + ос(х — у), где у — некоторая точка из Ь5^ и а > 0. Если еще потребовать, чтобы и £ то будет ос > 1.
Если и € сопуд и А — диаметр множества б, то А> ||д - у|| = |о:|||х - у\\. Следовательно, а < А/т. И, в силу свойства 1.1
{(и) > /(х) + а(/(у) - /(х)) > (1 - а)/(х) + а}(у) >
19
> (А/т — 1)|«| - А/т\г\ = —|г|. ■
Несложо проверяется
Свойство 1.7. У выпуклой функции / для любого числа с множество Ме = {х\/(х) < с} выпукло. Обратное неверно, т. е. функция может иметь выпуклость множеств Мс для всех с, но не быть выпуклой.
Свойство 1.8. Пусть / — скалярная выпуклая функция, заданная на конечном отрезке [а, Ь]. Тогда она имеет конечные правую }\ и левую /1 производные на интервале (а,Ь), в точке а — правую и /+(а) > -оо, в точке 6 — левую и /1(6) < +оо; обе односторонние производные монотонно возрастают на отрезке [а, 6] и
Г+(а) < /!(*) < /;(*) < /1(6)] V* € (а, 6). (1.20)
Действительно. Непосредственно из определения выпуклости, полагая а = Н/(6 - х), к € (0,6 - я), имеем неравенство
}(х + И) - }(х) < /(х) + а(}(Ь)~ /(ж))- /(х) _ /(Ь) - /(х) к ~ к 6 — х
Заменяя здесь 6 любым числом х+Н из интервала (х, 6) и назначая к меньше Я, убеждаемся в монотонности левой части неравенства по к. Откуда следует существование при к -> +0 ее предела, равного конечному числу либо -оо. После предельного перехода при к -+ +0
ЛИ < т ~/(Х) =: /(Ь,х),
о — X
где {(Ь,х) — разделенная разность функции / по узлам 6, х. Симметричные выкладки на правом конце для левой производной дают /(6,т) < /1(6). Откуда /;(*)</1(6) У*€[а,6).
Заменив в этих рассуждениях 6 на а, получим (а < 0 и см. свойство 1.1,
(1.6)) нужную оценку снизу.
Свойство 1.9. Пусть / — скалярная выпуклая функция, заданная на конечном отрезке [а, 6]. Пусть правая и левая производные удовлетворяют соответственно, /+(а) > -оо и /1(6) < +оо. Тогда
/Ы - Я*) = I* /-(*)Л = 1* /+(0 ск Ух,уб(а,Ь). (1.21)
Если доопределить /+ в 6 или /_ в а произвольными конечными числами, то эта формула будет справедлива также и при у = 6, и при х = а, соответственно.
Действительно.
1. Известно (теорема Лебега), что выпуклая функция имеет почти всюду монотонную производную.
2. / — абсолютно непрерывна.
Действительно, пусть М = тах(|/|(а)|, |/1(6)|), тогда в силу (1.20)
£ \/{х„ + К) - /(я„)| < М £ |М>
20
что и является определением абсолютной непрерывности.
3. Из п.З следует [74] (11.7.1) первое равенство в (1.21). Так как правая производная равна полной там, где последняя существует, и конечна, где полная не существует (т. е. на множестве нулевой меры), то верно и второе равенство из формулировки этого свойства.
Свойство 1.9. Пусть / — скалярная выпуклая функция, заданная на некотором множестве G. Тогда
(x,yeG Л х<у) => f'+{x) <
Действительно, из доказательства п. 1 свойства 1.8, при у = 6 можно извлечь оценку f'(x) < f(y,x), и оттуда же, полагая h -0, получим
ГЛу)> f(v,x)- •
В этой работе не используются вогнутые функции, но все результаты для выпуклых функций переносимы и на случай вогнутых с соответственной заменой max — на min, inf — на sup, < — на >, < — на >, и наоборот. Все это вытекает непосредственно из определений.
Определение 1.10. (классическое). Функция f называется вогнутой, если ее область задания D С Я” выпукла и для любых х, у из нее и для всех а из интервала (0,1) верно
!{ак) >
Нетрудно заметить, что это определение эквивалентно следующему:
Определение 1.11. Функция / называется вогнутой, когда функция -/ выпукла.
Отсюда вытекает возможность перенести все утверждения, верные для выпуклых функций на вогнутые с заменой направлений неравенств (если они есть в утверждении) на противоположные.
Следуя диаграмме (рис 1.1), перейдем к оставшимся теоремам Куна-Таккера.
Теорема 1.3. Пусть функции fug выпуклы, заданы на Rn и выполнено условие Слейтера (условие регулярности): существует точка х* такая, что д(х9) < 0. Тогда
1) существует решение задачи А (1.1) конечное либо бесконечное (т.е. инфимум целевой функции на допустимом множестве доставляет неограниченная последовательность),
2) в случае конечности решения задачи А у задачи В (1.2) также существует решение и решение задачи А является х-составляющей решения задачи В — седловой точки функции Лагранжа [84].
Продемонстрируем, как нарушение выпуклости либо условия Слейтера может привести к отсутствию седловой точки функции Лагранжа даже при наличии решения нелинейной программы.
21
Пример 1. Задача А;
Рі(х) = *2, дг{х) = X? - х3.
Решение ЗА существует (х\ = х2 = 0). Условие Слейтера выполняется, но функция 02 не выпукла.
Функция Лагранжа Р(я, А) = -Х\ + \\Х2 + А2(х? - х2) должна иметь в седловой точке (а:*, А*) абсолютный минимум по х и, поскольку она дифференцируема, седловая точка является решением системы Куна—Танкера и в частности, УхЕ(х*, А*) = 0. Но, с другой стороны,
т.е. решение задачи А — точка (0,0) не может быть т-составляющей решения системы Куна—'Танкера, а следовательно и ^-составляющей седловой точки функции Лагранжа. По теореме 1.2 в силу единственности решения задачи А у функции Лагранжа нет вообще седловой точки.
П р и м е р 2. Изменим в предыдущем примере первую функцию огрниче-ний: 01 = х1 +х2. Тогда задача С имеет решение = х2 = 0, Х\ = Х2 = 1, совпадающее по ^-составляющей с решением задачи А. Но функция Лагранжа с такими множителями
не имеет минимума по х. Таким образом, существует решение задач А и С, но не существует решения задачи В, т.е. седловой точки функции Лагранжа.
ПримерЗ. Изменим в примере 1 вторую функцию ограничений:
В этом случае функции / и 0 — выпуклые, но условие Слейтера не выполняется. Как и ранее, легко проверить, что точка (0,0) есть решение задачи А, но не может быть т-составляющей седловой точки функции Лагранжа.
Теорема 1.4. Пусть /ид — выпуклы и дифференцируемы, тогда если у задачи С (1.3) существует решение, то оно является решением задачи В
Остальные теоремы Куна-Таккера можно сформулировать на более широком классе функций, чем выпуклые.
Определение 1.12. Функция одного аргумента, заданная на связном множестве, называется слабо унимодальной, если она не убывает справа от множества минимальных значений и не возрастает слева от этого множества.
Определение 1.13. Функция нескольких аргументов, заданная на выпуклом множестве, называется слабо унимодальной, если она слабо унимодальна на любом отрезке в области задания.
Класс слабо унимодальных функций содержит в себе класс линейно унимодальных функций.
F(:r, А) = -х\ + х\ + х2 + х\ - х2 = х\
х\ < 0,
х\ > 0.
(1.2) [79].
22
Определение 1.14. Функция одного аргумента, заданная на связном множестве, называется линейно унимодальной, если она возрастает справа и убывает слева от множества минимальных значений.
Определение 1.15. Функция нескольких аргументов, заданная на выпуклом множестве, линейно унимодальна, если она линейно унимодальна на любом отрезке из области задания.
Определение 1.16. Функция / слабо унимодальна, если для любого числа с множество Мс = {х | {(х) < с} выпукло.
Определения 1.13 и 1.16 эквиваленты. Действительно, пусть функция / слабо унимодальна по определению 1.13 и пусть существуют число с и точки х, у из множества Мс в определении 1.16, но отрезок ху не принадлежит Мс. Это означает, что найдется точка г на отрезке ху, такая, что
Положим х — “слева” от г, у — “справа”. В направлении от г к у функция убывает, следовательно, множество минимальных значений должно находиться в том же направлении (справа) от г. От х к г функция возрастает, следовательно, множество минимальных значений должно находиться в противоположном направлении от г (слева). Противоречие доказывает выпуклость множества Мс для произвольного с. Таким образом из определения 1.13 следует определение
И обратно. Пусть множества Мс выпуклы для всех с и на некотором отрезке ху регистрируется нарушение определения 1.12. Например такое: справа от множества минимальных значений обнаружены две точки: и и V такие, что /(и) > /(и) > /(£), I < и < V и £ — из множества минимальных значений.
Положим с = /(и). Множество Мс должно быть выпуклым, но отрезок иЬ не принадлежит множеству Мс, хотя точки V, £ € Мс. Из противоречия следует определение 1.11.
Теорема 1.5. Пусть у задачи С (1.3) существует решение (х,Л) и выполнены условия:
1) функции {ид слабо унимодальны;
2) / — непрерывна;
<€/
где / — множество индексов существенных в х ограничений: I = {* |#(х) = 0}. Тогда (1.22) можно записать в виде
{(£) > с, {(х) < с, {(у) < с.
1.16.
О = ЧхР(х, А) = У/(і) + А^, А > 0,
(1.22)
Введем в рассмотрение выпуклый конус
к = {у IУ = £ А > 0},
-Ут/(£) Є К.
(1.23)
23
Рассмотрим полярный конус К+ := {u\Vgi(x)u >0, г G /} и конус К~ := -К+. Очевидно, что скалярное произведение любого вектора конуса К с любым вектором полярного конуса неотрицательно, а с любым вектором конуса К~ — неположительно, откуда
К- С {z\-V/(i) z < 0} =: К}. (1.24)
Множество допустимых значений М содержится в К" + х.
Действительно, покажем, что для любого i G / верно
Mi := {х | Qi(x) < 0} С {х | V<fc(x) (х- х) < 0} =: Kf + х. (1.25)
Пусть у G М, тогда в силу унимодальности отрезок ху С М», т.е. для всех
t в (0,1) точка х = fLy = х -f t(y - х) лежит в Л/j. И, разлагая & в ряд
Тэйлора, имеем:
0 > 9i(x) = 9i(x) + Vgi(x) {х-х) + ог(х -х) =
= Vft(x) (х - х) + ог(х -х) = tVgi(x) (у-х) + о2(<),
Здесь oi,02 - бесконечно малые. Если О Ф Vpt(x) (у -х) =: q, положим t столь малым, что |о2(01 5: 1^1/2, и тогда
О >qt- \qt\/2 = (2 - sgn(qt))qt/2.
Из положительности ^ следует q < 0, т.е. у G Kï и включение (1.25) истинно. Операция пересечения по i е I соотношений (1.25) дает
М = С f)(K- +i) = К~ + х.
Обозначим множество (х|/(х) < /(х)} через N. Факт принадлежности множества N := {х\}(х) < /(х)} конусу KJ + х устанавливается точно так же, как и включение (1.25) (Kj := —Kf ). Из этого факта следует, что все внутренние точки множества N являются внутренними точками конуса KJ +х. Поскольку в силу непрерывности / множество N открыто, все его точки есть внутренние точки для множества N и, следовательно, внутренние точки для конуса KJ + х, т. е.
N С (KJ + х) \ Г, (1.26)
(Г := d(Kj + х), д — символ операции нахождения границы множества).
Поскольку доказано М С К~ + х, из (1.24) следует М С Щ H- х, что в совокупности с
(К7+г)П(Л'/+ + г) = г,
приводит к MÇ\(KJ +х) С Г и из (1.26) вытекает MÇ]N = 0, т.е. пересечение множества допустимых значений и множества, на котором целевая функция принимает меньшие значения, пусто.
Замечание 1. Дифференцируемость функций / и g потребовалась лишь в одной точке х.
Замечание 2. Теорема 1.5 имеет характер необходимости, т.е. ее нельзя усилить снятием какого либо условия. Не составляет трудности найти контрпример для условия 1 из этой теоремы. Столь же прост и контрпример для условия
3.
24