10. Задача оптимизации#
В этом разделе изложены некоторые методы решения задачи безусловной оптимизации (unconstrained optimization), т.е. нахождение \(\mathbf{x}^*\), в котором достигается минимум функции \(f: \real^n \to \real\). Математически мы будем формулировать это так
Также существует задача условной оптимизации, когда поиск минимума (10.1) производится не по всему \(\real^n\), а по его подмножеству \(D\), называемым допустимым множеством (feasible region). Обычно, допустимое множество задаётся системой равенст и неравенст на компоненты аргумента \(\mathbf{x}\).
Методы оптимизации бывают детерминированными и стохастическими. В первом классе методов последовательность приближений решения однозначно определяется по начальным данным. Второй класс использует случайные числа. Мы рассмотрим детерминированные методы.
Детерминированный алгоритм решения (10.1) начинает с некоторого начального приближения решения \(\mathbf{x}_0\) и генерирует последовательность приближений \(\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots\), пока не достигнет требуемой точности. Существует две основные стратегии перехода от \(\mathbf{x}_k\) к \(\mathbf{x}_{k+1}\).
Первая стратегия использует линейный поиск. В этом варианте в точке \(\mathbf{x}_k\) определяется направление \(\mathbf{d}_k\), в котором функция убывает. Затем производится линейный поиск для скалярной функции от \(\alpha\)
а после нахождения \(\alpha^*\) новым приближением выбирают \(\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha^* \mathbf{d}_k\). Идеальный линейный поиск решает данную задачу точно, тем самым делая лучший шаг в сторону минимума \(f(\mathbf{x})\). Однако, это трудоёмкая задача и на практике оказывается, что лучше найти неточное приближение задачи (10.2).
Вторая стратегия использует доверительную область (trust region). В этой стратегии по информации о функции \(f(\mathbf{x}_k)\) строится её локальная модель \(m_k(\mathbf{x})\), например, квадратичная. Поскольку модель локальна, выбирается доверительная область \(\text{TR}\), где поведение \(m_k\) хорошо воспроизводит поведение \(f\). Обычно, эта область является шаром или эллипсом. Затем решается задача
и выбирают новое приближение \(\mathbf{x}_k + \delta\mathbf{x}^*\).
Эти две стратегии глобально отличаются порядком выбора направления и размера шага. В методах с линейным поиском сначала выбирается направление, а затем размер шага. В методах с доверительной областью – наоборот.
Мы рассмотрим только методы с линейным поиском.