новая папка 1 / 683056

УДК 517.518.244 (07)

П142

Рецензент – к. физ.-мат. наук, доц. Н.М. Мишачев

Палинчак, Н.Ф.

П142 Выпуклый анализ и методы оптимизации: методические указания к практическим занятиям для магистров [Текст] / Н.Ф. Палинчак. – Липецк: Изд-

во Липецкого государственного технического университета, 2018. – 16 с.

В методических указаниях рассмотрены основные понятия выпуклого анализа и некоторые приложения выпуклого анализа к задачам оптимизации.

Предназначены для магистров физико-технологического факультета по направлениям подготовки «Механика и математическое моделирование» и «Системный анализ и управление».

Ил. 4. Библиогр.: 5 назв.

© ФГБОУ ВО «Липецкий государственный технический

университет», 2018

2

Выпуклые множества

Одним из основных понятий выпуклого анализа является понятие выпуклого множества.

Определение. Непустое множество X Rn называется выпуклым, еслиx1 (1 )x2 X при всех x1, x2 X , [0, 1], т.е. если X вместе с любыми своими двумя точками x1 и x2 содержит соединяющий их отрезок.

Примерами выпуклых множеств служат линейное пространство, шар,

отрезок, прямая, луч, гиперплоскость, полиэдр. Пустое множество и одно-

точечное множество по определению считаются выпуклыми. На рисунке 1

представлены выпуклое и невыпуклое множества.

Рис. 1. Выпуклое (слева) и невыпуклое (справа) множества

Прежде чем сформулировать основные свойства выпуклых множеств,

напомним некоторые операции над множествами.

Пересечением множеств X1 , X 2 , , X m называется множество X ,

состоящее из тех и только тех точек x, которые принадлежат всем множествам

3

x2 X 2 .

Линейной комбинацией множеств X1 , X 2 , , X m с коэффициентами 1 ,

Замыканием множества X называется множество, являющееся объедине-

нием множества X и всех его предельных точек.

Выпуклые множества обладают следующими свойствами:

1.Пересечение любого числа выпуклых множеств является выпуклым множеством.

2.Сумма конечного числа выпуклых множеств является выпуклым множеством.

3.Разность выпуклых множеств является выпуклым множеством.

4.Произведение выпуклого множества на действительное число является выпуклым множеством.

5.Любая линейная комбинация конечного числа выпуклых множеств является выпуклым множеством.

6.Замыкание выпуклого множества является выпуклым множеством.

Для доказательства выпуклости множеств используют следующие ут-

верждения:

1. Для любых чисел a1 , a2 , , an , b1 , b2 , , bn справедливо неравенство

4

чисел не превосходит их среднего арифметического).

Пример. Доказать выпуклость множества X { x R2 : x12 x2 }.

( x1 (1 ) y1 )2 x2 (1 ) y2 .

Следовательно, x (1 ) y X для всех [0, 1] и множество X

выпукло.

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

жество X содержит все их выпуклые комбинации.

Теорема. Множество выпукло тогда и только тогда, когда оно содержит все выпуклые комбинации любого конечного число своих точек.

Если множество не является выпуклым, то его можно дополнить до вы-

пуклого множества.

5

Определение. Пересечение всех выпуклых множеств, содержащих мно-

множеством, так как X содержится, по крайней мере, в выпуклом множестве

R n . Выпуклая оболочка co( X ) является выпуклым множеством. Из определе-

ния следует, что co( X ) – минимальное выпуклое множество, содержащее X .

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

Выпуклая оболочка конечного числа точек, не лежащих на одной прямой, на плоскости представляет собой выпуклый многоугольник, а в пространстве – выпуклый многогранник. На рисунке 2 представлены множество B и co(B).

Рис. 2. Множество и его выпуклая оболочка:

B – множество; co(B) – выпуклая оболочка

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

Теорема (Каратеодори). Пусть X – произвольное непустое множество из

