\documentclass[11pt,twoside,reqno]{amsart}
\usepackage{daio-cp1251}
\usepackage{tikz}

%%%%%-----Авторы заполняют все аргументы в блоке команд ниже-----%%%%%%

%%---Номер УДК
\udc{519.8+518.25}

%%---Название статьи на русском и английском языках
\title[Методы негладкого анализа]{Методы негладкого анализа в задаче минимизации суммы модулей от~аффинных~функций}
\titleen[A short title]{The paper title}

%%---Имена авторов на русском языке и в транлитерации на латиницу, краткие и полные
\author[1,2]{Г. Ш. Тамасян}		%1,2 --- указать, в каком порядке перечислять адреса автора
\author[3,2]{Г. С. Шульга}		%3,1 --- указать, в каком порядке перечислять адреса автора
%\author[2,1]{И. О. Фамилия}		%2,1 --- указать, в каком порядке перечислять адреса автора
\authoren[1,2]{G. Sh. Tamasyan}
\authoren[3,2]{G. S. Shulga}
%\authoren[2,1]{I. O. Familiya}
\fullname{Тамасян Григорий Шаликович}
\fullname{Шульга Георгий Сергеевич}
%\fullname{Фамилия Имя Отчество}
\fullnameen{Grigoriy Sh. Tamasyan}
\fullnameen{Georgiy S. Shulga}
%\fullnameen{Imya O. Familiya}

%%---Адреса авторов на русском и английском языках в следующих форматах.
%%На русском:
%%---Организация,
%%---улица, дом, индекс город, страна
\address[1]{Военно-космическая академия им.~А.\,Ф.~Можайского,\\ул. Ждановская, 13, 197082 Санкт-Петербург, Россия}
\address[2]{Институт проблем машиноведения РАН,\\Большой проспект В. О., 61, 199178 Санкт-Петербург, Россия}
\address[3]{Санкт-Петербургский государственный университет,\\Университетская наб., 7--9, 199034 Санкт-Петербург, Россия}
%%На английском:
%%---Организация,
%%---дом улица, индекс город, страна
\addressen[1]{Mozhaiskiy Space Military Academy,\\13 Zhdanovskaya Street, 197082 St. Petersburg, Russia}
\addressen[2]{Institute of Problems of Mechanical Engineering, Russian Academy of Sciences,\\61 Bolshoj pr., V. O., 199178 St. Petersburg, Russia}
\addressen[3]{St. Petersburg State University,\\7-–9 Universitetskaya nab., 199034 St.~Petersburg, Russia}

%%---Адреса электронной почты авторов
\email{grigoriytamasjan@mail.ru}
\email{gdextrous@gmail.com}
%\email{email3}

%%---Аннотация на русском и английском языках
\abstract{Демонстрируется применение аппарата конструктивного негладкого анализа на задаче минимизации выпуклой кусочно-аффинной функции, заданной в виде суммы модулей от аффинных. Для общего случая использовалось  гиподифференциальное исчисление, в скалярном~--- субдифференциальное. Из анализа критерия оптимальности получено, что точку, доставляющую глобальный минимум, можно найти, решая соответствующую задачу линейного программирования. В скалярном же случае решением задачи является взвешенная медиана узлов ломаной.  Библиогр.~26}
\abstracten{Text. Bibliogr.~26}

%%---Ключевые слова статьи на русском и английском языках
\keywords{кусочно-аффинные функции, ломаная, метод наименьших модулей, субдифференциал, гиподифференциал, взвешенная медиана}
\keywordsen{a comma delimited list of keywords}

%%---Если необходимо, указание на грантовую поддержку на русском и английском языках
\thanks{Результаты п.~3--5 получены в Институте проблем машиноведения РАН при финансовой поддержке Российского научного фонда (проект №~23--41--00060)}
\thanksen{The results of Sec. 3--5 were obtained in the Institute of Problems of Mechanical Engineering, Russian Academy of Sciences with the support of the Russian Science Foundation, project no. 23--41--00060.}

%%%%%-----Конец блока команд, заполняемых автором-----%%%%%%

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\0bf}{\mathbf{0}}
\DeclareMathOperator{\gipod}{\mathsf{d}\!}

\usepackage{tikz}

\begin{document}

\thispagestyle{empty}
\settitle
\paperhead

\section*{Введение}

Пусть заданы вектора $a_k\in \mathbb{R}^n$ и числа $b_k\in \mathbb{R}$, $k\in 1:s$.  Рассмотрим задачу поиска безусловного минимума
\begin{equation}\label{eq:1}
  \sum_{k=1}^s | x^\top a_k -b_k| \longrightarrow \min_{x\in \mathbb{R}^n}.
\end{equation}
%Нетрудно заметить, что $f(x)$ непрерывная выпуклая кусочно-аффинная функция на всем пространстве~$\mathbb{R}^n$. Более того, функция~$f(x)$ ограничена снизу нулем и минимум в задаче~\eqref{eq:1} достигается, в общем случае в не единственной точке.

К проблеме минимизации суммы модулей от аффинных функций сводятся, например, такие прикладные задачи, как машинное обучение, линейный регрессионный анализ и  обработка измерительной информации с аномально большими ошибками (сбоями) \cite{MudrovRushko1983, Zuchovicki1962, AkimovMatasov2015, LakeevNoskov2012}, к которой метод наименьших модулей менее чувствительный, чем метод наименьших квадратов \cite{MudrovRushko1983, Gorelik2016, Tyrsin2020,TG_OML20230601}. К решению задачи минимизации выпуклой кусочно-аффинной функции может быть сведена проблема разрешимости интервальной системы линейных алгебраических уравнений (см. \cite{Shary1, Shary2}). Заметим, что и задачи с линейными ограничениями (типа равенств и/или неравенств) можно свести к задаче~\eqref{eq:1}. Для этого надо воспользоваться аппаратом точных штрафных функций (см. \cite{Eremin_1967, DMV_CNSA20151224, LNP_CNSA20140911}).

