Методы аппроксимации двумерных множеств конечными множествами и их приложение к некоторым геометрическим задачам оптимизации

Полный текст

Введение

При решении многих практических задач возникает задача оптимизации (для определенности — минимизации) некоторой целевой непрерывной функции $f( \boldsymbol{x})$, где ${\boldsymbol x}=(x_1,\ldots,x_n)\in\mathbb{R}^n$, на замкнутом ограниченном множестве $\boldsymbol{X}\subset\mathbb{R}^n$. В случае если требуется найти глобальный минимум, использование известных методов поиска локального минимума (см., например, [1]) оказывается малоэффективным.

Одним из возможных методов, применимых для нахождения именно глобального минимума, является использование конечного (аппроксимирующего) множества $\boldsymbol{X}^{\tau}$, которое является подмножеством $\boldsymbol{X}$ и для заданного $\tau > 0$ имеет для каждого $\boldsymbol x \in \boldsymbol X$ «представителя» $\tilde{\boldsymbol{x}} \in \boldsymbol{X}^{\tau}$ такого, что $\|\tilde{\boldsymbol{x}} - x\| \leqslant \tau$, где $\|\boldsymbol{x}\| = \max\{|x_1|, \ldots, |x_n|\}$. Такая аппроксимация практически реализуема лишь при небольших $n$, например $n = 2, 3, 4$. Однако и такие задачи нередко возникают на практике (см. раздел 2).

Имея метод построения аппроксимирующего множества $\boldsymbol{X}^{\tau}$ (для заданного $\tau > 0$), в случае липшицевой вещественнозначной функции $f( \boldsymbol{x})$ можно решать задачу глобальной минимизации этой функции на $\boldsymbol X$ с заданной точностью $\varepsilon > 0$. Пусть для некоторого числа $L > 0$ выполняется
\[ \begin{equation}
\forall \boldsymbol{x}, \bar{\boldsymbol{x}} \in \boldsymbol X \quad |f( \boldsymbol{x}) - f(\bar{\boldsymbol{x}})| \leqslant L \|\boldsymbol x - \bar{\boldsymbol{x}}\|.
\end{equation} \tag{1} \]
Тогда для точки $\tilde{\boldsymbol{x}}^{\tau} \in \boldsymbol{X}^{\tau}$ такой, что $f(\tilde{\boldsymbol{x}}^{\tau}) = \tilde{f}^{\tau} = \min f(\boldsymbol{X}^{\tau})$, при $\tau \leqslant \varepsilon / L$ выполняется
\[ \begin{equation}
f^{*} \leqslant f(\tilde{\boldsymbol{x}}^{\tau}) = \tilde{f}^{\tau} \leqslant f^{*} + \varepsilon,
\end{equation} \tag{2} \]
где $f^{*} = \min f( \boldsymbol{X})$. Соответственно, при выбранном $\tau > 0$ оценки (2) справедливы для $L\tau \leqslant \varepsilon$. Отметим, что для выполнения (2) условие (1) можно при любом фиксированном $\tau > 0$ ослабить, заменив на
\[ \begin{equation}
\forall \boldsymbol x, \bar{\boldsymbol{x}} \in \boldsymbol X \quad
\|\boldsymbol x - \bar{\boldsymbol{x}}\| \leqslant \tau \Rightarrow |f( \boldsymbol{x}) - f(\bar{\boldsymbol{x}})| \leqslant L \|\boldsymbol x - \bar{\boldsymbol{x}}\|.
\end{equation} \tag{3} \]

Для оценки эффективности предлагаемых в работе методов воспользуемся работой [2], в которой на простом примере глобальной оптимизации функции $f(\boldsymbol{x})$, удовлетворяющей условию (1) на $n$-мерном кубе
\[ \begin{equation*}
B_n = \{\boldsymbol{x} = (x_{1}, \ldots, x_{n}) \in \mathbb{R}^{n} \mid 0 \leqslant x_{i} \leqslant 1, \; i = 1, \ldots, n\}
\end{equation*} \]
(т.е. при $\boldsymbol X = B_n$), показано, что вычислительная сложность (т.е. количество вычислений значений функции $f(\boldsymbol{x})$) метода определения глобального минимума $\min\{f(\boldsymbol{x}) \mid \boldsymbol{x} \in B_n\}$ с точностью $\varepsilon > 0$ с помощью равномерного перебора (т. е. на прямом произведении равномерных сеток по каждой из координат с шагом $ {1}/{p}$, где $p = \lfloor {L}/({2\varepsilon})\rfloor + 1$, $\lfloor a \rfloor$ — целая часть числа $a$) не превосходит $ ( \lfloor {L}/({2\varepsilon}) \rfloor + 1 )^{n}$. При этом также показано, что нижняя оценка сложности для этой же задачи есть величина $(\lfloor {L}/({2\varepsilon}) \rfloor )^{n}$ (т. е. при любом используемом методе глобальной оптимизации при числе вычислений значений функции $f(\boldsymbol{x})$, не превышающем $ (\lfloor {L}/({2\varepsilon}) \rfloor )^{n}$, мы не можем гарантировать, что достигнутая точность будет меньше, чем заданное число $\varepsilon > 0$). Таким образом, при решении рассматриваемой задачи нижние и верхние оценки сложности совпадают с точностью до мультипликативной абсолютной константы. Это означает, что метод равномерного перебора является асимптотически оптимальным методом на классе функций, удовлетворяющих (1). В связи с этим представляется разумным использовать методы оптимизации, по возможности «близкие» к равномерному перебору (в предлагаемых ниже методах равномерность будет нарушаться только вблизи границы множества $\boldsymbol X$). Интуитивно понятно, что такая равномерность приводит к уменьшению необходимого числа вычислений значений функции $f(\boldsymbol{x})$ с учетом возможности даже самого «худшего» случая.

При решении практических задач значение константы $L$, удовлетворяющей (1), редко бывает известным. Тем не менее вычисление $\tilde{f}^{\tau}$ уже дает некоторую оценку сверху для $f^{*}$, которая становится все более точной с уменьшением $\tau$. Кроме того, для достижения требуемой точности $\varepsilon > 0$ достаточно, чтобы условие (1) (или (2)) выполнялось не на всем множестве $X$, а в окрестности хотя бы одной точки из $\operatorname{Arg} \min f(\boldsymbol{X}) = \{\boldsymbol{x} \in \boldsymbol X \mid f(\boldsymbol{x}) = f^{*}\}$. Действительно, если нашлись две точки $\boldsymbol{x}^{*} \in \boldsymbol X$, $\tilde{\boldsymbol{x}} \in \boldsymbol{X}^{\tau}$: $f(\boldsymbol{x}^{*}) = f^*$, $\|\boldsymbol{x}^{*} - \tilde{\boldsymbol{x}}\| \leqslant \tau$, и $|f(\boldsymbol{x}^{*}) - f(\tilde{\boldsymbol{x}})| \leqslant L_{*}\|\boldsymbol{x}^{*} - \tilde{\boldsymbol{x}}\|$, где $L_{*}$ — константа Липшица в $\tau$-окрестности точки $\boldsymbol{x}^{*}$ (а не на всем множестве $\boldsymbol X$), то
\[ \begin{equation*}
\min f(\boldsymbol{X}^{\tau}) \leqslant f(\tilde{\boldsymbol{x}}) \leqslant f(\boldsymbol{x}^{*}) + L_{*}\|\boldsymbol{x}^{*} - \tilde{\boldsymbol{x}}\| \leqslant \min f(\boldsymbol{X}) + L_{*} \tau.
\end{equation*} \]

Отметим в этой связи, что при обосновании сходимости методов оптимизации (даже локальной) часто ограничиваются доказательством утверждения о стремлении значения целевой функции у минимизирующей последовательности к минимуму, а иногда даже о стремлении градиента к нулю (см., например, [1, теоремы 1, 2, стр. 265, 266]). В рассматриваемом случае независимо от того, известна константа Липшица или нет, имеем
\[ \begin{equation*}
\lim\limits_{\tau \to 0+} \min f(X^{\tau}) = \lim\limits_{\tau \to 0+} f(\tilde{\boldsymbol{x}}^{\tau}) = \min f(\boldsymbol{X}),
\end{equation*} \]
т.е. сходимость метода в классическом его понимании выполняется.

Замечание 1. Рассмотрим вопрос о существовании константы Липшица $L$, удовлетворяющей (3) для некоторого $\tau = \tau_{0} > 0$ (и тогда (3) выполняется для любого $\tau \in (0, \tau_{0}]$). Для этого достаточно существование непрерывных частных производных у функции $f(\boldsymbol{x})$ на некотором открытом множестве $\check{\boldsymbol X} \supset \boldsymbol X$ таком, что $\forall \boldsymbol{x} \in \boldsymbol X$, $\forall \check{\boldsymbol{x}} \in \mathbb{R}^n$ $\|\check{\boldsymbol{x}} - \boldsymbol{x}\| \leqslant \tau_{0} \Rightarrow \check{\boldsymbol{x}} \in \check{\boldsymbol X}$. Во многих задачах это условие естественным образом выполняется. Для существования константы Липшица $L$, удовлетворяющей (1), достаточно существование непрерывных частных производных у функции $f(\boldsymbol{x})$ на некотором открытом множестве $\check{\boldsymbol X} \supset \operatorname{co} \boldsymbol X$, где $\operatorname{co} \boldsymbol X$ — выпуклая оболочка множества $\boldsymbol X$ (см., например, [1]). В некоторых случаях константы Липшица не существует, но тем не менее удается доказать выполнение $\lim\limits_{\tau \to 0+} \min f(\boldsymbol{X}^{\tau}) = \min f(\boldsymbol{X})$ (такой случай описывается в разделе 2).

При решении некоторых задач вычислительный процесс можно организовать таким образом, что одновременно с вычислением $\tilde{f}^{\tau} = \min f(\boldsymbol{X}^{\tau})$ вычисляется верхняя оценка $\tilde{L}$ для константы $L$ в окрестности текущей рассматриваемой точки из $\boldsymbol{X}^{\tau}$ (см., например, [3]), и тогда для выполнения (2) используем условие $\tilde{L}\tau \leqslant \varepsilon$ вместо $L\tau \leqslant \varepsilon$. Следует, однако, отметить, что метод вычисления константы $\tilde{L}$ из [3] не дает гарантированного значения константы Липшица, т.е. является эвристическим, а поэтому и использование $\tilde{L}$ вместо $L$ не всегда приводит к верному результату. Кроме того, эвристический метод вычисления константы $\tilde{L}$ из [3] может быть реализован лишь в случае, когда $\boldsymbol X$ — координатный параллелепипед, а также в случае специально организованного процесса вычислений значений функции $f(\boldsymbol{x})$. Такие ограничительные предположения в рассматриваемом ниже подходе отсутствуют.

Может оказаться, что значение $\tilde{f}^{\tau} = \min f(\boldsymbol X^{\tau})$ при выбранном $\tau > 0$ является приемлемым. В противном случае последовательно уменьшаем $\tau$, например, полагая $\tau := \tau / 2$, до получения приемлемого значения $\tilde{f}^{\tau}$.

В книге [1] приводится обзор некоторых методов глобальной оптимизации (см. [1, гл. 5, § 12]), которые можно объединить общим термином «методы покрытий». В большинстве случаев в этих методах предполагается, что множество $X$ является $n$-мерным координатным параллелепипедом. Кроме того, эти методы основываются на точном знании константы Липшица $L$, удовлетворяющей условию (1), и в случае отсутствия такой информации либо становятся неприменимыми, либо могут использоваться как эвристические методы. Один их таких методов описан в [1, стр. 355].

Таким образом, методы покрытий (см. некоторые варианты применения метода покрытий в [3–10]) имеют достаточно узкую область применимости, а в предлагаемом подходе на множество $\boldsymbol X$ не накладываются такие жесткие ограничения и знание константы Липшица не является обязательным.

Разработка и описание методов аппроксимации некоторых классов множеств, возникающих в практически значимых задачах, конечными множествами представляются важными и актуальными. Некоторые методы аппроксимации приводятся в разделе 1. В разделе 2 эти методы применяются к одной из геометрических задач оптимизации.

В связи с возникающими (и порой неразрешимыми) трудностями, связанными с решением задач глобальной оптимизации, авторы сделали упор на малую размерность решаемой задачи, а именно на двумерный случай. При такой размерности построение конечного множества $\boldsymbol X^{\tau} \subset \boldsymbol X$, аппроксимирующего множество возможных решений $\boldsymbol X$ с заданной точностью $\tau > 0$, является практически реализуемым при разумных ограничениях на величину $\tau$. Соответственно, нахождение минимального значения целевой функции на $X^{\tau}$ в этом случае также вполне реализуемо.

Авторы видят новизну предлагаемого подхода в использовании в разделе 1 «ступенчатой» структуры ограничений, задающих множество $\boldsymbol X$. Этот подход показал свою эффективность именно для двумерного случая (к сожалению, для трехмерного он уже «не работает»). Именно в двумерном случае достаточно просто можно выделить участки монотонности в одномерных функциях, задающих ограничения в $\boldsymbol X$.

В работе [10], на которую также указывается в [1], описан метод аппроксимации множества $\boldsymbol X$ произвольной размерности, описываемого системой ограничений вида неравенств. Однако его описание и алгоритмическая реализация являются гораздо более сложными, и при этом используются весьма существенные ограничения на функции в неравенствах.