R n , тогда выпуклая оболочка co( X ) множества X состоит из всевозможных выпуклых комбинаций не более чем ( n 1) точек множества X .

Определение. Конусом с вершиной в нуле называется множество K,

содержащее вместе с любой своей точкой x и точки вида x при всех 0.

Если множество K выпукло, то K называют выпуклым конусом.

6

Отметим основные свойства выпуклых конусов:

1. Выпуклый конус содержит всевозможные неотрицательные комбина-

ции своих точек.

2. Множество K является выпуклым конусом с вершиной в нуле тогда и

только тогда, когда для любых x1, x2 K, для любых i 0, 2 0 точка

1x1 2 x2 K.

3. Пусть K1 , K2 – выпуклые конусы с вершиной в нуле, тогда множества

K1 K 2 , K1 K 2 , K1 являются выпуклыми конусами с вершиной в нуле.

Определение. Пересечение всех выпуклых конусов с вершиной в нуле,

содержащих множество X , называется конической оболочкой множества X и

обозначается cone X .

На рисунке 3 приведен пример конической оболочки некоторого множества X .

Рис. 3. Коническая оболочка множества X

Теорема. Коническая оболочка множества совпадает с множеством всевозможных неотрицательных комбинацией точек из этого множества.

Теорема. Множество K является выпуклым конусом тогда и только тогда, когда оно совпадает со своей конической оболочкой.

Определение. Гиперплоскость H {x Rn : (с, x) } называют опорной

к множеству X Rn в точке y X , если множество X содержится в одном из

полупространств, порожденных H , а точка y принадлежит H , т.е. (c, x)

для всех x X и (c, y) .

7

Геометрически гиперплоскость H является опорной к множеству X ,

если множество X лежит по одну сторону от H и H проходит через одну из граничных точек множества X (рис. 4).

Рис. 4. Опорная гиперплоскость к множеству X

Теорема. В любой граничной точке y выпуклого множества X Rn

существует опорная гиперплоскость.

Теорема. Всякое непустое выпуклое замкнутое множество X Rn явля-

ется пересечением замкнутых полупространств, образованных всевозможными

опорными гиперплоскостями к множеству X , содержащими X .

Выпуклые функции

Важнейшим понятием выпуклого анализа является понятие выпуклой

функции.

Определение. Функция f (x), определенная на выпуклом множестве

X Rn , называется выпуклой, если f ( x1 (1 )x2 ) f (x1 ) (1 ) f (x2 )

для всех x1, x2 X , [0, 1]. Если выполнено строгое неравенство для любых x1, x2 X , x1 x2 , (0, 1), то функция f (x) называется строго выпуклой.

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

Пусть X – выпуклое множество, x1 и x2 – фиксированные точки из X , f (x) – произвольная функция, определенная на множестве X . Рассмотрим про-

межуток S(X , x1, x2 ) {t R : tx1 (1 t)x2 X}. Функцию одной переменной

8

(t) f (tx1 (1 t)x2 ), заданную на S( X , x1, x2 ), будем называть сечением функции f (x).

Теорема. Функция f (x), определенная на выпуклом множестве X ,

является выпуклой тогда и только тогда, когда любое сечение этой функции является функцией, выпуклой вниз.

Примером выпуклой на множестве Rn функции является линейная функция f (x) (a, x) b, где a R n – фиксированный вектор, b R – фикси-

9

5. Выпуклая функция, заданная на выпуклом множестве X Rn , непре-

рывна в любой внутренней точке множества X .

Проверку выпуклости функции часто неудобно проводить непосред-

ственно по определению. Для дифференцируемых функций существуют крите-

рии выпуклости, которые упрощают проверку выпуклости функции. Ниже

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

Для определения неотрицательности матрицы Гессе вторых производных обычно используют критерий Сильвестра: симметричная матрица является неотрицательно-определенной тогда и только тогда, когда все миноры,

образованные строками и столбцами этой матрицы с одинаковыми номерами,

10