В работе производится исследование экстремальной задачи~\eqref{eq:1} задействовав аппарат конструктивного негладкого анализа~\cite{VFDMVN,DVFVLV1981, VFDRAM, LNP2007, DMV_CNSA20191112}. Так как целевая функция выпуклая, то для общего случая используется гиподифференциальное исчисление, для скалярного~--- субдифференциальное.

Статья организована следующим образом. В разделе~1 приводятся вспомогательные сведения из негладкого анализа. В разделах~2--4 дана формальная постановка задачи и ее решение в общем случае. Раздел~5 посвящен анализу скалярного случая.


\section{Вспомогательные сведения}

\subsection{Элементы негладкого анализа}
Приведем некоторые сведения из конструктивного негладкого анализа \cite{VFDRAM,LNP2007, DMV_CNSA20191112}. Начнем с основного понятия, связывающего классический (гладкий) анализ с недифференцируемой оптимизацией~--- производной по направлению.

Пусть функция~$f$ определена на открытом множестве $U\subset \mathbb{R}^n$. Положим $ S = \left\{ g\in \mathbb{R}^n \mid \|g\|=1   \right\}$.

\begin{definition}
  Говорят, что функция~$f$ \textit{дифференцируема в точке~$x_0\in U$ по направлению~$g\in S$}, если существует конечный предел
\begin{equation*}%\label{eq:diff}
  f'(x_0,g) = \lim_{\alpha \rightarrow +0} \frac{f(x_0+\alpha g)-f(x_0)}{\alpha}.
\end{equation*}
Величина $f'(x_0,g)$ называется \textit{производной функции~$f$ в точке~$x_0$ по направлению~$g$}.
\end{definition}

\begin{definition}
Говорят, что функция~$f$, заданная и конечная на~$U$, \textit{субдифференцируема} в точке~$x_0$, если ее приращение допускает представление
\begin{equation}\label{eq:subdiff}
  f(x_0+\Delta)- f(x_0) = \max_{v\in \partial f(x_0)} v^\top\Delta + o(\|\Delta\|),
\end{equation}
где $\partial f(x_0)\subset \mathbb{R}^n $~--- выпуклый компакт, $\frac{o(\|\Delta\|)}{\|\Delta\|} \longrightarrow 0 $ при $\Delta \longrightarrow \0bf$, знак~${}^\top$ обозначает транспонирование. Множество $\partial f(x_0)$ называется \textit{субдифференциалом} функции $f$ в точке~$x_0$.
\end{definition}





Из \eqref{eq:subdiff} следует, что у субдифференцируемой в точке~$x_0$ функции~$f(x)$  существуют производные по всем направлениям, и что справедлива формула
\begin{equation*}
    f'(x_0,g)
    = \max_{v\in \partial f(x_0)} v^\top g \qquad \forall g\in S.
  \end{equation*}

