Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [ 11 ] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

Идеи дифференцируемости функции одной переменной легко обобщаются иа случай многомерного аргумента-достаточно рассмотреть вариации функции для его покомпонентных изменений. Например, рассмотрим в точке x = (x„ Xj, .... х„У отклик F иа приращение первой переменной, в то время как остальные п-1 переменных остаются неизменными. Если окажется, что существует предел

.F{xi+h, X,.....\)-Г{х)

-.Um-

назовем его частной производной от F по Xi. Эго число представляет собой наклон касательной к F вдоль направления Xi.

Аналогичным o6pa30.vi определяются частные производные от F по другим координатам, причем частную производную от F по х принято обозначать через 3f/3x,-F. Когда в точке х и в некоторой ее окрестности существуют все п частных производных и в х они непрерывны, то говорят, что F дифференцируема в х.

При определенных условиях (подобных рассмотренным ранее в одномерном случае) на каждую частную производную от F можно смотреть как на новую функцию вектора х. Из этих функций можно составить п-мерный вектор, который принято называть градиентом от F и обозначать через \F{x) или g{x):

Vf (x) = g(x).

К примеру, для функции F (х) вида

F (х) = XjXj -I- Xj cos Xj

/дГ\

3xi )/X5-XsSinx, N \2x,x,-)-cosx,/

ar I

Функцию F, градиент которой ие зависит от х, называют линейной функцией от х; в этом случае F (х) = сх-)-а. где с. а - некоторые фиксированные вектор и число соответственно, причем Vf (х) = с.

В одномерном случае производная определяет направление линии, касательной к кривой, заданной функцией F (х) Точно так же в многомерном случае градиент от f в точке х задает ориентацию касательной гиперплоскости к f в х. Он явлвется

ее нормалью, а расстояние от этой гиперплоскости до начала координат определяется значением F (х). В многомерном случае, как и в одномерном, есть функции, для которых условие дифференцируемости в некоторых точках ие соблюдается. На рис. 2j изображены линии уровня одной из таких функций: F (х) = шах { х, , \х\\. В точках, координаты которых связаны равенством x, = Xj, частных производных от F ие существует. Эти точки являются «угловыми» иа контурном графике. Возможны также ситуации, когда частные производные по одним координатам существуют, а по другим-нет.

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

больше числа предыдущего. Так, «первая производная» функции п переменных представляет собой п-мерный вектор, а ее «вторая производная» имеет уже п компонент, каждая из которых есть частная производная от соответствующей компоненты градиента по соответствующей переменной:

Рис. 2\. Контурный график функции /(х)=п]ах (lA-,). Ixgl}.

; = 1.....п.

(2.53)

Величины (2.53) обычно записывают так:

dxidxj

Если частные производные dF/dx,-, dF/dXj и dF/dx dxj существуют и непрерывны, то существуют и ffF/dXjdx,-, причем 9f/3x,-3x = = dF/дХ/ дх,. В этом случае все п «вторых частных производных» принято сводить в квадратную симметричную матрицу, именуемую матрицей Гессе функции F (х). Впредь эту матрицу будем обозначать через \F (х) илн через С (х):

Если матрица Гессе некоторой функции F постоянна, эту функцию называют квадратичной. Соответствующую F можно записать



