12. Задача с неравенствами. Необходимое условие оптимальности первого порядка

Пусть дана задача: (1)

Определение. Пусть – некоторый план, то есть . Говорят, что ое ограничение задачи (1) активно на этом плане, если оно принимает вид и пассивно, если .

Обозначим .

Ясно, что если – внутренняя точка, то .

Теорема 1. Пусть – локально-оптимальный план задачи (1). Тогда несовместна система неравенств:

(2)

(3)

Тогда система нер-в несовместна.

Доказательство. Пусть – локально-оптимальный план задачи (1). Предположим противное, то есть найдётся такой вектор , который удовлетворяет системе (2)-(3). Построим вектор . Докажем, что является планом задачи (1). Действительно, если , то получаем

при достаточно малых положительных .

Если , то при достаточно малых положительных .

Итак, при достаточно малых положительных – планы и они лежат в сколь угодно малой окрестности . Тогда получаем разложение:

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

Противоречие доказывает теорему.

Ч.т.д.

12. Задача снеравенствами. Обобщённое правило множителей Лагранжа

Пусть дана задача: (1)

Теорема 2. Пусть – локально-оптимальный план задачи (1). Тогда найдётся такой обобщённый вектор Лагранжа , что

1.

2. , не все равные нулю

3.

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

1. Пусть – локально-оптимальный план задачи (1). Тогда справедлива теорема 1, то есть, несовместна система неравенств (2)-(3). Применим к ней теорему Фаркаша о несовместности системы неравенств. Согласно теореме найдутся такие числа , не все равные нулю, что будет выполняться условие

(4)

Положим тогда остальные =0, и, добавив в (4) нулевые слагаемые, получим:

(5)

Это и есть условие стационарности (1).

2. Условие неотрицательности следует из теоремы Фаркаша.

3. Для получаем:

, так как по определению.

Для получаем:

, так как =0 по предположению.

Ч.т.д.

12. Задача с неравенствами. Классическое правило множителей Лагранжа

Пусть дана задача: (1)

Определение. Пусть – некоторый план задачи (1). Будем называть его обыкновенным, если вектора

(6)

линейно независимы.

Теорема 3. Пусть – обыкновенный локально-оптимальный план задачи (1). Тогда необходимо найдётся такой классический вектор Лагранжа , причём единственный (он может быть нулевым), что выполняется условие:

1.

2.

3. .

Доказательство. Пусть – обыкновенный локально-оптимальный план. В силу локальной оптимальности для него выполняется условие теорема 2, в частности, условия (4)-(5). Докажем, что в силу обыкновенности множитель . Предположим противное, то есть . Тогда из условия (4) получаем

,

в котором не все множители нулевые. Тогда это означает линейную зависимость векторов (6) и противоречит обыкновенности .

Итак, положительно. Разделим тогда выражение (5) на и переобозначим: , тогда придём к условию .

Условия 2 и 3 теоремы следуют из теоремы 2.

Докажем единственность . Предположим противное. Найдётся ещё один вектор Лагранжа такой что . Вычитая из этого равенства , придём к , причём не все коэффициенты . Это означает линейную зависимость векторов (6) и снова противоречит обыкновенности .

Ч.т.д.

Обсуждение. Теорема 2 и теорема 3 вместе приводят к принципу Лагранжа снятия ограничений в задаче (1), согласно которому и оптимальный план, и все локально оптимальные планы находятся среди решений систем

(7)

если они обыкновенные и

(8)

если не является обыкновенным.

Каждая из систем (7) и (8) представляет собой систему уравнений относительно неизвестных , то есть задача оптимизации сводится к алгебраической задаче.

Определение. Задачу (1) будем называть нормальной, если оптимальный план у неё обыкновенный.

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

Определение. Решение системы (7) будем называть условно-стационарной точкой задачи (1).

Для нормальных задач принцип Лагранжа можно переформулировать:

Если – локально-оптимальный план, то его нужно искать среди условно-стационарных точек задачи (1).

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