Журнал вычислительной математики и математической физики, 2019, T. 59, № 6, стр. 961-971

ВВЕДЕНИЕ

Пусть $X$ есть банахово пространство с нормой $\left\| {\, \cdot \,} \right\|$. Пусть выпуклая функция $E$ определена на $X$. Задача выпуклой оптимизации состоит в нахождении приближенного решения следующей задачи:

Следуя идеям работы [1], мы будем рассматривать задачу оптимизации в бесконечномерном пространстве. Это связано с тем, что в большинстве приложений пространство поиска хотя и является конечномерным, его размерность очень велика. Поэтому, так же как и в работе [1], наш интерес связан с получением оценок скорости сходимости алгоритмов, не зависящих от размерности пространства поиска. Очевидно, результаты для бесконечномерного банахова пространства предоставляют такие оценки скорости сходимости.

Многие проблемы в области машинного обучения могут быть сведены к задаче (1) с функцией потерь $E$ [2]. Во многих реальных приложениях необходимо, чтобы оптимальное решение $x{\kern 1pt} {\text{*}}$ задачи (1) имело простую структуру, например, представляло собой линейную комбинацию конечного числа элементов заданного множества (словаря $\mathcal{D}$ в $X$). Другими словами, $x{\kern 1pt} *$ должен быть разреженным по отношению к словарю $\mathcal{D}$ в $X$. Заметим, что требование разреженности можно заменить ограничением на кардинальность (то есть ограничением на количество элементов, используемых в линейных комбинациях элементов словаря $\mathcal{D}$ для построения приближенных решений задачи (1)). Тем не менее во многих случаях задачи оптимизации с ограничением на кардинальность являются задачами неполиномиальной сложности. По этой причине в реальных приложениях предпочитают использовать жадные алгоритмы, которые способны генерировать разреженные решения в силу своего дизайна.

Множество элементов $\mathcal{D}$ пространства $X$ называется словарем (см., например, [1]), если каждый элемент $g \in \mathcal{D}$ ограничен по норме единицей, $\left\| g \right\| \leqslant 1$, и замыкание линейной оболочки $\mathcal{D}$ совпадает с $X$, т.е. $\overline {\operatorname{span} \mathcal{D}} = X$. Словарь $\mathcal{D}$ называется симметричным, если $ - g \in \mathcal{D}$ для всякого $g \in \mathcal{D}$. Далее мы предполагаем, что словарь $\mathcal{D}$ является симметричным.

Нас интересует задача нахождения решений задачи (1), которые являются разреженными по отношению к словарю $\mathcal{D}$, т.е. мы рассматриваем задачу

