Математика: оптимизация с ограничениями-равенствами, ограничениями-неравенствами, смешанными ограничениями и ограничениями в формате Куна-Такера


При оптимизации (целевой) функции с несколькими переменными удобно рассмотреть 5 ситуаций. (Окаймлённая) матрица Гесса всегда будет симметричной по теореме Юнга.

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

К списку всех статей






Некоторые ВУЗы и программы, студентам которых была предоставлена квалифицированная помощь репетитора по математике, статистике, макро- и микроэкономике и прочим наукам с экономическим, финансовым и математическим уклоном.