Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Оптимизационные задачи для выпуклых функций

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

в случае градиентных методов, может быть осуществлен за счет подбора соответствующих начальных приближений х(0).

Однако существует один класс функций, для которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции.

F Функция f(x) = f (x1, x2, …, xn) называется выпуклой в области D, если для любых двух точек х(1),

х(2) D и любого λ [0,1] выполняется неравенство

если же

то функция называется вогнутой.

Геометрический смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на рис. 2.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки (х(1), f(x(1))) и (х(2), f(x(2))), а график вогнутой — выше.

Можно доказать, что достаточным условием выпуклости функции f (x1, x2, …, xn) является положительная определенность матрицы

называемой также матрицей Гессе, во всех точках х D. Соответственно, достаточным условием вогнутости является отрицательная определенность матрицы Гессе. В частности, для функций одной переменной достаточным условием выпуклости (вогнутости) является выполнение неравенства fn(x)≥0 (fn(x)≤0).

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


  • Разделы

  • Партнеры