Чтобы продемонстрировать существенное отличие предлагаемого подхода от метода, описанного в [10] (и аналогичных ему), рассмотрим следующие рассуждения, связанные с построением для множества $\boldsymbol X$ сетки $\boldsymbol{X}^{\tau}$, где ${\tau > 0}$, такой, что
\[ \begin{equation}
\boldsymbol{X}^{\tau} \subset \boldsymbol X, \quad \forall \boldsymbol{x} \in \boldsymbol X \quad
\exists \tilde{\boldsymbol{x}} \in \boldsymbol{X}^{\tau} : \|\tilde{\boldsymbol{x}} - \boldsymbol{x}\| \leqslant \tau.
\end{equation} \tag{4} \]
Если покрыть множество $\boldsymbol X$ кубиками $Q_{i}$ с длиной ребра $2\tau$ (оставим в стороне вопрос об алгоритме построения множества таких кубиков), где $\tau$ — шаг сетки, то возможны два случая: центр кубика $\operatorname{c}(Q_{i}) \in \boldsymbol X$ и $\operatorname{c}(Q_{i}) \not\in \boldsymbol X$. В первом случае добавляем точку $\operatorname{c}(Q_i)$ в сетку $\boldsymbol{X}^{\tau}$, а во втором — возникает вопрос о выполнении условия
\[ \begin{equation}
Q_{i} \cap \boldsymbol X \ne \varnothing.
\end{equation} \tag{5} \]
Если условие (5) выполняется, то для обеспечения выполнения (4) необходимо включить в сетку $\boldsymbol{X}^{\tau}$ какого-либо «представителя» $\boldsymbol{x}^{(i)} \in Q_{i} \cap \boldsymbol X$. При этом для некоторых точек $\boldsymbol{x} \in Q_{i} \cap \boldsymbol X$ может выполняться $\|\boldsymbol{x} - \boldsymbol{x}^{(i)}\| > \tau$ (вплоть до $\|\boldsymbol{x} - \boldsymbol{x}^{(i)}\| = 2\tau$), т.е. в этом случае для обеспечения выполнения (4) потребуется дополнительное дробление кубика $Q_{i}$ на $2^{n}$ кубиков $Q_{ij}$, получаемых из $Q_{i}$ делением его ребер пополам, и тогда для каждого из них также проверяем условие вида (5). При этом, если для каждого случая $Q_{ij} \cap \boldsymbol X \ne \varnothing$ любой представитель $\boldsymbol{x}^{(ij)} \in Q_{ij} \cap \boldsymbol X$ (хотя бы один) включается в сетку $\boldsymbol{X}^{\tau}$, то заведомо выполняется (4). Однако это легко сделать только в случае, когда задачи нахождения $\boldsymbol{x}^{(i)} \in Q_{i} \cap \boldsymbol X$, $\boldsymbol{x}^{(ij)} \in Q_{ij} \cap \boldsymbol X$ или подтверждения выполнения условий $Q_{i} \cap \boldsymbol X = \varnothing$, $Q_{ij} \cap \boldsymbol X = \varnothing$ решаются достаточно просто. Пусть $\boldsymbol X = \{\boldsymbol{x} \in \mathbb{R}^n \mid g_{1}(\boldsymbol{x}) \leqslant 0, \ldots, g_{r}(\boldsymbol{x}) \leqslant 0\}$. Тогда проверка выполнения условия $Q_{i} \cap \boldsymbol X \ne \varnothing$ (для кубика $Q_{i}$ такого, что не выполняется $g_{j}(\operatorname{c}(Q_{i})) \leqslant 0$, $j = 1, \ldots, r$) требует решения задачи глобальной оптимизации:
\[ \begin{equation}
g(\boldsymbol{x}) = \max\{g_{1}(\boldsymbol{x}), \ldots, g_{r}(\boldsymbol{x})\} \to \min (=\mu_{i}), \quad \boldsymbol{x} \in Q_{i}.
\end{equation} \tag{6} \]
Если $\mu_{i} > 0$, то $Q_{i} \cap \boldsymbol X = \varnothing$, и переходим к рассмотрению очередного кубика $Q_{i}$. Если $\mu_{i} \leqslant 0$, то $Q_{i} \cap \boldsymbol X \ne \varnothing$, и тогда дробим $Q_{i}$ на $2^{n}$ кубиков $Q_{ij}$, для каждого из которых в свою очередь решаем задачу глобальной оптимизации
\[ \begin{equation}
g(\boldsymbol{x}) = \max\{g_{1}(\boldsymbol{x}), \ldots, g_{r}(\boldsymbol{x})\} \to \min (=\mu_{ij}), \quad \boldsymbol{x} \in Q_{ij}.
\end{equation} \tag{7} \]
При этом, если $\mu_{ij} > 0$, то $Q_{ij} \cap \boldsymbol X = \varnothing$, а если $\mu_{ij} \leqslant 0$, то $Q_{i} \cap \boldsymbol X \ne \varnothing$, и тогда включаем в $\boldsymbol{X}^{\tau}$ любое решение задачи (7). Только решив все указанные задачи глобальной оптимизации вида (6), (7), мы соберем множество элементов сетки $\boldsymbol{X}^{\tau}$. Но даже в случае, когда множество $\boldsymbol X$ задается совокупностью линейных ограничений, для получения решения перечисленных задач потребуется достаточно большая вычислительная работа (решение огромного количества задач линейного программирования). А если функция $g(\boldsymbol{x})$ достаточно сложная (нелинейная, возможно, невыпуклая, многоэкстремальная)?

В этой связи следует отметить, что предлагаемая авторами методика существенно отличается от описанной выше процедуры нахождения элементов сетки $\boldsymbol{X}^{\tau}$ с помощью решения многочисленных задач глобальной оптимизации вида (6), (7). В методе, предлагаемом авторами, не требуется решения указанных задач глобальной оптимизации. Вместо решения каждой из таких задач достаточно вычислить значение функции лишь в одной специально выбранной точке!

Замечание 2. В численных методах решения некоторых математических задач (например, при численном решении дифференциальных уравнений в частных производных) также используются сеточные аппроксимации двумерных множеств для построения разностных схем. Однако при построении подобных сеток достигаются цели, отличные от рассматриваемых в задачах глобальной оптимизации. В частности, при построении таких сеток не ставится условие равномерности расположения её узлов. Например, часто используемым подходом является метод триангуляции, основанный на разбиении плоскости на треугольники (см., например, [11]), тогда как для равномерного расположения узлов приходим к разбиению плоскости на квадраты.

Замечание 3.Аппроксимация замкнутого ограниченного множества $\boldsymbol X \subset \mathbb{R}^n$ конечным множеством $\boldsymbol{X}^{\tau} \subset \boldsymbol X$ таким, что $\forall \boldsymbol{x} \in \boldsymbol X$ $\exists \tilde{\boldsymbol{x}} \in \boldsymbol{X}^{\tau}$: $\|\tilde{\boldsymbol{x}} - \boldsymbol{x}\| \leqslant \tau$, используется не только в задачах глобальной оптимизации. Аппроксимирующее множество $\boldsymbol{X}^{\tau}$ используется также в задачах векторной оптимизации, например, для аппроксимации конечными множествами множеств Парето-оптимальных оценок и решений (см., например, [12, 13]).

1. Построение конечного аппроксимирующего множества для двумерных множеств, заданных «ступенчатой» системой неравенств

Будем говорить, что некоторое множество $\boldsymbol S \subseteq \mathbb{R}^2$ описывается «ступенчатой» системой неравенств, если для заданных чисел $\alpha_{\boldsymbol S}$, $\beta_{\boldsymbol S}$, где $\alpha_{\boldsymbol S} < \beta_{\boldsymbol S}$, и двух заданных функций $g_{\boldsymbol S}(x)$, $\bar{g}_{\boldsymbol S}(x)$ выполняется
\[ \begin{equation}
\boldsymbol S = \{(x, y) \in \mathbb{R}^2 \mid \alpha_{\boldsymbol S} \leqslant x \leqslant \beta_{\boldsymbol S}, \; g_{\boldsymbol S}(x) \leqslant y \leqslant \bar{g}_{\boldsymbol S}(x)\}.
\end{equation} \tag{8} \]
Такой способ описания множества $\boldsymbol S$ является удобным для реализации численных методов аппроксимации этого множества конечным множеством, имеющим сколь угодно малое расстояние (в метрике Хаусдорфа [14, 15]) от $\boldsymbol S$. Это, в свою очередь, позволяет описывать численные методы оптимизации некоторой целевой функции на множестве $\boldsymbol S$.

1.1. Расстояния между множествами

Будем использовать следующую норму для $(x, y) \in \mathbb{R}^2$: $\|(x, y)\| = \max\{|x|, |y|\}$. Помимо этого будем использовать скалярное произведение векторов $(x, y)$, $(\bar{x}, \bar{y}) \in \mathbb{R}^2$: $\langle (x, y), (\bar{x}, \bar{y}) \rangle = x\bar{x} + y\bar{y}$, а также длину вектора $(x, y) \in \mathbb{R}^2$: $|(x, y)| = (x^2 + y^2)^{1/2}$. Заметим, что
\[ \begin{equation*}
\forall (x, y) \in \mathbb{R}^2 \quad \|(x, y)\| \leqslant |(x, y)| \leqslant \sqrt{2} \|(x, y)\|.
\end{equation*} \]

Для любого вектора $A = (a_1, a_2) \in \mathbb{R}^2$ и любых множеств $\boldsymbol S$, $\boldsymbol P \subseteq \mathbb{R}^2$ введем расстояния:
\[ \begin{gather*}
\rho_{e}(A, \boldsymbol S) = \inf\{|A - U| \mid U \in \boldsymbol S\},
\quad
\rho_{m}(A, \boldsymbol S) = \inf\{\|A - U\| \mid U \in \boldsymbol S\},
\\
\alpha_{e}(\boldsymbol P, \boldsymbol S) = \sup\{\rho_{e}(A, \boldsymbol S) \mid A \in \boldsymbol P\},
\quad
\alpha_{m}(\boldsymbol P, \boldsymbol S) = \sup\{\rho_m(A, \boldsymbol S) \mid A \in \boldsymbol P\},
\\
h_e(\boldsymbol P, \boldsymbol S) = h_e(\boldsymbol S, \boldsymbol P) =
\max\{\alpha_e(\boldsymbol P, \boldsymbol S), \alpha_e(\boldsymbol S, \boldsymbol P)\},
\\
h_m(\boldsymbol P, \boldsymbol S) = h_m(\boldsymbol S, \boldsymbol P) = \max\{\alpha_m(\boldsymbol P, \boldsymbol S), \alpha_m(\boldsymbol S, \boldsymbol P)\}.
\end{gather*} \]
Здесь $h_e(\boldsymbol P, \boldsymbol S)$, $h_m(\boldsymbol P, \boldsymbol S)$ — расстояние по Хаусдорфу между множествами $\boldsymbol S$ и $\boldsymbol P$ (см., например, [14, 15]).

Очевидно, что для любых множеств $\boldsymbol S , \boldsymbol P \subseteq \mathbb{R}^2$ выполняется
\[ \begin{equation*}
h_{e}(\boldsymbol P, \boldsymbol S) \leqslant \sqrt 2 h_m (\boldsymbol P, \boldsymbol S), \quad
h_m(\boldsymbol P, \boldsymbol S) \leqslant h_e(\boldsymbol P, \boldsymbol S),
\end{equation*} \]
а в случае $ \boldsymbol P \subseteq \boldsymbol S$ справедливо
\[ \begin{equation*}
h_{e}(\boldsymbol P, \boldsymbol S) = \alpha_e (\boldsymbol S, \boldsymbol P),
\quad
h_{m}(\boldsymbol P, \boldsymbol S) = \alpha_m (\boldsymbol S, \boldsymbol P).
\end{equation*} \]

Кроме того, если $W$ — ортогональная матрица порядка 2 (т.е. её вектор-строки, а также вектор-столбцы образуют ортонормированный базис в $\mathbb{R}^2$), $E$ — единичная матрица порядка 2, то для любых векторов $A$, $B \in \mathbb{R}^2$, множеств $\boldsymbol P$, $\boldsymbol S \subseteq \mathbb{R}^2$ и числа $\alpha > 0$ справедливы следующие соотношения:
\[ \begin{gather*}
WW^{\top} = W^{\top} W = E,
\\
|WA| = \langle WA, WA \rangle^{1/2} = \langle W^{\top}WA, A \rangle^{1/2} = \langle A, A \rangle^{1/2} = |A|,
\\
|WA - WB| = |W(A - B)| = |A - B|,
\\
h_e(W\boldsymbol P, W\boldsymbol S) = h_e(\boldsymbol P, \boldsymbol S),
\end{gather*} \]
\[ \begin{equation}
h_m(W\boldsymbol P, W\boldsymbol S) \leqslant h_e(W\boldsymbol P, W\boldsymbol S) = h_e(\boldsymbol P, \boldsymbol S) \leqslant \sqrt{2} h_m(\boldsymbol P, \boldsymbol S),
\end{equation} \tag{9} \]
\[ \begin{equation}
h_m(\boldsymbol P + A, \boldsymbol S + A) = h_m(\boldsymbol P, \boldsymbol S), \quad
h_e(\boldsymbol P + A, \boldsymbol S + A) = h_e(\boldsymbol P, \boldsymbol S),
\end{equation} \tag{10} \]
\[ \begin{equation*}
h_m(\boldsymbol S + A, \boldsymbol S) \leqslant \|A\|, \quad h_e(\boldsymbol S + A, \boldsymbol S) \leqslant |A|,
\end{equation*} \]
\[ \begin{equation}
h_m(\alpha \boldsymbol P, \alpha \boldsymbol S) = \alpha h_m(\boldsymbol P, \boldsymbol S), \quad
h_e(\alpha \boldsymbol P, \alpha \boldsymbol S) = \alpha h_e(\boldsymbol P, \boldsymbol S),
\end{equation} \tag{11} \]
где $\boldsymbol S + A = \{U + A \mid U \in \boldsymbol S\}$, $\alpha \boldsymbol S = \{\alpha U \mid U \in \boldsymbol S\}$.

Для любого непустого множества $\boldsymbol S\subseteq{\mathbb R}^2$ и числа $\tau>0$ обозначим
\[ \begin{gather*}
\operatorname{diam}_m(\boldsymbol S)=\sup\{\|U-V\| \mid U, V\in \boldsymbol S\}, \quad
\operatorname{diam}_e(\boldsymbol S)=\sup\{|U-V| \mid U, V\in \boldsymbol S\},
\\
O_m^{\tau }(\boldsymbol S)=\{(x,y)\in{\mathbb R}^2 \mid \exists (\bar{x},\bar{y})\in \boldsymbol S:
\|(x,y)-(\bar{x},\bar{y})\| \leqslant \tau\},
\\
O_e^{\tau}(\boldsymbol S)=\{(x,y)\in{\mathbb R}^2 \mid \exists (\bar{x},\bar{y})\in \boldsymbol S:
|(x,y)-(\bar{x},\bar{y})| \leqslant \tau \}.
\end{gather*} \]
В случае $\boldsymbol S=\{U\}$ кратко пишем $O_m^{\tau }(U),O_e^{\tau}(U)$ вместо $O_m^{\tau}(\{U\}),O_e^{\tau}(\{U\})$.

