Начальные сведения о численных методах оптимизации

Задача квадратичного программирования

Задачей квадратичного программирования называются задачи оптимизации с квадратичной целевой функцией и линейными ограничениями.

Имеет следующий вид:

(1.30)

Векторно-матричные формы записи задачи квадратичного программирования:

1)

2)

Множество X задаваемых ограничений является выпуклым.

Если матрица В является симметричной и неотрицательно определенной, то f(x) является выпуклой функцией на множестве X, а следовательно X – выпуклое и задача квадратичного программирования является выпуклой задачей оптимизации.

Составляем функцию Лагранжа и условия Куна-Таккера:

и, применяя условия Куна-Таккера,

(1.31)

(1.32)

(1.33)

(1.34)

(1.35)

(1.36)

(1.31)-(1.36) - условия дополняющей нежесткости.

Решить эту задачу практически невозможно.

Для решения в задачи (1.31)-(1.35) вводим дополнительные переменные.

В (1.31) введем дополнительные переменные

В (1.34) введем дополнительные переменные

Если

Если

Заменим условия дополняющей нежесткости:

Преобразуем условия Куна-Таккера

(1.37)

(1.38)

(1.39)

(1.40)

(1.41)

(1.42)

(1.37)-(1.40) – это система из (m+n) линейных уравнений, а неизвестных 2(m+n).

Таким образом, исходная задача квадратичного программирования эквивалентна задачи нахождения допустимого, то есть удовлетворяющего требованиям неотрицательности (1.38), 91.41) базисного решения системы линейных уравнений (1.37), (1.40), удовлетворяющего также условиям дополняющей нежесткости (1.39), (1.42).

Поскольку задача линейного программирования является выпуклой, то решение системы является оптимальным и единственным (если существует). Для нахождения ДБР системы (1.37), (1.40) используем метод искусственных переменных.

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

- число искусственных переменных

Далее составляется вспомогательная задача минимизации целевой функции, только условия дополняющей нежесткости в явном виде не входят.

Для решения вспомогательной задачи используется симплекс-метод, в котором учитываются условия дополняющей нежесткости (1.39), (1.42).

Замечание: Если одна из связанных перемененных базисная и не равна нулю, то другая в базис не может быть введена.

Выполнение условий (1.39), (1.42) означает, что и ,и не могут быть положительными одновременно. То есть переменную нельзя сделать базисной, если является базисной и принимает положительное значение. Тоже и для и .

Рассмотрим 2 ситуации:

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

ОДБРвсп=ДБРслау=Ркп

2) minF(z)>0. Среди базисных остались искусственные переменные, поэтому система линейных уравнений решения не имеет, а следовательно задача квадратичного программирования решения не имеет.

– точное решение задачи

– решение не точное, а оценка точки минимума (максимума).

Перейдем от точных аналитических к численным методам.

В процессе поиска вычисляются значения ,, их производные и находится оценка .

Алгоритмы, использующие только информацию о значениях функции называются алгоритмами нулевого порядка. Алгоритмы, использующие только информацию о первых производных называются алгоритмами первого порядка и т.д.

Большинство численных методов являются итерационными (пошаговыми). То есть задается начальная точка , потом определяются последующие точки, используя информацию о предыдущих точках, таким образом, чтобы последовательность сходилась к . Эти методы называются активными (последовательными).

То есть определяем:

если известно

Наряду существуют пассивные методы, в которых все точки от до определяются заранее, до начала вычислений. Число таких точек конечно.