Задача на безусловный минимум.

Теорема Куна-Таккера.

Рассмотрим задачу (1), в которой – вектор-функция, ф-ции – выпуклые ф-ции; – выпуклое мн-ство простой структуры, т.е. подмн-тво, кот. задается с помощью простейших ограничений на одну переменную (). Задача наз. основной задачей выпуклого программирования.

Опр. Мн-тво планов основной задачи выпуклого программирования регулярно, если существует вектор (2)

Усл.(2) наз. условием Слейтера. Геометрич.(2) означает,что у зад.(1) существует такой план , кот. явл. внутренней точкой по основным ограничениям.

Теорема 2. (Куна-Таккера) Для того, чтобы был оптимальный план основной задачи выпуклого программирования, для которой выполняется условие регулярности (2), необходимо и достаточно, чтобы существовал такой вектор такой, что пара является седловой точкой функции Лагранжа и при этом выполн. условие дополняющей не жесткости: .

Доказательство. Необходимость. Пусть – оптимал. план (1) и выполняется . Тогда по нему и параметрам зад.(1) построим три подмножества:

. Ясно, что мн-тво явл. границей мн-тва , т.е.

1. Доказываем, что множества и выпуклые.

2. Докажем, что множества и не пересекаются.

3. Докажем, что вектор .

4. Докажем, что в , а так как , то .

5. Докажем, что на выполняется условие .

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

Ч.т.д

Задача на безусловный минимум.

Задача имеет вид: (1), то есть .

Теорема 1. Если – локально-оптимальный план, то (2)

Теорема 2 (Необходимое условие оптимальности второго порядка). Если – локально-оптимальный план, то (3)

Опр. Точка наз. стационарной точкой функции , если она является решением системы (4)

Теор.3 (Достат. условие оптимальности). Если – стационарная точка ф-ции и , (5) то – локально-оптимальный план (1) (по крайней мере).

Замечание. При проверке условий (3) и (5) применяются критерии Сильвестра неотрицательности и положительности квадратных матриц.

Схема исследования задач типа (1)

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

2) Составляем систему (4) и находим стационарные точки функции (все). Только среди них может находиться оптимальный план и все локально-оптимальные планы. Пусть – все стационарные точки функции .

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

а) . Тогда, согласно теореме 3 – локально-оптимальный план.

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

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

4) Делаем вывод: среди точек, оказавшихся либо локально-оптимал. планами, либо подозрительных на решение, находим лучшую, т.е. подставляем точки в целевую ф-цию и лучшей будет точка с наименьшим значением ф-ции. Если док-но существование реш-я и построены все стационарные точки, то лучшая точка будет оптимал. планом. В общем случае, из-за сложности функции и невозможности найти все решения системы (4) исследование нельзя провести полностью и лучшая точка остается подозрительной на решение задачи.

 

3часть______________________________________________________

Метод равномерного поиска

Выбираем некоторое и разбиваем исходный отрезок [ ] на частей точками …, где и поочерёдно начиная с вычисляем значение функции . В силу унимодальности будут выполняться неравенства . Тогда ясно, что

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

Замечание. Можно сразу подобрать таким образом, чтобы выполнялось , но это не рационально, так как количество точек перебора будет очень большим. Лучше на 1-ом этапе исходный отрезок разбить на количество частей , потом количество точек увеличить.

 

Теорема Куна-Таккера.

Рассмотрим задачу (1), в которой – вектор-функция, ф-ции – выпуклые ф-ции; – выпуклое мн-ство простой структуры, т.е. подмн-тво, кот. задается с помощью простейших ограничений на одну переменную (). Задача наз. основной задачей выпуклого программирования.

Опр. Мн-тво планов основной задачи выпуклого программирования регулярно, если существует вектор (2)

Усл.(2) наз. условием Слейтера. Геометрич.(2) означает,что у зад.(1) существует такой план , кот. явл. внутренней точкой по основным ограничениям.

Теорема 2. (Куна-Таккера) Для того, чтобы был оптимальный план основной задачи выпуклого программирования, для которой выполняется условие регулярности (2), необходимо и достаточно, чтобы существовал такой вектор такой, что пара является седловой точкой функции Лагранжа и при этом выполн. условие дополняющей не жесткости: .

Доказательство. Необходимость. Пусть – оптимал. план (1) и выполняется . Тогда по нему и параметрам зад.(1) построим три подмножества:

. Ясно, что мн-тво явл. границей мн-тва , т.е.

1. Доказываем, что множества и выпуклые.

2. Докажем, что множества и не пересекаются.

3. Докажем, что вектор .

4. Докажем, что в , а так как , то .

5. Докажем, что на выполняется условие .

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

Ч.т.д

Задача на безусловный минимум.

Задача имеет вид: (1), то есть .

Теорема 1. Если – локально-оптимальный план, то (2)

Теорема 2 (Необходимое условие оптимальности второго порядка). Если – локально-оптимальный план, то (3)

Опр. Точка наз. стационарной точкой функции , если она является решением системы (4)

Теор.3 (Достат. условие оптимальности). Если – стационарная точка ф-ции и , (5) то – локально-оптимальный план (1) (по крайней мере).

Замечание. При проверке условий (3) и (5) применяются критерии Сильвестра неотрицательности и положительности квадратных матриц.