1.2. Вспомогательные утверждения об аппроксимации множества конечным множеством (сеткой) с заданной точностью

Рассмотрим задачу аппроксимации некоторого ограниченного множества $\boldsymbol S \subset \mathbb{R}^2$ конечным множеством $\boldsymbol S^{\tau} \subset \mathbb{R}^2$, удовлетворяющим для заданного $\tau > 0$ условиям
\[ \begin{equation*}
\boldsymbol S^{\tau} \subseteq \boldsymbol S, \quad h_m(\boldsymbol S^{\tau}, \boldsymbol S) = \alpha_m( \boldsymbol S, \boldsymbol S^{\tau}) \leqslant \tau.
\end{equation*} \]
Примеры аппроксимации некоторых сложных множеств конечными можно найти, например, в [12, 13].

Нам понадобятся следующие утверждения.

Утверждение 1. Пусть $Q = \{(x, y) \in \mathbb{R}^2 \mid \alpha_1 \leqslant x \leqslant \beta_1, {\alpha_2 \leqslant y \leqslant \beta_2}\}$ (где $\alpha_1 < \beta_1$, $\alpha_2 < \beta_2$) — координатный прямоугольник, $g(x)$ — функция, определенная и монотонно невозрастающая (неубывающая) на $[\alpha_1, \beta_1]$, $Q_g = \{(x, y) \in Q \mid y \leqslant g(x)\}$. Тогда $Q_g \ne \varnothing \Leftrightarrow (\alpha_1, \alpha_2) \in Q_{g}$ ($Q_{g} \ne \varnothing \Leftrightarrow (\beta_1, \alpha_2) \in Q_{g}$).

Доказательство. Рассмотрим случай монотонного невозрастания функции $g(x)$ (т.е. $x_{1} \leqslant x_{2} \Rightarrow g(x_{1}) \geqslant g(x_{2})$). Пусть $Q_{g} \ne \varnothing$. Тогда $\exists (x_{0}, y_{0}) \in Q$: $y_{0} \leqslant g(x_{0})$, откуда $\alpha_{2} \leqslant y_{0}$, $\alpha_{1} \leqslant x_{0}$, и, используя монотонное невозрастание функции $g(x)$, получаем: $g(\alpha_{1}) \geqslant g(x_{0}) \geqslant y_{0} \geqslant \alpha_{2}$, т.е. $(\alpha_{1}, \alpha_{2}) \in Q_{g}$. В обратную сторону рассуждения очевидны. Рассмотрим теперь случай монотонного неубывания $g(x)$. Пусть $Q_{g} \ne \varnothing$. Тогда $\exists (x_{0}, y_{0}) \in Q$: $y_{0} \leqslant g(x_{0})$, откуда $\alpha_{2} \leqslant y_{0}$, $x_{0} \leqslant \beta_{1}$, и, используя монотонное неубывание $g(x)$, получаем: $g(\beta_{1}) \ge g(x_{0}) \ge y_{0} \ge \alpha_{2}$, т.е. $(\beta_{1}, \alpha_{2}) \in Q_{g}$. В обратную сторону рассуждения очевидны. $\square$

Утверждение 2. Пусть $\boldsymbol S$ — некоторое непустое множество из $\mathbb{R}^2$,
\[ \begin{equation*}
\textstyle
\boldsymbol S \subseteq \bigl[\bigcup_{i=1}^{r_{1}} \boldsymbol Q_{\tau, i} \bigr] \bigcup
\bigl[\bigcup_{i=1}^{r_{2}} \tilde{\boldsymbol Q}_{\tau, i} \bigr],
\end{equation*} \]
где $\boldsymbol Q_{\tau, i}$, $ \tilde{\boldsymbol Q}_{\tau, i}$ — множества из $\mathbb{R}^{2}$ такие, что
\[ \begin{equation}
\exists C_{\tau, i} \in \boldsymbol Q_{\tau, i} \cap \boldsymbol S : \forall U \in \boldsymbol Q_{\tau, i} \|U - C_{\tau, i}\| \leqslant \tau ,
\end{equation} \tag{12} \]
\[ \begin{equation}
\operatorname{diam}_{m}(\tilde{ \boldsymbol Q}_{\tau, i}) \leqslant \tau, \quad
\exists \tilde{C}_{\tau, i} \in \tilde{ \boldsymbol Q}_{\tau, i} \cap \boldsymbol S.
\end{equation} \tag{13} \]

Тогда для множества $ \boldsymbol S^{\tau} = \bigl[\bigcup_{i=1}^{r_{1}} C_{\tau, i} \bigr] \bigcup \bigl[\bigcup_{i=1}^{r_{2}} \tilde{C}_{\tau, i} \bigr]$ выполняется $\boldsymbol S^{\tau} \subseteq \boldsymbol S$, $h_{m}(\boldsymbol S, \boldsymbol S^{\tau}) \leqslant \tau$.

Доказательство. Из условий доказываемого утверждения следует, что $\boldsymbol S^{\tau} \subseteq \boldsymbol S$. В силу того, что $\boldsymbol S^{\tau} \subseteq \boldsymbol S$, остается доказать, что
\[ \begin{equation*}
\alpha_{m}(\boldsymbol S, \boldsymbol S^{\tau}) = \sup\{\rho_m(U, \boldsymbol S^{\tau}) \mid U \in \boldsymbol S\} \leqslant \tau.
\end{equation*} \]

Пусть $U \in \boldsymbol S$. Покажем, что $\rho_m(U, \boldsymbol S^{\tau}) \leqslant \tau$. Рассмотрим два возможных случая:

1. $U \in \bigcup_{i=1}^{r_{1}} \boldsymbol Q_{\tau, i}$. Тогда, например, $U \in \boldsymbol Q_{\tau, 1}$ и в силу (12) для $C_{\tau, 1} \in \boldsymbol S^{\tau}$ выполняется $\|U - C_{\tau, 1}\| \leqslant \tau$, т.е. $\rho_{m}(U, \boldsymbol S^{\tau}) \leqslant \|U - C_{\tau, 1}\| \leqslant \tau$;
2. $U \in \bigcup_{i=1}^{r_{2}} \tilde{\boldsymbol Q}_{\tau, i}$. Тогда, например, $U \in \tilde{\boldsymbol Q}_{\tau, 1}$ и в силу (13) для $\tilde{C}_{\tau, 1} \in \tilde{\boldsymbol Q}_{\tau, 1} \cap \boldsymbol S^{\tau}$ выполняется $\|U - \tilde{C}_{\tau, 1}\| \leqslant \operatorname{diam}_{m}(\tilde{\boldsymbol Q}_{\tau, 1}) \leqslant \tau$, т.е. $\rho_{m}(U, \boldsymbol S^{\tau}) \leqslant \|U - \tilde{C}_{\tau, 1}\| \leqslant \tau$. $\square$

1.3. Построение конечного множества (сетки) $\boldsymbol{S^{\tau}}$, удовлетворяющего заданным условиям

Построим сетку $\boldsymbol S^{\tau}$, удовлетворяющую для заданного $\tau > 0$ условиям
\[ \begin{equation}
\boldsymbol S^{\tau} \subseteq \boldsymbol S, \quad h_m(\boldsymbol S^{\tau}, \boldsymbol S) =
\alpha_m(\boldsymbol S, \boldsymbol S^{\tau}) \leqslant \tau,
\end{equation} \tag{14} \]
где $\boldsymbol S$ — множество, удовлетворяющее (8).

Рассмотрим сначала простой случай, когда $g_{\boldsymbol S}(x) \equiv 0$, и при этом для простоты обозначений вместо $\bar{g}_{\boldsymbol S}(x)$, $\alpha_{\boldsymbol S}$, $\beta_{\boldsymbol S}$ используем $g(x)$, $\alpha$, $\beta$ соответственно, т.е. теперь
\[ \begin{equation}
\boldsymbol S = \{(x, y) \in \mathbb{R}^{2} \mid \alpha \leqslant x \leqslant \beta, 0 \leqslant y \leqslant g(x)\}, \quad \alpha < \beta.
\end{equation} \tag{15} \]

Кроме того, считаем, что функция $g(x)$ является неотрицательной и невозрастающей на $[\alpha, \beta]$ (т.е. $\forall x_{1}, x_{2} \in [\alpha, \beta]$ $x_{1} \leqslant x_{2} \Rightarrow g(x_{1}) \geqslant g(x_{2})$).

Построим вспомогательную сетку по оси $Ox$. Обозначим
\[ \begin{equation*}
T^{\tau} = \bigl\{x_{i}^{\tau} \triangleq \alpha + \tau + 2i\tau, \; i = 0, 1, \ldots, i_{\max} \bigr\},
\end{equation*} \]
где $i_{\max}$ — максимальное целое число $i \geqslant 0$, при котором $\alpha + 2i\tau < \beta$ (при этом может оказаться, что $\alpha + 2(i_{\max} + 1)\tau = \beta$). В особом случае, когда $\alpha + \tau \geqslant \beta$, полагаем $T^{\tau} = \{\beta\}$. Кроме того, если оказалось, что $x_{i_{\max}}^{\tau} > \beta$, то полагаем $x_{i_{\max}}^{\tau} = \beta$. При этом, очевидно, справедливо
\[ \begin{equation*}
T^{\tau} \subseteq [\alpha, \beta], \quad h_m(T^{\tau}, [\alpha, \beta]) = \alpha_{m}([\alpha, \beta], T^{\tau}) \leqslant \tau.
\end{equation*} \]

Рис. 1. Выбор элементов, принадлежащих $\boldsymbol S^{\tau}$
[Figure 1. Selection of elements belonging to $\boldsymbol S^{\tau}$]

Пусть теперь для некоторого $i_{0} \in \{0, 1, \ldots, i_{\max} - 1\}$ выполняется условие (см. рис. 1)
\[ \begin{equation}
\alpha + 2i_{0} \tau \leqslant x \leqslant \alpha + 2(i_{0} + 1)\tau,
\end{equation} \tag{16} \]
(соответственно, в случае $i_{0} = i_{\max}$ справедливо $\alpha + 2i_{0} \tau \leqslant x \leqslant \beta$, а в случае $T^{\tau} = \{\beta\}$ выполняется $\alpha \leqslant x \leqslant \beta$; для определенности рассмотрим случай (16), другие случаи рассматриваются аналогично). Обозначим $\bar{y} = g(\alpha + 2i_{0} \tau) = \max\{g(x) \mid \alpha + 2i_{0} \tau \leqslant x \leqslant \alpha + 2(i_{0} + 1)\tau\}$ (см. рис. 1). Будем рассматривать нетривиальный случай, когда $\bar{y} > 0$. Пусть $j_{0}$ — максимальное число среди чисел $j \in \{0, 1, \ldots\}$, для которых $2j\tau < \bar{y}$. Далее рассматриваем для случая (16) $j_{0} + 1$ горизонтальных слоев, для которых выполняется
\[ \begin{equation*}
2j\tau \leqslant y \leqslant 2(j + 1)\tau, \quad j = 0, 1, \ldots, j_{0},
\end{equation*} \]
и при этом $2j_{0} \tau < \bar{y}$, $2(j_{0} + 1)\tau \geqslant \bar{y}$. Пусть далее (см. рис. 1)
\[ \begin{equation*}
\check{y} = g(\alpha + \tau + 2i_{0} \tau) =
\max \bigl\{g(x) \mid \alpha + \tau + 2i_{0} \tau \leqslant x \leqslant \alpha + 2(i_0 + 1)\tau \bigr\}
\end{equation*} \]
и $j_{1}$ — максимальное число среди целых чисел $j \geqslant 0$, для которых $2j\tau + \tau \leqslant \check{y}$. Возможен также случай, когда $\check{y} < \tau$, при котором такого числа $j_{1}$ нет.

Тогда при $\check{y} \ge \tau$ для каждого номера $j \in \{0, 1, \ldots, j_{1}\}$ выполняется
\[ \begin{equation}
2j\tau + \tau \leqslant \check{y} = g(\alpha + \tau + 2i_{0} \tau),
\end{equation} \tag{17} \]
откуда
\[ \begin{equation*}
C_{\tau, j} = (\alpha + \tau + 2i_{0} \tau, 2j\tau + \tau) \in \boldsymbol S,
\end{equation*} \]
где $\boldsymbol S$ удовлетворяет (15). При этом $C_{\tau, j}$ является центром квадрата (с длинами сторон, равными $2\tau$)
\[ \begin{equation*}
Q_{\tau, j} = \bigl\{
(x, y) \in \mathbb{R}^2 \mid \alpha + 2i_{0} \tau \leqslant x \leqslant \alpha + 2(i_0 + 1)\tau, \;
2j\tau \leqslant y \leqslant 2(j + 1)\tau \bigr\},
\end{equation*} \]
и поэтому
\[ \begin{equation}
\forall (x, y) \in Q_{\tau, j}, j \in \{0, 1, \ldots, j_{1}\}, \quad
\|(x, y) - C_{\tau, j}\| \leqslant \tau .
\end{equation} \tag{18} \]

Включаем в $\boldsymbol S^{\tau}$ все $C_{\tau, j}$, удовлетворяющие (17), где $j \in \{0, 1, \ldots, j_{1}\}$, а тем самым и (18).

Далее рассматриваем квадраты $Q_{\tau, j}$ при $j \in \{j_{1} + 1, \ldots, j_{0}\}$ (а в случае $\check{y} < \tau$ — при $j \in \{0, \ldots, j_{0}\}$). Каждый из них разбиваем на 4 квадрата, длины сторон которых равны $\tau$. Согласно утверждению 1, чтобы определить, имеются ли в любом из них точки, принадлежащие $\boldsymbol S$, достаточно проверить принадлежность $\boldsymbol S$ левой нижней вершины каждого из них. Это условие заведомо не выполняется для верхнего правого квадрата (поскольку при $j \in \{j_{1} + 1, \ldots, j_{0}\}$ справедливо $2j\tau + \tau > \check{y} = g(\alpha + \tau + 2i_{0} \tau)$, а левой нижней вершиной этого квадрата является $(\alpha + \tau + 2i_{0} \tau, 2j\tau + \tau)$). Для проверки выполнения этого условия для остальных трех квадратов потребуются только уже вычисленные значения $\bar{y} = g(\alpha + 2i_{0} \tau)$ и $\check{y} = g(\alpha + \tau + 2i_{0} \tau)$. Если для некоторого из трех квадратов условие принадлежности $\boldsymbol S$ выполняется, то включаем в $\boldsymbol S^{\tau}$ соответствующую левую нижнюю вершину квадрата, принадлежащую $\boldsymbol S$. Такими вершинами для каждого $j \in \{j_{1} + 1, \ldots, j_{0}\}$ могут оказаться любые из трех точек:
\[ \begin{equation*}
(\alpha + 2i_{0} \tau, 2j\tau), \quad (\alpha + 2i_{0} \tau, 2j\tau + \tau), \quad (\alpha + 2i_{0} \tau + \tau, 2j\tau).
\end{equation*} \]
При этом для левой нижней вершины $\tilde{C}$ каждого из рассматриваемых квадратов $\tilde{Q}$ выполняется
\[ \begin{equation*}
\forall (x, y) \in \tilde{Q} \quad
\|(x, y) - \tilde{C}\| \leqslant \operatorname{diam}_{m}(\tilde{Q}) \leqslant \tau.
\end{equation*} \]

