Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 512, № 1, стр. 78-80

Рассматривается задача

где $\Pi = \{ x \in {{\mathbb{R}}^{n}}\,{\text{|}}\,{{a}^{i}} \leqslant {{x}^{i}} \leqslant {{b}^{i}},i = 1, \ldots ,m\} $. При этом считаем, что в точке минимума $x{\kern 1pt} * = \mathop {\arg \min }\limits_{x \in \Pi } \varphi (x)$, $\varphi (x{\kern 1pt} *) = 0$ и ${{a}^{i}} > 0$, $i = 1, \ldots ,m$.

Данные предположения не являются принципиальными, но облегчают описание предложенного подхода решения таких задач. Пусть $\{ x_{j}^{*}\} $, $j \in P$, множество локальных минимумов для задачи (1), $P = \{ 1, \ldots ,p\} $, и глобальный минимум достигается при $j = {{j}_{0}}$ в точке $x_{{{{j}_{0}}}}^{*} = x{\kern 1pt} *$. В общем случае данная задача является многоэкстремальной. Один из способов ее решения – это классический градиентный метод [1], схема которого имеет следующую структуру

и при определенных условиях на выбор шага ${{\alpha }_{k}}$ (например, [1, 2]), последовательность x_k сходится к некоторому локальному минимуму $x_{j}^{*}({{x}_{0}})$ (см. [1]). Проблема состоит в том, что локальных минимумов может быть много $(j \in P)$ и, в зависимости от начальной точки ${{x}_{0}}$, мы получим тот или иной локальный экстремум $x_{j}^{*}({{x}_{0}}) \ne x{\kern 1pt} *$. Учитывая свойства градиентного метода, естественно предположить, что

– итерационная последовательность (2), определенная начальной точкой ${{x}_{0}}$, будет сходиться к ближайшему локальному минимуму, т.е.

Предположение (4) весьма естественно, и мы примем его в качестве отправного.

Отметим, что функция $\varphi (x)$ определена только в прямоугольнике $\Pi $, но мы можем ее доопределить гладким образом за границы прямоугольника (параллелепипеда) $\Pi $ так, что

где ${\text{P}}{{{\text{r}}}_{\Pi }}( \cdot )$ – оператор проектирования на Π, т.е. $\varphi (x)$ будет квадратично возрастать вне прямоугольника Π и заведомо вне Π не будет локальных экстремумов у доопределенной функции $\varphi (x)$: и значения $\varphi (x)$ при будут больше, чем внутри прямоугольника Π.

Новизна метода состоит в том, что делается замена координат

и минимизируется функция $\bar {\varphi }(y) = \varphi (x(y))$ во всем пространстве ${{\mathbb{R}}^{n}}$, где $x(y)$ – решение системы (6). Здесь $\varepsilon > 0$ достаточно малое число, при котором фиктивные (локальные) минимумы $y_{j}^{*}\, = \,\frac{{x_{j}^{*}}}{{\varphi (x_{j}^{*})\, + \,\varepsilon }}$, $j \in P{{\backslash }}\{ {{j}_{0}}\} $, функции $\bar {\varphi }(y)$ остаются в ограниченном параллелепипеде где ${{\bar {a}}^{i}} = \frac{{{{a}^{i}}}}{{M + \varepsilon }}$, ${{\bar {b}}^{i}} = \frac{{{{b}^{i}}}}{{m + \varepsilon }}$, $M = \mathop {\max }\limits_{j \in P\backslash \{ {{j}_{0}}\} } \varphi (x_{j}^{*})$, m = = $\mathop {\min }\limits_{j \in P\backslash \{ {{j}_{0}}\} } \varphi (x_{j}^{*})$, а глобальный минимум $y_{j}^{*}$ = y* = = $\frac{{x{\kern 1pt} *}}{{\varphi (x{\kern 1pt} *) + \varepsilon }} = \frac{{x{\kern 1pt} *}}{\varepsilon }$ отбрасывается от области $\bar {\Pi }$, в которой локализуются фиктивные экстремумы $y_{j}^{*}$, $j \in P{{\backslash }}\{ {{j}_{0}}\} $, т.е. где N достаточно велико и $N \to \infty $ при $\varepsilon \to 0$. Причем в новых переменных функция $\bar {\varphi }(y)$ достигает минимума в точке $y{\text{*}} = \frac{{x{\text{*}}}}{\varepsilon }$, т.е. $\bar {\varphi }{\kern 1pt} '(y{\kern 1pt} *) = 0$. В дальнейшем, при использовании наших построений, потребуется решать одномерное уравнение (см. ниже (8)) на каждом шаге итерационного процесса, что является платой за возможность получения (вычисления) глобального минимума в пространстве ${{\mathbb{R}}^{n}}$ и, на наш взгляд, является несравненно более элементарной процедурой при решении $n$-мерной задачи. Поэтому мы будем использовать задачу (8) как вспомогательную и несравнимо более простую, не требующую особых вычислительных затрат. При этом для всех фиктивных экстремумов $y_{j}^{*}$, $j \in P{{\backslash }}\{ {{j}_{0}}\} $, будет выполнено неравенство ${\text{||}}y_{j}^{*}{\text{||}} \leqslant C$, где константа C не зависит от N, а ${\text{||}}y{\kern 1pt} *{\text{||}} = {\text{||}}y_{{{{j}_{0}}}}^{*}{\text{||}} \geqslant N = \frac{1}{\varepsilon }$ при $N$ достаточно больших. Если взять начальную точку ${{y}_{0}} = (2N, \ldots ,2N{{)}^{ \top }}$, то будет выполнено соотношение (4), так как при $N$ достаточно больших. Здесь мы учитываем, что $y{\kern 1pt} * > 0$, ибо $x{\kern 1pt} * > 0$. Таким образом, градиентный метод ${{y}_{0}} = (2N, \ldots ,2N{{)}^{ \top }}$ с выбором шага по формуле (3), согласно предположению (4), будет сходиться к точке глобального минимума y* функции $\bar {\varphi }(y)$ = = φ(x(y)), а значит к $x{\kern 1pt} *$.

