Задачи квадратичной оптимизации - 4 - Методы квадратичной оптимизации

Это 17-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.

После определения типов квадратичных форм, которые можно оптимизировать, в этой статье обсуждаются методы оптимизации квадратичных форм.

текущий номер

Решение уравнений $\bf{Ax}=\bf{b}$
в $\bf{A}$ является положительно полуопределенной матрицей
$\bf{A}$ Ранг и его расширенная матрица $\bf{Ab}$ ранг равный

Оптимизация

Алгебра

Исключение по Гауссу

Математически исключение Гаусса (или перевод: исключение Гаусса) — это алгоритм линейного алгебраического программирования, который можно использовать для решения систем линейных уравнений. Однако его алгоритм очень сложен, и он не часто используется в дополнение к методам вычитания и вычитания, чтобы найти ранг матрицы и найти обратную обратимую квадратную матрицу.

существует $\bf{A}$ Когда определитель $x_n$ Затем постепенно вводите и вычисляйте другие неизвестные, чтобы получить результат вычисления.

\begin{equation} \begin{split} {a_{11}}{x_1} + {a_{12}}{x_2} + \cdots {a_{1n}}{x_n} = {b_1}\\\\ {a_{22}}{x_2} + \cdots {a_{2n}}{x_n} = {b_2}\\\\ \vdots \\\\ {a_{nn}}{x_n} = {b_n} \end{split} \end{equation}

Другие алгебраические методы усовершенствованы на основе исключения Гаусса.

Исключение главного элемента Гаусса

Чтобы решить проблему недостаточной точности, вызванную тем, что главный элемент равен 0 или абсолютное значение главного элемента слишком мало, предлагается исключить главный элемент.
Основная идея состоит в том, чтобы выбрать строку с наибольшим абсолютным значением коэффициента в качестве эталона для исключения, что может эффективно решить вышеуказанные проблемы.

инверсия матрицы

для матрицы $\bf{A}$ В случае обратимости его можно получить непосредственно $\bf{A}$ Обратная матрица , тогда:

{\bf{x}} = {\bf{A^{-1}}}{\bf{b}}

Итерационный метод

Временная сложность алгебраического метода равна $O(n^3)$ порядок величины трудно принять на практике;

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

Метод наискорейшего спуска/градиентный метод

Продолжайте движение в направлении, противоположном текущему градиенту, пока градиент направления не станет равным 0, пересчитайте градиент текущего положения и начните заново.
Повторяйте процесс, пока точность не будет удовлетворительной.

Метод сопряженных градиентов

Сопряженный градиент находится междукрутой спускиНьютонМетод между методами, который использует только преимущества первого порядка.Производнаяинформации, но преодолевает недостаток медленной сходимости метода наискорейшего спуска и избегаетНьютонметод требует хранения и вычисления ГессематрицаИ недостатком обратного метода сопряженных градиентов является не только решение крупномасштабныхсистема линейных уравненийОдин из самых полезных методов и один из самых эффективных алгоритмов для решения больших нелинейных оптимизаций.

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

Затем мы сосредоточимся на итеративном методе