Действуя таким образом для всех $i_{0} \in \{0, 1, \ldots, i_{\max}\}$ (в случае $i_{0} = i_{\max}$ действуем аналогично, но в случае $\beta < \alpha + \tau + 2i_{0} \tau$ всюду вместо $\alpha + \tau + 2i_{0} \tau$ используем $\beta$ и, в частности, вместо $\check{y} = g(\alpha + \tau + 2i_{0} \tau)$ полагаем $\check{y} = g(\beta)$), в силу утверждения 2 получаем требуемое множество $\boldsymbol S^{\tau}$, удовлетворяющее (14). Действительно, выполнение условий вида (12) для $C_{\tau, j}$ и $Q_{\tau, j}$ следует из (18), а условий вида (13) — из приведенных выше неравенств для $\tilde C$ и $\tilde Q$.

Таким образом, рассмотрен случай, когда выполняется (15) (т.е. $\boldsymbol S = \{(x, y) \in \mathbb{R}^2 \mid \alpha \leqslant x \leqslant \beta, 0 \leqslant y \leqslant g(x)\}$), и функция $g(x)$ является неотрицательной и монотонно невозрастающей на $[\alpha, \beta]$. Очевидно, что условие $0 \leqslant y$ (взятое для простоты) можно заменить на более общее $\gamma \leqslant y$, где $\gamma$ — произвольное число, в предположении, что $\gamma \leqslant g(x)$ при $x \in [\alpha, \beta]$. Совершенно аналогично рассматривается случай, когда при выполнении (15) функция $g(x)$ является неотрицательной и монотонно неубывающей на $[\alpha, \beta]$. Кроме того, подобный подход применяется для случаев, когда при задании $\boldsymbol{S}$ по схеме (15) вместо условия $0 \leqslant y \leqslant g(x)$ используется альтернативное условие $g(x) \leqslant y \leqslant 0$, где функция $g(x)$ является неположительной и монотонно неубывающей либо, напротив, монотонно невозрастающей (а также более общие условия: $\gamma \leqslant y \leqslant g(x)$ или $g(x) \leqslant y \leqslant \gamma$ соответственно). В более общих случаях разбиваем $[\alpha, \beta]$ сначала на участки $[\bar{\alpha}, \bar{\beta}]$, где $\bar{\alpha} < \bar{\beta}$, такие, что для каждого из них найдется число $\bar{\gamma}$, для которого выполняется
\[ \begin{equation*}
\forall x \in [\bar{\alpha}, \bar{\beta}] \quad g_{\boldsymbol S}(x) \leqslant \bar{\gamma} \leqslant \bar{g}_{\boldsymbol S}(x)
\end{equation*} \]
(тогда $\boldsymbol S = \{(x, y) \in \mathbb{R}^{2} \mid \bar{\alpha} \leqslant x \leqslant \bar{\beta}, g_{\boldsymbol S}(x) \leqslant y \leqslant \bar{g}_{\boldsymbol S}(x)\} = \{(x, y) \in \mathbb{R}^2 \mid {\bar{\alpha} \leqslant x \leqslant \bar{\beta}}, g_{\boldsymbol S}(x) \leqslant y \leqslant \bar{\gamma}\} \bigcup \{(x, y) \in \mathbb{R}^2 \mid \bar{\alpha} \leqslant x \leqslant \bar{\beta}, \bar{\gamma} \leqslant y \leqslant \bar{g}_{\boldsymbol S}(x)\}$), а затем каждый такой участок $[\bar{\alpha}, \bar{\beta}]$ — на участки монотонности относительно функции $g_{\boldsymbol S}(x)$ (при рассмотрении случая $g_{\boldsymbol S}(x) \leqslant y \leqslant \bar{\gamma}$) или относительно функции $\bar{g}_{\boldsymbol S}(x)$ (при рассмотрении случая $\bar{\gamma} \leqslant y \leqslant \bar{g}_{\boldsymbol S}(x)$). Тогда объединение сеток по всем этим участкам даст искомую сетку для всего множества $\boldsymbol S$.

Замечание 4. Множество $\boldsymbol S^{\tau}$, удовлетворяющее (14), можно использовать в случае решения задачи глобальной оптимизации некоторой целевой функции $f(x, y)$ на замкнутом ограниченном множестве $\boldsymbol S \subset \mathbb{R}^2$, т.е. задачи вида
\[ \begin{equation*}
f(x, y) \to \min (= f^*); \quad (x, y) \in \boldsymbol S.
\end{equation*} \]
Действительно, для получения приближенного решения этой задачи можно найти для достаточно малого $\tau > 0$ значение
\[ \begin{equation*}
\tilde{f}^{(\tau)} = \min\{f(x, y) \mid (x, y) \in \boldsymbol S^{\tau}\}.
\end{equation*} \]
Тогда в случае, если функция $f(x, y)$ удовлетворяет условию Липшица на $\boldsymbol S$, т.е. существует константа $L_{f} > 0$ такая, что
\[ \begin{equation}
\forall (x, y), (\bar{x}, \bar{y}) \in \boldsymbol S \quad |f(x, y) - f(\bar{x}, \bar{y})| \leqslant L_{f} \|(x, y) - (\bar{x}, \bar{y})\|,
\end{equation} \tag{19} \]
то для $\tilde{f}^{(\tau)}$ выполняется
\[ \begin{equation}
f^* \leqslant \tilde{f}^{(\tau)} \leqslant f^* + L_{f} \tau.
\end{equation} \tag{20} \]
Заметим, что условие (19) можно ослабить и вместо него при выбранном $\tau > 0$ использовать условие
\[ \begin{equation}
\forall (x, y), (\bar{x}, \bar{y}) \in \boldsymbol S \quad \|(x, y) - (\bar{x}, \bar{y})\| \leqslant \tau
\Rightarrow |f(x, y) - f(\bar{x}, \bar{y})| \leqslant L_{f} \|(x, y) - (\bar{x}, \bar{y})\|,
\end{equation} \tag{21} \]
при выполнении которого также будет справедливо (20). Более того, вместо величины $L_{f}$ в (20) можно использовать величину $\tilde{L}_{f}$, удовлетворяющую еще более слабому условию (чем (21)). Пусть $\operatorname{Arg}\min f(\boldsymbol S) = \{(x, y) \in \boldsymbol S \mid f(x, y) = f^*\}$ и величина $\tilde{L}_{f}$ удовлетворяет условию
\[ \begin{equation*}
\exists (\tilde{x}, \tilde{y}) \in \operatorname{Arg}\min f(\boldsymbol S) :
\forall (x, y) \in \boldsymbol S \cap O_{m}^{\tau}((\tilde{x}, \tilde{y})) \quad
f(x, y) \leqslant f^* + \tilde{L}_{f} \|(x, y) - (\tilde{x}, \tilde{y})\|.
\end{equation*} \]
Тогда (20) очевидным образом выполняется при замене $L_{f}$ на $\tilde{L}_{f}$.

2. Об одной геометрической задаче, в описании которой используется множество, описываемое «ступенчатой» системой неравенств

2.1. Задача поиска кусочно-линейного маршрута, соединяющего две заданные точки $\boldsymbol{A}$, $\boldsymbol{ B \in \mathbb{R}^2}$, с возможностью совершения одного поворота в промежуточной точке $\boldsymbol{C \in \mathbb{R}^2}$

Предполагается, что угол поворота $\varphi$ в точке $C$ имеет ограничение вида $\varphi \in [-\varphi_{0}, \varphi_{0}]$, где $\varphi_{0}$ — заданный предельный угол поворота, $\varphi_{0} \in (0, \pi)$. Обозначим множество возможных значений для точки $C$ через $\boldsymbol S^{(1)}(A, B, \varphi_0)$. В этом разделе будут получены формулы для описания этого множества, а также приведен алгоритм построения конечного множества $\boldsymbol S^{(\tau, 1)}(A, B, \varphi_0)$, аппроксимирующего $\boldsymbol S^{(1)}(A, B, \varphi_0)$ с заданной точностью $\tau > 0$, основанный на методе, полученном в разделе 1. Кроме того, будут описаны задача поиска оптимального маршрута и метод ее решения, использующий $\boldsymbol S^{(\tau, 1)}(A, B, \varphi_0)$.

2.2. Угол между векторами

Для произвольных ненулевых векторов $A = (a_1, a_2) \in \mathbb{R}^2$, $B = (b_1, b_2) \in \mathbb{R}^2$ угол между этими векторами (предполагаем, что эти векторы имеют начало в одной точке $O = (0, 0) \in \mathbb{R}^2$) будем обозначать через $\angle(A, B)$. При этом будем учитывать направление угла от вектора $A$ в сторону вектора $B$, так что $\angle(A, B) = -\angle(B, A)$. Положительным считаем направление по часовой стрелке. Значения углов находятся в промежутке $(-\pi, \pi]$ (для угла между противоположно направленными векторами выбираем значение $\pi$). Кроме того, для большей общности рассуждений в случае нулевого вектора $A$ или $B$ полагаем $\angle(A, B) = 0$. Нетрудно показать, что
\[ \begin{equation*}
\angle(A, B) > 0 \Leftrightarrow \det
\begin{bmatrix} a_{1} & a_{2} \\ b_{1} & b_{2} \end{bmatrix} < 0
\end{equation*} \]
(в силу того, что векторное произведение векторов $(a_{1}, a_{2}, 0)$, $(b_{1}, b_{2}, 0) \in \mathbb{R}^3$ образует правую тройку).

Пример 1.

1. Для $A = (0, 1) \in \mathbb{R}^2$, $B = (1, 0) \in \mathbb{R}^2$ выполняется
   \[ \begin{equation*}
   \angle(A, B) = {\pi}/{2} > 0, \quad \det \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = -1 < 0.
   \end{equation*} \]
2. Для $A = (-1, 3) \in \mathbb{R}^2$, $B = (-5, 2) \in \mathbb{R}^2$ выполняется
   \[ \begin{equation*}
   \det \begin{bmatrix} -1 & 3 \\ -5 & 2 \end{bmatrix} = \begin{bmatrix} -1 & 3 \\ -5 & 2 \end{bmatrix} = -2 + 15 = 13 > 0 \Rightarrow \angle(A, B) < 0.
   \end{equation*} \]

Для точек $A$, $B \in \mathbb{R}^2$ через \([A, B] = \{(x, y) = \alpha A + (1 - \alpha)B \in \mathbb{R}^2 \mid \alpha \in [0{,} 1]\} \) обозначим отрезок прямой, соединяющий точки $A$ и $B$.

Замечание 5. Для попарно различных точек $A$, $B$, $C \in \mathbb{R}^2$, не лежащих на одной прямой, можно аналитически определить, где находится точка $C$ относительно прямой, проходящей через точки $A$ и $B$ и направленной от $A$ к $B$. Тогда в случае, если точка $C$ не принадлежит этой прямой, находим знак угла (вычисляя значение соответствующего определителя) $\alpha = \angle\bigl(B - A, C - ({A + B})/{2}\bigr)$ (вместо $({A + B})/{2}$ можно взять любую точку этой прямой). Если $\alpha > 0$, то точка $C$ находится справа от этой прямой, а если $\alpha < 0$, то слева.

Вернемся к исходной задаче поиска кусочно-линейного маршрута, соединяющего две заданные точки $A$, $B \in \mathbb{R}^2$, с возможностью совершения одного поворота в промежуточной точке $C \in \mathbb{R}^2$. Теперь мы можем описать введенное ранее множество $\boldsymbol S^{(1)}(A, B, \varphi_{0})$. Действительно, при выборе точки $C$ для осуществления допустимого поворота имеем следующее (геометрическое) условие: $\angle(B - C, C - A) \in [-\varphi_{0}, \varphi_{0}]$, т.е.
\[ \begin{equation*}
\boldsymbol S^{(1)}(A, B, \varphi_0) = \bigl\{C \in \mathbb{R}^2 \mid \angle(B - C, C - A) \in [-\varphi_{0}, \varphi_{0}] \bigr\}
\end{equation*} \]
(в случае $\angle(B - C, C - A) = 0$ точка $C$ принадлежит $[A, B]$). Кроме того, обозначим
\[ \begin{gather*}
\check{\boldsymbol S}^{(1)}(A, B, \varphi_{0}) =
\bigl\{C \in \mathbb{R}^2 \mid 0 \leqslant \angle(B - C, C - A) \leqslant \varphi_{0} \bigr\},
\\
\hat{\boldsymbol S}^{(1)}(A, B, \varphi_{0}) = \bigl\{C \in \mathbb{R}^2 \mid -\varphi_{0} \leqslant \angle(B - C, C - A) \leqslant 0 \bigr\}.
\end{gather*} \]
Далее, чтобы получить аналитическое описание множества $\boldsymbol S^{(1)}(A, B, \varphi_{0})$, воспользуемся вспомогательной задачей, получающейся из исходной (т.е. общей) благодаря удобному выбору фиксированных точек $A$ и $B$, расположенных симметрично относительно начальной точки $O(0, 0)$.

2.3. Вспомогательная задача

