2.4. Проблема единого подхода к задачам математического программирования. Условия существования оптимума

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

- множество K называется конусом с вершиной в начале координат, если вместе с точкой (вектором) X оно содержит и точки (векторы) аХ, а≥0;

- двойственным (или сопряженным) данному K называется конус K^*, содержащий те точки (векторы) Y, которые удовлетворяют условию (Y, Х)≥0, ∀X∈K, где (Y, X) - скалярное произведение указанных X, Y (см. рис. 2.4; конус K^* заштрихован);

- Многогранным конусом, образованным на базе векторов V_p, называется множество векторов X, получаемых

как Х = ^NΣ_p=1 а_рV_р при ∀a_i≥0 (рис. 2.5);

- конусом возможных направлений K_Х0, рассматриваемым по отношению к некоторому выпуклому множеству U и связанным с произвольной точкой Х₀∈U, называется совокупность всех отличных от нуля векторов 8, каждому из которых можно поставить в соответствие такое число ρ_δ>0, что X=Х₀+ρ_δδ будет принадлежать U пои любом 0<ρ_δ≤ρ, ρ>0 (см. рис. 2.6; здесь K_X0 образован векторами X - Х₀, составляющими с касательной угол, не превышающий π);

- конусом возможных направлений K^f_X0, рассматриваемым по отношению к некоторой функции f(X) и связанным с Х₀, называется совокупность 8^0, каждому из которых можно поставить в соответствие такое число ρ_δ>0, f(X₀+ρ_δδ)≤f(X₀) при любом 0<ρ_δ≤ρ, ρ>0 (другими словами, K^f_X0 содержит точки X, в которых значения f не превышают f(X₀)).

Рассмотренные определения позволяют сформулировать ряд теорем, которые используются в дальнейшем для исследования свойств экстремума f(X).

Рис. 2.4

Рис. 2.5

I. Если U - замкнутое выпуклое множество и Y - внешняя по отношению к U точка, то существует единственная точка Х₀∈U, обладающая свойством ||Х₀-Y||<||X-Y|| для ∀ Х∈U, Х ≠ Х₀ (действительно, величина ||X-Y|| является непрерывной неотрицательной функцией X, и на произвольном замкнутом множестве она достигает своего минимума ||X₀-Y||; поскольку U выпукло, Х₀ - единственна, см. рис. 2.7).

II. Если U - выпуклое замкнутое множество и Y - внешняя по отношению к U точка, то существует такой вектор А, что (А, Х)<(А, Y) для ∀X∈U (первая теорема о отделимости).

Рис. 2.6

Рис. 2.7

Рис. 2.8

Доказательство: пусть X - произвольная точка области U; тогда Q∈U, если Q = aX+(1-a)X₀, 0<а<1 (свойство выпуклости U), и в силу утверждения I выполнено неравенство ||Y-X₀||²<||Y-Q||², которое может быть - интерпретировано как (Y-Х₀, Y-X₀) < (1-а) Х₀-аХ, Y-(1-а) Х₀-аХ) или а²-2а(Х-Х₀, Y-X₀)>0, скольку все эти соотношения должны иметь место и при сколь угодно малых а>0, необходимо (X-Х₀, Y-Х₀) < 0; положив Y-Х₀ = А, получим (Х-Х₀, А) < 0 или (А, Х)<(А, Х₀) и тем более (А, X)<(А, Y) (см. рис. 2.8); из условия (А, X)<(А, Y) следует (kA, X) < (kА, Y), k>0, поэтому без потери общности можно принять ||А|| = 1. □

III. Если U₁, U₂ - выпуклые замкнутые множества, не имеющие общих точек, то существует такой вектор А, что (А, Х)<(А, Y) для ∀ X∈U₁ и ∀Y∈U₂ (вторая теорема об отделимости).

Доказательство: пусть P - множество точек Р = Х-Y при Х∈U₁ ,Y∈U₂; можно показать, что P выпукло в рассматриваемых условиях; кроме того, всегда можно считать точку 0 внешней по отношению к Р; следовательно, существует вектор А, для которого (А, Р)<(А, 0) или (А, X-Y)<0; последнее неравенство равносильно утверждению (А, Х)><(А, Y) (см. рис. 2.9). □ Геометрический смысл этого результата заключается в возможности провести некоторую разделяющую гиперплоскость, так что области U>₁ и U₂ окажутся "по разные стороны" от нее (приведенную теорему обычно называют теоремой об отделимости двух выпуклых множеств) .

Непосредственное использование введенных выше понятий связано с рассмотрением важной теоремы (9): если Х°∈U есть точка минимума функции f(X) и множество U выпукло, то пересечение конусов K^f_X° и K_X° пусто.

Доказательство: пусть рассматриваемое пересечение не пусто и X̂ есть произвольная точка, ему принадлежащая; если Х° является внутренней экстремальной точкой, то K_X° совпадает с U и X̂∈K^f_X°∩U (рис. 2.10); из факта принадлежности X̂ множеству K^f_X° следует f(Х̂)<f(Х°) (см. определение K^f_x°), т. е. Х° не доставляет минимума f(X) (возникшее противоречие доказывает исходное утверждение); аналогичная ситуация возникает и в случае, когда Х° лежит на границе U (см. рис. 2.10). □

Рис. 2.9

Рис. 2.10

Обычно область U представляется как пересечение нескольких областей U_i, порождаемых отдельными ограничениями, входящими в систему вида g_i(Х)≤b_i или φ_i(Х)≤0, т. е.

Пусть U_i выпуклы; обозначив конус возможных направлений, относящийся к U_i как K⁽ⁱ⁾_X° конус K^f_X° как K⁽⁰⁾_X° приходим к заключению: f(X) достигает минимума в X°∈U если