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

[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]

Как }же было сказано в гл. 1, класс задач NCP разбивают на подклассы, и делается это по ряду признаков, существенных для выбора метода решения. Эти признаки упоминались в гл. 1, а различные методы (с указанием ориентации) будут представлены в дальнейшем. Однако, прежде чем говорить о методе, необходимо определить, что понимается под «решением» задачи NCP, и выяснить, какими свойствами оно обладает. Мы будем называть решением NCP точку локального минимума целевой функции в допустимой области, г. е. точку, удовлегворяющ>Ю ограничениям задачи и характерную тем, что между значениями целевой функции в ней и в соседних допустимых тонких имеются специфические отношения. Формальные определения звучат следующим образом. Пусть X*-допустимая точка NCP н через N(x*. 6) обозначено множество допустимых точек, содержащихся в 6-окрестностн х*.

Определение А. Точка х* является точкой сильного лекального минимума в задаче NCP, если существует число 6>0, талое что А1. F(x*)<Fly) для всех y&N(x, 6), уф)С.

Заметим, что под это определение подпадае!, в частности, особый случай, когда Л?(х*, 6) состоит из единственной точки х*.

Определение В. Точка х* является точкой слабого локального минимума в задаче NCP. если существует число 6>0, такое что

81. F(х) < F (у) для всех yN (х*. 6);

82. X* не ydociemeopiem определению сильного локального минимума.

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

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

Три выделенные разновидности минимума проиллюстрированы на рис. ЗЬ. Как видно из этого рисунка, бывают задачи, в которых

присутствуют минимумы всех сортов; с другой стороны, попадаются и такие, в которых минимумов нет вообще. В частности, значения функции f (х) в допустимых точках могут оказаться не ограниченными снизу. Это весьма вероятно, к примеру, если f (x)=x,-fx и допустимая область не ограничена. Минимума может не существовать и прн ограниченной снизу f (.v). если она монотонно убывает при х,стремящейся вбесконечность. При.меромслужит/(х)=е"*.


Рис ЗЬ. Примеры минимумов в одномерном случае.

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

Определения А и В сильного и слабого локальных минимумов сами по себе практической ценности не имеют. Использование их для проверки точки на оптимальность предполагало бы подсчет значений F для всех допустимых точек из ее 6-окрестности, и, даже учитьшая, что на цифровой машине потребуется перебрать лишь конечный набор представимых соседних точек, соответствующий объем вычислений все равно пришлось бы признать неприемлемым. К счастью, если F (х) и {с;(х)) обладают некоторыми свойствами гладкости, удается найтн иные, более конструктивные способы описания оптимальных точек.

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



3.2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ 3.2.1. ОДНОМЕРНЫЙ СЛУЧАЙ

Мы начнем изучение условий оптимальности с простейшей задачи о безусловной минимизации функции одной переменной: найти minf(K).

Будет показано, что если f всюду дважды непрерывно дифференцируема и X*- точка ее локального минимума, то должны выполняться следующие соотношения:

Необходимые условия минимума в одномерной задаче без ограничений А1. Г{х*)=0. А2. Г(х*)>0.

Равенство А1 доказывается от противного. Мы установим, что при ненулевой производной f {х*) в каждой окрестности х* нашлись бы точки с меньшим значением /, а поскольку никаких ограничений иа х иет, это противоречило бы определению х* как точки минимума. В силу гладкости / справедливо следующее разложение.

