§ 1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ И ОСНОВНЫЕ ПОЛОЖЕНИЯ

- целевую функцию /(*), где х = (х!,..., хп)Т, определенную на л-мерном

евклидовом пространстве Яп. Ее значения характеризуют степень достижения цели, во имя которой поставлена или решается задача;

- множество допустимых решений X pound; Я*, среди элементов которого осу­ществляется поиск.

Требуется найти такой вектор х* из множества допустимых решений, которому соответствует минимальное значение целевой функции на этом множе­стве:

/(**) = ^тц^/(*)- (1.1)

Замечания 1.1.

1. Задача поиска максимума функции /(х) сводится к задаче поиска ми­нимума путем замены знака перед функцией на противоположный (рис. 1.1): /(**)= таpound; /(*)=- тpound; [- /(*)] •

2. Задача поиска минимума и максимума целевой функции /(х) называет­ся задачей поиска экстремума:

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

экстремума. Если X = Яп, т.е. ограничения (условия) на вектор х отсутствуют, решается задача поиска безусловного экстремума.

4. Решением задачи поиска экстремума является пара |х*,/(х*)|, вклю­чающая точку х* и значение целевой функции в ней.

5. Множество точек минимума (максимума) целевой функции /(х) на

множестве X обозначим X*. Оно может содержать конечное число точек (в том числе одну), бесконечное число точек или быть пустым.

Определение 1.1. Точка х* еХ называется точкой глобального (абсолютного) минимума функции /(х) на множестве X, если функция достигает в этой точке своего наименьшего значения, т.е.

/(*•)*/(*) V* е ЛГ .

Определение 1.2. Точка х* еХ называется точкой локального (относитель­ного) минимума функции /(х) на множестве X, если существует е gt; 0, такое, что

если х е X и ||х- х*|| lt; е, то /(**) lt; /(х).

Замечания 1.2.

1. В определении 1.1 точка х* сравнивается по величине функции со всеми точками из множества допустимых решений X, а в определении 1.2 - только с принадлежащими ее е - окрестности (рис. 1.2).

Рис. 1.2 2. Если в определениях 1.1 и 1.2 знак неравенства lt; заменить на 2, то по­лучатся определения глобального (абсолютного) и локального (относительного) максимумов. 3. Глобальный экстремум всегда является одновременно локальным, но не наоборот. Определение 1.3. Поверхностью уровня функции /(х) называется множество точек, в которых функция принимает постоянное значение, т.е. /(х) = const. Если л = 2, поверхность уровня изображается линией уровня на плоскости R2.

Пример 1.1. Построить линии уровня функций: a) f{x) = xl + xl\ б) f(x) = 2L+xj;

в) f(x) = дс| - х\; г) /(х,, х2) = .

? Уравнения линий уровня имеют следующий вид:

а) f(x) = х2 + х\ = const -г2 - уравнение окружностей с центром в точке (О, Of и радиусом, равным г (рис. 1.3, а)\

х2

б) /(*) = — + х2 = const - уравнение эллипса. Если const = 1, то а = 2, 6 = 1- большая и малая полуоси (рис. 1.3, б);

в) /(*) = х2 - х2 = const - уравнение гиперболы (рис. 1.3, в);

г) f(x\gt;х2) = Х2 = const - уравнение двух параллельных оси Охх прямых

(рис. 1.3, г). #9632;

в

Пример 1.2. На рис. 1.4 изображены линии уровня функции. Цифры ука­зывают значение функции /(х) на соответствующей линии. Точкам А и В со­ответствуют значения функции /(А) = 10 и /(В) = 5. Требуется классифициро­вать точки экстремума.

? Функция рассматривается на множестве В2, т.е. решается задача поиска безусловного экстремума. В точке А с координатами (1,3)г достигается локальный

минимум; в точке В с координатами (3,1)гдостигается локальный и глобальный

минимум одновременно; в точке С нет ни минимума, ни максимума, так как по одним направлениям функция убывает, а по другим возрастает. Заметим, что изображенная структура линий уровня типична для так называемых многоэкс­тремальных задач.«

Рис. 1.4

Пример 1.3. На рис. 1.5 изображен ірафик функции /(х), определенной на

множестве X ш Я. Требуется классифицировать точки экстремума.

