Лабораторная работа: Методы оптимизации функций многих переменных

≥0. (12′)

Условие (13) максимума функции Лагранжа по λ эквивалентно выполнению в точке (х*, λ*) неравенства

≤0. (13′)

Утверждение 2. х* - оптимальное решение задачи (3) в том и только в том случае, когда существует такой вектор λ* ≥0, что (х* , λ*) - седловая точка функции Лагранжа L (x ,λ).

1.3 Решение задач квадратичного программирования методом седловой точки

Рассмотрим задачу квадратичного программирования, т.е.

f (x ) = (С x,x ) + (d,x ) min, (15), g (x ) =Ax ≤ b ,

где С - матрица размера n*n ; d, х - векторы-столбцы n *1; А - матрица размера m*n ; b - вектор-столбец m *1. Для задачи квадратичного программирования критерий существования седловой точки приобретает вид задачи решения СЛАУ. Действительно, функция Лагранжа в этом случае запишется в виде

L = d_k x_k +c_kj x_k x_j + λ_i (a_ij x_j - b_i ), (16)

где c_kj - элементы матрицы С ; d_k - элементы вектора d ; b_i - элементы вектора свободных членов b ; a_ij - элементы матрицы А ; λ_i - коэффициенты Лагранжа. Необходимые и достаточные условия оптимальности решения х* принимают вид

v_j d_j +2c_kj x_k +λ _i a_ij , v_j ≥0, (j =1,…,n ), (17)

y_i a_ij x_j -b_{i , -} y_i ≤0, (i =1,...,m ), (18)

x_j v_j =0, x_j ≥0, (j =1,...,n ), (19)

λ_i (-y_i ) =0, λ_i ≥0. (20)

Равенства (17), (18) образуют систему n+ m линейных уравнений с 2 (n+ m ) неизвестными x_1,…, x_n , v₁ ,…, v_n , λ₁ ,…, λ_m , y_1,…, y_m . Решения этой системы, при которых выполняются равенства (19), (20), дают координаты седловой точки (х*, λ* ). Соответственно n координат х* дают оптимальное решение задачи (15).

2. Порядок выполнения лабораторной работы

Построить допустимую область задачи и линии уровня.

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

Для каждой точки указать активные и пассивные ограничения. Проверить выполнение достаточных условий экстремума в найденных стационарных точках. Найти глобальный минимум функции. Используя критерий (утверждение 1), пров?