Опишем множество $\boldsymbol S^{(1)}(A, B, \varphi_{0})$ при следующих специально выбранных точках: $A = (0, -1)$, $B = (1, 0)$. Соответственно обозначим $\boldsymbol S_{\varphi_{0}}^{(1)} = \boldsymbol S^{(1)} \bigl((0, -1), (1, 0), \varphi_{0} \bigr)$, где $\varphi_{0} \in (0, \pi)$. Опишем $\boldsymbol S_{\varphi_{0}}^{(1)}$ с помощью простой «ступенчатой» системы неравенств. Множество $\boldsymbol S_{\varphi_{0}}^{(1)}$ состоит из двух симметричных частей (долей): левой
\[ \begin{equation*}
\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = \bigl\{C \in \mathbb{R}^2 \mid -\varphi_{0} \leqslant
\angle\bigl((0, 1) - C, C - (0, -1)\bigr) \leqslant 0 \bigr\}
\end{equation*} \]
и правой
\[ \begin{equation*}
\check{\boldsymbol S}_{\varphi_{0}}^{(1)} = \bigl\{C \in \mathbb{R}^2 \mid 0 \leqslant
\angle\bigl((0, 1) - C, C - (0, -1)\bigr) \leqslant \varphi_{0} \bigr\}
\end{equation*} \]
так, что $\boldsymbol S_{\varphi_{0}}^{(1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$. Очевидно, что для $C = (c_{1}, c_{2}) \in \mathbb{R}^2$ выполняется
\[ \begin{gather*}
\angle\bigl((0, 1) - C, C - (0, -1)\bigr) = \angle \bigl((-c_{1}, 1 - c_{2}), (c_{1}, c_{2} + 1)\bigr),
\\
\angle\bigl((0, 1) - (-C), -C - (0, -1)\bigr) = \angle\bigl((c_{1}, c_{2} + 1), (-c_{1}, 1 - c_{2})\bigr) =
\\
\hspace{6cm}
= -\angle\bigl((0, 1) - C, C - (0, -1)\bigr),
\end{gather*} \]
т.е.
\[ \begin{equation*}
{ 0 \,{\leqslant}\, \angle \bigl((0, 1) - C, C - (0, -1)\bigr) \, {\leqslant}\, \varphi_{0} \Leftrightarrow -\varphi_{0} \, {\leqslant}\, \angle\bigl((0, 1) - (-C), -C - (0, -1)\bigr) \,{\leqslant}\, 0},
\end{equation*} \]
откуда $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\check{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\hat{\boldsymbol S}_{\varphi_{0}}^{(1)}$. Следовательно, достаточно описать множество $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, поскольку множество $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)}$ описывается аналогично.

Замечание 6. Из условий $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_0}^{(1)}$, $\boldsymbol S_{\varphi_{0}}^{(1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ следует, что $\boldsymbol S_{\varphi_{0}}^{(1)} = -\boldsymbol S_{\varphi_{0}}^{(1)}$, т.е. точка $O(0, 0)$ является центром антисимметрии для множества $\boldsymbol S_{\varphi_{0}}^{(1)}$. Кроме того, нетрудно видеть, что
\[ \begin{equation*}
C = (c_{1}, c_{2}) \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)} \Leftrightarrow
(c_{1}, -c_{2}) \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)}, \quad
C = (c_{1}, c_{2}) \in \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \Leftrightarrow
(c_{1}, -c_{2}) \in \hat{\boldsymbol S}_{\varphi_{0}}^{(1)},
\end{equation*} \]
откуда в силу $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ получаем
\[ \begin{equation*}
C = (c_{1}, c_{2}) \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)} \Leftrightarrow (-c_{1}, c_{2}) \in \hat{\boldsymbol S}_{\varphi_{0}}^{(1)}.
\end{equation*} \]
Таким образом, ось $Ox$ является осью симметрии для множеств $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)}$, а $Oy$ — осью симметрии для $\boldsymbol S_{\varphi_{0}}^{(1)}$.

Таким образом, $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ — множество всех точек $C \in \mathbb{R}^2$, находящихся справа от оси $Oy$, и таких, что, двигаясь по ломаной $[(0, -1), C] \cup [C, (0, 1)]$, мы осуществляем в точке $C$ допустимый поворот, т.е. не превышающий по модулю заданный угол $\varphi_{0} \in (0, \pi)$.

Отметим некоторые простые геометрические свойства множества $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$. Если для некоторого $\varphi \in (0, \varphi_{0}]$ выполняется $0 \leqslant \angle\bigl((0, 1) - C, C - (0, -1)\bigr) = \varphi$, т.е. $C \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, то $[(0, -1), C] \subseteq \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, поскольку $\forall \alpha \in (0, 1]$ для $C_{\alpha} = (0, -1) + \alpha(C - (0, -1))$ справедливо
\[ \begin{equation*}
\angle\bigl((0, 1) - C_{\alpha}, C_{\alpha} - (0, -1)\bigr) \leqslant \angle\bigl((0, 1) - C, C - (0, -1)\bigr) = \varphi
\end{equation*} \]
(см. рис. 2), и при $\alpha \in (0, 1)$ это неравенство является строгим. Кроме того, если $\angle\bigl((0, 1) - C, C - (0, -1)\bigr) = \varphi \in (0, \varphi_{0})$, то найдется $\alpha_{0} > 1$ такое, что $\angle\bigl((0, 1) - C_{\alpha_{0}}, C_{\alpha_{0}} - (0, -1)\bigr) = \varphi_{0}$ (см. рис. 2).

Рис. 2. Взаимное расположение точек $C$, $C_\alpha$ и $C_{\alpha_0}$
[Figure 2. Relative positions of the points $C$, $C_\alpha$, and $C_{\alpha_0}$]

Используя эти простые свойства, нетрудно показать, что
\[ \begin{equation}
\textstyle
\check{\boldsymbol S}_{\varphi_{0}}^{(1)} = \bigcup_{C \in \check{\Gamma}_{\varphi_{0}}} [(0, -1), C],
\end{equation} \tag{22} \]
где $\forall \varphi \in (0, \pi)$ $\check{\Gamma}_{\varphi} = \bigl\{C \in \mathbb{R}^2 \mid \angle \bigl((0, 1) - C, C - (0, -1)\bigr) = \varphi \bigr\}$.

Заметим, что $\check{\Gamma}_{\varphi}$ является геометрическим местом точек $C(x, y)$, лежащих правее оси $Oy$, и таких, что $\angle \bigl((0, -1) - C, (0, 1) - C\bigr) = \pi - \varphi$, т.е. является дугой окружности радиуса $R_{\varphi} = \sin^{-1} \varphi$ (см. рис. 3, 4) с центром в точке $\check{G}_{\varphi} = (-\operatorname{ctg}\varphi, 0)$, длина которой равна $2\varphi R_{\varphi}$. Множество точек $C(x, y)$, принадлежащих этой кривой, удовлетворяет условиям
\[ \begin{equation}
\bigl(x + R_{\varphi} - \operatorname{tg}\tfrac{\varphi}{2} \bigr)^{2} + y^{2} = R_{\varphi}^{2} = \sin^{-2} \varphi,
\quad 0 \leqslant x \leqslant \operatorname{tg}\tfrac{\varphi}{2}.
\end{equation} \tag{23} \]
Например, при $x = \operatorname{tg}\tfrac{\varphi}{2}$ из (23) имеем $R_{\varphi}^{2} + y^{2} = R_{\varphi}^{2}$, откуда $y = 0$, а при $x = 0$ имеем
\[ \begin{multline*}
y^{2} = \sin^{-2} \varphi - \bigl( \sin^{-1}\varphi - \operatorname{tg}\tfrac{\varphi}{2} \bigr)^{2} = {}
\\
{} =
\frac{1}{\sin^{2} \varphi} - \frac{1}{\sin^{2} \varphi} + \frac{2\operatorname{tg}\tfrac{\varphi}{2}}{\sin\varphi} - \operatorname{tg}^{2} \tfrac{\varphi}{2} =
\\
= \frac{1}{\cos^{2} \tfrac{\varphi}{2}} - \frac{\sin^{2} \tfrac{\varphi}{2}}{\cos^{2} \tfrac{\varphi}{2}} = 1.
\end{multline*} \]

Рис. 3. Точка $C \in \check{\Gamma}_\varphi$
[Figure 3. The point $C \in \check{\Gamma}_\varphi$]

Рис. 4. Точка $C (\operatorname{tg} \tfrac \varphi 2, 0) \in \check{\Gamma}_\varphi$
[Figure 4. The point $C (\operatorname{tg} \tfrac \varphi 2, 0) \in \check{\Gamma}_\varphi$]

Таким образом, указанная кривая и представляет собой множество $\check{\Gamma}_{\varphi}$, и с учетом (22) $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ — часть круга радиуса $R_{\varphi_{0}} = \sin^{-1} \varphi_{0}$ с центром в точке $\check{G}_{\varphi_{0}} = \bigl(-R_{\varphi_{0}} + \operatorname{tg}\tfrac{\varphi_{0}}{2}, 0 \bigr) = (-\operatorname{ctg}\varphi_{0}, 0)$, ограниченная слева хордой $AB$:
\[ \begin{multline}
\check{\boldsymbol S}_{\varphi_{0}}^{(1)} =
\Bigl\{ (x, y) \in \mathbb{R}^{2} \mid 0 \leqslant x \leqslant \operatorname{tg}\tfrac{\varphi_{0}}{2},
- \sqrt{ R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2} }
\leqslant y \leqslant {} \\
{} \leqslant \sqrt{ R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2} } \Bigr\}.
\end{multline} \tag{24} \]

2.4. Построение конечной $\boldsymbol{\tau}$-сети для вспомогательной задачи

Из сопоставления (24) и (8) видим, что описание множества $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ в виде (24) является ступенчатым, где в соответствии с (8)
\[ \begin{multline}
\qquad\qquad
\alpha_{S} = 0, \quad \beta_{\boldsymbol S} = \operatorname{tg}\tfrac{\varphi_{0}}{2}, \quad
g_{\boldsymbol S}(x) =
\sqrt{
R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2}
},
\\
\bar{g}_{\boldsymbol S}(x) = - \sqrt{
R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2}
}.
\end{multline} \tag{25} \]
Кроме того, в случае $\varphi_{0} \in \bigl(0, \frac{\pi}{2}\bigr]$ функция $g_{\boldsymbol S}(x)$ из (25) является монотонно убывающей на $[\alpha_{\boldsymbol S}, \beta_{\boldsymbol S}] = \bigl[0, \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr]$, а функция $\bar{g}_{S}(x)$ — монотонно возрастающей. Заметим далее, что в случае $\varphi_{0} \in \bigl(\frac{\pi}{2}, \pi \bigr)$ точка $\check{G}_{\varphi_{0}} = (-\operatorname{ctg}\varphi_{0}, 0)$ лежит правее точки $(0, 0)$ и при этом на отрезке $[0, -\operatorname{ctg}\varphi_{0}]$ функция $g_{\boldsymbol S}(x)$ ($\bar{g}_{\boldsymbol S}(x)$) из (25) является монотонно возрастающей (убывающей), а на отрезке $\bigl[-\operatorname{ctg}\varphi_{0}, \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr]$ монотонно убывающей (возрастающей), т.е. к множеству $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ применим метод, описанный в разделе 1 и позволяющий строить для любого заданного $\tau > 0$ конечное множество $\check{\boldsymbol S}_{\boldsymbol \varphi_{0}}^{(\tau, 1)}$, удовлетворяющее условиям
\[ \begin{equation}
\check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)} \subseteq \check{\boldsymbol S}_{\varphi_{0}}^{(1)},
\quad
h_{m} (\check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)}, \check{\boldsymbol S}_{\varphi_{0}}^{(1)} ) = \alpha_{m} (\check{\boldsymbol S}_{\varphi_{0}}^{(1)}, \check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)} ) \leqslant \tau.
\end{equation} \tag{26} \]

Используя $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\boldsymbol S_{\varphi_{0}}^{(1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, получаем, что по множеству $\check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)}$ можно построить аппроксимирующее множество $\boldsymbol S_{\varphi_{0}}^{(\tau, 1)}$ и для всего множества $\boldsymbol S_{\varphi_{0}}^{(1)}$ (например, положив $\hat{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)}$, $\boldsymbol S_{\varphi_{0}}^{(\tau, 1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(\tau, 1)}$), т.е. удовлетворяющее условиям
\[ \begin{equation}
\boldsymbol S_{\varphi_{0}}^{(\tau, 1)} \subseteq \boldsymbol S_{\varphi_{0}}^{(1)}, \quad
h_{m}(\boldsymbol S_{\varphi_{0}}^{(\tau, 1)}, \boldsymbol S_{\varphi_{0}}^{(1)}) = \alpha_{m}(\boldsymbol S_{\varphi_{0}}^{(1)}, \boldsymbol S_{\varphi_{0}}^{(\tau, 1)}) \leqslant \tau.
\end{equation} \tag{27} \]

Замечание 7. На точку поворота $C(x, y)$, а тем самым и на элементы множеств $\boldsymbol S_{\varphi_{0}}^{(1)}$, $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)}$ могут быть наложены некоторые дополнительные условия, например, условие вида (ограничение на максимальную длину прямолинейного участка маршрута):
\[ \begin{equation}
|C - (0, 1)| \leqslant \sigma, \quad |C - (0, -1)| \leqslant \sigma,
\end{equation} \tag{28} \]
где $\sigma \geqslant 1$ (при $\sigma < 1$ условия (28) становятся несовместными). Из (28) получаем
\[ \begin{equation*}
x^{2} + (y - 1)^{2} \leqslant \sigma^{2}, \quad
x^{2} + (y + 1)^{2} \leqslant \sigma^{2},
\end{equation*} \]
откуда
\[ \begin{gather*}
-\sigma \leqslant x \leqslant \sigma, \quad
-\sqrt{\sigma^{2} - x^{2}} + 1 \leqslant y \leqslant \sqrt{\sigma^{2} - x^{2}} + 1,
\\
\phantom{-\sigma \leqslant x \leqslant \sigma, \quad }
-\sqrt{\sigma^{2} - x^{2}} - 1 \leqslant y \leqslant \sqrt{\sigma^{2} - x^{2}} - 1,
\end{gather*} \]
что равносильно условиям
\[ \begin{equation}
-\sigma \leqslant x \leqslant \sigma, \quad
-\sqrt{\sigma^{2} - x^{2}} + 1 \leqslant y \leqslant \sqrt{\sigma^{2} - x^{2}} - 1.
\end{equation} \tag{29} \]

