Метод областей доверия в математической оптимизации
Trust region
Метод доверительных областей в математической оптимизации: поиск минимума функции с помощью модели, расширяя/сужая область доверия в зависимости от точности.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В математической оптимизации доверительная область – это подмножество области определения целевой функции, которая аппроксимируется с помощью модельной функции (часто квадратичной). Если в доверительной области найдена адекватная модель целевой функции, то область расширяется; в противном случае, если аппроксимация неточна, то область сужается. Качество аппроксимации оценивается путем сравнения отношения ожидаемого улучшения, полученного из модельной аппроксимации, к фактическому улучшению, наблюдаемому в целевой функции. Простое пороговое значение этого отношения используется в качестве критерия для расширения и сужения – модельной функции «доверяют» только в той области, где она обеспечивает разумную аппроксимацию. Методы доверительных областей в некотором смысле двойственны методам поиска вдоль прямой: методы доверительных областей сначала выбирают размер шага (размер доверительной области), а затем направление шага, в то время как методы поиска вдоль прямой сначала выбирают направление шага, а затем размер шага. Общая идея, лежащая в основе методов доверительных областей, известна под многими названиями; по-видимому, термин впервые был использован Соренсеном (1982). Популярный учебник Флетчера (1980) называет эти алгоритмы методами с ограниченным шагом. Кроме того, в ранней основополагающей работе по этому методу Голдфельд, Куандт и Троттер (1966) называют его квадратичным подъемом по склону.
In mathematical optimization, a trust region is the subset of the region of the objective function that is approximated using a model function (often a quadratic). If an adequate model of the objective function is found within the trust region, then the region is expanded; conversely, if the approximation is poor, then the region is contracted. The fit is evaluated by comparing the ratio of expected improvement from the model approximation with the actual improvement observed in the objective function. Simple thresholding of the ratio is used as the criterion for expansion and contraction—a model function is "trusted" only in the region where it provides a reasonable approximation. Trust region methods are in some sense dual to line search methods: trust region methods first choose a step size (the size of the trust region) and then a step direction, while line search methods first choose a step direction and then a step size. The general idea behind trust region methods is known by many names; the earliest use of the term seems to be by Sorensen (1982). A popular textbook by Fletcher (1980) calls these algorithms restricted step methods. Additionally, in an early foundational work on the method, Goldfeld, Quandt, and Trotter (1966) refer to it as quadratic hill climbing.
Пример
Концептуально, в алгоритме Левенберга — Марквардта целевая функция итеративно аппроксимируется квадратичной поверхностью, после чего оценка обновляется с использованием линейного решателя. Это само по себе может не сходиться корректно, если начальное приближение слишком далеко от оптимума. По этой причине алгоритм ограничивает каждый шаг, предотвращая слишком большое изменение. Он определяет "слишком большое изменение" следующим образом: вместо решения уравнения для , он решает уравнение для , где — диагональная матрица с диагональю, совпадающей с диагональю A, а λ — параметр, контролирующий размер доверительной области. Геометрически это добавляет параболоид с центром в к квадратичной форме, что приводит к уменьшению шага. Суть в том, чтобы изменять размер доверительной области (λ). На каждой итерации затухающее квадратичное приближение предсказывает определенное уменьшение функции стоимости, , которое, как ожидается, будет меньше истинного уменьшения. Зная , мы можем оценить, рассматривая отношение . По этому отношению можно скорректировать размер доверительной области. В общем случае ожидается, что будет немного меньше, чем , и, следовательно, отношение будет находиться в пределах, например, от 0,25 до 0,5. Если отношение больше 0,5, значит, шаг затухает слишком сильно, поэтому доверительную область следует расширить (уменьшить λ) и повторить итерацию. Если отношение меньше 0,25, значит, истинная функция слишком сильно отклоняется от приближения доверительной области, поэтому доверительную область следует сузить (увеличить λ) и попробовать снова.
Conceptually, in the Levenberg–Marquardt algorithm, the objective function is iteratively approximated by a quadratic surface, then using a linear solver, the estimate is updated. This alone may not converge nicely if the initial guess is too far from the optimum. For this reason, the algorithm instead restricts each step, preventing it from stepping "too far". It operationalizes "too far" as follows. Rather than solving for , it solves , where is the diagonal matrix with the same diagonal as A, and λ is a parameter that controls the trust region size. Geometrically, this adds a paraboloid centered at to the quadratic form, resulting in a smaller step. The trick is to change the trust region size (λ). At each iteration, the damped quadratic fit predicts a certain reduction in the cost function, , which we would expect to be a smaller reduction than the true reduction. Given , we can evaluate
By looking at the ratio , we can adjust the trust region size. In general, we expect to be a bit smaller than , and so the ratio would be between, say, 0.25 and 0.5. If the ratio is more than 0.5, then we are damping the step too much, so expand the trust region (decrease λ) and iterate. If the ratio is smaller than 0.25, then the true function is diverging "too much" from the trust region approximation, so shrink the trust region (increase λ) and try again.