АББ

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

Теория

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

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

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

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

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

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