Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

2.12. Некоторые экстремальные свойства функций на выпуклых множествах

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

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

Определение. Направление s≠0 в точке х выпуклого множества X называется возможным, если существует такое число λ0>0, что для всех λ∈[0, λ0] будет

x + λs ∈X.

Например, если Х = {х: x≥0},то в точке х = 0 любой вектор s≥0, s≠0 задает возможное направление. А в точке


возможным является любое направление


где s2, s3, ..., sn - произвольные числа, s≠0.

Очевидно, если х - внутренняя точка множества X, то любое направление s в этой точке является возможным.

Теорема 2.12.Для того чтобы точка х* выпуклого множества X являлась точкой локального минимума дифференцируемой на X функции φ(х), необходимо, чтобы для всех х ∈ X из достаточно малой окрестности точки х* выполнялось неравенство


Пусть х* - точка локального минимума. Рассмотрим ε - окрестность точки х*:


Тогда для всех х ∈ X ∩ U будет


Так как множество X ∩ U выпукло, то любое возможное направление в точке х* может быть представлено в виде s = x-x*, и для будет


Поэтому


Замечание. В терминах "возможных направлений" эту теорему можно сформулировать следующим образом:

Для того чтобы точка х* выпуклого множества X являлась точкой локального минимума дифференцируемой на X функции φ(x), необходимо, чтобы в этой точке производные по всем возможным направлениям были неотрицательными.

Теорема 2.13.Если выпуклы функция φ(х) и множество X, то любая точка х*∈Х, являющаяся точкой локального минимума, будет оптимальной для задачи минимизации φ(х) на выпуклом множестве X. Множество оптимальных точек выпукло.

Доказательство. Предположим, что х* не является оптимальной точкой, то есть найдется х'∈Х такая, что

φ(x')<φ(x*)

Рассмотрим точки вида

x = αx' + (1-α)х*, α∈(0, 1].

Так как множество X выпукло, то х ∈ X. Далее, из выпуклости φ (х) и из предположения об х' следует


то есть


Но это противоречит условию, что х* - точка локального минимума, поскольку при малых а точка х находится в достаточно малой окрестности точки х*. Наконец, убедимся, что множество


выпукло. Действительно, пусть х'∈G и x"∈G. Поскольку G⊆X, а X выпукло, то для 0≤λ≤1 будет

λx' + (1-λ)x" ∈X

а ввиду выпуклости φ(x) имеем


С другой стороны, поскольку μ - минимальное значение φ(x) на X, то


откуда


то есть G выпукло.

Теорема 2.14.Для того чтобы точка х* выпуклого множества X являлась точкой минимума выпуклой и дифференцируемой на X функции φ(х), то есть оптимальной точкой, необходимо и достаточно, чтобы для любого x ∈ X выполнялось неравенство

<φ'(x*), x-x*>≥0.

Необходимость. Следует из двух предыдущих теорем.

Достаточность. Пусть для любой точки х∈Х будет

<φ'(x*), x-x*>≥0.

Из выпуклости φ(x) следует

φ(x) - φ(x*)≥<φ'(x*), x-x*>≥0.

то есть x* оптимальна.

Теорема 2.15.Если φ(x) строго выпукла на выпуклом множестве X и точка х* ∈ X оптимальна, то есть


то для всех х ∈ X и х ≠ х* будет

φ(x)>φ(x*),

и значит, точка х* единственна.

Доказательство. Предположим, что найдется точка x'∈Х и х*≠х' такая, что

φ(х') = φ(x*) = μ.

Тогда для любого α∈(0, 1] точка x = αx' + (1-α)x* принадлежит множеству X и в силу строгой выпуклости функции φ (х) будет


что противоречит оптимальности точки х*.

Наконец, рассмотрим еще один критерий оптимальности. Пусть

v = x-vφ' (х),

где число v>0 - любое. Обозначим через p = p(v) проекцию точки v на множество X.

Теорема 2.16.Для того чтобы точка х* выпуклого множества X являлась точкой минимума выпуклой и дифференцируемой на X функции φ(х), необходимо и достаточно, чтобы

x* = p(v*),

где v* = x*-vφ'(x*).

Доказательство.

Достаточность. Пусть x* = p (v*). Так как р (v*) есть проекция точки v* на X, то из (2.2) получаем для всех х∈Х неравенство

≤0.

И так как v* = x* - vφ' (х*) и v>0 то, следовательно,

<φ'(x*), х-x*>≥0,

то есть, по теореме 2.14, х*-точка минимума.

Необходимость. Пусть х* - точка минимума. Тогда для любого х∈Х будет

<φ'(x*), х-x*>≥0,

или

-v<φ'(x*), х-x*>≥0,

Но -v<φ'(x*). х-x*>≥0, следовательно,

≤0,

то есть х* в силу теоремы 2.2 есть проекция точки v* на X:

x* = p(v*).

Замечание.Легко убедиться, что если освободить φ(х) от требований выпуклости, то будет справедливо следующее утверждение:

Для того чтобы точка х* выпуклого множества X являлась точкой локального минимума дифференцируемой на X функции φ(х), необходимо, чтобы

x* = p(v*).
предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"