Математика: оптимизация с ограничениями-равенствами, ограничениями-неравенствами, смешанными ограничениями и ограничениями в формате Куна-Такера
При оптимизации (целевой) функции с несколькими переменными удобно рассмотреть 5 ситуаций. (Окаймлённая) матрица Гесса всегда будет симметричной по теореме Юнга.
- Ограничения отсутствуют. Шаг 1: решить условия первого порядка, найти подозрительные точки. Шаг 2: проверить найденные точки с помощью условий второго порядка (матрица Гесса). Максимум достигается в подозрительной точке, если знаки миноров чередуются начиная с отрицательного (первый, третий и прочие нечётные миноры отрицательны, а чётные миноры положительны). Минимум достигается в подозрительной точке, если все миноры положительны. Если есть строгие нарушения знаков миноров (меньше нуля вместо больше нуля и наоборот), это седловая точка. Если таких строгих нарушений нет, но есть нулевые миноры, то ничего определённого сказать нельзя и требуется дополнительный анализ, например, графический. Пример решённой задачи.
- Есть ограничения в виде равенств. Пример: x+y = 10. Шаг 1: проверить NDCQ. Шаг 2: составить Лагранжиан. Шаг 3: решить условия первого порядка, найти подозрительные точки. Шаг 4: проверить найденные точки с помощью условий второго порядка (окаймлённая матрица Гесса). Смотреть только n-k самых больших главных миноров (начиная с меньшего). Здесь n это число инструментальных переменных, k число ограничений. Если k является чётным, то правило такое же, как в случае 1 - максимум достигается, если знаки миноров чередуются начиная с отрицательного (первый, третий и прочие нечётные миноры отрицательны, а чётные миноры положительны). И так же минимум достигается, если все миноры положительны. Если k является нечётным, то наоборот по сравнению со случаем 1: максимум достигается, если знаки миноров чередуются начиная с положительного (первый, третий и прочие нечётные миноры положительны, а чётные миноры отрицательны). И с минимумом наоборот по сравнению со случаем 1: он достигается, если все миноры отрицательны. Пример решённой задачи.
- Есть ограничения в виде неравенств, при этом среди них нет ограничений на неотрицательность инструментальных переменных в формате Куна-Такера. Пример: x+y ≤ 10. Шаг 1: проверить NDCQ. Шаг 2: перевернуть знаки ограничений на "≤", если в задаче надо найти максимум. Перевернуть знаки ограничений на "≥", если в задаче надо найти минимум. Шаг 3: составить Лагранжиан. Шаг 4: решить условия первого порядка. Условия второго порядка не решать. Пример решённой задачи.
- Есть одновременные ограничения в виде неравенств и равенств, т.е. смешанные ограничения. Пример: x+y ≤ 10 и 4xy = 7. Пример решённой задачи.
- Есть ограничения в формате Куна-Такера. Пример: x+y ≤ 10, x ≤ 0, y ≤ 0. Пример решённой задачи.