При этом $\bar {\varphi }'(y) = \varphi _{x}^{'}(x(y)) \cdot x{\kern 1pt} '(y)$, где $x(y)$ берем как решение уравнения (6) и по теореме о неявной функции

Очевидно, что для существования $\bar {\varphi }{\kern 1pt} '(y)$ нужно требовать невырожденность матрицы $x{\kern 1pt} '(y)$ во всех точках $y \in {{\mathbb{R}}^{n}}$.

Все вышеизложенное можно сформулировать в виде следующего результата:

Теоpема 1. Пусть $\varphi \in {{C}^{2}}({{\mathbb{R}}^{n}})$, ${\text{||}}\varphi {\kern 1pt} '{\kern 1pt} '(x){\text{||}} \leqslant C$, $x\, \in \,{{\mathbb{R}}^{n}}$, выполняется предположение (4) и матрица $x{\kern 1pt} '(y)$ невырождена для всех $y \in {{\mathbb{R}}^{n}}$.

Тогда существует достаточно большое ${{N}_{0}} > 0$, такое, что при $N \geqslant {{N}_{0}}$ и ${{y}_{0}} = (2N, \ldots ,2N{{)}^{ \top }}$ выполняется неравенство

и метод (7) сходится к $y{\kern 1pt} *$ при $k \to \infty $, где ${{\alpha }_{k}}$ выбирается из условия (3). (Или ${{x}_{k}} \to x{\kern 1pt} *$ при $k \to \infty $.)

Доказательство. Достаточно показать, что вне области $\bar {\Pi }$ не будет локальных экстремумов, кроме $y{\kern 1pt} *$, т.е. $\bar {\varphi }{\kern 1pt} '(y) \ne 0$, $y \in {{\mathbb{R}}^{n}}{{\backslash }}\bar {\Pi }$.

Действительно, если для некоторого $\tilde {y} \in {{\mathbb{R}}^{n}}{{\backslash }}\bar {\Pi }$ будет $\bar {\varphi }{\kern 1pt} '(\tilde {y}) = 0$, то либо $\varphi _{x}^{'}(x(\tilde {y})) = 0$, либо матрица $x{\kern 1pt} '(\tilde {y})$ вырождена. Второе очевидно невозможно в силу условий теоремы. Если же $\varphi _{x}^{'}(x(\tilde {y})) = 0$, то либо $\tilde {y} \in \bar {\Pi }$, что и требовалось, либо соответствующий . Но в последнем случае градиент $\varphi _{x}^{'}(x(\tilde {y}))$ не может равняться нулю вне области $\Pi $, согласно (5). Теорема доказана. ◻

Подчеркнем тот факт, что по формуле

$x({{y}_{k}})$ ищется как решение одномерного уравнения относительно неизвестного $x$: здесь $x = t \cdot {{y}_{k}}$, $t \in R$, что является более простой вычислительной задачей, по сравнению с решением системы $n$-мерных уравнений. Тогда последовательность $\{ {{y}_{k}}\} $ сходится к $y{\kern 1pt} *$ при $k \to \infty $, $x{\kern 1pt} * = \varepsilon \cdot y{\kern 1pt} *$.

Другой подход к решению задачи глобальной оптимизации можно найти, например, в [3].

ИСТОЧНИК ФИНАНСИРОВАНИЯРабота выполнена при финансовой поддержке Российского научного фонда (проект №~21-71-30005).