С учетом условий (29) $\beta_{\boldsymbol S}$, $g_{\boldsymbol S}(x)$, $\bar{g}_{\boldsymbol S}(x)$ в (25) поменяются на
\[ \begin{gather*}
\beta_{\boldsymbol S} = \min \bigl\{\operatorname{tg}\tfrac{\varphi_{0}}{2}, \sigma \bigr\},
\\
g_{\boldsymbol S}(x) = \min \Bigl\{
\sqrt{R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2} }
, \sqrt{\sigma^{2} - x^{2}} - 1\Bigr\},
\\
\bar{g}_{\boldsymbol S}(x) = \max \Bigl\{
-\sqrt{R_{\varphi_{0}}^{2} - \bigl(x + R_{\varphi_{0}} - \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr)^{2} }, -\sqrt{\sigma^{2} - x^{2}} + 1
\Bigr\}.
\end{gather*} \]
При этом промежутки монотонности выделяются у новых функций столь же очевидным образом, а условия вида $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\boldsymbol S_{\varphi_{0}}^{(1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ сохраняются. Таким образом, аппроксимирующие множества, удовлетворяющие (27), могут быть получены и при дополнительном условии (28).

Помимо (28) на точку поворота $C(x, y)$ могут быть наложены и некоторые другие условия, например,
\[ \begin{equation}
\|C - (0, 1) \| \geqslant s, \quad \|C - (0, -1)\| \geqslant s,
\end{equation} \tag{30} \]
где $s \in (0, 1)$ (ограничение на возможность поворота рядом с начальной и конечной точками маршрута). Эти условия также легко учесть, модифицируя соответствующим образом $\beta_{\boldsymbol S}$, $g_{\boldsymbol S}(x)$, $\bar{g}_{\boldsymbol S}(x)$ в (26). Например, в случае отсутствия ограничений (28) с учетом только условий (30) $g_{\boldsymbol S}(x)$, $\bar{g}_{\boldsymbol S}(x)$ в (25) поменяются на $\tilde{g}_{\boldsymbol S}(x)$, $\check{g}_{\boldsymbol S}(x)$ соответственно, где
\[ \begin{gather*}
\tilde{g}_{\boldsymbol S}(x) =
\begin{cases} \min\{g_{\boldsymbol S}(x), 1 - s\}, & x \in [0{,} s],
\\ g_{\boldsymbol S}(x), & x \in \bigl(s, \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr], \end{cases}
\\
\check{g}_{\boldsymbol S}(x) =
\begin{cases} \max \{\bar{g}_{\boldsymbol S}(x), -1 + s\}, & x \in [0{,} s],
\\ \bar{g}_{\boldsymbol S}(x), & x \in \bigl(s, \operatorname{tg}\tfrac{\varphi_{0}}{2} \bigr].
\end{cases}
\end{gather*} \]
Участки монотонности у функций $\tilde{g}_{\boldsymbol S}(x)$, $\check{g}_{\boldsymbol S}(x)$ выделяются очевидным образом. Нетрудно также учесть одновременное выполнение условий (28), (30). Условия типа (30) (по ограничению возможности поворота рядом с начальной и конечной точками маршрута) могут иметь несколько иной вид:
\[ \begin{equation}
|C - (0, 1)| \geqslant s, \quad |C - (0, -1)| \geqslant s,
\end{equation} \tag{31} \]
Эти условия также достаточно легко учесть, модифицируя соответствующим образом $\beta_{\boldsymbol S}$, $g_{\boldsymbol S}(x)$, $\bar{g}_{\boldsymbol S}(x)$ в (25).

2.5. Формула перехода от вспомогательной задачи к общей

Приведем формулу, позволяющую выразить множество
\[ \begin{equation*}
\boldsymbol S^{(1)}(A,B,\varphi_0)=\{C\in{\mathbb R}^2 \mid \angle(B-C,C-A)\in[-\varphi_0,\varphi_0]\}
\end{equation*} \]
через $\boldsymbol S_{\varphi_0}^{(1)} = \boldsymbol S^{(1)} \bigl((0,-1),(1,0),\varphi_{0}\bigr)$ с помощью простого линейного преобразования. Положим
\[ \begin{equation}
E^{(2)}=(e_{1}^{(2)} , e_{2}^{(2)})=(B-A)/|B-A|, \quad
E^{(1)}=(e_{1}^{(1)} , e_{2}^{(1)})=(e_{2}^{(2)} , -e_{1}^{(2)}).
\end{equation} \tag{32} \]
Тогда, очевидно, выполняется
\[ \begin{equation*}
|E^{(1)}|=|E^{(2)}|=1, \quad \langle E^{(1)}, E^{(2)} \rangle =0,
\end{equation*} \]
т.е. $E^{(1)}$, $E^{(2)} $ — ортонормированный базис в ${\mathbb R}^2$, матрица
\[ \begin{equation}
W=\Bigg[\begin{array}{cc} e_{1}^{(1)} & e_{1}^{(2)} \\ e_{2}^{(1)} & e_{2}^{(2)} \end{array}\Bigg]
\end{equation} \tag{33} \]
— ортогональная и, следовательно,
\[ \begin{equation*}
\forall U, V\in{\mathbb R}^2 \quad
\langle WU,WV \rangle = \langle W^{\top} WU,V \rangle = \langle U,V \rangle.
\end{equation*} \]

Нетрудно показать (используя равенства $\hat{\boldsymbol S}_{\varphi _{0}}^{(1)}=-\check{\boldsymbol S}_{\varphi _{0} }^{(1)}$, $\boldsymbol S_{\varphi _{0} }^{(1)} =\hat{\boldsymbol S}_{\varphi _{0} }^{(1)}\cup\check{\boldsymbol S}_{\varphi _{0} }^{(1)} $), что
\[ \begin{gather}
\check{\boldsymbol S}^{(1)}(A,B,\varphi _{0})=\frac{|B-A|}{2} W\check{\boldsymbol S}_{\varphi _{0} }^{(1)} +(A+B)/2,
\\
\hat{\boldsymbol S}^{(1)}(A,B,\varphi _{0})=\frac{|B-A|}{2} W\hat{\boldsymbol S}_{\varphi _{0} }^{(1)} +(A+B)/2,
\\
\boldsymbol S^{(1)}(A,B,\varphi _{0})=\frac{|B-A|}{2} W \boldsymbol S_{\varphi _{0} }^{(1)} +(A+B)/2,
\end{gather} \tag{34} \]
Например,
\[ \begin{multline*}
\frac{|B-A|}{2} W\bigg[\begin{array}{r} {0} \\ {-1} \end{array}\bigg]+\frac{A+B}{2}
=
-\frac{|B-A|}{2} \bigg[\begin{array}{c} e_{1}^{(2)} \\ e_{2}^{(2)} \end{array}\bigg]+\frac{A+B}{2} = {}
\\
{} =-\frac{|B-A|}{2} \frac{B-A}{|B-A|} +\frac{A+B}{2} =-\frac{B-A}{2} +\frac{A+B}{2} =A,
\end{multline*} \]
\[ \begin{multline*}
\frac{|B-A|}{2} W\bigg[\begin{array}{c} {0} \\ {1} \end{array}\bigg]+\frac{A+B}{2} =\frac{|B-A|}{2} \bigg[\begin{array}{c} e_{1}^{(2)} \\ e_{2}^{(2)} \end{array}\bigg]+\frac{A+B}{2} = {}
\\ {}
=\frac{B-A}{2} +\frac{A+B}{2} =B,
\end{multline*} \]
\[ \begin{equation*}
\frac{|B-A|}{2} W\bigg[\begin{array}{c} {0} \\ {0} \end{array}\bigg]+\frac{A+B}{2} =\frac{A+B}{2} ,
\end{equation*} \]
\[ \begin{multline*}
\frac{|B-A|}{2} W\bigg[\begin{array}{c} {1} \\ {0} \end{array}\bigg]+\frac{A+B}{2} =\frac{|B-A|}{2} \bigg[\begin{array}{r} {e_{2}^{(2)} } \\ {-e_{1}^{(2)} } \end{array}\bigg]+\frac{A+B}{2} = {}
\\ {}
=\frac{1}{2} \bigg[\begin{array}{c} {b_{2} -a_{2} } \\ {a_{1} -b_{1} } \end{array}\bigg]+\frac{A+B}{2} ,
\end{multline*} \]
\[ \begin{equation*}
\bigg|\frac{1}{2} \bigg[\begin{array}{c} {b_{2} -a_{2} } \\ {a_{1} -b_{1} } \end{array}\bigg]\bigg|=\frac{|B-A|}{2} ,
\qquad\bigg \langle\frac{1}{2} \bigg[\begin{array}{c} {b_{2} -a_{2} } \\ {a_{1} -b_{1} } \end{array}\bigg], \frac{B-A}{2} \bigg \rangle =0.
\end{equation*} \]
При этом точка $(1, 0)$ находится справа от луча, направленного из точки $(0, -1)$ и проходящего через точку $(0,1)$, поскольку (см. замечание 5)
\[ \begin{multline*}
\det \bigg[\begin{array}{cc} {0} & {2} \\ {1} & {0} \end{array}\bigg]=0-2=-2 <0 \quad
\Rightarrow
\\
\angle \Bigl((0, 1)-(0,-1), (1, 0)-\tfrac{(0, 1)+(0, -1)}{2} \Bigr)= \angle \bigl((0,2),(1,0)\bigr ) > 0.
\end{multline*} \]
Покажем, что также и точка $C=\tfrac{|B-A|}{2} W\Big[\begin{array}{c} {1} \\ {0} \end{array}\Big]+\tfrac{A+B}{2}$ находится справа от луча, направленного из точки $A$ и проходящего через точку $B$. Действительно,
\[ \begin{multline*}
\det \bigg[\begin{array}{l} B-A \\ C-\tfrac{A+B}{2} \end{array}\bigg]=
\det \frac{1}{2} \bigg[\begin{array}{cc} b_{1} -a_{1} & b_{2} -a_{2} \\ b_{2} -a_{2} & a_{1} -b_{1} \end{array}\bigg]={}
\\
{} =\frac{1}{2} \bigl(-(b_{1} -a_{1} )^{2} -(b_{2} -a_{2} )^{2} \bigr) < 0
\quad \Rightarrow \quad
\angle \bigl(B-A, C-\tfrac{A+B}{2} \bigr) >0.
\end{multline*} \]
Совершенно аналогично доказывается, что $\forall C\in\check{\boldsymbol S}_{\varphi _{0} }^{(1)} $ для $\tilde{C}=\tfrac{|B-A|}{2} WC + \tfrac{A+B}{2} $ выполняется $\angle\bigl(B-A, \tilde{C}-\tfrac{A+B}{2} \bigr)>0$.

2.6. Построение конечной $\boldsymbol{\tau }$-сети для исходной задачи

Опишем теперь метод нахождения конечной сетки, аппроксимирующей с заданной точностью $\tau >0$ множество
\[ \begin{equation*}
\boldsymbol S^{(1)}(A,B,\varphi _{0})=\{C\in{\mathbb R}^2 \mid \angle(B-C, C-A)\in[-\varphi _{0} ,\varphi _{0}]\}.
\end{equation*} \]
Будем аппроксимировать правую долю (левая аппроксимируется аналогично), т.е. множество
\[ \begin{equation*}
\check{\boldsymbol S}^{(1)}(A,B,\varphi _{0})=\{C\in{\mathbb R}^2 \mid \angle(B-C,C-A)\in[0,\varphi_0]\}.
\end{equation*} \]
Будем строить конечное множество $\check{\boldsymbol S}^{(\tau , 1)}(A, B, \varphi _{0})$, удовлетворяющее условиям
\[ \begin{equation}
\!\!
\begin{array}{l}
\check{\boldsymbol S}^{(\tau ,1)}(A,B,\varphi _{0})\subseteq
\check{\boldsymbol S}^{(1)}(A,B,\varphi _{0}), \; \;
h_m\bigl(\check{\boldsymbol S}^{(\tau ,1)} (A,B,\varphi _{0}), \check{\boldsymbol S}^{(1)}(A,B,\varphi _{0}) \bigr)\leqslant \tau .
\end{array}\!\!\!\!\!\!
\end{equation} \tag{35} \]
Но тогда в силу (34), (26), а также (9), (10), (11) получаем, что при $\bar{\tau }>0$ для множества
\[ \begin{equation}
\bar{\boldsymbol S}^{\bar{\tau}}(A,B,\varphi _{0})=\frac{|B-A|}{2} W\check{\boldsymbol S}_{\varphi _{0} }^{(\bar{\tau} , 1)} +(A+B)/2
\end{equation} \tag{36} \]
справедливо
\[ \begin{equation*}
\bar{\boldsymbol S}^{\bar{\tau}}(A,B,\varphi _{0})\subseteq \check{\boldsymbol S}^{(1)}(A,B,\varphi _{0}),
\;\;
h_{m}\bigl(\bar{\boldsymbol S}^{\bar{\tau }} (A,B,\varphi _{0}), \check{\boldsymbol S}^{(1)}(A,B,\varphi _{0})\bigr)\leqslant \sqrt{2} \frac{|B-A|}{2} \bar{\tau }.
\end{equation*} \]

Таким образом, если при $\bar{\tau }>0$ задавать конечное множество $\bar{\boldsymbol S}^{\bar{\tau}}(A,B,\varphi _{0})$ по формуле (36), то в качестве множества $\check{\boldsymbol S}^{(\tau ,1)}(A,B,\varphi _{0})$, удовлетворяющего (35) для заданного $\tau >0$, достаточно положить $\check{\boldsymbol S}^{(\tau ,1)}(A,B,\varphi _{0})=\bar{\boldsymbol S}^{\bar{\tau }}(A,B,\varphi _{0})$ при любом $\bar{\tau }\in \bigl(0,\tfrac{\sqrt{2} }{|B-A|} \tau \bigr]$. Поскольку аппроксимация левой доли производится аналогично (в силу $\hat{\boldsymbol S}_{\varphi _{0} }^{(1)} =-\check{\boldsymbol S}_{\varphi _{0} }^{(1)}$; см. раздел 2.1), будем считать, что полностью описан метод построения для заданного $\tau >0$ конечного аппроксимирущего множества $\boldsymbol S^{(\tau ,1)}(A,B,\varphi _{0})$, удовлетворяющего условиям
\[ \begin{equation*}
\boldsymbol S^{(\tau ,1)}(A,B,\varphi _{0})\subseteq \boldsymbol S^{(1)}(A,B,\varphi _{0}),
\quad
h_{m}\bigl(\boldsymbol S^{(\tau ,1)}(A,B,\varphi _{0}), \boldsymbol S^{(1)}(A,B,\varphi _{0})\bigr)\leqslant \tau .
\end{equation*} \]

2.7. Задача поиска оптимального кусочно-линейного маршрута, соединяющего две заданные точки $\boldsymbol{A, B\in{\mathbb R}^2}$, с возможностью совершения одного поворота в промежуточной точке $\boldsymbol{C\in{\mathbb R}^2}$

Вернемся к рассматриваемой в настоящем разделе задаче и сформулируем соответствующую задачу оптимизации. Ранее была получена формула (34) для описания
\[ \begin{equation*}
\boldsymbol S^{(1)}(A,B,\varphi _{0})= \{C\in{\mathbb R}^2 \mid \angle(B-C, C-A) \in[-\varphi _{0} ,\varphi _{0}]\}
\end{equation*} \]
— множества возможных значений для промежуточной точки $C$, каждое из которых дает одно из возможных решений исследуемой задачи. Опишем соответствующую ей задачу оптимизации. Пусть $f_{0}(C)$ — функция, определенная при $C=(c_{1} , c_{2})\in \boldsymbol S^{(1)}(A,B,\varphi _{0})$, такая, что для некоторого числа $L_{0} >0$ выполняется (см. также замечание 8)
\[ \begin{equation}
\forall C, D\in \boldsymbol S^{(1)}(A,B,\varphi _{0}) \quad |f_{0}(C)-f_{0}(D)|\leqslant L_{0} \| C-D \|.
\end{equation} \tag{37} \]
Пусть значение функции $f_{0}(C)$ характеризует суммарные затраты (штраф) на строительство маршрута, состоящего из двух прямолинейных участков: одного из них, соединяющего точки $A$, $C$, а второго — соединяющего точки $C$ и $B$.

Замечание 8. В случае $\varphi_{0}\in\bigl(0,\tfrac{\pi}{2}\bigr]$ множество $\boldsymbol S^{(1)}(A,B,\varphi _{0})$, являющееся объединением двух выпуклых множеств (долей) $\check{\boldsymbol S}^{(1)}(A,B,\varphi _{0})$, $\hat{\boldsymbol S}^{(1)}(A,B,\varphi _{0})$, само является выпуклым и в этом случае условие (37) будет следствием аналогичных условий, выполненных для каждого из этих его подмножеств. В случае $\varphi _{0} \in \bigl(\tfrac{\pi }{2} ,\pi \bigr)$ множество $\boldsymbol S^{(1)}(A,B,\varphi _{0})$ уже не будет выпуклым, хотя обе его доли остаются выпуклыми. Вследствие этого выполнение условий вида (37) для каждой из его долей не гарантирует выполнения условия (37) для всего множества $\boldsymbol S^{(1)}(A,B,\varphi _{0})$, а лишь с дополнительным коэффициентом (можно показать, что в случае $\varphi _{0}\in\bigl(\tfrac{\pi }{2} ,\pi \bigr)$ в условии (37) для всего множества $\boldsymbol S^{(1)}(A,B,\varphi _{0})$ следует использовать $L_{0} / \sin\varphi _{0}$ вместо $L_{0} $ — константы Липшица для каждой из долей). Тем не менее, поскольку мы обычно ограничиваемся рассмотрением правой доли (вследствие равенства $\hat{\boldsymbol S}_{\varphi _{0} }^{(1)}=-\check{\boldsymbol S}_{\varphi _{0} }^{(1)} $), нас всегда будет интересовать не общая константа $L_{0}$, удовлетворяющая (37), а константа, при которой выполняется условие вида (37) для каждой из долей множества $\boldsymbol S^{(1)}(A,B,\varphi _{0})$ (т.е. без замены $L_{0} $ на $L_{0} / \sin\varphi _{0} $).

Пусть далее $h(\varphi)$, где $\varphi \in [-\varphi_{0}, \varphi_{0}]$, — неотрицательная функция, накладывающая штраф за поворот $\varphi$, где $h(0) = 0$. При этом направление поворота не является важным, т.е. функция $h(\varphi)$ является четной: $\forall \varphi \in [-\varphi_{0}, \varphi_{0}]$ $h(-\varphi) = h(\varphi) = h(|\varphi|)$. Будем считать, что функция $h(\varphi)$ также удовлетворяет условию Липшица на множестве $[-\varphi_{0}, \varphi_{0}]$ с некоторой константой $L_{h} > 0$:
\[ \begin{equation*}
\forall \alpha, \beta \in [-\varphi_{0}, \varphi_{0}] \quad |h(\alpha) - h(\beta)| \leqslant L_{h}|\alpha - \beta|.
\end{equation*} \]
Введем целевую функцию
\[ \begin{equation*}
f_{1}(C) = f_{0}(C) + h(\Psi(C)), \quad \text{где } \Psi(C) = \angle(B - C, C - A).
\end{equation*} \]
Теперь мы можем сформулировать следующую задачу оптимизации. Требуется найти точку $C^{*} \in S^{(1)}(A, B, \varphi_{0})$ такую, что
\[ \begin{equation}
f_{1}(C^{*}) = \min\{f_{1}(C) \mid C \in S^{(1)}(A, B, \varphi_{0})\}.
\end{equation} \tag{38} \]

Осталось выяснить, удовлетворяет ли условию Липшица функция $\Psi(C) = \angle(B - C, C - A)$. Выясним этот вопрос, а также подберем методы приближенного решения задачи (38) сначала для простейшего случая с $A = (0, -1)$, $B = (1, 0)$, ограничиваясь правой долей $\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$. В силу $\hat{\boldsymbol S}_{\varphi_{0}}^{(1)} = -\check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, $\boldsymbol S_{\varphi_{0}}^{(1)} = \hat{\boldsymbol S}_{\varphi_{0}}^{(1)} \cup \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$ обобщение этого случая на $\boldsymbol S_{\varphi_{0}}^{(1)}$ не вызывает затруднений. Покажем, что минимальное значение константы Липшица $L(\bar{C})$ для функции $\Psi(C)$ в окрестности любой точки $\bar{C} = (\bar{c}_{1}, \bar{c}_{2}) \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, где $\bar{c}_{1} > 0$, $\bar{c}_{2} \in [1{,} -1]$, удовлетворяет неравенству $L(\bar{C}) \geqslant \tfrac{\Psi(\bar{C})}{\bar{c}_{1}}$. Действительно, используя очевидное равенство $\Psi(0, \bar{c}_{2}) = 0$ ($\Psi(C) = \angle(B - C, C - A) = 0$ при $C \in [A, B]$), имеем
\[ \begin{equation*}
|\Psi(\bar{C}) - \Psi(0, \bar{c}_{2})| =
\tfrac{\Psi(\bar{C})}{\bar{c}_{1}} \bar{c}_{1} =
\tfrac{\Psi(\bar{C})}{\bar{c}_{1}} \|\bar{C} - (0, \bar{c}_{2})\|.
\end{equation*} \]

При этом, если $\varphi_{1} \in \bigl(0, \min\bigl\{\varphi_{0}, \frac{\pi}{2}\bigr\}\bigr)$, $\bar{C} \in \check{\Gamma}_{\varphi_{1}} = \{C \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)} \mid \Psi(C) = \varphi_{1}\}$, то $\bar{c}_{2} \in [1{,} -1]$, $L(\bar{C}) \geqslant \frac{\Psi(\bar{C})}{\bar{c}_{1}} = \tfrac{\varphi_{1}}{\bar{c}_{1}}$, и если точка $\bar{C}$ близка к любой из точек $A = (0, -1)$ или $B = (1, 0)$, то число $\bar{c}_{1}$ может быть сколь угодно малым. Таким образом, константа Липшица для $\Psi(C)$ может принимать сколь угодно большие значения, а следовательно, и для функции $h(\Psi(C))$, и для целевой функции $f_{1}(C)$ константа Липшица может также принимать сколь угодно большие значения.