? Решается задача поиска безусловного экстремума. На рис. 1.5 выделим є-окрестности точек А,В,...,Г и проверим выполнение определений 1.1 и 1.2 с учетом пп. 1, 2 замечаний 1.1, 1.2. В результате получаем: точка А - точка ло­кального минимума; точки Д Е - точки локального максимума; бесконечное множество точек из отрезка СВ - точки локального минимума; точка - точка локального и одновременно глобального минимума; глобальный максимум отсутствует.

ю

Пример 1.4. Найти точки экстремума функций /(х) = х2 + х2 и

х2

/(*) = + Х2 на множестве Л2.

? Обе целевые функции имеют в точке х* « (0,0)т локальный и одновре­менно глобальный минимум, а локальных и глобальных максимумов не имеют (см. рис. 1.3 а,б), ш

Пример 1.5. Найти точки экстремума функции /(х) = х2 + х2 на множестве X = {х | х\ - х{ + 3 = 0 }.

? Решается задача поиска условного экстремума. Линии уровня функции /(х) представляются окружностями (см. рис. 1.3, а), а множество допустимых

решений X - параболой с уравнением хі = х\ + 3. В точке х* = (3,0)г, /|х*| = 9

достигается глобальный минимум (рис. 1.6). Заметим, что эта точка является точкой касания линии уровня и кривой, описывающей множество X. Глобаль­ный максимум на данном множестве не достигается. Если поменять знак перед функцией на противоположный, то в точке х* функция /(х) = -х2 - х\ будет достигать глобального максимума на множестве X, что соответствует п. 1 заме­чаний 1.1. #9632;

Пример 1.6. Найти точки экстремума функции /(х) = х2 +х2 на множестве Аг = {х|х1 +Х2“2 = 0}.

? Решается задача поиска условного экстремума. Линии уровня функции /(х) представляются окружностями (см. рис. 1.3, а), а множество допустимых

решений X - графиком прямой. В точке х* *(1,1)г, /|х*| = 2 достигается гло­

бальный минимум (рис. 1.7). Глобальный максимум на данном множестве не существует. Заметим, что, как и в, примере 1.5, в точке х* линии уровня касают­ся кривой, описывающей ограничения. #9632;

Пример 1.7.

ЛГ = {х|х,2-х|-1=о}.

? Решается задача поиска условного экстремума. Линии уровня функции f(x) представляются окружностями (см. рис. 1.3, а), а множество X - гиперболой (рис. 1.8). Имеются две точки глобального минимума:

х* = (l.of, х* = (-1,0 f, /(х’)= /Гх*1 = 1.

X х2 v }

В них выполняется свойство касания линий уровня и кривых, описывающих множество X, отмеченное при решении примеров 1.5, 1.6. Точки глобального и локального максимума отсутствуют. #9632;

Пример 1.8. Найти точки экстремума функ­ции f(x) - х{ на множестве допустимых решений

X = {* I х\ + х2 ^ 1» *1 ^ 0, х2 pound; 0}.

? Решается задача поиска условного экстре­мума. Линии уровня функции имеют уравнение f(x) = хх = const и представляются прямыми, па- Рис. 1.8 раллельными оси Ох2. Множество допустимых ре­

шений, где все ограничения выполняются одно­временно, заштриховано на рис. 1.9. В точке С = (1,0)г, /(С) = 1 достигается глобальный максимум, на множестве точек отрезка АВ достигается глобальный минимум с значением целевой функции /(gt;4) = f(B) = 0. #9632;

С

Рис. 1.9

Пример 1.9. Найти точки экстремума функции /(х) = -х2 на множестве X = {х\-2lt;gt;хй\}.

? Решается задача поиска условного экстремума. Глобальный максимум достигается в точке В при х = 0, /(В) = 0. Локальный минимум достигается в точке С при х = 1, /(С) = -1, а глобальный минимум - в точке А при х = -2, /(gt;4) = -4 (рис. 1.10). #9632;

Пример 1.10. Найти точки экстремума функции /(х) = 1пх на множестве ДГ = {х | 0 lt; х lt; 3 }.

? Решается задача поиска условного экстремума. Функция не имеет точек локального и глобального экстремума, так как не выполняются определения 1.1 и 1.2 (рис 1.11). При приближении к левой границе значение функции стремит­ся к /* = -оо (функция является неограниченной снизу), а при приближении к правой границе функция возрастает, но не имеет максимума, так как точка х = 3 не принадлежит множеству X. #9632;

/

/

Определение 1.4. Градиентам У/(х) непрерывно дифференцируемой функ­ции /(х) в точке х называется вектор-столбец, элементами которого являются частные производные первого порядка, вычисленные в данной точке:

ГМг!)

дхх

ёМ

'УМ-

дх2

ёМ

дхп

Градиент функции направлен по нормали к поверхности уровня (см. опре­деление 1.3), т.е. перпендикулярно к касательной плоскости, проведенной в точ­ке х , в сторону наибольшего возрастания функции в данной точке.

Определение 1.5. Матрицей Гессе Н{х) дважды непрерывно дифференциру­емой в точке х функции /(х) называется матрица частных производных второго порядка, вычисленных в данной точке:

*№)

дхідхп

pound;М

дх2дхп г2/(х)

дхі

, д2/(х)

гдеА*=^

Замечания 1.3.

1. Матрица Гессе является симметрической размера (пхп).

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

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

4/*(х) = /(х + Ах)- /(х) = У/(х)Г Ах + - А хТН(х) Ах + о||Дх||2|, (1.2)

где о|||Ах||2| - сумма всех членов разложения, имеющих порядок выше второго; АхгЯ(х) Ах - квадратичная форма.

Пример 1.11. Для функции /(х) = х2 + х\ необходимо:

а) вычислить и построить градиент в точках х° = (0,1)г, х1 =

х2 = (1,0)Т, хъ = (0, - 1)г; б) найти матрицу Гессе.

? По определениям 1.4, 1.5 имеем:

Щх) = {гхь2х2?, У/-(х°) = (0,2)7\ У/(х1) = (л/2,ЦТ, У/(х2) = (2,0)Г,

У/(х3) = (0,-2)Г, Я(х) = ^ °).

Заметим, что матрица Гессе квадратичной функции не зависит от х. На рис. 1.12 изображены найденные градиенты. #9632;

Пример 1.12. Для функции /(х) = х2 + х\ вычислить градиент и найти мат­рицу Гессе в точках х° = (О,О)7, х1 = (1,1)^ *

? Согласно определениям 1.4 и 1.5 имеем:

Определение 1.6. Квадратичная форма Дхг#(х)Дх (а также соответствую­щая матрица Гессе #(х)) называется:

положительно определенной (Я(х) gt; 0), если для любого ненулевого Дх выполняется неравенство Дх7#(х)Дх gt; 0;

отрицательно определенной (Я(х) lt; 0), если для любого ненулевого Дх вы­полняется неравенство ДхгЯ(х) Дх lt; 0;

положительно полуопределенной (Я(х) gt; 0), если для любого Ах выполняет­ся неравенство ДхгЯ(х) Дх pound; 0 и имеется отличный от нуля вектор Ах, для ко­торого ДхгЯ(х)Дх = 0;

отрицательно полуопределенной (Я(х) й 0), если для любого Ах выполняет­ся неравенство ДхгЯ(х) Дх й 0 и имеется отличный от нуля вектор Ах, для ко­торого ДхгЯ(х)Дх = 0;

неопределенной (Я(х) ^0 ) , если существуют такие векторы Ах, Дх, что выполняются неравенства ДхгЯ(х)Дх gt; 0, АхТН(х)Дх lt;0;

тождественно равной нулю (Я(х) amp; 0), если для любого Дх выполняется ДхгЯ(х)Дх = 0.

Пример 1.13. Классифицировать квадратичную форму и матрицу Гессе Я-(; ^] » полученную в примере 1.11.

? Выпишем квадратичную форму:

АхТ НАх = (Д*1 Ддс2)[ц °)(^)=2А^+2Дх|.

Очевидно, ДхгЯДхgt;0 для любого ненулевого Дх. Согласно определению 1.6 квадратичная форма (матрица Гессе) положительно определенная. #9632;

Пример 1.14. Классифицировать квадратичную форму и матрицу Гессе

гг (2 0gt;1

Я = I о д! gt; полученную в примере 1.12.

? Выпишем квадратичную форму:

АХТНАХ = (АХ1 Д*2)(2 о) (дх2) = 2 Д^'2'

Очевидно, ДхгЯ(х)Дх pound; 0 для любого вектора Ах и ДхгЯ(х) Ах = 0 для Ах! = 0 и любых Дх2 * 0. Согласно определению 1.6 квадратичная форма (матрица Гес­се) положительно полуопределенная. #9632;

Пример 1.15. Найти матрицу Гессе функции /(х) = х* - х2 и классифици­ровать ее.

? Следуя определению 1.5, получаем Я(х) = ^ • Выпишем соответ­

ствующую квадратичную форму:

При А*! = 0 и любых Дх2 * О квадратичная форма отрицательна, а при АХ} * О и Ах2 = 0 положительна. Согласно определению 1.6 квадратичная форма (матрица Гессе) неопределенная. #9632;

Определение 1.7. Множество X pound; В* называется выпуклым, если оно содер­жит всякий отрезок, концы которого принадлежат X , т.е. если для любых х1,х2 єX и 0lt;И1 справедливо А.Х1 + (1 -Х)х2 еX.

Пример 1.16. Требуется выбрать выпуклые множества среди изображенных нарис. 1.13.

а б в

? На рис. 1.13, а-г множества выпуклые, так как удовлетворяют определе­нию 1.7, а остальные не являются выпуклыми. #9632;

Образно говоря, выпуклыми являются множества, которые не содержат quot;вмятин”, quot;дырокquot; и состоят из одного quot;кускаquot;. Примерами выпуклых множеств служат также само пространство Rn, отрезок, прямая, шар.

Определение 1.8'. Функция /(х), определенная на выпуклом множестве X, называется выпуклой, если f{% х1 + (1 - А.) х2 J pound; A. f[xl ) + (1 - A.) f[x2 J Vx1, x2 e X, 0 lt; A. lt; 1.

Определение 1.9. Функция /(x), определенная на выпуклом множестве X, называется строго выпуклой, если f{% х1 + (1 - А.) х2 ) lt; A. f(xl j + (1 - A.) /(*2) Vx1,x2 eX9 x1 ф x2, 0 lt; X lt; 1.

Определение 1.10. Функция /(х), определенная на выпуклом множестве X, называется сильно выпуклой с константой / gt; 0 , если

f{%xl + (1 - А,)х2) pound; Xf[xx) + (1 - А,)/(х2) - ^ Х(1 - X) Цх1 - х2||2 Vx!,x2 еХу х19tx2, 0lt; А, ^ 1.

Замечания 1.4.

1. Функцию /(х) называют выпуклой, если она целиком лежит не выше

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

2. Если функция сильно выпуклая, то она одновременно строго выпуклая и выпуклая. Если функция строго выпуклая, то она одновременно выпуклая.

3. Выпуклость функции можно определить по матрице Гессе: если #(х) pound; 0 Vx е Rn, то функция выпуклая;

если Н(х) gt;0 Vx е Rn, то функция строго выпуклая;

если Я(х) gt; IE Vx g Rn, где E - единичная матрица, то функция сильно выпуклая.

Пример 1.17. Дана функция /(х) = х2, определенная на множестве X = {х | -1 lt; х lt; 1} (рис. 1.14). Требуется исследовать ее на выпуклость.

? Функция является строго выпуклой согласно п. 1 замечаний 1.4, так как она целиком лежит ниже отрезка, соединяющего две ее произвольные, но не совпадающие точки (рис. 1.14). Более того, функция одновременно является сильно выпуклой, так как согласно п. 3 замечаний 1.4 выполняется условие Я(х) = /quot;(х) = 2pound;/ при 0lt;/^2. Очевидно, условия выпуклости и строгой вы­пуклости также выполняются (см. п.З замечаний 1.4), что иллюстрирует справед­ливость п. 2 замечаний 1.4. #9632;

/

Рис. 1.14

Пример 1.18. Дана функция /(х) = х, определенная на множестве

X = {х | 0 lt; х pound; 1} (рис. 1.15). Требуется исследовать ее на выпуклость.

? Согласно п. 1 замечаний 1.4 функция является выпуклой, так как она целиком лежит не выше отрезка, соединяющего две ее произвольные точки, но не является строго выпуклой и тем более сильно выпуклой. #9632;

Пример 1.19. Исследовать выпуклость функции /(х) = х2 + х\ на множест­ве Л2.

? Согласно результату примера 1.11 матрица Гессе удовлетворяет условию

-м-е 3 ^/(о 1) ПРИ 0lt; ^ 2. Следуя п. 3 замечаний 1.4, можно сделать

вывод о сильной выпуклости функции. Одновременно она является строго вы­пуклой и выпуклой (см. п. 2 замечаний 1.4). #9632;

19

Далее при решении примеров используются следующие свойства выпуклых функций.

Утверждение 1.1.

1. Если /(х) выпуклая функция на выпуклом множестве X, то всякая точка

локального минимума является точкой ее глобального минимума на X (см. пример 1.6).

2. Если выпуклая функция достигает своего минимума в двух различных точ­ках, то она достигает минимума во всех точках отрезка, соединяющего эти две точки (см. пример 1.8).

3. Если /(х) строго выпуклая функция на выпуклом множестве X, то она

может достигать своего глобального минимума на X не более чем в одной точке (см. пример 1.6).

Определение 1.11. Функция /(х) удовлетворяет условию Липшица на отрезке [а,Ь], если существует такое число Ь gt; 0 (константа Липшица), что

\Пх')-/{хquot;)\и\х'-хquot;\ (1.3)

для всех х' и хquot;, принадлежащих [а,Ь] .

Замечания 1.5.

1. Если неравенство (1.3) выполняется с константой Ь, то оно справедливо для бесконечного множества констант, больших Ь. Как правило, представляет интерес минимальная из констант Липшица.

2. Из условия (1.3) следует непрерывность функции /(х) на отрезке [а,Ь]. Если кроме того функция имеет на [а,Ь] непрерывную производную, то кон-

станта Липшица L = ^ |/’(*) | •

3. Условие (1.3) означает, что модуль углового коэффициента любой хорды графика функции /(х) не превосходит L.

Пример 1.20. Проверить, удовлетворяют ли условию Липшица следующие функции: а) /(х) = 2х на отрезке [0,1]; б) /(x) = sinx на отрезке [0,тс];

в )/(x) = Vx на отрезке [0,1].

? Воспользуемся определением 1.11 и п.2 замечаний 1.5:

а) функция /(х) = 2х удовлетворяет условию Липшица на отрезке [0,1] с константой L = 2;

б) функция /(х) = sinx удовлетворяет условию Липшица на отрезке [0, тс]

с константой L = ^ rrj^c ^ | cos х | = 1;

в) функция /(х) = 4х не удовлетворяет условию Липшица на отрезке [0,1], так как при х -#9658; +0 угловой коэффициент касательной к 1рафику неадраничен- но возрастает, а переходя в (1.3) к пределу при | х - хquot; | -gt;• 0, можно заключить, что если в некоторой точке существует касательная к 1рафику функции /(х) , то модуль ее углового коэффициента не может превышать L. #9632;

Задачи для самостоятельного решения

1. Найти точки экстремума функции /(х) = + .(*2,+ ^ на множе-

4 9

ствеЛ2.

Ответ: в точке х* = (3,- 2)г- одновременно локальный и глобальный без­условный минимум.

2. Найти точки экстремума функции/(х) = -(хх +1)2 - -*2 + ^ на множе-

16

ствеЛ2.

Ответ: в точке х*=(-1,-4)г- одновременно локальный и глобальный безусловный максимум.

3. Найти точки экстремума функции /(х) = — на множестве

X

X = {х| 0 lt; х lt; 2}.

Ответ: функция не имеет точек локального и глобального экстремума.

4. Найти точки экстремума функции /(х) = (Х| -1)2 + (х2 -1)2 на множе­стве X = {х| X} + х2 * 0}.

Ответ: в точке х* = (0,0)г - одновременно локальный и глобальный услов­ный минимум.

5. Найти точки экстремума функции /(х) = X!2 - 4х^2 + 4х22 на множест­ве Я2.

Ответ: так как /(х) = (х! - 2х2)2, то во всех точках прямой с уравнением х{ = 2х2 достигается одновременно локальный и глобальный минимум.

6. Проверить знакоопределенность матрицы Гессе целевой функции

/(х) = X!3 + х23 - ЗХ|Х2 в точке (0,0)Т.

Ответ: матрица Гессе и соответствующая квадратичная форма неопреде­ленные.

7. Проверить знакоопределенность матрицы Гессе целевой функции

х 2

/(х) = —1— + х22 . Исследовать ее на выпуклость.

4

Ответ: матрица Гессе положительно определенная. Функция является сильно выпуклой, так как Н(х) pound; / Е при 0 lt; / й - .

8. Проверить знакоопределенность матрицы Гессе целевой функции

/(х) = X!2 - 4х^2 + 4х22 . Исследовать ее на выпуклость.

Ответ: матрица Гессе положительно полуопределенная, функция выпук­лая.