Выбор алгоритма

Алгоритмы fmincon

fmincon имеет пять опций алгоритма:

  • 'interior-point' (значение по умолчанию)

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Используйте 'interior-point' алгоритм сначала.

    Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

  • Чтобы запустить оптимизацию снова, чтобы получить больше скорости на малых и средних проблемах, попробуйте 'sqp' затем, и 'active-set' в последний раз.

  • Используйте 'trust-region-reflective' когда применимо. Ваша проблема должна иметь: целевая функция включает градиент, только границы, или только линейные ограничения равенства (но не оба).

Смотрите потенциальную погрешность с алгоритмами внутренней точки.

Обоснование позади рекомендаций

  • 'interior-point' решает большие, разреженные проблемы, а также небольшие плотные проблемы. Алгоритм удовлетворяет границам во всех итерациях и может восстановиться с NaN или Inf результаты. Это - крупномасштабный алгоритм; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Алгоритм может использовать специальные методы для крупномасштабных проблем. Для получения дополнительной информации см. Алгоритм Внутренней точки в fmincon options.

  • 'sqp' удовлетворяет границам во всех итерациях. Алгоритм может восстановиться с NaN или Inf результаты. Это не крупномасштабный алгоритм; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы.

  • 'sqp-legacy' похоже на 'sqp', но обычно медленнее и использует больше памяти.

  • 'active-set' может сделать большие шаги, который добавляет скорость. Алгоритм является эффективным на некоторых проблемах с несглаженными ограничениями. Это не крупномасштабный алгоритм; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы.

  • 'trust-region-reflective' требует, чтобы вы предоставили градиент и позволяет только границы или линейные ограничения равенства, но не обоих. В рамках этих ограничений алгоритм решает и большие разреженные проблемы и небольшие плотные проблемы эффективно. Это - крупномасштабный алгоритм; смотрите Крупномасштабный по сравнению с Алгоритмами Средней шкалы. Алгоритм может использовать специальные методы, чтобы сохранить использование памяти, такое как функция умножения Гессиана. Для получения дополнительной информации смотрите Доверительную область Отражающий Алгоритм в fmincon options.

Для описаний алгоритмов см. Ограниченные Нелинейные Алгоритмы Оптимизации.

Алгоритмы fsolve

fsolve имеет три алгоритма:

  • 'trust-region-dogleg' (значение по умолчанию)

  • 'trust-region'

  • 'levenberg-marquardt'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Используйте 'trust-region-dogleg' алгоритм сначала.

    Для справки, если fsolve сбои, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

  • Чтобы решить уравнения снова, если вы имеете функцию умножения якобиана или хотите настроить внутренний алгоритм (см. Алгоритм Доверительной области в fsolve options), попробуйте 'trust-region'.

  • Попытайтесь синхронизировать все алгоритмы, включая 'levenberg-marquardt', найти алгоритм, который работает лучше всего над вашей проблемой.

Обоснование позади рекомендаций

  • 'trust-region-dogleg' единственный алгоритм, который специально разработан, чтобы решить нелинейные уравнения. Другие пытаются минимизировать сумму квадратов функции.

  • 'trust-region' алгоритм является эффективным на разреженных проблемах. Это может использовать специальные методы, такие как функция умножения якобиана для крупномасштабных проблем.

Для описаний алгоритмов смотрите, что уравнение Решает Алгоритмы.

Алгоритмы fminunc

fminunc имеет два алгоритма:

  • 'quasi-newton' (значение по умолчанию)

  • 'trust-region'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Если ваша целевая функция включает градиент, используйте   'Algorithm' = 'trust-region', и набор SpecifyObjectiveGradient опция к true.

  • В противном случае используйте   'Algorithm' = 'quasi-newton'.

Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

Для описаний алгоритмов см. Неограниченные Нелинейные Алгоритмы Оптимизации.

Алгоритмы наименьших квадратов

lsqlin

lsqlin имеет три алгоритма:

  • 'interior-point', значение по умолчанию

  • 'trust-region-reflective'

  • 'active-set'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Попробуйте 'interior-point' сначала.

    Совет

    Для лучшей эффективности, когда ваша входная матрица C имеет большую часть ненулевых записей, задайте C как обычная двойная матрица. Точно так же для лучшей эффективности, когда C имеет относительно немного ненулевых записей, задайте C как разреженный. Для получения дополнительной информации типа данных смотрите Разреженные матрицы. Можно также установить внутренний тип линейной алгебры при помощи 'LinearSolver' опция.

  • Если вы не имеете никаких ограничений или только связанных ограничений, и хотите более высокую точность, больше скорости, или хотите использовать функцию умножения якобиана с Линейным методом наименьших квадратов, попробуйте 'trust-region-reflective'.

  • Если у вас есть большое количество линейных ограничений и не большое количество переменных, попробуйте 'active-set'.

Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

Смотрите потенциальную погрешность с алгоритмами внутренней точки.

Для описаний алгоритмов смотрите Наименьшие квадраты (Подбор кривой Модели) Алгоритмы.

lsqcurvefit и lsqnonlin

lsqcurvefit и lsqnonlin имейте два алгоритма:

  • 'trust-region-reflective' (значение по умолчанию)

  • 'levenberg-marquardt'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Обычно попробуйте 'trust-region-reflective' сначала.

  • Если ваша проблема является недоопределенной (меньше уравнений, чем размерности), используйте 'levenberg-marquardt'.

Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

