2. Общая постановка задачи

Если в задаче математического программирования целевая функция f (x) и (или) хотя бы одна из функций системы ограничений g_i (x) нелинейна, то такой раздел называется нелинейным программированием (НЛП).

В общем виде задача нелинейного программирования (ЗНЛП) состоит в определении максимального (минимального) значения функции

(2.1)

при условии, что ее переменные удовлетворяют соотношениям

g_i (x₁, x₂, ..., x_n) = b_i, i=1, 2, ..., k,

g_i (x₁, x₂, ..., x_n) <= b_i, i = k+1, k+2, ..., m. (2.2)

Если f и g — линейные функции, то задача (2.1)-(2.2) является задачей линейного программирования.

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

Если отсутствуют ограничения (2.2), то задачу называют задачей безусловной оптимизации.

3. Задача безусловной оптимизации

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

3.1. Определения.

Итак, мы будем рассматривать задачу безусловной оптимизации f(x)  min, (1)

где f: R^m  R. Точка x*  R^m называется решением задачи (1) (или точкой глобального безусловного минимума функции f), если f(x*)  f(x) (2)

при всех x  R^m. Если неравенство (2) выполнено лишь для x, лежащих в некоторой окрестности U(x^*,r) радиуса r точки x*, то точка x* называется локальным решением задачи (1), или точкой локального безусловного минимума функции f. Если неравенство (2) строгое при всех x  x*, то говорят о строгом глобальном и, соответственно, строгом локальном минимумах.

Аналогичные понятия (максимумов) определяются для задачи f(x)  max

З а д а ч а  2.1. Докажите, что точка x* является точкой глобального безусловного (соответственно, локального, строгого) максимума функции f в том и только том случае, когда она является точкой глобального безусловного (соответственно, локального, строгого) минимума функции f.

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

3.3. О дифференцируемости функций на Rm.

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

Вектор a  R^m такой, что f(x + h) = f(x) + (a, h)+o(h)

при всех h  R^m называется производной или градиентом функции f в точке x. Здесь и ниже символ o(h) обозначает произвольную функцию, обладающую свойством

o(h) ||h||

 0 при h 0.

Функция f называется при этом дифференцируемой в точке x. Градиент обычно обозначается f (x), или grad f(x), или f(x). Мы будем, как правило, использовать первое обозначение. Известно, что в координатной форме градиент имеет вид

f (x) =

 

f(x) x1

, ...,

f(x) xm

 

=

 

f(x1, ..., xm) x1

, ...,

f(x1, ..., xm) xm

 

.

Функция f: R^m  R^m дифференцируемая в каждой точке называется дифференцируемой.

Если дополнительно найдется линейный самосопряженный оператор A: R^m  R^m такой, что при всех h  R^m

где запись o(h²) означает, что

o(h2) ||h||2

 0 пpи h ,

то f называется дважды дифференцируемой в точке x, а оператор A называется второй производной функции f в точке x и обозначается f (x) либо ²f(x). Матрицей, отвечающей оператору A = f (x), служит, как нетрудно видеть, так называемая матрица Гессе или гессиан функции f:

A =

        

2f(x) x1x1 ··· 2f(x) x1xm : ··· : 2f(x) xmx1 ··· 2f(x) xmxm

        

.

З а д а ч а  2.2*. Пусть A — линейный самосопряженный оператор в R^m, b  R^m, c  R и f(x) = (Ax, x)/2 + (b, x) + c. Докажите, что f (x) = Ax + b, и f (x) = A.

Если функция F: R^m  R^k, то линейный оператор A: R^m  R^k такой, что

F(x + h) = F(x) +Ah +o(h)

называется производной функции F в точке x и обозначается F (x) (это обобщение понятия градиента на случай функций со значениями в R^k).

Если функция F: R^m  R дифференцируема, то ее градиент можно рассматривать как функцию из R^m в R^m: каждому x  R^m ставится в соответствие точка из f (x)  R^m.

З а д а ч а  2.3*. Докажите, что [f (x)] = f (x). Поясним: здесь [f (x)] — производная функции x  f (x), действующей из R^m в R^m, а f (x) — вторая производная функции f: R^m  R^m.

Еще одно полезное понятие. Функция F: R^m R^k по определению удовлетворяет условию Липшица с константой , если при всех x, y  R^m ||F(x)  F(y)||   ||x  y||.

З а д а ч а  2.4*. Пусть F: R^m R^k дифференцируема. Докажите, что F удовлетворяет условию Липшица с константой , в том и только том случае, если ||F (x)||   при всех x.

Ниже нам потребуется следующее простое утверждение. Если f: R^m  R — дважды непрерывно дифференцируемая функция, то для того, чтобы ее градиент f  удовлетворял условию Липшица с константой  необходимо и достаточно, чтобы при всех x  R^m выполнялось неравенство f   . Действительно, в силу задачи 2.3 при всех t  R и x, h  R^m

(f (x + th), th)  (f (x), th) = (f (x)th, th) + (o(th), th).

Но тогда в силу условия Липшица для f 

(f (x)h, h)   1 t2 |(f (x + th)  f (x), th)| +  o(th, th) t2  

  ||th||2 t2  +  ||o(th)|| · ||th|| t2  =  ||h||2 +  ||o(th)|| t ||h||.

Устремляя t к 0, получим неравенство

(f (x)h, h)   ||h||2,

(5)

эквивалентное нужному неравенству f (x)  .

З а д а ч а  2.5. Докажите обратное утверждение.

В заключение пункта еще одно обозначение. Мы будем писать f  C, f  C¹ и f  C², если f соответственно непрерывна, непрерывно дифференцируема и дважды непрерывно дифференцируема.