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

Алгоритмы fmincon

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

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

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

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

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

    Для получения справки в случае сбоя минимизации см. Раздел «Когда решатель отказывает» или «Когда решатель мог добиться успеха».

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

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

См. Потенциальная неточность с алгоритмами Interior-Point.

Рассуждения за рекомендациями

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

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

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

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

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

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

fsolve алгоритмы

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

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

  • 'trust-region'

  • 'levenberg-marquardt'

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

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

    Для помощи, если fsolve fails, см., Когда решатель отказывает или Когда решатель мог преуспеть.

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

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

Рассуждения за рекомендациями

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

  • The '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'.

Для получения справки в случае сбоя минимизации см. Раздел «Когда решатель отказывает» или «Когда решатель мог добиться успеха».

См. Потенциальная неточность с алгоритмами Interior-Point.

Для описания алгоритмов см. Алгоритмы наименьших квадратов (Model Fitting).

lsqcurvefit и lsqnonlin

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

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

  • 'levenberg-marquardt'

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

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

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

Для получения справки в случае сбоя минимизации см. Раздел «Когда решатель отказывает» или «Когда решатель мог добиться успеха».

Для описания алгоритмов см. Алгоритмы наименьших квадратов (Model Fitting).

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

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

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

  • 'interior-point-legacy'

  • 'interior-point'

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

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

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

Для получения справки в случае сбоя минимизации см. Раздел «Когда решатель отказывает» или «Когда решатель мог добиться успеха».

См. Потенциальная неточность с алгоритмами Interior-Point.

Рассуждения за рекомендациями

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

  • The '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'.

Для получения справки в случае сбоя минимизации см. Раздел «Когда решатель отказывает» или «Когда решатель мог добиться успеха».

См. Потенциальная неточность с алгоритмами Interior-Point.

Для описания алгоритмов см. «Алгоритмы квадратичного программирования».

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

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

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

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

Потенциальная неточность с алгоритмами Interior-Point

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

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

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

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

  • Запустите другой алгоритм, начиная с решения interior-point. Это может быть неудачно, потому что некоторые алгоритмы могут использовать чрезмерную память или время, и все 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

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

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