Производная по направлению и градиент.

Модели выпуклого программирования

Постановка вопроса

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

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

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

Х1

y=f(x1,x2)

y

Функция f(Х), определенная на выпуклом множестве М n-мерного пространства En, называется выпуклой на М, если для любых точек Х₁ и Х₂, принадлежащих М, и для любого числа λ, 0 ≤ λ≤1 справедливо неравенство

N

Х2

f((1- λ) Х₁+ λ Х₂) ≤(1- λ) f(Х₁)+ λ f(Х₂) (8.1)

x2

т.е., график выпуклойфункции f(Х) расположен ниже (не выше) любой своей хорды (рис. 8.1).

Х1

Х2

N

Иногда выпуклые функции называют выпуклыми вниз, а вогнутые – выпуклыми вверх.

Рис. 8.1.

x1

Если в условии (8.1) знак ≤ изменить на ≥, получим определение вогнутой функции.

Если неравенство (8.1) выполняется как строгое, то функция называется строго выпуклой (или строго вогнутой).

Выпуклость (вогнутость) функции одной или двух переменных видна по ее графику.

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

x_j ≥ 0, j=1, 2, …, n (8.2)

g_i(X) ≤ 0, i=1, 2, …, m (8.3)

и доставляет глобальный минимум функции F=f(x₁, x₂, …, x_n). При этом заданные функции f, g₁, g₂, …, g_m, определенные на n-мерных векторах X с неотрицательными компонентами, предполагаются выпуклыми.

Векторы, удовлетворяющие условиям (8.2) и (8.3), называются допустимыми, а искомые векторы – оптимальными.

Производная по направлению и градиент.

Если функция F дифференцируема в точке Х, то она имеет в этой точке производную по любому направлению l.

Определение 1. Производной функции F(X) по направлению l в точке Х⁰ называется предел . (8.4)

Направление l обычно задается вектором l = (l₁, l₂, …, l_n).

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

(8.5)

где l_i – длина проекции вектора l на ось х_i;

|l| - длина вектора l, т.е. .

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

Определение 2. Градиентом функции F(X) называется вектор, проекциями которого на координатные оси служат соответствующие частные производные этой функции, т.е.

=

Можно показать, что max достигается тогда, когда направление l совпадает с направлением . По формуле (8.5) производная функции F по направлению равна

Таким образом, в каждой точке Х направление градиента является направлением наибольшего возрастания функции, а длина градиента равна наибольшей скорости возрастания функции в этой точке.

Выпуклые функции обладают следующими аналитическими и алгебраическими свойствами:

1. Если функция F(X) выпукла, то функция –F(X) вогнута.

2. Выпуклая (вогнутая) функция, определенная на выпуклом множестве М, непрерывна в каждой внутренней точке этого множества.

3. Если функции выпуклые при всех неотрицательных значениях переменных, то область решений системы неравенств является выпуклым множеством (если она не пуста).

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

5. Дважды дифференцируемая функция F(X) является выпуклой в том и только в том случае, когда

(8.6)

для любых Х М и Δx_i, Δx_j, не обращающихся в нуль одновременно.