ΑΒΒ - αΒΒ - Wikipedia

"Alpha BB" перенаправляется сюда. Для использования в других целях см. ABB (значения).

αΒΒ второго порядка детерминированная глобальная оптимизация алгоритм поиска оптимумов общих дважды непрерывно дифференцируемых функций.^[1][2] Алгоритм основан на создании расслабление для нелинейных функций общего вида путем наложения их на квадратичный коэффициент достаточной величины, называемый α, такой, чтобы полученная суперпозиция была достаточной для преодоления наихудшего сценария невыпуклости исходной функции. Поскольку у квадратичной есть диагональ Матрица Гессе, эта суперпозиция по существу добавляет число ко всем диагональным элементам исходного гессиана, так что результирующий гессиан равен положительно-полуопределенный. Таким образом, результирующая релаксация выпуклая функция.

Теория

Пусть функция ${\displaystyle {f({\boldsymbol {x}})\in C^{2}}}$ - функция общей нелинейной невыпуклой структуры, заданная в конечном ящике ${\displaystyle X=\{{\boldsymbol {x}}\in \mathbb {R} ^{n}:{\boldsymbol {x}}^{L}\leq {\boldsymbol {x}}\leq {\boldsymbol {x}}^{U}\}}$.Затем выпуклое занижение (расслабление) ${\displaystyle L({\boldsymbol {x}})}$ этой функции можно построить над ${\displaystyle X}$ путем наложения суммы одномерных квадратичных квадратов, каждая из которых имеет достаточную величину, чтобы преодолеть невыпуклость ${\displaystyle {f({\boldsymbol {x}})}}$ везде в ${\displaystyle X}$, следующее:

${\displaystyle L({\boldsymbol {x}})=f({\boldsymbol {x}})+\sum _{i=1}^{i=n}\alpha _{i}(x_{i}^{L}-x_{i})(x_{i}^{U}-x_{i})}$

${\displaystyle L({\boldsymbol {x}})}$ называется ${\displaystyle \alpha {\text{BB}}}$ занижатель общих функциональных форм. Я упал ${\displaystyle \alpha _{i}}$ достаточно велики, новая функция ${\displaystyle L({\boldsymbol {x}})}$ выпукла всюду в ${\displaystyle X}$. Таким образом, локальная минимизация ${\displaystyle L({\boldsymbol {x}})}$ дает строгую нижнюю оценку значения ${\displaystyle {f({\boldsymbol {x}})}}$ в этой области.

Расчет ${\displaystyle {\boldsymbol {\alpha }}}$

Существует множество методов расчета значений ${\displaystyle {\boldsymbol {\alpha }}}$ вектор. Доказано, что при ${\displaystyle \alpha _{i}=\max\{0,-{\frac {1}{2}}\lambda _{i}^{\min }\}}$, куда ${\displaystyle \lambda _{i}^{\min }}$ - допустимая нижняя граница ${\displaystyle i}$-е собственное значение матрицы Гессе ${\displaystyle {f({\boldsymbol {x}})}}$, то ${\displaystyle L({\boldsymbol {x}})}$ недооценка гарантированно будет выпуклой.

Один из самых популярных методов получения этих допустимых оценок собственных значений - использование масштабированной теоремы Гершгорина. Позволять ${\displaystyle H(X)}$ - интервальная матрица Гессе ${\displaystyle {f(X)}}$ за интервал ${\displaystyle X}$. Потом, ${\displaystyle \forall d_{i}>0}$ допустимая нижняя граница собственного значения ${\displaystyle \lambda _{i}}$ может быть получено из ${\displaystyle i}$-й ряд ${\displaystyle H(X)}$ следующее:

${\displaystyle \lambda _{i}^{\min }={\underline {h_{ii}}}-\sum _{i\neq j}(\max(|{\underline {h_{ij}}}|,|{\overline {h_{ij}}}|{\frac {d_{j}}{d_{i}}})}$

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

1. "Подход к глобальной оптимизации микрокластеров Леннарда-Джонса." Журнал химической физики, 1992, 97(10), 7667-7677
2. "αBB: метод глобальной оптимизации для общих невыпуклых задач с ограничениями." Журнал глобальной оптимизации, 1995, 7(4), 337-363