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

Множество S называется выпуклым, если все точки прямой, соединяющей любые две точки множества, принадлежат данному множеству.

Более формально S – выпуклое множество, если для любых двух векторов x⁽¹⁾ и x⁽²⁾ из S вектор x =x⁽¹⁾ +(1-)x⁽²⁾ также принадлежит S при любых значениях , заключенных в пределах от ноля до единицы.

Свойства выпуклого множества:

1. Множество всех допустимых решений задачи линейного программирования является выпуклым.

2. Пересечение выпуклых множеств есть выпуклое множество.

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

4. Гиперплоскость является выпуклым множеством. Гиперплоскостью называется множество всех точек x , удовлетворяющих равенству cx = z при заданном векторе c ≠0 и заданной скалярной величине z . Вектор c носит название нормали к гиперплоскости. Например, множество представляет собой гиперплоскость.

5. Полупространство является выпуклым множеством. Полупространством называется множество всех точек x , удовлетворяющих неравенству c ∙ x ≤ z или неравенству c ∙x ≥ z при заданном векторе c ≠ 0 и заданной скалярной величине z . [1]

3.5. Вогнутые и выпуклые функции

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

Функция n переменных f (x) , определенная на выпуклом множестве D, называется выпуклой функцией тогда и только тогда, когда для любых двух точек x⁽¹⁾ и x⁽²⁾ D и 0≤≤1 выполняется неравенство

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

Свойства выпуклых функций:

1. Хорда, соединяющая две любые точки графика выпуклой функции, всегда проходит над (или выше) кривой в интервале между двумя этими точками.

2. Тангенс угла наклона касательной, или первая производная f (x) , возрастает или, по крайней мере, не убывает при увеличении x .

3. Вторая производная f (x) всегда не отрицательна на рассматриваемом интервале.

4. Линейная аппроксимация f (x) в любой точке интервала всегда позволяет получить нижнюю оценку истинного значения функции (рис. 3.5.2). Линейная аппроксимация функции f (x) в точке x⁰ строится путем исключения членов второго порядка и более высокого порядка из разложения функции в ряд Тейлора:

.

Таким образом, для всех x верно следующее неравенство:

5. Для выпуклой функции локальный минимум всегда является глобальным минимумом.

Функция f (x) является вогнутой функцией на множестве D тогда и только тогда, когда f (x) – выпуклая функция.

Рис. 3.5.1. Выпуклая функция

Рис. 3.5.2. Линейная аппроксимация выпуклой функции [1]

3.6. Максимизация (минимизация) функции при ограничении

Необходимо максимизировать функцию f (x) при ограничении

a ≤x ≤b , где a и b – границы изменения значений переменной x . Так как функция исследуется на заданном интервале, проверку наличия локального оптимума необходимо проводить не только в стационарных точках, но и в граничных точках интервала.

Последовательность действий

1. Приравнять df/dx =0 и найти все стационарные точки.

2. Выбрать все стационарные точки, расположенные в интервале [a, b] и точки a и b на границах интервала.

3. Найти наибольшее значение функции в точках, определенных в п. 2. Данное значение соответствует глобальному максимуму.

Для поиска глобального минимума алгоритм остается тем же, но в п. 3 находится минимум функции. [1]