ГЛАВА 9

ЧИСЛЕЕШЫБ МЕТОДЫ БЕЗУСЛОВНОЙ ШТИМИЗАШШ

§1 . НЕОБХОДИМЬЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ ЭКСТРЕМУМА В ЗАДАЧАХ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Пусть задано множество X с R и функция /(х)=/(х .Xg,... ,х), определенная на множестве X.

Определения. Точка х* € X называется точкой локального минимума

функции /(X) на множестве X, если существует шар

Ug(x*)={x: x-x*j } такой, что для любого х € gC*) выполняется неравенство

fix*) fix). И)

Если неравенство (1) выполняется как строгое (при х ? х*), то говорят, что X* - точка строгого локального минимума. Точка X* € X называется точкой глобального минимума функции /(х) на множестве X, если нерабенство (1) выполняется для любого х из множества X.

Аналогично определяются точки локального и глобального максимума функции /(X) на множествр X.

Точки локального минимума и максимума функции fix) называют точками экстремума этой функции.

Задача отыскания всех локальных минимумов (максимумов) функции fix), если множество X совпадает со всем /г-мерным пространством, т.е. X = R"", называется задачей безусловной оптимизации, а функция /(X) - целевой функцией.

Задачу отыскания точек локального минимума целевой функщш /(X) символически записывают так:

/(X) - mm, X € R". (2)

Аналогично, задачу отыскания точек локального максимума функций /(X) символически записывают следующим образом:

/(X) -* max, X t R. (3)

Задача (3) эквивалентна задаче

-/(X) - mm, X f R"-в том смысле, что множества локальных и глобальных решещй этих задач соответственно совпадают.

Теорема 1 (о необходимых условиях локального минимума). Пусть I X* - точка локального минимума функции fix), которая имеет

§1. Условия екстремума в задачах безусловной оптимизации 151 в этой точке непрерывные частные производные -(х)

(/=1,2.....п); тогда частные производные функции /(х) в этой

точке равны нулю, т.е.

-(X*) = О (/=1.2.....л).

Иначе говоря, в этой точке градиент функции

а/ а/ а/.

v/(x*)=(

дх дх дх

Id п

равен нулевому вектору, т.е. v/(x*)=0.

Определение. Точка х*, удовлетворящая условию

v/(x*) = О,

называется стационарны! точкой функции fix).

bfe всякая стационарная точка функции fix) является решением задачи (2).

Определения. Пусть даны квадратная матрица A=iaj) порядка п и

вектор X € R"". Умножение матрицы А на вектор х дает вектор у=, координаты которого определяются соотношениями

= J ajXj ((=1,2,...,n).

Квадратная матрица А называется симметричной, если а=а.

(Симметричная матрица А называется неотрицательно шределенной,

если для любого вектора х € R" скалярное произведение векторов у= и X неотрицательно, т.е. (i4x,x)>0,* положительно 01феделен-ной, если (,х) > О, X 0; неположительно определенной, если (i4x,x) 0; отрицательно определенной, если (4х,х) < О, х 0.

Теорема 2 (критерий Сильвестра). Симметричная матрица А неотрицательно (положительно) определена тогда и только тогда, когда все главные (угловые) миноры неотрицательны (положительны):

= а > О ( > 0). Ag =

11 12 1 22

> о ( > 0).

Тмба 9. Чюгяеяшю метода бегусловиой оптшаюащш

«11 la «13

*1 «22 «23 «51 «32 «33

> О ( > О),.... det ii > о < > О).

Спметричввя И8трвц8 ii является ввшмкшительво (отрш1втелло)

опредаленвс! тогда в только тогда, когда знаки шсладователь-ных главных миноров чередуются, щячем = а < О ( < О)

= 0 С > О), A3 = «О ( < О),... . Определение. Матрица вида

дхдх дх

нашлзается матрицей Гессе функции fix).

Т1еорем8 3» Если точка х* - локальше ревеню задачи (2) в в этой точке функция fix) имеет вещюрыкше частные прсшзводвне до второго порядка вкяючнтельво, то матрица Гессе функцив fix) в

точке X* является иеотряцательно «феделенвой, т.е.

(И(х*)х,х) >0 VX € Й.

Ивореме 4 (о достаточшх усяовявх локальвого эвстреедма). Если

точка X* является стацшнаршй точкс 4йгнкции fix), т.е.

v/(x*) S О, и матрица Гессе функции fix) в точке х* появт-тельно охфеделена, то х* - строгое локальное ревевие задачи (2); если ве точка х* является стацишаршй для #нкцив / (х) в матрица Гессе в нев отрицательш сацюделенв, то х*- строгое локальное ревение задачи (3), Затчашв. Зедача одномерной минимизации

fix) -» Bin, X с R является частным случаем задачи (2)*