где ${{\Sigma }_{m}}(\mathcal{D})$ есть множество всех $m$-членных полиномов по отношению к словарю $\mathcal{D}$: ${{\Sigma }_{m}}(\mathcal{D})$ = = $\left\{ {x \in X:x = \sum\nolimits_{g \in \Lambda } \,{{c}_{g}}g,\;\# (\Lambda ) = m,\;\Lambda \subset \mathcal{D}} \right\}$.

Одним из классов конструктивных методов для нахождения наилучших $m$-членных приближений является класс жадных алгоритмов. Жадные алгоритмы в силу своей конструкции способны находить разреженные решения по отношению к словарю $\mathcal{D}$. Возможно, метод Франк–Вульфа [3], который также известен как метод условного градиента [4], является одним из самых известных алгоритмов для нахождения оптимальных решений условных задач выпуклой оптимизации. В.Ф. Демьянов и А.М. Рубинов обобщили его на случай произвольных банаховых пространств [5]. Дальнейшее исследование алгоритмов типа Франк–Вульфа можно найти в работах [6]–[8]. В статье [8] приводятся прямые и двойственные результаты по сходимости алгоритмов типа Франк–Вульфа на основе применения идей двойственности, представленных в работе [6]. В последнее время были получены новые результаты по сходимости жадных алгоритмов [9]–[20].

Одной из задач вида (1) является проблема построения регрессии типа LASSO, в которой размер словаря является чрезвычайно большим и может расти экспоненциально по отношению к размерности исходного пространства. Поэтому, чтобы разработать алгоритм, имеющий полиномиальное время работы относительно размерности пространства, необходимо ввести дополнительные структурные ограничения и предположения. В работах [2], [21], [22] предполагается, что можно выполнить линейную оптимизацию по словарю за полиномиальное время по отношению к размерности задачи. Другим ключевым структурным ограничением является то, что целевая функция допускает разреженные приближенные решения. Подобный подход используется в работе [23], в которой применяется метод Франк–Вульфа для поиска равновесного распределения потоков в модели Бэкмана, при этом использование геометрической интерпретации транспортных потоков позволило авторам эффективно снизить размерность пространства поиска. Отметим также статью [24], в которой задача ранжирования объектов по значимости (PageRank) рассматривается как выпуклая задача минимизации над симплексом и, используя разреженную структуру задачи, предложено ее решение с использованием итерационных методов, которые на каждой итерации состоят из подзадач полиномиальной сложности. Необходимо упомянуть работу [25], в которой изучаются проблемы, в которых вспомогательная задача на шаге жадного спуска, являющаяся задачей оптимизации линейной формы на симплексе, может быть эффективно решена (т.е. предполагается наличие так называемого линейного минимизационного оракула).

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

• чебышёвский жадный алгоритм (Chebyshev greedy algorithm, CGA),

• слабый чебышёвский жадный алгоритм, (weak Chebyshev greedy algorithm, WCGA),

• слабый чебышёвский жадный алгоритм с ошибкой $\delta $, (weak Chebyshev greedy algorithm with error $\delta $, WCGA($\delta $)).

Прямой результат о сходимости алгоритма WCGA был получен в [1]. В данной работе мы докажем прямой результат о сходимости алгоритма WCGA($\delta $). Отметим, что в работе [1] показывается, что алгоритм WCGA для нахождения разреженных решений задачи (2) по отношению к словарю $\mathcal{D}$ также решает и задачу (1).

Развивая идеи [6] и [8], мы вводим понятие зазора двойственности для получения двойственных оценок сходимости алгоритмов WCGA и WCGA($\delta $) при нахождении разреженных решений задач выпуклой оптимизации типа (2). В статье мы находим оценки значений зазора двойственности в зависимости от числа итераций для рассматриваемых слабых жадных алгоритмов.

1. ЖАДНЫЕ АЛГОРИТМЫ

Для функционала $F \in X{\text{*}}$ и элемента $f \in X$ в данной статье мы будем использовать следующее обозначение $F(f) = \left\langle {F,f} \right\rangle $.

Пусть $\Omega : = \left\{ {x \in X:E(x) \leqslant E(0)} \right\}$ и предположим, что $\Omega $ ограничено. Будем предполагать, что функция $E$ дифференцируема по Фреше на $\Omega $. Из свойства выпуклости $E$ следует, что для произвольных $x,y \in \Omega $ справедливо неравенство

где $E{\kern 1pt} {\text{'}}(x)$ есть дифференциал Фреше функции $E$ в точке $x$.

Мы предполагаем, что существует элемент $x{\kern 1pt} {\text{*}}$ (не обязательно единственный) банахова пространства $X$, в котором достигается минимум $E{\kern 1pt} *: = E(x{\kern 1pt} *)$. Очевидно, что множество всех элементов, в которых достигается минимум, является выпуклым. Отметим, что минимум $E{\kern 1pt} {\text{*}}$ будет достигаться на элементе (или множестве элементов), принадлежащих множеству $\Omega $.

Пусть ${{A}_{1}}(\mathcal{D})$ означает замыкание (в $X$) выпуклой оболочки словаря $\mathcal{D}$.

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

Алгоритм 1 (CGA) есть итерационный алгоритм, предназначенный для решения задачи (2). Этот алгоритм на каждой итерации $m \geqslant 1$ переходит к следующему состоянию ${{G}_{m}}$ по индукции, используя текущее состояние ${{G}_{{m - 1}}}$ и элемент ${{\phi }_{m}}$, полученный на шаге выбора направления наискорейшего спуска жадного алгоритма. На этом шаге максимизируется некоторый линейный функционал, определенный градиентной информацией состояния, полученного на предыдущей итерации алгоритма. Алгоритм 1 является алгоритмом типа алгоритма Франк–Вульфа, так как в каждом текущем состоянии ${{G}_{{m - 1}}}$ он использует линеаризацию целевой функции $E$ и осуществляет движение в сторону элемента словаря $\mathcal{D}$, который минимизирует этот линейный функционал.

После того, как найден элемент ${{\varphi }_{m}}$ на шаге выбора направления наискорейшего спуска жадного алгоритма, осуществить переход в новое состояние ${{G}_{m}}$ из текущего состояния ${{G}_{{m - 1}}}$ можно разными способами. В частности, на практике часто используются такие разновидности жадного алгоритма, как градиентный метод, метод приведенного градиента, метод сопряженного градиента, методы преследования (см., например, [3], [26]–[28]). В алгоритмах 1–3 мы используем так называемый поиск типа Чебышёва и выбираем среди всех линейных комбинаций ${{\phi }_{i}}$, $i = 1,2,\; \ldots ,\;m$, такой элемент ${{G}_{m}}$ из ${\text{span}}\left\{ {{{\phi }_{i}}} \right\}_{{i = 1}}^{m}$, на котором достигается инфимум функции $E$.

Отметим, что на шаге выбора направления спуска жадного алгоритма мы ищем супремум среди элементов словаря $\mathcal{D}$ (а не замыкания его выпуклой оболочки ${{A}_{1}}(\mathcal{D})$), поскольку почти все точки множества ${{A}_{1}}(\mathcal{D})$ есть линейные комбинации бесконечного числа элементов словаря, и в связи с этим оптимальное решение, полученное таким образом, не обязано быть разряженным по отношению к словарю $\mathcal{D}$.

Для многих прикладных задач нахождение точного решения подзадачи $su{{p}_{{s \in \mathcal{D}}}}\left\langle { - E{\kern 1pt} {\text{'}}({{G}_{{m - 1}}}),s} \right\rangle $ на шаге выбора направления наискорейшего спуска жадного алгоритма может оказаться слишком сложным с вычислительной точки зрения (или даже невозможным). В связи с этим интерес представляет следующая модификация чебышёвского жадного алгоритма CGA с ослаблением требования нахождения оптимального решения [1], [19]. Пусть $\tau : = \left\{ {{{t}_{m}}} \right\}_{{m = 1}}^{\infty }$ будет последовательностью неотрицательных чисел ${{t}_{m}} \leqslant 1$, $m = 1,2,\; \ldots $, которую мы будем называть ослабляющей. Алгоритм 2 использует ослабляющую последовательность $\tau $ на шаге выбора направления наискорейшего спуска жадного алгоритма для нахождения приближенного решения ${{\phi }_{m}}$ этой подзадачи, который имеет качество приближения (мультипликативно) по меньшей мере ${{t}_{m}}$ на шаге $m$. Именно поэтому алгоритм называется слабым.

Далее, на шаге чебышёвского поиска Алгоритма 2 мы пытаемся решить задачу выпуклой оптимизации относительно переменных ${{\omega }_{i}}$, $i = 1, \ldots ,\;m$, с ошибкой $\delta $. В книге [29] приведены быстрые алгоритмы для приближенного решения такого рода задач (см. также [19]).

На шаге чебышёвского поиска Алгоритма 2 предполагается существование оптимальных значений ${{\omega }_{i}}$, $i = 1,\; \ldots ,\;m$. Однако Алгоритм 3 использует возможность приближенного решения, и данное предположение не требуется.

Алгоритмы используют один атом из словаря на каждой итерации, и поэтому гарантируют разреженность получаемых приближенных решений. Алгоритмы являются слабыми в том смысле, что они решают линейные задачи оптимизации на шаге выбора направления наискорейшего спуска приближенно. Более того, один из рассматриваемых в статье алгоритмов (WCGA($\delta $)) использует также приближенное решение на шаге чебышёвского поиска.

Статья [30] анализирует другую модификацию алгоритма WCGA – приближенный слабый чебышёвский жадный алгоритм (the approximate weak Chebyshev greedy algorithm, AWCGA). AWCGA проводит чебышёвский поиск с приближенным нахождением $n$-членного аппроксиманта, однако, в отличие от WCGA($\delta $), алгоритм AWCGA использует мультипликативный нормирующий функционал.

2. ПРЯМЫЕ ОЦЕНКИ

Модуль гладкости функции $E$ на ограниченном множестве $\Omega $ определяется следующим образом:

Функция $E$ называется равномерно гладкой на $\Omega $, если $\mathop {lim}\limits_{u \to 0} \rho (E,u){\text{/}}u = 0$.

Лемма 1 (см. [1, лемма 1.1]). Пусть $E$ дифференцируема по Фреше и выпукла на $\Omega $. Тогда для всех $x \in \Omega $

Следующая лемма приводится в [1] как лемма 2.2.

Лемма 2. Пусть $F$ есть ограниченный линейный функционал и пусть $\mathcal{D}$ есть словарь. Тогда

Обозначим

Используя геометрические свойства функции $E$, в статье [1] получена, в частности, следующая оценка скорости сходимости алгоритмов CGA, WCGA.

Теорема 1 (прямая оценка для CGA, WCGA). Пусть $E$ есть равномерно гладкая выпуклая функция с модулем гладкости $\rho (E,u) \leqslant \gamma {{u}^{q}}$, $1 < q \leqslant 2$. Тогда для ослабляющей последовательности $\tau = \left\{ {{{t}_{m}}} \right\}_{{m = 1}}^{\infty }$, $0 < {{t}_{m}} \leqslant 1$, $m = 1,2,\; \ldots $, для CGA (при ${{t}_{m}} = 1$, $m = 1,2,\; \ldots $) и WCGA справедлива оценка

где $C(E,q,\gamma )$ есть положительное число, не зависящее от $m$.

Заметим, что в статье [1] получена более общая оценка

где Неравенство (3) следует из (4), так как $x* \in {{\mathcal{L}}_{{{{A}_{0}}}}}$.

Лемма 3. Пусть неотрицательные числа ${{a}_{0}},{{a}_{1}},\; \ldots ,\;{{a}_{N}}$ таковы, что

для $m \leqslant K: = [{{\delta }^{{ - 1/q}}}]$, $q \in \left( {1,2} \right]$. Тогда

Лемма 4. Пусть $E$ есть равномерно гладкая выпуклая функция с модулем гладкости $\rho (E,u)$ on $\Omega $. Пусть ${{f}_{\epsilon }}$ принадлежит ${{\mathcal{L}}_{{{{A}_{\epsilon }}}}}$. Тогда для WCGA($\delta $) будет

для $m = 1,2,\; \ldots ,\;{{\delta }^{{ - 1/q}}}$.

Доказательство. Из определения ${{G}_{m}}$ в описании алгоритма WCGA($\delta $) мы имеем

Шаг чебышёвского поиска WCGA($\delta $) влечет Из леммы 1 следует, что Из шага выбора направления спуска WCGA($\delta $) имеем Из леммы 2 получаем

Возьмем $\omega = \lambda {{t}_{m}}A_{\epsilon }^{{ - 1}}$, получим

Из выпуклости $E$ имеем

Из (6)–(11) следует, что

Так как $E({{G}_{{m - 1}}}) \leqslant E(0)$, имеем ${{G}_{{m - 1}}} \in \Omega $. Наше предположение об ограниченности множества $\Omega $ приводит к тому, что существует константа ${{C}_{1}}$ такая, что $\left\| {{{G}_{{m - 1}}}} \right\| \leqslant {{C}_{1}}$. Так как ${{\phi }_{m}} \in \mathcal{D}$, получаем $\left\| {{{\phi }_{m}}} \right\| \leqslant 1$. Таким образом,

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

Теорема 2 (прямая оценка для WCGA($\delta $)). Пусть $E$ есть равномерно гладкая выпуклая функция с модулем гладкости $\rho (E,u) \leqslant \gamma {{u}^{q}}$, $1 < q \leqslant 2$. Тогда, для ослабляющей последовательности $\tau = \left\{ {{{t}_{k}}} \right\}_{{k = 1}}^{\infty }$, $0 < {{t}_{k}} \leqslant 1$, $k = 1,2,\; \ldots $, имеем для WCGA($\delta $)

где $C(E,q,\gamma )$ есть положительное число, не зависящее от $m$.

Доказательство. Докажем более общее неравенство

где $C(E,q,\gamma )$ есть положительное число, не зависящее от $m$. Неравенство (12) следует из (13), так как $x* \in {{\mathcal{L}}_{{{{A}_{0}}}}}$.

Неравенства (6) и (10) влекут неравенство

Так как $m \leqslant {{\delta }^{{ - 1/q}}}$, имеем и поэтому, ${{G}_{m}} \in {{\Omega }_{1}}: = \left\{ {x \in X:E(x) \leqslant E(0) + 1} \right\}$ для $m \leqslant {{\delta }^{{ - 1/q}}}$. Пусть ${{a}_{n}}: = E({{G}_{n}}) - E(f)$. Из леммы 4 следует, что Если ${{a}_{m}}$ неотрицательны, то мы применяем лемму 3 со значениями $\text{v} = {{t}_{m}}M_{0}^{{ - 1}}$ и $B = 2\gamma C_{0}^{q}$.

Обозначим $K: = [{{\delta }^{{ - 1/q}}}]$. Пусть $n{\text{'}}$ есть наименьшее из $\left[ {1,K} \right]$ таких, что ${{a}_{{n{\text{'}}}}} < 0$. Тогда из (14) и $m \leqslant {{\delta }^{{ - 1/q}}}$ следует, что ${{a}_{m}} \leqslant C{{m}^{{1 - q}}}$ для всех $n{\text{'}} \leqslant m \leqslant K$.

3. ЗАЗОР ДВОЙСТВЕННОСТИ И ДВОЙСТВЕННЫЕ ОЦЕНКИ

В данном разделе представлены двойственные результаты о сходимости для алгоритмов CGA, WCGA и WGAFR($\delta $).

Важной проблемой при выполнении вычислений при решении задач оптимизации является создание “сертификата”, который можно использовать для эффективной проверки того, что решение (с заданной точностью) получено. В статье [31] вводится понятие сертификатов в контексте вычислительных задач с выпуклой структурой. Методы, в которых имеются оценки на сертификат точности, относятся к классу прямо-двойственных методов [32]. Следует отметить, что сертификат точности (accuracy certificate), с одной стороны, позволяет обосновать прямо-двойственность исследуемого метода [31], а с другой, сертификат точности является вычислимым и поэтому могут использоваться в качестве оценки близости текущей точки к оптимальному решению. Дальнейшее развитие этих идей можно найти в работе [33]. В данной работе мы предлагаем в качестве такого сертификата “близости” к оптимальному решению использовать зазор двойственности.

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

Определение 1. Определим зазор двойственности для состояния $G \in \Omega $ и ошибки $\epsilon $ следующим образом:

Полезное свойство зазора двойственности описывается следующим утверждением.

Утверждение 1. Пусть $E$ есть выпуклая функция, определенная на банаховом пространстве $X$. Тогда для любого $x \in \Omega $ будет

Доказательство. Пусть ${{x}_{\epsilon }}$ таков, что $E({{x}_{\epsilon }}) - E(x{\kern 1pt} *) < \epsilon $ и ${{x}_{\epsilon }}{\text{/}}{{A}_{\epsilon }} \in {{A}_{1}}(\mathcal{D})$, т.е. ${{x}_{\epsilon }} \in {{\mathcal{L}}_{{{{A}_{\epsilon }}}}}$. Вначале покажем, что

Так как $E$ является выпуклой на $X$, для всякого $x \in \Omega $ будет

Так как ${{x}_{\epsilon }} \in {{\mathcal{L}}_{{{{A}_{\epsilon }}}}}$, имеем Так как ${{\mathcal{L}}_{{{{A}_{\epsilon }}}}} = {{A}_{\epsilon }}{{A}_{1}}(\mathcal{D})$, получаем где мы использовали утверждение леммы 2.

Тогда из (16)–(18) следует, что

и мы получаем наше утверждение (поскольку $E({{x}_{\epsilon }}) - E(x*) < \epsilon $).

Таким образом, практическая применимость зазора двойственности связана с тем фактом, что зазор двойственности $g(x)$ является оценкой ошибки приближения оптимального состояния $E(x{\text{*}})$ текущим состоянием $E(x)$.

Справедлив следующий двойственный результат для алгоритмов CGA и WCGA.

Теорема 3. Пусть $E$ есть равномерно гладкая выпуклая функция, определенная на банаховом пространстве $X$. Пусть $\rho (E,u)$ есть модуль гладкости функции $E$ и предположим, что $\rho (E,u) \leqslant \gamma {{u}^{q}}$, $1 < q \leqslant 2$. Пусть $\tau = \left\{ {{{t}_{m}}} \right\}_{{m = 1}}^{\infty }$, $0 < \theta < {{t}_{k}} < 1$, $k = 1,2, \ldots $, есть ослабляющая последовательность. Предположим, что CGA или WCGA выполнены для $N > 2$ итераций. Тогда найдется такая итерация $1 \leqslant \tilde {m} \leqslant N$, что

где $\beta > 0$ не зависит от $N$.

Имеет место следующий двойственный результат для алгоритма WCGA($\delta $).

Теорема 4. Пусть $E$ есть равномерно гладкая выпуклая функция, определенная на банаховом пространстве $X$. Пусть $\rho (E,u)$ есть модуль гладкости функции $E$ и предположим, что $\rho (E,u) \leqslant \gamma {{u}^{q}}$, $1 < q \leqslant 2$. Пусть $\tau = \left\{ {{{t}_{m}}} \right\}_{{m = 1}}^{\infty }$, $0 < \theta < {{t}_{k}} < 1$, $k = 1,2,\; \ldots $, есть ослабляющая последовательность. Предположим, что алгоритм WCGA($\delta $) выполнен для $0 < N \leqslant {{\delta }^{{ - 1/q}}}$ итераций. Тогда найдется такая итерация $1 \leqslant \tilde {m} \leqslant N$, что

где $\beta > 0$ не зависит от $N$.

Достаточно доказать двойственный результат для алгоритма с ошибкой WCGA($\delta $) (теорему 4) и тогда  теорема 3  будет  непосредственно следовать из соответствующего результата для WCGA($\delta $).

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

Лемма 5. Пусть $E$ есть равномерно гладкая выпуклая функция, определенная на банаховом пространстве $X$. Пусть $\rho (E,u)$ означает модуль гладкости функции $E$. Тогда для WCGA($\delta $) справедливо следующее неравенство:

где ${{C}_{0}}$ не зависит от $m$.

Доказательство. Из определения ${{G}_{m}}$ в описании алгоритма WCGA($\delta $) имеем

Шаг чебышёвского поиска для WCGA($\delta $) влечет Из леммы 1 следует, что Из шага выбора направления наискорейшего спуска алгоритма WCGA($\delta $) следует Возьмем $\omega = \lambda {{t}_{m}}A_{\epsilon }^{{ - 1}}$, тогда Используя (20) и определение зазора двойственности (15), имеем

Из (19), (21) и (22) следует, что

Из $E({{G}_{{m - 1}}}) \leqslant E(0)$ следует, что ${{G}_{{m - 1}}} \in \Omega $. Предположение ограниченности $\Omega $ приводит к тому, что найдется такая константа ${{C}_{1}}$, что $\left\| {{{G}_{{m - 1}}}} \right\| \leqslant {{C}_{1}}$. Так как ${{\phi }_{m}} \in \mathcal{D}$, имеем $\left\| {{{\phi }_{m}}} \right\| \leqslant 1$. Таким образом,

и лемма доказана.

Лемма 6. Пусть $0 < \mu < 1$ есть некоторое действительное число и пусть $M$ является натуральным числом. Тогда

где ${{\epsilon }_{m}}$ определено в (5) и ${{m}_{0}} = [\mu M]$.

Доказательство. Из (5) следует, что

Пусть $\epsilon {\kern 1pt} *: = \tfrac{\epsilon }{{{{\mu }^{{1 - q}}}}}$, т.е. $\epsilon {\kern 1pt} {\text{*}}{{\mu }^{{1 - q}}} = \epsilon $. Заметим, что ${{\mu }^{{1 - q}}} > 1$ и $\tfrac{\epsilon }{{{{\mu }^{{1 - q}}}}} < \epsilon $. Имеем Из (23) следует, что

Доказательство теоремы 4. Мы докажем более общее утверждение, следствием которого является утверждение теоремы: найдется такая итерация $1 \leqslant \tilde {m} \leqslant N$, что

где $\beta > 0$ не зависит от $N$. Из (13) следует, что Предположим, что для всех $[\mu N] \leqslant m \leqslant N$, $0 < \mu < 1$ ($\mu $ фиксировано и будет определено позже).

Из леммы 5 с $\lambda = {{\epsilon }_{m}}$ следует, что

Используя наше допущение (24), неравенство (25) может быть переписано в виде

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

1) $\theta \leqslant {{t}_{k}} \leqslant 1$, $k = 1,2,\; \ldots $;

2) ${{\epsilon }_{{{{m}_{0}}}}} \leqslant {{\mu }^{{1 - q}}}{{\epsilon }_{N}}$ (лемма 3);

3) так как $[\mu N] \leqslant m \leqslant N$, имеем ${{\epsilon }_{{[\mu N]}}} \geqslant {{\epsilon }_{m}} \geqslant {{\epsilon }_{N}}$.Тогда (26) дает

Если мы запишем цепь неравенств для всех $m = {{m}_{0}},\; \ldots ,\;N$, ${{m}_{0}}: = [\mu N]$, мы получим

Если взять достаточно большое $\beta $, то мы получим $E({{G}_{m}}) - E{\kern 1pt} * < 0$, что невозможно. Параметр $\mu $ можно взять таким, что

ЗАКЛЮЧЕНИЕ

Теоремы 1 и 2 дают оценки прямых ошибок приближения оптимального решения $E(x{\kern 1pt} *)$ текущим решением $E(G)$ для слабых чебышёвских жадных алгоритмов. Однако, так как для многих прикладных задач оптимальное значение $E(x{\kern 1pt} *)$ и константа $\gamma $ в модуле гладкости функции $E$ неизвестны, величина оценки ошибки приближения к оптимальному решению на текущей итерации $E(G) - E(x{\kern 1pt} *)$ неизвестна. Значение зазора двойственности $g(G)$, определенного в (15) и оценки которого получены в теоремах 3 и 4, вычисляется неявно на шаге выбора направления наискорейшего спуска на каждой итерации жадных алгоритмов WCGA или WCGA($\delta $) и является подходящей величиной для оценки прямой ошибки $E(G) - E(x{\kern 1pt} *)$, поскольку зазор двойственности есть верхняя оценка прямой ошибки (см. утверждение 1).