Между тем большие значения константы Липшица у функции $\Psi(C)$ возникают лишь в малых окрестностях точек $A$ и $B$. При рассмотрении практических задач (например, проектирование канатной дороги) ситуация, когда единственный поворот планируется совершить вблизи начальной точки $A$ или конечной точки $B$, является невозможной. Учитывая это, можно в соответствии с замечанием 7 наложить на $C$ дополнительные условия, которые при сведении общей задачи к вспомогательной приведут к условиям вида (30) или (31). Что касается точек $C \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)}$, не находящихся вблизи точек $A = (0, -1)$ или $B = (1, 0)$, то $\Psi(C) = \angle(B - C, C - A) \in (0, \varphi_{0}]$ — угол, определяемый по формуле
\[ \begin{equation*}
\Psi(C) = \angle(B - C, C - A) = \arccos\frac{\langle B - C, C - A \rangle}{|B - C| \cdot |C - A|} = \arccos u(C)
\end{equation*} \]
или по формуле
\[ \begin{equation*}
\Psi(C) = \begin{cases}
\phantom{\pi -{}\!}\arcsin v(C), & \Psi(C) \in \bigl[0, \tfrac{\pi}{2}\bigr], \\
\pi - \arcsin v(C), & \Psi(C) \in \bigl(\tfrac{\pi}{2}, \pi \bigr),
\end{cases}
\end{equation*} \]
где
\[ \begin{gather*}
u(C) = \frac{1 - c_{1}^{2} - c_{2}^{2}}{\sqrt{c_{1}^{2} + (1 - c_{2})^{2}} \cdot \sqrt{c_{1}^{2} + (1 + c_{2})^{2}}},
\\
v(C) = \sqrt{1 - u^{2}(C)} = \frac{2c_{1}}{\sqrt{c_{1}^{2} + (1 - c_{2})^{2}} \cdot \sqrt{c_{1}^{2} + (1 + c_{2})^{2}}}.
\end{gather*} \]
При этом всегда можно выбрать формулу, соответствующую случаю, когда $\min\{|u(C)|, v(C)\} \leqslant \tfrac{\sqrt{2}}{2}$ (функции $\arccos u$, $\arcsin u$ являются бесконечно гладкими с ограниченной производной при $|u| \leqslant \tfrac{\sqrt{2}}{2}$). Используя обе эти формулы, нетрудно доказать, что функция $\Psi(C)$ является бесконечно гладкой на множестве $\mathbb{R}^2 \setminus \{A, B\}$. Можно также наложить дополнительные ограничения (30) (или (31)), где $s > 0$ — некоторое выбранное число, и тогда можно определить (точно или приближенно) значение константы Липшица $L_{s}$ для функции $\Psi(C)$ на компакте $\operatorname{Co}\{C \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)} \mid \|(0, 1) - C\| \geqslant s, \|(0, -1) - C\| \geqslant s\}$ (или, соответственно, на $\operatorname{Co}\{C \in \check{\boldsymbol S}_{\varphi_{0}}^{(1)} \mid |(0, 1) - C| \geqslant s, |(0, -1) - C| \geqslant s\}$), на котором эта функция имеет ограниченные частные производные $\Psi_{c_{1}}(C)$, $\Psi_{c_{2}}(C)$. Учитывая, что оптимизационная задача для определения числа $L_{s}$ имеет размерность 2, эту задачу можно решить достаточно точно (с небольшой погрешностью).

Нетрудно доказать, что несмотря на то, что функция $f_{1}(C)$ не удовлетворяет на $\boldsymbol S_{\varphi_{0}}^{(1)}$ условию Липшица, тем не менее справедливо

Утверждение 3. Пусть $\tau_{n} > 0$, $n = 1, 2, \ldots$, $\lim\limits_{n \to \infty} \tau_{n} = 0$. Тогда
\[ \begin{equation*}
\lim\limits_{n \to \infty} \min f_{1}(\boldsymbol S_{\varphi_{0}}^{(\tau_{n}, 1)}) = \min f_{1}(\boldsymbol S_{\varphi_{0}}^{(1)}).
\end{equation*} \]

Покажем теперь, как можно при этом использовать дополнительное ограничение вида (30), т.е. отбраковывать «лишние решения» $C\in \boldsymbol S_{\varphi _{0} }^{(\tau ,1)} $, не удовлетворяющие (30). Величина $s$ может определяться из практических (технических) соображений, а также вычисляться исходя из предположения о том, чтобы обязательное выполнение (30) для $C\in \boldsymbol S_{\varphi _{0} }^{(\tau ,1)} $ не меняло итогового значения $\min f_{1} (\boldsymbol S_{\varphi _{0} }^{(\tau ,1)})$. Обозначим $\bar{f}_{0} =f_{0}(B)=f_{1}(B)$ — значение целевой функции в случае выбора $C\in[A, B]$, т.е. выбираем прямой маршрут из $A$ в $B$ без использования поворота, поскольку $\forall C\in[A,B]$ $\Psi(C)=0$, $h(\Psi(C))=0$, $f_{1}(C)=f_{1}(B)=f_{0}(B)=\bar{f}_{0} $.

Рассмотрим нетривиальный случай, когда это простейшее решение не является оптимальным. Пусть мы нашли некоторое рекордное значение $\tilde{b}$, перебирая значения $f_{1}(C)$ при различных $C\in \boldsymbol S_{\varphi _{0} }^{(1)} $. Например, $\tilde{b}=f_{1}^{(\tau_{0})} =\min f_{1}(\boldsymbol S_{\varphi _{0} }^{(\tau _{0} ,1)} ))$, где $\tau _{0} >0$ — начальная («грубая») величина для $\tau $. Пусть при этом $\tilde{b}<\bar{f}_{0} $ и $\theta =\bar{f}_{0} -\tilde{b}>0$. Тогда можно положить в (30) $s=\theta /L_{0} $, поскольку
\[ \begin{multline*}
\|(0,1)-C\|< {\theta }/{L_{0} } \Rightarrow f_{1}(C)=f_{0}(C)+h(\Psi(C))\geqslant f_{0}(C)\geqslant {}
\\
{} \geqslant f_{0}(B)-L_{0}\| B-C \|>f_{0}(B)-\theta =\tilde{b}
\end{multline*} \]
(аналогично для точки $(0, -1)$), т.е. в $s$-окрестности точек $A=(0,-1)$, $B =(0,1)$ улучшение значения $\tilde{b}$ невозможно. При этом вместо величины $L_{0}$, удовлетворяющей (37), достаточно использовать константу Липшица функции $f_{0}(C)$ на $O_{m}^{s}([A,B])\cap \boldsymbol S_{\varphi _{0} }^{(1)} $, где $s=\theta /L_{0}$. Подчеркнем, что при таком подходе требуется знание величины $L_{0} $, что не всегда выполняется. Аналогичные рассуждения с незначительными изменениями переносятся и на случай, когда используется дополнительное ограничение (31).