Р(ху = -хЮх + сГх + а, (2.54)

где G, с н а - не зависящие от х матрица, вектор и число (множитель 1/2 перед квадратичным слагаемым вводится для того, чтобы скомпенсировать двойку, возникающую при дифференцировании). Заметим, что выражения для производных от функции (2.54) таковы: vf(4=Gx+c, Vf(x)=G.

Дифференцирование вторых производных функции п переменных дает п» третьих производных и т. д. Частные производные от F г-го порядка обозначают через

в.,а.,,...ах,./ = .....

или через Vf (х). Надо, однако, отметить, что производные порядков выше второго редко используются в оптимизационных процедурах.

Определения производных, согласованные с данными выше, легко построить для векториозиачной функции. Эти производные надо рассматривать как результат независимого дифференцирования ее скалярных компонент. Одни шаг такого дифференцирования дает матрицу коби. Для т-мериой функции /(x)=(/i(x), ,f,n(x)V «-мерного аргумента х - это mxn-матрнца, ((,/)-й элемент которой есть производная от fi по Xji соотвегственно /-я строка этой матрицы представляет собой вектор, получающийся транспонированием градиента функции Заметим, что матрица Гессе скалярной функции f (х) совпадает с матрицей Якоби ее градиента.

Класс функций, имеющих непрерывные производные порядков с первого по к-й, обозначают через С. Класс принято называть множеством дважды непрерывно дифференцируемых функций. Дифференцируемые функции иногда называют также «гладкими». Эгот термин оправдан приведенной выше интерпретацией точек разрывов производных как «угловых» точек функции.

Обозначим через g функцию п переменных, и пусть / - векторная функция, такая, что /={/,(0), , , „ fniV. где каждая /, есть скалярная функция одного аргумента 6, Тогда производная от gif(e)) по е определяется следующей формулой, обобщающей приведенное ранее правило дифференцирования сложных функций:

g (/ т=(/; (в) /; (в),,. /; (е» vg (/>.

2,3,3, ПОРЯДОК ФУНКЦИИ

Пусть /(h) -некоторая функция скалярного аргумента ft. Говорят, что / (ft) имеет порядок hP (и пишут при этом f(h)0 (ft)), если существует конечное число Л1 (М > 0), не зависящее от ft.

такое, что при достаточно малых \h\ выполняется неравенство

\f{h)\M\h\P. (2.55)

Значение подобных оценок состоит в том, что иа их основе сопоставляют скорость стремления к нулю разных функций. Считают, что если р > 9, то величина О (ftp) и.меет ,;более высокий порядок малости", чем величина О (ft"), и ее модуль при малых ft сходится к нулю быстрее. Надо, однако, иметь в виду, что гарантировать правильность этого вывода можно лишь в том случае, если в качестве показателей р и q берутся максимально возможные.

Когда выбирают схему аппроксимации какой-то величины, то обычно предпочтение отдают той схеме, ошибки которой имеют наибольший порядок. В этом, безусловно, есть рациональное зерно, но тем не менее некоторая осторожность здесь не помешает-ведь истинное значение О (hP) определяется помимо р константой М и величиной ft. Поэто.му, например, функция /i(/!) = IO-ft оказывается при h > 10-1° ближе к нулю, чем (ft) = 10« ft", хотя последняя 1шеет более высокий порядок малости.

2,3.4, ТЕОРЕМА ТЕЙЛОРА

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

В одномерном случае справедлива следующая

Теорема Тейлора. Если f g С, пю для любых х, h существует число О (0<е<1), такое, что

f(x + h) = f(x) + hf (X) + ~ liT (X) -f .,, -1- A-if-i. (X) +

-f 77 ftf(*:-)-№),

(2.56)

где через f * (x) обозначается k-я производная от f, вычисленная в точке X.

Используя формализм, введенный в предыдущем разделе, тейлоровское разложение (2,56) можно переписать так:

f(x+h)=f{x)-hhr (x)+-iftT W-f . • -)-(7/»-T-"()-t-0(ftO.

Здесь учтено, что величина \ ограничена на отрезке [х, x-fft].

От рассмотренного скалярного случая легко перейти к векторному. Пусть X-некоторая точка, а р-направление в п-мерном пространстве, и пусть F g С. Тогда величина F (x-fftp) будет г раз



непрерывно дифференцируемой функцией скалярного аргу.мента Л, и в соответствии с теоремой Тейлора ее представление типа (2.56) в окрестности точки h = 0 выглядит так:

F(x + hp) = F (к) + hg(xy p + ~hp-rC{x)p+..

+(7=1)Т "D-F (X) + hDF (Х + Шр). Здесь е - некоторое число из отрезка 0, И, а

DF (X) = 2 Д ... • P,3xjx-J..ax,]

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

F(x + hp) = F (х) +hg (xVp + lhYG {х)р + 0 т.

Заметим, что скорость изменения функции f при движении вдоль направлеиня р из точки д: задается величиной g (л;)р. Последнюю принято называть первой производной по направлению. Аналогично число pG (х) р представляет собой вторую производную функции F по направлению р. Ее обычно называют кривизной F вдоль р. Если для некоторого р выполнено неравенство рС (л;) р > О « 0), то говорят, что р-направление положительной кривизны (отрицательной кривизны).

Из разложения функции F около точки х по Тейлору вытекают простые способы ее аппроксимации в окрестности ic. Например, пренебрегая в этом разложении всеми иелинейностями по h, получим

F(i-\-p)F(£)-\-f;(x)-rp. Выражение F {x)-\-g(x) р задает линейную функцию п-мериого вектора р (смещения из х) и аппроксимирует значение f в точке х--р с ошибкой порядка pf. Учет еще одного члена тейлоровского разложения приводит к квадратичной аппроксимации:

F (x-f р) я; F (i) + g ()Гр +1. рго (J) р. Ее ошибка имеет порядок pf.

2.3.5. конечнаразностная аппроксимация ПРОИЗВОДНЫХ Из тейлоровских разложений вытекают не только способы аппроксимации неи.звестных значений функции в окрестности по известным значениям ее самой и ее производных в точке, но н способы решения обратной задачи, а нмеино задачи аппроксимации иеиз-


вестиых значений производных в точке по известным значениям функции в окрестности. В одномерном случае представление (2.56) дважды непрерывно дифференцируемой функции / в окрестности точки X можно переписать так:

"+~=/()-Ьт/"(+)- (2-5

где 0<е,<1. Отсюда следует, что

if±IliW = /(;e) + 0(A). (2.58)

Соответственно, используя в качестве приближения величины f (х) левую часть этого равенства, мы допускаем ошибку порядка ft. Эту ошибку принято назьшать ошибкой отбрасывания. В общем случае параметр 6, остае/ся неизвестным, и поэтому точное значение последней, равное Ijil" (+)• определить ие удается. Приходится удовлетворяться рассчитываемым или оцениваемым значением ее верхней границы.

Величину h в (2.58) принято называть конечно-разностным интервалом. Когда модуль много меньше частного If {x)\/\f"(x-i -1-61/1)1, ошибка отбрасывания будет «малой». Левая часть равенства (2.58). определяющая наклон хорды, которая соединяет на графике функции / точки (х, Цх)) и (x+h, f(x-\-h)), называется праеой конечно-разностной аппроксимацией производной f (х).

Аналогично для точки x-h имеем

/ (X-U)=f (X) -hf (X) -)- \ hr (д;-е,Л). (2.59)

где OsjBjsS 1. Из этого представления следует формула левой конечно-разностной аппроксимации:

f,JЫJ. (2.60)

Здесь ошибка равна ljif"(x-eji).

Если в формулах (2.57). (2.59) выполнить еще по одному шагу тейлоровского разложения, результатами будут равенства вида

/(x-fft) = f {x) + hl W + \ hr (XI -fO (ft»). (2.61)

/ (Х-Л) = f (x)-hr (X) -L AT (X) -)-0 (A). (2.62)

Вычтем второе из первого и поделим полученную разность на Л; это приведет к равенству

n+h)-nx-h) + о (h), (2.63)

В котором нет слагаемых с /"(х), так как оин сокращаются прн вычитании. Выражение в его левой части называют центральной конечно-разностной аппроксимацией для f (х); соответствующая



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [ 11 ] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0015