Выпуклая (вогнутая) функция

Задача оптимизации значительно усложняется, если целевая функция f( ) может иметь в допустимой области G не один, а несколько максимумов или минимумов. В этом случае глобальный экстремум может достигаться на границе области и не совпадать с локальным экстремумом. Если заранее известно существование глобального экстремума у функции f( ) (например, на основании Теоремы 5.2.), то достаточно найти все стационарные точки и сравнить значения функции f( ) в этих точках с экстремальными значениями на границе области. Наибольшее значение будет соответствовать глобальному максимуму. Решение такой задачи может оказаться очень трудоемким, ввиду большого числа ограничений вида (5.1) в практических задачах.

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

Пусть f( ) целевая функция, заданная на выпуклом множестве G; ₁, ₂– две произвольные точки из G, 0£t –произвольная точка отрезка, соединяющего ₁, ₂. Рассмотрим отрезок соединяющий значения f( ₁₎и f( ₂) функции f( )

Определение 5.7.Функцию f( ) называют выпуклой, если она целиком лежит выше (не ниже) отрезка, соединяющего две ее произвольные точки, т. е., для любых ₁, _2,и будет выполняться неравенство:

(5.5)

Определение 5.8. Функцию f( ) называют вогнутой, если она целиком лежит ниже (не выше) отрезка, соединяющего две ее произвольные точки, т. е., если

(5.6)

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

f max f f

z z

z f f

min

X X X

x₁x_optx₂x₁x_optx₂x₁x₃x_optx₄x_opt=x₂

а) б) в)

Рис. 5.3 Функции: выпуклая а); вогнутая б); общего вида в).

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

Теорема 5.4. Любой локальный максимум выпуклой или локальный минимум вогнутой функции являются одновременно глобальным.

Теорема 5.5.Сильный глобальный минимум выпуклой или максимум вогнутой функций, заданных в выпуклой области может достигаться (а в закрытой ограниченной области – достигается) только на границе области.

Приведенные теоремы позволяют выделить некоторые приемы, упрощающие нахождение глобального экстремума:

1. Если функция выпуклая (вогнутая) и из уравнений (5.4) получена стационарная точка, то в ней достигается глобальный максимум (минимум).

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

И, наконец, стоит отметить, что сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая).

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

Линейная функция f( )= является выпуклой (и вогнутой) на всем пространстве R⁽ⁿ⁾. Однако она не является ни строго выпуклой, ни строго вогнутой. Квадратичная функция:

f( )= (5.7)

является выпуклой на всем пространстве R⁽ⁿ⁾, если она отрицательно (не положительно) определенная, то есть, если f( )£0 при любом , кроме =0. Квадратичная функция является вогнутой на всем пространстве R⁽ⁿ⁾, если она положительно (не отрицательно) определенная, то есть, если f( )>0 при любом , кроме =0.

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

(5.8)

Здесь, диагональные элементы c_ij являются коэффициентами при х_i², а недиагональные элементы c_ij=c_ji равны половине коэффициента при x_ix_j в формуле (5.7).

Теорема 5.6. Для того чтобы квадратичная функция (5.7) была положительно (отрицательно) определенной, необходимо и достаточно, чтобы все корни уравнения (5.8) были положительными (отрицательными).

Если среди этих корней есть хотя бы один равный нулю – квадратичная функция неотрицательная (неположительная). Наконец, если имеются корни разного знака – квадратичная функция неопределенная.