/ (x* 4-в) = / (х«) -I- еГ (x*) -I- 4- вГ (x* -I- 0Е,,

(3.1)

где б (0<В<1) - некоторое число, вообще говоря зависящее от е. Допустим, что производная / (x*) отрицательна. Тогда должно С5Тцествовать числоё (¥> 0), такое, что е/ (xy + efix + ee) < О

для всех е из диапазона О < е<е. При каждом нз таких е в силу (3.1) получим, что /(x*-f с)</(х»). Следовательно, в каждой окрестности х* найдется точки с меньшим значением функции. Это противоречит оптимальности х*, и, значит, / (х*) ие может быть отрицательной величиной. Аналогично устанавливается, что производная / (х*) не может быть положительной. Стало быть, если x*-точка локального минимума, то производная / (х*) равна нулю.

Любую точку x, в которой выполнено равенство /(х) = 0, называют стационарной точкой функции /. Только что было показано, что стационарность-это одно из свойств точек минимумов гладких функций; ясно, однако, что стационарными будут и точки нх локальных максимумов. Кроме того, производная может обращаться в нуль в точках, где нет ни минимума, нн максимума; их называют точками перегиба. Например, начало координат будет стационарной, но не экстремальной точкой функции f{x)=x (рис. Зс).

Требование равенства нулю производной /(х*) называют необходимым условием оптима.1ьности первого порядка. В названии

отражено, что это условие касается только первой производной. Из аналогичных соображений неравенство А2 принято называть условием второго порядка. Его мы также докажем от противного. Пустьх*-точка локального минимума. Тогда в силу А1 f (х*)=0, и разложение (3.1) принимает вид

/(хЧ-е) = /(х«)--4-ЕГ(с + еЕ). (3.2)

Еслн величина /"(х*) отрицательна, то функция Г(х), являясь по предположению непрерывной, будет отрицательной

в любой точке нз некоторой окрестности

x*. Соответственно прн любом ненулевом е, достаточно малом, чтобы точка х*-Ье попала в эту окрестность, нз (3.2) получим /(х*--е)</(х*). Но это противоречило бы определению х* как точки локального минимума. Значит, неравенство Г(х*)<0 невозможно.

Необходимые условия часто привле- р„с. зс. Функция /И=Л кают для того, чтобы установить неоптимальность точки. Если же требуется доказать ее оптимальность. обращаются к достаточным условиям, соблюдение которых является гарантией оптимума. В частности, существование в точке х* сильного локального минимума обеспечено, если справедливы два следующих соотношения:

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

81. Г(х*)=0.

82. Г(х*)>0.

Равенство В1 уже знакомо нам как необходимое условие оптимальности. Когда оно выполнено, можно пользоваться разложением (3.2). Еслн же выполняется и условие В2, то непрерывность Г (х) позволяет утверждать, что фигурирующая в этом разложении вторая производная f (х*--0е) при достаточно малых по мод5лю в будет положительной. Тогда для ненулевых малых с из (3.2) получим неравенство /(х*-Ье)>/(х*), т. е. f(x*) меньше значения / в лю(Зой не совпадающей с х* точке нз некоторой окрестности х*. Это н означает, что х* - точка сильного локального минимума.

Прн разрывных /(х) или / (х) дополнить исходное определение сильного локального минимума практически ценными условиями оптимальности непросто, но кое-что сказать все же можно. Так, например, еслн х* не является точкой разрыва / н в некоторой окрестности x* функция / дважды непрерывно дифференцируема, то можно утверждать, что для х* сохраняют силу все доказанные выше условия оптимальности. Если же f{x) непрерывна, но х*-



точка разрыва / (х), то нетрудно доказать такое утверждение; для того чтобы в х* существовал сильный локальный минимум, достаточно наличия неравенств /!,(л;*)>0, fL(x*}<0.


(i) [ii) (Ш)

Рис. 3d. Три типа минимума в одномерном случае.

На рис. 3d показаны трн ситуации с точками минимума: (i) функция / всюду дважды непрерывно дифференцируема; (ii) f разрывна, но ие в точке х"; (iii) х- точка разрыва производной f.

3.2.2. МНОГОМЕРНЫЙ СЛУЧАЙ

В данном разделе рассматривается задача минимизации функции п переменных;

иСР найти min F (х).

Как и в одномерном случае, начнем с необходимых условий оптимальности. Эти условия для точки X*, где реализуется локальный минимум функции F(x), состоят в следующем;

Необходимые условия минимума для задачи UCP

С1. g(x*)l=0, т. е. X* является стсищонариой точкой. С2. Матрица G(x*) положительно полг/опрвделена.

Для доказательства снова воспользуемся тейлоровским разложением целевой функции в окрестности точки х*:

F(x + Bp) = F (х*) 4- ерГд (х«) -I-1 ерС (х« -I- евр) р. (3.3)

Здесь в и е - числа, причем 0<е<1, а р - вектор размерности п. Не умаляя общности, можно предполагать, что е в (3.3) есть величина положительная.

Необходимость равенства С1 докажем от противного. Допустим, что X*-точка локального минимума, но градиент g(x*) не равен нулю. Тогда найдется вектор р, такой, что

p-g(x»)<0. (3.4)

Например, этому неравенству удовлетворит р = - g (jc«). Сутцест-вуюг и другие подходящие р, причем всех нх принято называть

направлениями спуска в точке х*. Зафиксировав какое-нибудь из указанных р, мы всегда сможем подобрать положительное число е так, что для любого положительного е, удовлетворяющего неравенству Е<ё, в правой части (3.3) будет epg {х*)-{-/рСх(х*-\-+ еОр) р < 0. Соответственно для данных вир получим f (л:*+ ep)<f (>:*).

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

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

Доказательство необходимости условия второго порядка С2 также построим на противоречии. Прежде всего заметим, что в силу С1 справедливо разложение


Рис. Зе. Седловая точка в двумерном случае.

f (х* -I- ер) = f (X*) -(- i ерГО (х« -1- вОр) р.

(3.5)

При этом из непрерывности матричной функции О (х) следует, что для любого р величина p"G (х*-1-е6р)р будет мало отличаться от p"G(x*)p, если только взять е достаточно малым. Значит, при наличии у О (х*) хотя бы одного отрицательного собственного значения, полагая р равным соответствующему собственному вектору, для всех малых по модулю ненулевых в получим неравенство р0 (х*-1-ебр)р < 0. Но это с учетом (3.5) означало бы, что в каждой окрестности X* найдутся точки с меньшими значениями F. Последнее невозможно в силу оптимальности х", что и доказывает справедливость В2.

Докажем теперь условия, достаточные для того, чтобы точка X* была точкой сильного локального минимума в задаче UCP. Они состоят в следующем:



[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.0012