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


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

2.5. Теорема Милютина-Дубовицкого. Интерпретации общих условий экстремума

Остается выяснить, при каких условиях пересечение


окажется пустым. Ответ на "этот вопрос дает теорема Милютина-Дубовицкого.

Пусть R̃ - эвклидово пространство размерности (m+1)n (оно может быть образовано как прямое произведение m+1 пространств R(n)i предварительно пронумерованных). Произвольный вектор Z∈R̃ определяется совокупностью векторов Х(i), принадлежащих соответствующим R(n)i (i = 0,....,m), а его проекциями на координатные оси в R(n)s являются xjs (j = 1,....,n; 0≤s≤m).

Вектор X(s)∈R(n)s с составляющими xjs может быть назван R(n)s - компонентой Z,

Все X(s), представляемые в виде суммы Х° + ρδ(s)δ(s) (s) (0≤ρδ(s)≤ρ(s)) составляют множество R(s) все Z, компоненты X(s) которых принадлежат только R(s), образуют множество R̃, включенное в R̃; наконец, все Z, имеющие равные компоненты X(s) (s = 0,....,m), образуют выпуклое множество П. Если пересечение конусов пусто, то пусто и пересечение множеств R(s).

Предположим, что


Отсюда следует: множества Π и R̃ не имеют общих элементов (если бы существовал хотя бы один такой элемент точка Z, все ее R(n)s -компоненты принадлежали бы R(s), оставаясь равными между собой; по это означало бы существование элемента, входящего во все R(s), что противоречит рассматриваемому предположению).

Поскольку два выпуклых множества Π и R̃ не имеют общих точек, их можно разделить. Другими словами в R̃ найдется такой вектор А≠0 с R(n)s-компонентами A(s), что (A, ZR) > (A, Zn) для любых ZR ∈ R̃ и ZΠ ∈ Π.

Это неравенство можно переписать в виде


или, учитывая форму представления X(s),

(2.10)

Рассматриваемые соотношения имеют место при любых ХП(s) и любых неотрицательных ρδ(s), меньших или равных ρ(s), поэтому можно положить ХΠ(s) = Х°, ρδ(s) = ρ(s) для s = p (0≤p≤m), ρ(s) = 0 для s≠p. Следовательно, (A(р), δ(р) за 0 для произвольного δ(р)∈K(p) и А(р)∈K(p)*

Неравенство (12.10) должно выполняться и тогда, когда ∀ρ(s)δ (s = 0,...,m);


или


где В = ХП(s) - Х° - вектор, не зависящий от s вследствие равенства всех ХП(s) (они являются компонентами вектора ZΠ ∈ П), В свою очередь,

неравенство


справедливо для любых том числе и для


но это возможно лишь при


Таким образом, получены условия существования в точке X°∈U минимума функции f(X), что находит отражение в уже упоминавшейся теореме Милютина-Дубовицкого (10): для того, чтобы множество


было пустым, необходимо существование таких векторов А(i), принадлежащих соответствующим K(i)*которые удовлетворяли бы условию


не будучи все равными нулю.

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

Пусть выпуклые множества Ui определяются условиями gi(X)≤bi (i = 1,.....,m) или просто φi(Х)≤0, где φi(X) - дифференцируемые функции (функция f(X) тоже считается дифференцируемой). Пересечение U = ∩i Ui (область определения задачи) не пусто, т. е. задача является содержательной. Исследуем сначала конус K(0).

Вдоль всех направлений, его составляющих, f(X) убывает, поэтому (df/de) = (∇f, е)<0, при е∈K(0) (другими словами, K(0) объединяет такие векторы е, что(∇f, е)<0). Сопряженный конус K(0)* объединяет точки (векторы) А0, удовлетворяющие условию (А0, е) > 0. Следовательно, А0 = λ0∇f при λ0≤0 (произвольному А, соответствует не положительное число λ0). Относительно K(i) (i = 1,....,m) можно заметить следующее: если Х° является внутренней точкой области Ui, то конус K(i) совпадает с Rn; если же Х° есть граничная точка Ui, то конус K(i) содержит векторы е, образующие тупой угол с направлением (∇φi). (см. рис. 2.11), т. е. e∈K(i) при (∇φi(Х°), е)<0, а сопряженный :конус образуют векторы Ai = λiφi (Х°) при λi<0 (эти условия могут быть интерпретированы и так: если Ai∈K(i)*, то либо Аi=0 при φi(Х°)<0, либо Аi = λiφi(Х°), λi<0 при φi(Х°) = 0). Отсюда следует другая формулировка теоремы (10): для того чтобы f(X) достигала минимума в точке Х° при ограничениях φi(Х)≤0, необходимо существование таких чисел λi≤0, (t = 1,....,m), которые, не будучи все равными нулю, удовлетворяли бы условиям


причем λi=0 при φi(X)<0.

Рис. 2.11
Рис. 2.11

В этой формулировке рассматриваемая теорема совпадает с правилом множителей Лагранжа. Оказывается, при определенных условиях она приводит и к теореме Куна-Таккера.

Пусть X* -точка минимума вогнутой функции f(X) на выпуклом непустом множестве


заданном ограничениями φi(X)≤0, где φi - выпуклые функции. Очевидно, X* удовлетворяет требованиям теоремы (10), например, в ее последней формулировке, из которой следует


(всегда либо φi*) = 0, либо соответствующий множитель λi*, обращается в нуль). Таким образом, для любого λi≤0 имеем


или Φ(Х**)≥Φ(Х*,Λ), где Φ - функция [Лагранжа. Вместе с тем, в силу вогнутости (по предположению) функций f(X), λiφi(Х) (λi≤0, i = 1,...,m) вогнутой по X оказывается и Φ(Х, Λ), что позволяет утверждать Φ(Х, Λ*)≥Φ(Х*, Λ*) (равенство ∇Φ = 0 предполагается выполненным в силу требований теоремы Милютина - Дубовицкого). Полученные соотношения указывают на существование седловой точки X*, Λ* функции Лагранжа как необходимое и достаточное условие экстремума f(X) в рассматриваемом случае.

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

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





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


Диски от INNOBI.RU




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