%\begin{example}
Нетрудно убедиться, что для дифференцируемой в точке~$x_0$ функции~$f(x)$ субдифференциал $\partial f(x_0)$ состоит из одного элемента $\{ f'(x_0) \}$.


\begin{definition}
Говорят, что функция~$f$, заданная и конечная на~$U$, \textit{гиподифференцируема в точке~$x \in U$}, если существует такой выпуклый компакт~$\gipod f(x)\subset \mathbb{R}\times\mathbb{R}^n$, что справедливы разложение в точке~$x$ вида
$$
f(x+\Delta)=f(x)+\max_{(\alpha,v)\in \gipod f(x)} \left[ \alpha +  v^\top\Delta \right]+o_x(\Delta),
$$
и равенство
$$
\max_{(\alpha,v)\in \gipod f(x)}  \alpha = 0.
$$
Здесь $\alpha\in \mathbb{R}$, $v\in \mathbb{R}^n$, $\frac{o_x(\gamma\Delta)}{\gamma} \longrightarrow 0$ при $\gamma \longrightarrow 0$ для всех~$\Delta\in \mathbb{R}^n$.
\end{definition}

Множество $\gipod f(x)$ называется \textit{гиподифференциалом} функции $f$ в точке~$x$. Элементы множества $\gipod f(x)$ называются \textit{гипоградиентами}.

\begin{definition}
Функция~$f$ называется \textit{непрерывно гиподифференцируемой} в точке~$x\in U$, если она гиподифференцируема в каждой точке некоторой окрестности~$U_x\subset U$ точки~$x$, и существует гиподифференциальное отображение $U_x \ni z \longmapsto \gipod f(z)$ непрерывное по Хаусдорфу в точке~$x$.
\end{definition}

Классы субдифференцируемых и гиподифференцируемых функций совпадают. Более того,  справедливо соотношение
$$
\partial f(x_0) = \Big\{ v\in \mathbb{R}^n \mid \left( \begin{smallmatrix}
                                                   0 \\
                                                   v
                                                 \end{smallmatrix}\right) \in   \gipod f(x_0)\Big\}.
$$
Но, в отличии от субдифференциала, непрерывные гиподифференциалы наиболее интересны с практической точки зрения в конструировании численных методов оптимизации. В частности, последние обладают непрерывным направлением спуска (подъема), аналогично градиентным методам в гладком случае.

Приведем основные формулы исчисления непрерывно гиподифференцируемых функций:
\begin{enumerate}
  \item Пусть функции $f_1$ и $f_2$ непрерывно гиподифференцируемы в точке~$x$. Тогда сумма этих функций непрерывно гиподифференцируема в этой точке, при этом
\begin{equation}\label{eq:giposum}
\gipod\,  (f_1+f_2)(x) = \gipod f_1(x)+ \gipod  f_2(x).
\end{equation}


  \item Пусть функция $f$ непрерывно гиподифференцируема в точке~$x$. Тогда при любом неотрицательном~$\lambda$ функция $\lambda f$ также непрерывно гиподифференцируема в этой точке, причем
\begin{equation}\label{eq:gipoprod}
\gipod\,  (\lambda f)(x) = \lambda \gipod f(x).
\end{equation}

\item Пусть функции~$f_i(x)$, $i\in 1:s$ непрерывно гиподифференцируемы в точке~$x$. Тогда функция $f(x)=\max\limits_{i\in 1:s} f_i(x)$ непрерывно гиподифференцируема в этой точке. При этом гиподифференциал~$\gipod f(x)$ описывается следующим образом:
    \begin{equation}\label{eq:gipomax}
    \gipod  f(x) = \conv\Big\{ {f_i(x)-f(x)\choose \0bf_n}+\gipod f_i(x) \mid 1\leqslant i \leqslant s \Big\}.
    \end{equation}
\end{enumerate}

Здесь над гиподифференциалами определены операции \textit{сложения по Минковскому} и \textit{умножения на константу}, а именно
\begin{gather*}
W + V = \left\{ w+v \mid w\in W,\; v\in V \right\}, \\
  \lambda V = \left\{ \lambda v \mid v\in V \right\},
\end{gather*}
где $W$, $V$~--- выпуклые компакты в~$\mathbb{R}^n$, $\lambda$~--- вещественное число.

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

\begin{example}
Для произвольной непрерывно дифференцируемой на всем пространстве функции~$f$ в качестве непрерывного гиподифференциала можно взять
$$
\gipod  f(x) = \bigg\{ {0 \choose f'(x)}\bigg\}.
$$
\end{example}
\begin{example}
Пусть заданы $a\in \mathbb{R}^n$, $b\in \mathbb{R}$. Найдем гиподифференциал функции $f(x)=| x^\top a  - b|$. Заметим, что функцию $f(x)$ можно переписать следующим образом
$$
f(x)=\max\left\{x^\top a  - b, -(x^\top a  - b)\right\}.
$$
Тогда, используя формулу~\eqref{eq:gipomax} и предыдущий пример, получим
$$
\gipod  f(x)=
\conv\bigg\{ { x^\top a  - b - | x^\top a  - b| \choose a},{ -(x^\top a  - b) - | x^\top a  - b| \choose -a} \bigg\}.
$$
\end{example}





\begin{theorem}
Для того чтобы точка~$x_*$ была точкой минимума функции~$f(x)$ на~$\mathbb{R}^n$, необходимо, а в случае выпуклости~$f$ и достаточно, чтобы выполнялось неравенство
\begin{equation}\label{eq:2a}
f'(x_*,g) \geqslant 0 \quad \forall g\in S.
\end{equation}
\end{theorem}

Точка~$x_*$, для которой выполняется неравенство~\eqref{eq:2a}, называется \textit{стационарной точкой} функции~$f(x)$ на~$\mathbb{R}^n$.
\begin{theorem}
Условие стационарности равносильно включению
$$
\0bf_{n+1} \in \gipod f(x_*).
$$
\end{theorem}

\begin{remark}
Субдифференциальное исчисление и условие минимума формально имеет такой же вид, что и для гиподифференцируемых функций (см.~\eqref{eq:giposum}--\eqref{eq:gipomax}). Для этого в формулах необходимо заменить знак $\gipod$  на $\partial$ и учесть, что для функции $f(x)=\max\limits_{i\in 1:s} f_i(x)$ субдифференциал  $\partial f(x_0)$ вычисляется следующим образом:
$$
\partial f(x_0) = \conv \bigcup_{i\in I(x_0)} \partial f_i(x_0),
$$
где $I(x_0)=\left\{ i\in 1:s \mid f_i(x_0)= f(x_0) \right\}$.
\end{remark}


\subsection{Кусочно-аффинная функция} В работе \cite[п. 4.2]{Zalgaler_1997}, в частности, доказано утверждение, что непрерывная кусочно-аффинная функция представима в виде разности двух выпуклых кусочно-аффинных функций. В работах \cite{Melzer,Kripfganz,Gorokhovik_Zorko_1994,Gorokhovik_Zorko_2011} было показано, что любая кусочно-аффинная функция допускает аналитическое представление в виде суммы максимума и минимума от конечных семейств аффинных функций. В статье \cite{Angelov2016}, используя аппарат кодифференциального исчисления, реализованы алгоритмы представления кусочно-аффинной функции в указанном выше виде.

Покажем, что целевая функция задачи~\eqref{eq:1} является выпуклой кусо\-чно-аффинной функцией, а следовательно гиподифференцируемой. Для начала напомним несколько свойств связанных с функцией максимума:
\begin{equation}\label{eq:2}
  \big| g(x) \big| = \max\big\{ {-g(x)}, g(x) \big\},
\end{equation}
\begin{equation}\label{eq:3}
   h(x) + \max_{k\in 1:m} g_k(x) = \max_{k\in 1:m} \big\{ h(x) + g_k(x)\big\},
\end{equation}
\begin{gather}
  \big| g(x) \big| + \big| h(x) \big| = {}\notag \\
  {}=\max \big\{ -g(x)-h(x),g(x)-h(x),-g(x)+h(x),g(x)+h(x)\big\}. \label{eq:4}
\end{gather}

Применяя необходимое число раз равенство \eqref{eq:4}, сумму модулей можно представить в виде максимума от $2^s$ аффинных функций. В общем случае большинство функций под максимумом неактивные и их можно отбросить (см. \cite{Angelov2016, TG_OML2023}). Например, в скалярном случае их количество равно $s+1$. Выпуклость целевой функции следует из того, что поточечный максимум от выпуклых функций образует выпуклую функцию.

\section{Задача}
Используя аппарат гиподифференциального исчисления, исследовать
задачу поиска безусловного минимума
\begin{equation}\label{eq:6}
  f(x):=\sum_{j=1}^s | f_j(x)| \longrightarrow \min_{x\in \mathbb{R}^n},
\end{equation}
где $f_j(x)=x^\top a_j -b_j$, $j\in 1:s$.

Как было ранее замечено, целевая функция $f(x)$~--- непрерывная выпуклая кусочно-аффинная функция на всем пространстве~$\mathbb{R}^n$. Более того, функция~$f(x)$ ограничена снизу нулем, а минимум в задаче~\eqref{eq:6} достигается, в общем случае, не в единственной точке.

\section{Гиподифференциал целевой функции}

Гиподифференциал целевой функции складывается из гиподифференциалов $\gipod | f_j(x)|$, $j\in 1:s$. Используя результаты примера~2, имеем
$$
\gipod| f_j(x)| = \conv\bigg\{ { f_j(x) - | f_j(x)| \choose a_j},{ -f_j(x) - | f_j(x)| \choose -a_j} \bigg\}.
$$
Тогда искомый гиподифференциал функции $f(x)$ принимает вид
$$
\gipod f(x) = \sum_{j=1}^s \gipod| f_j(x)| =\sum_{j=1}^s\conv\bigg\{ { f_j(x) \choose a_j},{ -f_j(x)  \choose -a_j} \bigg\}-{ f(x) \choose \0bf_n}.
$$

Запишем общий вид гипоградиента $G$ из $\gipod f(x)$. Заметим, что любой элемент $G$ из $\gipod f(x)$ можно представить в виде
$$
G = \sum_{j=1}^s G_j-{ f(x) \choose \0bf_n},
$$
где $G_j$~--- соответствующие элементы из $\gipod| f_j(x)|$. Более того, имеем
$$
G_j(\lambda_j) = \lambda_j { f_j(x)  \choose a_j}+(1-\lambda_j){ -f_j(x)  \choose -a_j}
=(2\lambda_j-1){ f_j(x)  \choose  a_j},
$$
где $\lambda_j \in [0,1]$, $j\in 1:s$.

Положим $\mu_j=2\lambda_j-1$, $j\in 1:s$. Тогда получим общий вид гипоградиента $G\in \gipod f(x)$:
\begin{equation}\label{eq:7}
  G(\mu_1\ldots,\mu_s) =
  \left(
  \begin{array}{c}
  \sum\limits_{j=1}^s\mu_j f_j(x) - f(x)\\
  \sum\limits_{j=1}^s\mu_j a_j
  \end{array}
  \right),
\end{equation}
где $\mu_j\in [-1,1]$, $j\in 1:s$. Таким образом, гиподифференциал целевой функции представим в виде
$$
\gipod f(x) = \conv\big\{
G(\mu_1\ldots,\mu_s) \mid \mu_j\in [-1,1],\; j\in 1:s
\big\}.
$$
%где $G(\mu_1\ldots,\mu_s)$ имеет вид \eqref{eq:7}.

\section{Критерий оптимальности}
Обозначим
$$
A = [a_1,\dots,a_s], \qquad
b= (b_1, \ldots, b_s ),\qquad
\mu= \left(
       \begin{array}{c}
         \mu_1 \\
         \vdots \\
         \mu_s \\
       \end{array}
     \right).
$$
Тогда \eqref{eq:7} примет вид
\begin{equation}\label{eq:8}
G(\mu) =
  \left(
  \begin{array}{c}
  (x^\top A - b)\mu - f(x)\\
  A\mu
  \end{array}
  \right).
\end{equation}


\begin{claim}
Для того чтобы точка~$x_*\in \mathbb{R}^n$ доставляла глобальный минимум в~задаче~\eqref{eq:6}, необходимо и достаточно, чтобы нашелся вектор~$\mu^*\in \mathbb{R}^s$ такой, что
\begin{equation}\label{eq:9}
  \left\{
    \begin{array}{l}
      -b\mu^* = f(x_*),\\
      A\mu^* = \0bf_n,\\
\mu^*_j\in [-1,1],\quad j\in 1:s.
    \end{array}
  \right.
\end{equation}
\end{claim}
\begin{proof}
В силу выпуклости целевой функции~$f(x)$, достаточно показать, что условие~\eqref{eq:9} равносильно включению (см. теорему~2)
\begin{equation}\label{eq:10}
\0bf_{n+1} \in \gipod f(x_*).
\end{equation}

Действительно, используя общий вид гипоградиента \eqref{eq:8}, включение~\eqref{eq:10} означает, что найдется такой вектор~$\mu^*\in \mathbb{R}^s$ с компонентами $\mu_j^*\in [-1,1]$, $j\in 1:s$, для которого $G(\mu^*)=\0bf_{n+1}$, т.~е.
$$
  \left\{
    \begin{array}{l}
      (x_*^\top A - b)\mu^* - f(x_*) = 0,\\
      A\mu^* = \0bf_n.
    \end{array}
  \right.
$$
Отсюда получаем систему~\eqref{eq:9}, если упростить первое уравнение, воспользовавшись вторым условием. \clmp
\end{proof}

Рассмотрим задачу линейного программирования
\begin{gather}
  -b\mu \longrightarrow \max,\notag\\
      A\mu = \0bf_n,\label{eq:11}\\
\mu_j\in [-1,1],\quad j\in 1:s.\notag
\end{gather}
Она имеет решение, т.~к. множество планов (точек, удовлетворяющих ограничениям задачи) образует непустой выпуклый компакт. Обозначим произвольное решение задачи~\eqref{eq:11} через $\widehat{\mu}$.

\begin{corollary}
Множество решений задачи~\eqref{eq:6} совпадает с множеством решений уравнения
\begin{equation}\label{eq:12}
 \sum_{j=1}^s | x^\top a_j -b_j| = -b\widehat{\mu}.
\end{equation}
\end{corollary}

\begin{claim}
Пусть $\widehat{\mu}$~--- некоторое решение задачи~\eqref{eq:11}. Все множество решений задачи~\eqref{eq:6} описывается следующей линейной системой
\begin{equation}\label{eq:13}
\left\{
  \begin{array}{ll}
    x^\top a_j - b_j\leqslant0 & \hbox{$\text{при}\; j\in I_{-}(\widehat{\mu})$}, \\
    x^\top a_j - b_j=0 & \hbox{$\text{при}\; j\in I_{0}(\widehat{\mu})$}, \\
    x^\top a_j - b_j\geqslant0 & \hbox{$\text{при}\; j\in I_{+}(\widehat{\mu})$}.
  \end{array}
\right.
\end{equation}
Здесь $I_{-}(\widehat{\mu})$, $I_0(\widehat{\mu})$, $I_{+}(\widehat{\mu})$~--- индексные множества, определяемые следующим образом:
\begin{gather*}
I_{-}(\widehat{\mu})=\left\{ j\in 1:s \mid \widehat{\mu}_j = -1 \right\},\quad I_{+}(\widehat{\mu})=\left\{ j\in 1:s \mid \widehat{\mu}_j = 1 \right\},\\
  I_0(\widehat{\mu})=\left\{ j\in 1:s \mid \widehat{\mu}_j\in (-1, 1) \right\}.
\end{gather*}
\end{claim}
\begin{proof}
Так как $\widehat{\mu}$~--- оптимальный план задачи~\eqref{eq:11}, то
$$
A\widehat{\mu} = \0bf_n.
$$
Умножим обе части этой системы слева на $x^\top$ и прибавим к \eqref{eq:12}, получим
$$
\sum_{j=1}^s | x^\top a_j -b_j| = (x^\top A -b)\widehat{\mu}.
$$
Отсюда следует, что
$$
\sum_{j=1}^s | x^\top a_j -b_j| = \sum_{j=1}^s ( x^\top a_j -b_j)\widehat{\mu},
$$
поэтому
$$
\left\{
  \begin{array}{ll}
    x^\top a_j - b_j\leqslant0, & \hbox{$\text{если}\; \widehat{\mu}=-1$}, \\
    x^\top a_j - b_j=0, & \hbox{$\text{если}\; |\widehat{\mu}|<1$}, \\
    x^\top a_j - b_j\geqslant0, & \hbox{$\text{если}\; \widehat{\mu}=1$}.
  \end{array}
\right.
$$
 \clmp
\end{proof}

\begin{remark}
Чтобы найти (частное) решение~$x_*$ задачи~\eqref{eq:6}, можно поступить так: последовательно решить две задачи линейного программирования, а именно,  сперва задачу~\eqref{eq:11}, а после~--- с нулевой целевой функцией при ограничениях~\eqref{eq:13}.
\end{remark}

\begin{remark}
В силу теории двойственности \cite{GavurinMalozemov,VFP_2020, TG_ShG_OML20221208} решения задач \eqref{eq:11} и \eqref{eq:6} тесно взаимосвязаны. Указанную связь используют современные методы решения задач линейного программирования, например, двойственный симплекс метод, метод внутренней точки.  Данные методы определяют одновременно решения прямой и двойственной задач, то есть достаточно решить подобным методом только \textit{одну} задачу~\eqref{eq:11} и на выходе будет пара $(\widehat{\mu}, x_*)$, где $x_*$~--- двойственные переменные, решение исходной задачи \eqref{eq:6}.
\end{remark}


\section{Скалярный случай}
Рассмотрим задачу минимизации непрерывной выпуклой ломаной (в форме Бернштейна)
\begin{equation}\label{equ:1b}
  f(x) = \sum_{k=1}^{s} a_k \big| x - t_k \big| \longrightarrow \min_{x\in \mathbb{R}},
\end{equation}
где $a_k>0$, $k\in 1:s$, $t_1,\ldots,t_s$~--- попарно различные узлы ломаной.

Применяя аппарат субдифференциального исчисления покажем, что решением задачи~\eqref{equ:1b} является взвешенная медиана. Заметим, что поиск взвешенной медианы занимает линейное время~\cite{bib:Malistov}. Другой подход к решению задачи~\eqref{equ:1b} рассмотрен в работе~\cite{TG_ShG_CNSA20210324}.

\begin{definition} (\cite[с.~255]{bib:cormen}) Пусть имеется конечный набор различных вещественных чисел $b_1, b_2, \ldots, b_s$, для которых заданы положительные веса ${w}_1,{w}_2, \ldots,{w}_s$. \textit{Взвешенной $($нижней$)$ медианой} называется элемент~$b_\ell$, удовлетворяющий неравенствам
$$
\sum_{k\, : \,  b_k<b_\ell} {w}_k < \tfrac12 A
%$$
\qquad
\text{и}
\qquad
%$$
\sum_{k\, : \,  b_k>b_\ell} {w}_k \leqslant \tfrac12 A,
$$
где $A={w}_1+{w}_2+\ldots+{w}_s$.
\end{definition}

Упорядочим пары $(t_k,a_k)$, $k=1:s$, по возрастанию первой компоненты. Получим последовательность
$$
({b}_1,{w}_1),\; ({b}_2,{w}_2),
\ldots, ({b}_s, {w}_s),
$$
где ${b}_1<{b}_2<\ldots<{b}_s$.

Целевая функция~$f(x)$ состоит из $s+1$ звена, а угловые коэффициенты её звеньев можно вычислить по следующим формулам:
$$
p_0=-\sum_{i=1}^{s} {w}_i,\qquad p_{\ell} = \sum_{j=1}^{\ell} {w}_j - \sum_{i=\ell+1}^{s} {w}_i, \quad \ell=1:s-1, \qquad p_s=\sum_{j=1}^{s} {w}_j.
$$
Эти формулы можно переписать компактнее. Введем $ {w}_0= {w}_{s+1}=0$. Тогда
\begin{equation}\label{equ:9}
  p_{\ell} = \sum_{j=0}^{\ell} {w}_j - \sum_{i=\ell+1}^{s+1} {w}_i, \quad \ell=0:s.
\end{equation}

Отметим, что точка минимума (если она не единственная, то крайняя слева на вещественной оси) характеризуется изменением угла наклона звена ломаной с отрицательного значения на неотрицательное, то есть $p_j<0$, а $p_{j+1}\geqslant 0$. Если же угловой коэффициент  звена ломаной изменяется с отрицательного на положительное значение, то глобальный минимум единственный.

Обозначим через $\ell^*\in 1:s$ индекс взвешенной медианы для набора точек $b_1, b_2, \ldots, b_s$ с весами ${w}_1,{w}_2, \ldots,{w}_s$, т.~е. $b_{\ell_*}$~--- взвешенная медиана и для набора узлов $t_1$, $t_2$, $\ldots, t_s$ с весами $a_1,a_2,\ldots,a_s$.

\begin{claim}
Взвешенная медиана набора узлов $t_1$, $t_2$, $\ldots, t_s$ с~весами
$a_1,a_2,\ldots,a_s$ доставляет глобальный минимум в задаче~\eqref{equ:1b}.
\end{claim}
\begin{proof}
Для доказательства утверждения достаточно показать, что на индексе $\ell^*\in 1:s$ (взвешенной медианы) выполняются неравенства:
\begin{eqnarray}
  p_{\ell^*-1}=\sum_{j=0}^{\ell^*-1} {w}_j - \sum_{i=\ell^*}^{s+1} {w}_i &<& 0, \label{eq:12a}
  \\
  p_{\ell^*}=\sum_{j=0}^{\ell^*} {w}_j - \sum_{i=\ell^*+1}^{s+1} {w}_i & \geqslant & 0. \label{eq:12b}
\end{eqnarray}

%\begin{figure}[h!]
%\begin{center}
%
%%\psset{unit=1cm, arrowscale=2}
%\begin{picture}(-2,-0.5)(2,3.5)
%\psline[arrows=->,arrowscale=2,linewidth=0.5pt](-2,0)(2,0)
%%\psline[arrows=->,arrowscale=2,linewidth=0.5pt](0,-0.5)(0,3.5)
%
%\psline[linewidth=1.5pt](-2,2.5)(-1,0.5)
%\psline[linewidth=1.5pt](-1,0.5)(1,0.5)
%\psline[linewidth=1.5pt](1,0.5)(2,2.5)
%
%\uput[r](-1.8,1.9){\scriptsize $p_0=-2$}
%\uput[u](0,0.5){\scriptsize $p_1=0$}
%\uput[l](1.6,1.5){\scriptsize $p_2=2$}
%
%\psline[linestyle=dashed](-1,-0.1)(-1,0.5)
%\psline[linestyle=dashed](1,-0.1)(1,0.5)
%
% \uput[d](-1,0){\footnotesize $\hat{b}_1$}
% \uput[d](1,0){\footnotesize $\hat{b}_2$}
%
%\end{picture}\qquad\qquad
%
%
%\psset{unit=1cm, arrowscale=2}
%\begin{picture}(-2.5,-0.5)(2.1,3.1)
%\psline[arrows=->,arrowscale=2,linewidth=0.5pt](-2.5,0)(2.1,0)
%%\psline[arrows=->,arrowscale=2,linewidth=0.5pt](0,-0.5)(0,3.5)
%
%\psline[linewidth=1.5pt](-2.5,3)(-2,1.5)
%\psline[linewidth=1.5pt](-2,1.5)(-1,0.5)
%\psline[linewidth=1.5pt](-1,0.5)(1,2.5)
%\psline[linewidth=1.5pt](1,2.5)(1.5,3.6)
%
%\uput[r](-2.3,2.5){\scriptsize $p_0=-3$}
%\uput[r](-1.8,1.3){\scriptsize $p_1=-1$}
%\uput[r](-0.5,1.0){\scriptsize $p_2=1$}
%\uput[l](1.2,3.1){\scriptsize $p_3=3$}
%
%
%
%\psline[linestyle=dashed](-2,-0.1)(-2,1.5)
%\psline[linestyle=dashed](-1,-0.1)(-1,0.5)
%\psline[linestyle=dashed](1,-0.1)(1,2.5)
%
% \uput[d](-2,0){\footnotesize $\hat{b}_1$}
% \uput[d](-1,0){\footnotesize $\hat{b}_2$}
% \uput[d](1,0){\footnotesize $\hat{b}_3$}
%\end{picture}
%\end{center}
%\par
%\fcaption{Рис. График ломаной $f(t)$ при m равное 2 и 3}
%\end{figure}


Вычислим субдифференциал целевой функции. Имеем
$$
\partial f(x)= \sum_{j=1}^s \partial f_j(x),
$$
где
$$
\partial f_j(x)=
\left\{
  \begin{array}{ll}
    \left\{w_j\right\}, & \text{если}\; x>b_j; \\
    \conv\left\{-w_j,w_j\right\}, & \text{если}\; x=b_j;\\
    \left\{-w_j\right\}, & \text{если}\; x<b_j.
  \end{array}
\right.
$$

Введем $N_{-}(x)$, $N_0(x)$, $N_{+}(x)$~--- индексные множества, определяемые следующим образом:
\begin{gather*}
N_{+}(x)=\left\{ j\in 1:s \mid  b_j < x \right\},\quad N_{-}(x)=\left\{ j\in 1:s \mid  b_j > x \right\},\\
N_0(x)=\left\{ j\in 1:s \mid  b_j = x \right\}.
\end{gather*}
Очевидно, что при наших предположениях $|N_{-}(x)|+|N_{+}(x)| + |N_{0}(x)|=s$ и множество~$N_{0}(x)$ либо пустое, либо одноэлементное.

Положим $S = \sum\limits_{j\in N_{+}(x)}w_j-\sum\limits_{j\in N_{-}(x)}w_j$. Тогда
\begin{equation}\label{equ:7}
\partial f(x)=
\left\{
  \begin{array}{ll}
    \{S\}, & \text{если}\; N_{0}(x)=\varnothing; \\
    \{S\} + \conv\left\{-w_k,w_k\right\}, & \text{если}\; N_{0}(x)=\{k\}.
  \end{array}
\right.
\end{equation}

Разберем подробно оба случая. Случай первый: $N_0(x)=\varnothing$. Значит, точка~$x$ не совпадает ни с одним из узлов ломаной, а тогда критерий оптимальности $0 \in \partial f(x)$  будет выполнен, если $S= 0$, т.~е.
\begin{equation}\label{equ:8}
\sum\limits_{j\in N_{+}(x)}w_j=\sum\limits_{j\in N_{-}(x)}w_j.
\end{equation}

Определим индекс $\ell_* \in N_{+}$, такой что
$$
b_{\ell^*} = \max\limits_{j\in N_{+}(x)}b_j.
$$
Ясно, что тогда $b_{\ell^*+1} = \min\limits_{j\in N_{-}(x)}b_j$. В итоге, в силу равенства \eqref{equ:8}, имеем выполнение неравенств \eqref{eq:12a} и \eqref{eq:12b} только для точек $x\in (b_{\ell^*}, b_{\ell^*+1})$. Это означает, что каждая точка $x$ из интервала $(b_{\ell^*}, b_{\ell^*+1})$ является взвешенной медианой, доставляющей глобальный минимум целевой функции.

Разберем второй случай. Пусть $N_{0}(x)=\{k\}$. Тогда критерий оптимальности будет выполнен, если
$$
0 \in \conv\left\{S-w_k,S+w_k\right\}.
$$
В силу положительности $w_j$, $j\in 1:s$, данное включение равносильно одной из следующих систем:
\begin{equation}\label{equ:10}
\left\{
  \begin{array}{ll}
    \sum\limits_{j\in N_{+}(x)}w_j-\sum\limits_{j\in N_{-}(x)}w_j - w_k< 0, \\
    \sum\limits_{j\in N_{+}(x)}w_j-\sum\limits_{j\in N_{-}(x)}w_j + w_k\geqslant 0,
  \end{array}
\right.
\end{equation}
или
\begin{equation}\label{equ:11}
\left\{
  \begin{array}{ll}
    \sum\limits_{j\in N_{+}(x)}w_j-\sum\limits_{j\in N_{-}(x)}w_j - w_k\leqslant 0, \\
    \sum\limits_{j\in N_{+}(x)}w_j-\sum\limits_{j\in N_{-}(x)}w_j + w_k> 0.
  \end{array}
\right.
\end{equation}

Выражения в левых частях этих систем, есть ни что иное, как угловые коэффициенты ломаной (см.~\eqref{equ:9}), которые в узле $b_k$ изменили знаки. Точнее, из \eqref{equ:10} имеем, что взвешенная нижняя медиана $b_{\ell_*}$ совпадает с~$b_k$, а из \eqref{equ:11}~---
$$
b_{\ell_*} =
\left\{
  \begin{array}{ll}
    b_k, & \text{если } S<w_k; \\
    b_{k-1}, & \text{если } S=w_k.
  \end{array}
\right.
$$
Таким образом, глобальный минимум целевой функции достигается в единственной точке~$b_k$, если $|S|\neq w_k$. Иначе, на отрезке $[b_{\ell_*},b_{\ell_*+1}]$, если $S+w_k=0$ или на отрезке $[b_{\ell_*-1},b_{\ell_*}]$, если $S-w_k=0$.

\clmp
\end{proof}

\begin{corollary}
Пусть $t_{*}$~--- взвешенная медиана для набора точек $t_1, t_2, \ldots, t_s$ с весами ${a}_1,{a}_2, \ldots,{a}_s$.  Тогда угловой коэффициент звена ломаной располагающего справа от взвешенной медианы вычисляется по формуле:
$$
p_{*} = \sum_{k\, : \,  t_k\leqslant t_{*}} w_k - \sum_{k\, : \,  t_k>t_{*}} w_k.
$$
Если $p_{*}>0$, то $t_{*}$~--- единственный глобальный минимум в задаче~\eqref{equ:1b}. Если $p_{*}=0$, то глобальный минимум достигается на точках из отрезка~$[t_{*},\widehat{t}]$, где $\widehat{t} = \min\limits_{t_j>t_*} t_j$.
\end{corollary}


\begin{thebibliography}{19}	%аргумент 9, если цитируется до 9 источников

\bibitem{MudrovRushko1983} Мудров В.И., Кушко В.Л. Методы обработки измерений: квазиправдоподобные оценки. М.: Радио и связь, 1983. 304~с.

\bibitem{Zuchovicki1962} Зуховицкий С.И. О приближении несовместной системы линейных уравнений по принципу минимизации суммы модулей всех уклонений. Докл. АН СССР, 1962, 143, №~5, С.~1030-1033.

\bibitem{AkimovMatasov2015} Акимов~П.~А., Матасов~А.~И. \emph{Итерационный алгоритм для $\ell_1$-аппрок\-симации в динамических задачах оценивания}~// Автоматика и телемеханика. 2015. №~5. С.~7--26.

\bibitem{LakeevNoskov2012} Лакеев~А.~В., Носков~С.~И. \emph{Метод наименьших модулей для линейной регрессии: число нулевых ошибок аппроксимации}~// Современные технологии. Системный анализ. Моделирование. 2012. №~2(34). С.~48--50.

\bibitem{Gorelik2016} Горелик~В.~А., Трембачева~О.~С., \emph{Решение задачи линейной регрессии с использованием методов матричной кopрекции в метрике $\ell_1$}~// Ж. вычисл. матем. и матем. физ. 2016. Т.~56, №~2. С.~202--207.

\bibitem{Tyrsin2020} Сурин~В.~А., Тырсин~А.~Н.  \emph{Применение обобщенного метода наименьших модулей в задачах обработки и анализа изображений}~// Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. 2020. №~2. С.~45-55. DOI~10.24143/2072-9502-2020-2-45-55.

\bibitem{TG_OML20230601} Тамасян~Г.~Ш. \emph{О диких точках}~// Семинар «O \& ML». Избранные доклады. 1 июня 2023~г. URL: http://oml.cmlaboratory.com/reps23.shtml\#0601 (дата обращения: 31.01.2024).

\bibitem{Shary1} Шарый~С.\:П. Сильная согласованность в задаче восстановления зависимостей при интервальной неопределенности данных~// Вычислительные технологии. 2017. Т.~22. \No~2. С.~150--172.


\bibitem{Shary2} Шарый~С.\:П., Шарая~И.\:А. Распознавание разрешимости интервальных уравнений и его приложения к анализу данных~// Вычислительные технологии. 2013. Т.~18. \No~3. С.~80--109.

\bibitem{Eremin_1967} Еремин~И.И. Метод <<штрафов>> в выпуклом
программировании~// Доклады АН СССР, 1967. Т.~143, №~4.
С.~748--751.

\bibitem{DMV_CNSA20151224} Долгополик~М.~В. \emph{Основы теории точных штрафных функций}~// Семинар «CNSA \& NDO». Избранные доклады. 24 декабря 2015~г.
    URL: http://cnsa.cmlaboratory.com/reps15.shtml\#1224 (дата обращения: 31.01.2024).

\bibitem{LNP_CNSA20140911} Полякова~Л.~Н \emph{Метод точных штрафнов: другой подход}~// Семинар «CNSA \& NDO». Избранные доклады. 11 сентября 2014~г. URL: http://cnsa.cmlaboratory.com/reps14.shtml\#0911 (дата обращения: 31.01.2024).

\bibitem{VFDMVN} Демьянов~В.\:Ф., Малоземов~В.\:Н. Введение в минимакс. М.: Наука, 1972. 368~с.

\bibitem{DVFVLV1981} Демьянов~В.\:Ф., Васильев~Л.\:В. Недифференцируемая оптимизация. М.: Наука, 1981. 384~с.

\bibitem{VFDRAM} Демьянов~В.~Ф., Рубинов~А.~М. \emph{Основы негладкого анализа и
квазидифференциальное исчисление.} М.: Наука, 1990. 432~с.

\bibitem{LNP2007} Полякова~Л.\:Н. Непрерывные методы безусловной минимизации гиподифференцируемых функций~// Вестник СПбГУ. Сер.~10, 2007. вып.~3. С.~71--81.

\bibitem{DMV_CNSA20191112} Долгополик~М.~В. \emph{О непрерывной кодифференцируемости}~// Семинар «CNSA \& NDO». Избранные доклады. 12 ноября 2019~г. URL: http://cnsa.cmlaboratory.com/reps19.shtml\#1112 (дата обращения: 31.01.2024).

\bibitem{Zalgaler_1997} Залгаллер В. А. \emph{О представлении функций нескольких переменных разностью выпуклых функций}~// Зап. научн. сем. ПОМИ. 1997. Т.~246. С.~36--65.

\bibitem{Melzer} Melzer~D. \textit{On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions}. In: Demyanov~V.~F., Dixon~L.~C.~W. (eds.) Quasidifferential Calculus, Springer: Berlin, Heidelberg. 1986. P.~118--134.

\bibitem{Kripfganz} Kripfganz~A., Schulze~R. \textit{Piecewise affine functions as a difference of two convex functions}~// Optimization. 1987. Vol.~18. No.~1. P.~23--29.

\bibitem{Gorokhovik_Zorko_1994} Gorokhovik~V.~V. Zorko~O.~I. Piecewise affine functions and polyhedral sets~// Optimization. 1994. Vol.~31. No.~3. P.~209--221.

\bibitem{Gorokhovik_Zorko_2011} Gorokhovik~V.~V. Geometrical and analytical characteristic properties of piecewise affine mappings // arXiv preprint: 1111.1389, 2011. URL: https://arxiv.org/pdf/1111.1389.pdf

\bibitem{Angelov2016} Ангелов~Т.\:А. Представление кусочно-аффинных функций в виде разности полиэдральных~// Вестник С.-Петербург. ун-та. Прикл. матем. Информ. Проц. упр. 2016. Т.~12. №~1.  С.~4--18. URL: http://cyberleninka.ru/article/v/predstavlenie-kusochno-affinnyh-funktsiy-v-vide-raznosti-poliedralnyh

\bibitem{TG_OML2023} Тамасян~Г.~Ш. \emph{О компактном представлении кодифференциала непрерывной ломаной заданной в форме Бернштейна}~// Семинар «O \& ML». Избранные доклады. 9 ноября 2023~г. URL: http://oml.cmlaboratory.com/reps23.shtml\#1109 (дата обращения: 31.01.2024).

\bibitem{GavurinMalozemov} Гавурин~М.\:К., Малоземов~В.\:Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛГУ, 1984. 176~с.

\bibitem{VFP_2020} Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: МЦНМО, 2020. 416 с.

\bibitem{TG_ShG_OML20221208} Тамасян~Г.~Ш., Шульга~Г.~С. \emph{К вопросу о минимизации выпуклой кусочно-аффинной функции}~// Семинар «O \& ML». Избранные доклады. 8 декабря 2022~г. URL: http://oml.cmlaboratory.com/reps22.shtml\#1208 (дата обращения: 31.01.2024).

\bibitem{bib:Malistov}  Малистов А. С. \emph{О поиске медианы массива за линейное время}~// Матем. просв., сер. 3, 21, МЦНМО, М., 2017, 265–270.

\bibitem{TG_ShG_CNSA20210324} Тамасян~Г.~Ш., Шульга~Г.~С. \emph{Быстрый алгоритм минимизации выпуклой ломаной}~// Семинар «CNSA \& NDO». Избранные доклады. 24 марта 2021~г. URL: http://cnsa.cmlaboratory.com/reps21.shtml\#0324 (дата обращения: 31.01.2024).

\bibitem{bib:cormen} Кормен~Т., Лейзерсон~Ч., Ривест~Р., Штайн~К. \emph{Алгоритмы. Построение и анализ}~// 3-е издание, Вильямс, 2013.



\end{thebibliography}

\end{document}