Для описаний алгоритмов смотрите Наименьшие квадраты (Подбор кривой Модели) Алгоритмы.

Алгоритмы линейного программирования

linprog имеет три алгоритма:

  • 'dual-simplex', значение по умолчанию

  • 'interior-point-legacy'

  • 'interior-point'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации

Используйте 'dual-simplex' алгоритм или 'interior-point' алгоритм сначала.

Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

Смотрите потенциальную погрешность с алгоритмами внутренней точки.

Обоснование позади рекомендаций

  • Часто, 'dual-simplex' и 'interior-point' алгоритмы быстры, и используют наименьшее количество памяти.

  • 'interior-point-legacy' алгоритм похож на 'interior-point', но 'interior-point-legacy' может быть медленнее, менее устойчивым, или использовать больше памяти.

Для описаний алгоритмов см. Линейные Алгоритмы Программирования.

Алгоритмы квадратичного программирования

quadprog имеет три алгоритма:

  • 'interior-point-convex' (значение по умолчанию)

  • 'trust-region-reflective'

  • 'active-set'

Использование optimoptions установить Algorithm опция в командной строке.

Рекомендации
  • Если у вас есть выпуклая проблема, или если вы не знаете, выпукла ли ваша проблема, используйте 'interior-point-convex'.

  • Совет

    Для лучшей эффективности, когда ваша матрица Гессиана H имеет большую часть ненулевых записей, задайте H как обычная двойная матрица. Точно так же для лучшей эффективности, когда H имеет относительно немного ненулевых записей, задайте H как разреженный. Для получения дополнительной информации типа данных смотрите Разреженные матрицы. Можно также установить внутренний тип линейной алгебры при помощи 'LinearSolver' опция.

  • Если у вас есть невыпуклая проблема только с границами, или только с линейными равенствами, используйте 'trust-region-reflective'.

  • Если у вас есть положительная полуопределенная проблема с большим количеством линейных ограничений и не большим количеством переменных, попробуйте 'active-set'.

Для справки, если минимизация перестала работать, смотрите, Когда Сбои Решателя или Когда Решатель Может Успешно выполниться.

Смотрите потенциальную погрешность с алгоритмами внутренней точки.

Для описаний алгоритмов см. Алгоритмы Квадратичного программирования.

Крупномасштабные по сравнению со среднемасштабными алгоритмами

Алгоритмом оптимизации является large scale, когда это использует линейную алгебру, которая не должна хранить, ни работать с, полные матрицы. Это может быть сделано внутренне путем хранения разреженных матриц, и при помощи линейной алгебры для разреженных матриц для расчетов, когда это возможно. Кроме того, внутренние алгоритмы или сохраняют разреженность, такую как разреженное разложение Холесского, или не генерируют матрицы, такие как метод сопряженных градиентов.

В отличие от этого методы medium-scale внутренне создают полные матрицы и используют плотную линейную алгебру. Если проблема является достаточно большой, полные матрицы поднимают существенное количество памяти, и плотная линейная алгебра может потребовать, чтобы долгое время выполнилось.

Не позволяйте имени “крупный масштаб”, вводят в заблуждение вас; можно использовать крупномасштабный алгоритм на небольшой проблеме. Кроме того, вы не должны задавать разреженные матрицы, чтобы использовать крупномасштабный алгоритм. Выберите алгоритм средней шкалы, чтобы получить доступ к дополнительной функциональности, такой как дополнительные типы ограничения, или возможно для лучшей эффективности.

Потенциальная погрешность с алгоритмами внутренней точки

Алгоритмы внутренней точки в fmincon, quadprog, lsqlin, и linprog имейте много хороших характеристик, таких как низкое использование памяти и способность решить большие задачи быстро. Однако их решения могут быть немного менее точными, чем те из других алгоритмов. Причина этой потенциальной погрешности состоит в том, что (внутренне расчетный) барьерная функция сохраняет, выполняет итерации далеко от контуров ограничения неравенства.

В наиболее практических целях обычно вполне мала эта погрешность.

Чтобы уменьшать погрешность, попытайтесь:

  • Повторно запустите решатель с меньшим StepTolerance, OptimalityTolerance, и возможно ConstraintTolerance допуски (но сохраняют допуски разумными.) Смотрите Допуски и Критерий остановки).

  • Запустите различный алгоритм, начинающий с решения внутренней точки. Это может перестать работать, потому что некоторые алгоритмы могут использовать чрезмерную память или время и все linprog и некоторые quadprog алгоритмы не принимают начальную точку.

Например, попытайтесь минимизировать функциональный x, когда ограничено ниже 0. Используя fmincon interior-point по умолчанию алгоритм:

options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off');
x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x =

   2.0000e-08

Используя fmincon sqp алгоритм:

options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x2 =

   0

Точно так же решите ту же задачу с помощью linprog interior-point-legacy алгоритм:

opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy');
x = linprog(1,[],[],[],[],0,[],1,opts)
x =

   2.0833e-13

Используя linprog dual-simplex алгоритм:

opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)
x2 =

     0

В этих случаях алгоритмы внутренней точки менее точны, но ответы вполне близко к правильному ответу.

Для просмотра документации необходимо авторизоваться на сайте