РЕШЕНИЕ НЕМОНОТОННЫХ ВАРИАЦИОННЫХ НЕРАВЕНСТВ МЕТОДОМ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ НА ОСНОВЕ ЗАЗОРНЫХ ФУНКЦИЙ

SOLVING NON-MONOTONE VARIATIONAL INEQUALITIES

VIA GLOBAL OPTIMIZATION BASED ON GAP FUNCTIONS

Batdavaa Avirmediin

Master's student, Erdenet Institute of Mongolian University of Science and Technology,

Mongolia, Erdenet

АННОТАЦИЯ

В данной работе рассматривается задача переформулировки немонотонного вариационного неравенства в задачу глобальной оптимизации. Поскольку большинство классических методов ориентировано на монотонный случай, разработка практически применимых подходов для немонотонных задач по-прежнему остаётся актуальной проблемой. С использованием понятий зазорной функции и остаточной функции построено теоретическое обоснование сведения исходной задачи к задаче оптимизации с нулевым глобальным минимумом. При условии липшицевой непрерывности отображения F на компактном множестве D доказано, что обе функции — зазорная и остаточная — удовлетворяют условию Липшица. Показано, что при выполнении указанных условий задача (1) может быть решена стандартными методами липшицевой оптимизации, в частности методом ветвей и границ.

ABSTRACT

This paper addresses the problem of reformulating a non-monotone variational inequality as a global optimization problem. Since most classical methods are designed for the monotone case, the development of practically applicable approaches for the non-monotone setting remains a relevant challenge. Using the concepts of the gap function and the residual function, we establish a theoretical framework for reducing the original problem to an optimization problem with a zero global minimum value. Under the assumption that the mapping F is Lipschitz continuous on a compact set D, it is proved that both the gap function and the residual function satisfy the Lipschitz condition. It is further shown that, under these conditions, problem (1) can be solved by standard Lipschitz optimization methods, including the branch and bound algorithm.

Ключевые слова: зазорная функция; глобальная оптимизация; метод ветвей и границ; липшицева непрерывность.

Keywords: gap function; global optimization; branch and bound method; Lipschitz continuity.

ВВЕДЕНИЕ

Пусть F : ℝⁿ → ℝⁿ — непрерывное отображение, D ⊆ ℝⁿ — непустое выпуклое множество. Задача вариационного неравенства состоит в нахождении точки x^* ∈ D такой, что

⟨F(x*), x − x*⟩ ≥ 0,  ∀x ∈ D.                     (1)

Задача вариационного неравенства была впервые введена Дж.-Л. Лионсом и Г. Стампаккьей в 1967 году в рамках абстрактного функционального анализа и впоследствии стала одним из центральных понятий прикладной математики. Она находит применение в задачах инженерного расчёта, моделировании экономического равновесия, механике контактных взаимодействий и ряде других областей. Следует отметить, что задача (1) является весьма общей: в частности, при

F(x) = ∇f(x) она сводится к условию оптимальности задачи минимизации f(x) → min, x ∈ D, а при D = ℝⁿ — к системе нелинейных уравнений F(x) = 0.

Несмотря на то что для решения задачи (1) разработано значительное число методов [1, 2, 4, 5, 6], большинство из них рассчитано на монотонный случай; эффективные практические методы для немонотонных задач встречаются значительно реже. Для монотонного случая хорошо разработаны метод проекции, метод внутренней точки, а также подходы, основанные на целевых функциях (merit functions). Обзор этих методов содержится в работах Харкера П.Т. и Пана Дж.-С. [6], а также Факкинеи Ф. и Пана Дж. [2]. В Монголии исследования вариационных неравенств проводились, в частности, доцентом МГУ (МУНТ) доктором Мажиг Мэнд-Амаром и его соавторами [7]; в указанных работах предпринята попытка решения немонотонных задач с помощью гибридного эволюционного алгоритма. Среди зарубежных исследователей данного направления следует выделить М. Фукусиму [4, 5] и П.М. Пардалоса [8].

Значительная часть методов решения вариационных неравенств основана на идее переформулировки исходной задачи в задачу другого класса [7, 8]. Данный процесс принято называть построением зазорной функции; его рассмотрению посвящён следующий раздел.

ЗАЗОРНЫЕ ФУНКЦИИ И ГЛОБАЛЬНАЯ ОПТИМИЗАЦИЯ