Применение модификации варианта метода с использованием дополнительного условия (30) (или (31)) также имеет свой смысл, поскольку при этом происходит сокращение объема вычислений (отбрасываются точки из $\boldsymbol S_{\varphi _{0} }^{(1,\tau)} $, не удовлетворяющие (30) (или (31)). При этом с каждым новым $\tau =\tau _{n} $ величина $s=s(\tau _{n})$ уточняется (может значительно увеличиваться).

Опираясь на приведенные рассуждения, опишем метод приближенного решения основной задачи (38) с произвольными $A$, $B\in{\mathbb R}^2$. Рассмотрим уравнение относительно неизвестного $\bar{C}\in{\mathbb R}^2$:
\[ \begin{equation}
C=\omega(\bar{C})=\tfrac{|B-A|}{2} W\bar{C}+(A+B)/2,
\end{equation} \tag{39} \]
где $C\in S^{(1)}(A,B,\varphi _{0})$, $W$ — ортогональная матрица, удовлетворяющая условиям (32), (33). Как было показано в разделе 2.5, для этой матрицы выполняется (34). Из (39) однозначно получаем
\[ \begin{equation}
\bar{C}=\xi(C)=\tfrac{2}{|B-A|} W^{\top} \bigl(C-\tfrac{A+B}{2} \bigr),
\end{equation} \tag{40} \]
т.е. по формуле (40) любой точке $C\in S^{(1)}(A,B,\varphi _{0})$ можно поставить в соответствие точку $\xi(C)\in S_{\varphi _{0} }^{(1)} $, и при этом $\xi(A)=(0, -1)$, $\xi(B)=(0, 1)$. Более того, используя (34), получаем
\[ \begin{equation*}
\omega(\boldsymbol S_{\varphi _{0} }^{(1)})= \boldsymbol S^{(1)}(A,B,\varphi _{0}),\quad
\xi(\boldsymbol S^{(1)}(A,B,\varphi _{0}))= \boldsymbol S_{\varphi _{0} }^{(1)}.
\end{equation*} \]

Обозначим $\bar{\Psi}(\bar{C})=\angle\bigl((0,1)-\bar{C},\bar{C}-(0,-1)\bigr)$, где $\bar{C}\in \boldsymbol S_{\varphi _{0} }^{(1)} $. Заметим, что в силу ортогональности матрицы $W$ для любых $\bar{C}\in S_{\varphi _{0} }^{(1)}$ выполняется
\[ \begin{equation*}
\bar{\Psi}(\bar{C})=\angle \bigl(B-\omega(\bar{C}),\omega(\bar{C})-A\bigr)=\Psi(\omega(\bar{C})),
\end{equation*} \]
откуда $\forall \bar{C}\in \boldsymbol S_{\varphi _{0} }^{(1)}$ $h\bigl(\bar{\Psi}(\bar{C})\bigr)=h\bigl(\Psi(\omega(\bar{C}))\bigr)$. Обозначим
\[ \begin{multline}
\forall \bar{C}\in \boldsymbol S_{\varphi _{0} }^{(1)} \quad
\tilde{f}_{0}(\bar{C})=f_{0}\bigl(\omega(\bar{C})\bigr), \quad
\tilde{h}\bigl(\Psi(\bar{C})\bigr)=h\bigl(\Psi(\omega(\bar{C}))\bigr)=h\bigl(\bar{\Psi}(\bar{C})\bigr),
\\
\tilde{f}_{1}(\bar{C})=f_{1}\bigl(\omega(\bar{C})\bigr)=\tilde{f}_{0}(\bar{C})+\tilde{h}\bigl(\Psi(\bar{C})\bigr)=\tilde{f}_{0} \bigl(\bar{C})+h(\bar{\Psi}(\bar{C})\bigr).
\end{multline} \tag{41} \]
Тогда $\tilde{f}_{1}(\boldsymbol S_{\varphi _{0}}^{(1)})=f_{1}\bigl(\omega( \boldsymbol S_{\varphi _{0} }^{(1)})\bigr)=f_{1}\bigl(\boldsymbol S^{(1)}(A,B,\varphi _{0})\bigr)$, откуда
\[ \begin{equation*}
\min \tilde{f}_{1}(\boldsymbol S_{\varphi _{0} }^{(1)}) =
\min f_{1}\bigl(\boldsymbol S^{(1)}(A,B,\varphi _{0})\bigr) ,
\end{equation*} \]
где $\tilde{f}_{1}(\bar{C})$ удовлетворяет (41). Но тогда в качестве приближенного значения для $\min f_{1}\bigl(\boldsymbol S^{(1)}(A,B,\varphi _{0}) \bigr) $ можно взять $\min \tilde{f}_{1}(\boldsymbol S_{\varphi _{0} }^{(\tau ,1)}) $ при достаточно малом $\tau >0$, поскольку в силу утверждения 3 имеем
\[ \begin{equation*}
\lim\limits_{\tau \to 0+}\min\tilde{f}_{1}(\boldsymbol S_{\varphi _{0}}^{(\tau ,1)})=
\min \tilde{f}_{1} (\boldsymbol S_{\varphi _{0} }^{(1)})=
\min f_{1}\bigl(\boldsymbol S^{(1)}(A,B,\varphi _{0})\bigr) .
\end{equation*} \]

Заметим далее, что в силу (37) выполняется
\[ \begin{multline*}
\forall \bar{C}, \bar{D}\in \check{\boldsymbol S}_{\varphi _{0} }^{(1)} \quad
|\tilde{f}_{0}(\bar{C})-\tilde{f}_{0} (\bar{D})|\leqslant L_{0} \|\omega(\bar{C})-\omega(\bar{D}) \|\leqslant{}
\\
{}
\leqslant \tfrac{|B-A|}{2} L_{0} \| W(\bar{C}-\bar{D}) \| \leqslant
\tfrac{|B-A|}{2} L_{0} |W(\bar{C}-\bar{D})|=
\tfrac{|B-A|}{2} L_{0} |\bar{C}-\bar{D}|\leqslant{}
\\ {}
\leqslant \tfrac{|B-A|}{\sqrt{2} } L_{0} \| \bar{C}-\bar{D} \|.
\end{multline*} \]
Таким образом, в случае, если величина $L_{0} $ известна (аналогично для доли $\hat{S}_{\varphi _{0} }^{(1)} $; см. замечание 8), то при вычислении величины $\min \tilde{f}_{1}(\boldsymbol S_{\varphi _{0} }^{(1)})$ можем воспользоваться описанным выше методом подбора подходящей величины $s$ такой, что при вычислении $\min \tilde{f}_{1}(\boldsymbol S_{\varphi _{0} }^{(1)})$ можно не учитывать значения $\tilde{f}_{1}(C)$ для $C\in \boldsymbol S_{\varphi _{0} }^{(1)} $, не удовлетворяющих (30) (или (31)).

Замечание 9. Заметим, что $\forall C, \tilde{C}\in \boldsymbol S^{(1)}(A, B, \varphi _{0})$
\[ \begin{equation*}
|\xi(C)-\xi(\tilde{C})|=\tfrac{2}{|B-A|}|W^{B}(C-\tilde{C})|=\tfrac{2}{|B-A|}|C-\tilde{C}|,
\end{equation*} \]
откуда $\forall C\in \boldsymbol S^{(1)}(A,B,\varphi _{0})$
\[ \begin{equation}
|\xi(C)-(0,-1)|=\tfrac{2}{|B-A|}|C-A|, \quad |\xi(C)-(0, 1)|=\tfrac{2}{|B-A|}|C-B|.
\end{equation} \tag{42} \]
Используя (42), получаем, что если на точку $C\in \boldsymbol S^{(1)}(A,B,\varphi _{0})$ накладывается дополнительное ограничение вида
\[ \begin{equation*}
|C-A|\leqslant \sigma |B-A|/2, \quad |C-B|\leqslant \sigma |B-A|/2,
\end{equation*} \]
то в соответствии с замечанием 7 используем в описанном методе модифицированные множества $ \boldsymbol S_{\varphi _{0} }^{(1)}$, $\boldsymbol S_{\varphi _{0} }^{(\tau ,1)} $ с учетом выполнения условия (28). Соответственно, если на точку $C\in \boldsymbol S(A,B,\varphi _{0})$ накладывается дополнительное ограничение вида
\[ \begin{equation*}
|C-A|\geqslant s|B-A|/2, \quad |C-B|\geqslant s|B-A|/2,
\end{equation*} \]
то в соответствии с замечанием 7 используем в описанном методе модифицированные множества $\boldsymbol S_{\varphi _{0} }^{(1)}$, $\boldsymbol S_{\varphi _{0} }^{(\tau ,1)} $, с учетом выполнения условия (31). Можно одновременно учитывать условия (28), (31).

Заключение

Перечислим основные результаты работы.

1. Введено понятие множества, описываемого ступенчатой системой неравенств вида (8).
2. Получены вспомогательные утверждения об аппроксимации ограниченного множества $\boldsymbol S\subset\mathbb{R}^2$ конечной сеткой с точностью $\tau>0$. На их основе предложен метод построения аппроксимирующего множества $\boldsymbol S^{\tau}$ для множества $\boldsymbol S\subset\mathbb{R}^2$, задаваемого системой неравенств вида (8)
3. Исследована задача поиска кусочно-линейного маршрута между точками $A$, $B\in\mathbb{R}^2$ с одним поворотом в промежуточной точке $C\in\mathbb{R}^2$ при ограничении на угол поворота. Сформулирована простейшая вспомогательная задача, удобная для исследований. C помощью простых формул описано множество возможных точек для осуществления одного поворота во вспомогательной задаче (т.е. получено аналитическое выражение для описания этого множества), из которого с помощью простого линейного преобразования вида (34) может быть получено множество возможных решений для исходной задачи. Показано, что множество возможных решений в простейшей задаче описывается «ступенчатой» системой неравенств вида (8), а следовательно, для аппроксимации этого множества применимы методы из раздела 1. Соответственно, конечное аппроксимирующее множество для множества допустимых решений во вспомогательной задаче с помощью простого линейного преобразования вида (34) преобразуется в конечное аппроксимирующее множество для множества допустимых решений в исходной задаче.
4. Разработан приближенный метод решения задачи поиска оптимального кусочно-линейного маршрута, соединяющего две заданные точки $A$, $B\in{\mathbb R}^{2}$, с возможностью совершения одного поворота в промежуточной точке $C\in{\mathbb R}^{2} $, основанный на использовании конечного аппроксимирующего множества для множества возможных решений рассматриваемой задачи оптимизации.

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

Конкурирующие интересы. Авторы заявляют об отсутствии конфликта интересов в отношении авторства и публикации данной статьи.
Авторский вклад и ответственность. В.Н. Нефедов — общая концепция статьи; разработка комплексной математической модели, включая метод аппроксимации замкнутых ограниченных множеств в R2 конечными подмножествами с заданной точностью (в метрике Хаусдорфа) для класса множеств, задаваемых ступенчатыми системами неравенств; подготовка первоначального варианта рукописи; доработка рукописи. Ф.В. Свойкин — инициация исследования; постановка задачи оптимизации кусочно-линейных маршрутов; формулировка цели и задач работы. Б.А. Гарибян — разработка математической и геометрической моделей; подготовка первоначального варианта рукописи; доработка рукописи. А.В. Ряпухин — постановка геометрической задачи оптимизации на замкнутых множествах; разработка математической модели; доработка рукописи. Н.С. Королько — формулировка практических требований к модели; построение геометрической модели на основе оригинальной технической разработки поворотного механизма канатно-трелевочной установки.
Финансирование. Исследование выполнено без привлечения внешнего финансирования.
Благодарность. Авторы выражают благодарность рецензентам за внимательное прочтение статьи, а также за ценные предложения и комментарии, которые способствовали улучшению работы.

Об авторах

Виктор Николаевич Нефедов

Московский авиационный институт (национальный исследовательский университет)

Email: nefedovvn54@yandex.ru
ORCID iD: 0000-0001-6053-2066
Scopus Author ID: 7103271245
ResearcherId: S-2650-2019
https://www.mathnet.ru/person63464

кандидат физико-математических наук, доцент; доцент; каф. 805 математической кибернетики¹

Россия, 125993, Москва, Волоколамское шоссе, 4

Федор Владимирович Свойкин

Санкт-Петербургский государственный лесотехнический университет имени С. М. Кирова

Email: svoykin_fv@mail.ru
ORCID iD: 0000-0002-8507-9584
SPIN-код: 8938-6910
Scopus Author ID: 57217847423
ResearcherId: AAC-4074-2020
https://www.mathnet.ru/person228056

кандидат технических наук, доцент; доцент; каф. технологии лесозаготовительных производств²

Россия, 194021, Санкт-Петербург, Институтский пер., 5

Борис Александрович Гарибян

Московский авиационный институт (национальный исследовательский университет)

Email: bagarib@yandex.ru
ORCID iD: 0000-0001-8309-3086
SPIN-код: 8622-4854
Scopus Author ID: 57202449216
ResearcherId: Y-6983-2018
https://www.mathnet.ru/person228057

кандидат физико-математических наук, доцент; доцент; каф. 805 математической кибернетики¹

Россия, 125993, Москва, Волоколамское шоссе, 4

Анатолий Вячеславович Ряпухин

Московский авиационный институт (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: anatoliiruapukhin@yandex.ru
ORCID iD: 0000-0002-2208-6875
SPIN-код: 6693-0850
Scopus Author ID: 57211373896
ResearcherId: ABB-3999-2020
https://www.mathnet.ru/person145977

старший преподаватель; каф. 101 проектирования и сертификации авиационной техники¹

Россия, 125993, Москва, Волоколамское шоссе, 4

Николай Сергеевич Королько

Санкт-Петербургский государственный лесотехнический университет имени С. М. Кирова

Email: kns89lta@mail.ru
ORCID iD: 0009-0009-6289-2984
SPIN-код: 6309-8365
Scopus Author ID: 57220187617
https://www.mathnet.ru/person228087

аспирант; каф. технологии лесозаготовительных производств²

Россия, 194021, Санкт-Петербург, Институтский пер., 5

Список литературы

Дополнительные файлы