Рассмотрим задачу (1) вариационного неравенства в случае, когда F : ℝⁿ → ℝⁿ — немонотонное непрерывное отображение, D — непустое выпуклое множество.

Определение. Функция θ : D → ℝ⁺ называется зазорной функцией для задачи (1), если x^* ∈ D является решением задачи (1) тогда и только тогда, когда θ(x^*) = 0.

Зазорная функция θ обладает важным свойством: она служит критерием оптимизации при проверке сходимости алгоритма. В частности, последовательность x_k сходится к решению x^* тогда и только тогда, когда θ(x_k) → 0. С помощью зазорной функции задача (1) сводится к следующей задаче глобальной оптимизации с нулевым глобальным минимумом:

min θ(x),  x ∈ D.                     (2)

В литературе наиболее широко используются следующие зазорные функции:

зазорная функция [4, 5]:

θgap(x) = sup_y∈D ⟨F(x), x − y⟩;                     (3)

остаточная функция [2]:

θnat(x) = ‖x − Π_D(x − F(x))‖,                     (4)

где Π_D(z) := arg min_y∈D ‖z − y‖ — проекция точки z на множество D.

Для установления липшицевости указанных функций будем предполагать, что множество D компактно, а отображение F липшицево на D с константой L_F > 0, то есть

‖F(x) − F(y)‖ ≤ L_F ‖x − y‖,  ∀x, y ∈ D.

Обозначим через L₁ и L₂ глобальные максимумы функций ‖F(y)‖ и ‖x − y‖ на множестве D соответственно:

L₁ = max_y∈D ‖F(y)‖,   L₂ = max_x,y∈D ‖x − y‖.                     (5)

Теорема 1. Если отображение F липшицево на компактном множестве D с константой L_F, то зазорная функция θ_gap (3) является липшицевой на D с константой L_gap := L_F L₂ + L₁.

Доказательство. Для произвольных x, y ∈ D имеем:

θgap(x) − θgap(y) = max_z∈D ⟨F(x), x − z⟩ − max_z∈D ⟨F(y), y − z⟩

≤ max_z∈D ⟨F(x) − F(y), x − z⟩ + ⟨F(y), x − y⟩

≤ (L_F L₂ + L₁) ‖x − y‖ = L_gap ‖x − y‖.

Аналогично устанавливается неравенство в обратную сторону, откуда получаем

|θgap(x) − θgap(y)| ≤ L_gap ‖x − y‖,  ∀x, y ∈ D,

что и завершает доказательство теоремы. ∎

Теорема 2. Если отображение F липшицево на компактном множестве D с константой L_F, то остаточная функция θ_nat (4) является липшицевой на D с константой L_nat := L_F + 2.

Доказательство. Для произвольных x, y ∈ D обозначим H(x) = Π_D(x − F(x)). Тогда:

|θnat(x) − θnat(y)| = | ‖x − H(x)‖ − ‖y − H(y)‖ |

≤ ‖(x − H(x)) − (y − H(y))‖ ≤ ‖x − y‖ + ‖H(x) − H(y)‖.

Применяя свойство невозрастания оператора проекции, получаем:

‖H(x) − H(y)‖ ≤ ‖(x − F(x)) − (y − F(y))‖ ≤ ‖x − y‖ + ‖F(x) − F(y)‖.

Следовательно:

|θnat(x) − θnat(y)| ≤ 2 ‖x − y‖ + L_F ‖x − y‖ = L_nat ‖x − y‖.

Теорема доказана. ∎

Замечание 1. Из теорем 1 и 2 следует, что обе функции — зазорная θ_gap и остаточная θ_nat — пригодны для сведения задачи (1) к задаче липшицевой глобальной оптимизации. Константы Липшица этих функций различны: L_gap = L_F L₂ + L₁ и L_nat = L_F + 2. Выбор конкретной функции в зависимости от числовых характеристик задачи может существенно влиять на скорость сходимости алгоритма.

Замечание 2. Условия теорем — компактность множества D и липшицевость отображения F — не являются чрезмерно ограничительными с практической точки зрения. В инженерных и экономических задачах расчётная область, как правило, ограничена и компактна, а условие Липшица естественным образом выполняется для большинства физически мотивированных отображений.