The 14 references with contexts in paper V. Krutikov N., Ya. Vershinin N., В. Крутиков Н., Я. Вершинин Н. (2016) “СУБГРАДИЕНТНЫЙ МЕТОД МИНИМИЗАЦИИ С КОРРЕКЦИЕЙ ВЕКТОРОВ СПУСКА НА ОСНОВЕ ПАР ОБУЧАЮЩИХ СООТНОШЕНИЙ // SUBGRADIENT MINIMIZATION METHOD WITH DESCENT VECTORS CORRECTION BY MEANS OF TRAINING RELATIONS PAIRS” / spz:neicon:vestnik-k:y:2014:i:1:p:46-54

1
Гилл, Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М. Райт. – М.: Мир, 1985. – 509 с.
Total in-text references: 4
  1. In-text reference with the coordinate start=1735
    Prefix
    Введение В связи с ростом приложений методов оптимизации в технике, экономике, управлении потребность в методах решения гладких и негладких задач минимизации большой размерности постоянно растет. Как отмечено в
    Exact
    [1]
    Suffix
    , метод сопряженных градиентов (МСГ) (см., например [1; 2]) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7].

  2. In-text reference with the coordinate start=1788
    Prefix
    Введение В связи с ростом приложений методов оптимизации в технике, экономике, управлении потребность в методах решения гладких и негладких задач минимизации большой размерности постоянно растет. Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например
    Exact
    [1; 2]
    Suffix
    ) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7].

  3. In-text reference with the coordinate start=22694
    Prefix
    Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным. В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ)
    Exact
    [1]
    Suffix
    , метода сопряженных градиентов (МСГ) [1, 2], алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжениемсжатием пространства (М2) [5; 7]. В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией.

  4. In-text reference with the coordinate start=22733
    Prefix
    Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным. В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ) [1], метода сопряженных градиентов (МСГ)
    Exact
    [1, 2]
    Suffix
    , алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжениемсжатием пространства (М2) [5; 7]. В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией.

2
Поляк, Б. Т. Введение в оптимизацию / Б. Т. Поляк. – М.: Наука. – 1983. –384 с.
Total in-text references: 2
  1. In-text reference with the coordinate start=1788
    Prefix
    Введение В связи с ростом приложений методов оптимизации в технике, экономике, управлении потребность в методах решения гладких и негладких задач минимизации большой размерности постоянно растет. Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например
    Exact
    [1; 2]
    Suffix
    ) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7].

  2. In-text reference with the coordinate start=22733
    Prefix
    Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным. В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ) [1], метода сопряженных градиентов (МСГ)
    Exact
    [1, 2]
    Suffix
    , алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжениемсжатием пространства (М2) [5; 7]. В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией.

3
Крутиков, В. Н. Новый релаксационный метод недифференцируемой минимизации / В. Н. Крутиков, Т. В. Петрова // Математические заметки ЯГУ. – 2001. – Т. 8. – Вып. 1. – С. 50 – 60.
Total in-text references: 12
  1. In-text reference with the coordinate start=2073
    Prefix
    В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ
    Exact
    [3; 6; 7]
    Suffix
    . В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7]. Имеющиеся на настоящий момент РСМ с растяжением пространства [4 – 7; 10], основываются на взвешенной обучающей информации, собранной на всей траектории минимизации.

  2. In-text reference with the coordinate start=2688
    Prefix
    Они соизмеримы по скорости сходимости на гладких функциях с квазиньютоновскими методами и эффективны при решении негладких задач овражного типа [4 – 7; 10]. В силу необходимости хранения и преобразования матриц их эффективность по затратам времени счета резко снижается на задачах высокой размерности. Существующие многошаговые РСМ
    Exact
    [3; 6 – 9]
    Suffix
    , не имеющие в своем составе матриц, используют незначительный объем памяти, необходимой для хранения, имеют незначительные вычислительные затраты на обслуживание итерации метода, что позволяет использовать их при решении большеразмерных задач, но при этом они существенно уступают в скорости сходимости субградиентным методам с растяжением пространства и подвержены зацикливанию на овражных з

  3. In-text reference with the coordinate start=3225
    Prefix
    использовать их при решении большеразмерных задач, но при этом они существенно уступают в скорости сходимости субградиентным методам с растяжением пространства и подвержены зацикливанию на овражных задачах негладкой оптимизации, что определяет актуальность их совершенствования на базе повышения объема используемой обучающей информации. Предлагаемый в работе РСМ, в отличие от метода из
    Exact
    [3]
    Suffix
    , для цели повышения эффективности алгоритма обучения, основан на использовании дополнительных обучающих соотношений на итерации. Отмеченное нововведение, сравнительно с методом из [3], обеспечивает более широкий диапазон решаемых задач негладкой оптимизации и более высокую скорость сходимости при решении гладких и негладких задач минимизации. 1.

  4. In-text reference with the coordinate start=3392
    Prefix
    Предлагаемый в работе РСМ, в отличие от метода из [3], для цели повышения эффективности алгоритма обучения, основан на использовании дополнительных обучающих соотношений на итерации. Отмеченное нововведение, сравнительно с методом из
    Exact
    [3]
    Suffix
    , обеспечивает более широкий диапазон решаемых задач негладкой оптимизации и более высокую скорость сходимости при решении гладких и негладких задач минимизации. 1. Постановка задачи Пусть решается задача минимизации выпуклой на Rnфункции )(xf.

  5. In-text reference with the coordinate start=4668
    Prefix
    Пусть nRG принадлежит некоторой гиперплоскости, а его ближайший к началу координат вектор )(G является также и ближайшим к началу координат вектором гиперплоскости. Тогда решение системы (, ) 1,sgg G является также решением и для (1). Его можно найти как решение системы [4 – 7] ( , ),0,1,..., ,1.iiisg y ik y (2) В
    Exact
    [3]
    Suffix
    (см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2).

  6. In-text reference with the coordinate start=5037
    Prefix
    см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов
    Exact
    [3; 6; 7]
    Suffix
    . В случае ортогональности векторов ig в (2) метод (3) на последовательности уравнений из (2) сходится не более чем за n итераций [6 – 7]. Можно построить метод решения системы уравнений (2) на последовательной ортогонализации векторов ig.

  7. In-text reference with the coordinate start=7771
    Prefix
    Метод (3) дает приближение 1ks, удовлетворяющее уравнению 1),(kgs, т. е. последнему по       , (,)0.(b) (,) , (,)0,(a) 211 1 1 1 kkk k kk k kkk kggеслиg g gg g gеслиgg p (5)      где 4. Положить 1kk. Перейти на пункт 2. Алгоритм А1 отличается от алгоритма решения неравенств на основе алгоритма Качмажа (обозначим его А0)
    Exact
    [3; 6; 7]
    Suffix
    реализацией пункта 3. В А0 вместо (4), (5) используется формула (3). Согласно (4), (5) равенство 1),(1kkgs выполняется всегда, а равенство 1),(11kkgs сохраняется в случае преобразования (5 b), что соответствует точному решению двух последних равенств из (2).

  8. In-text reference with the coordinate start=12937
    Prefix
    Если ki1, то перейти на пункт 2. 10. Если kkmqi, то перейти на пункт 2, иначе прейти на пункт 4. Алгоритм М1 отличается от известного метода 6; 7]. Пусть функцияnxxfR),( выпукла. Обознаминимизации
    Exact
    [3; 6; 7]
    Suffix
    , основанного на алгоритме речим d()ρ(()),(){R()()}zfxfxzDxfxn. Примечание 1. Для выпуклой на Rn функции, при ограниченности множества D()0x для точек ()0 * xDx , удовлетворяющих условию 0 d(*)dx шения неравенств А0 с формулой Качмажа (3) (назовем его М0), реализацией пункта 5, где вместо формул (4), (5) используется преобразование (3).

  9. In-text reference with the coordinate start=19619
    Prefix
    пунктов алгоритма М1 (9 или 10) произойдет обновление при некотором i = j, будет выполнено одно из неравенств (26), (27), где последний переход в неравенствах следует из определения величин 0E и 0M. Но (25) противоречит как (26), так и (27). Полученное противоречие доказывает теорему. 4. Реализация алгоритма минимизации Алгоритм М1 реализован согласно технике реализации РСМ
    Exact
    [3; 6; 7]
    Suffix
    . Рассмотрим версию алгоритма М1, включающую в себя процедуру одномерной минимизации вдоль направления s, функции которой заключаются в построении: а) текущего приближения минимума xm; б) точки y из окрестности xm, такой, что для )(1yfg выполняется неравенство (,)01gs.

  10. In-text reference with the coordinate start=23683
    Prefix
    Первый из них используется для решения неравенств в пункте 2, а второй – в пункте 3, для коррекции направления спуска с помощью формулы (3) с целью обеспечения необходимого условия 0),(1iigs возможности спуска в направлении (1is). Как показано в
    Exact
    [3; 4; 6;7]
    Suffix
    итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ [3; 4; 6; 7], нет теоретических рекомендаций по улучшению решения системы неравенств.

  11. In-text reference with the coordinate start=23913
    Prefix
    Как показано в [3; 4; 6;7] итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ
    Exact
    [3; 4; 6; 7]
    Suffix
    , нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится. Хотя обоснование сходимости идеализированных версий РСМ [3 – 10] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется c процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличивать

  12. In-text reference with the coordinate start=24635
    Prefix
    При этом минимальный шаг на итерации не может быть меньше некоторой доли начального шага, величина которой задана в (30) параметрами 1γq = 0.1 и γq = 0.2, приведенные значения которых использовались нами при расчетах. 5. Численный эксперимент Алгоритм М1 реализован согласно технике реализации алгоритма М0
    Exact
    [3; 6; 7]
    Suffix
    , в которой ключевое значение играют коэффициенты уменьшения 1mq и n 2) 22 * 22 1 * 0 ,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 fxkf   k  k  xx n  3) 1 22 311 1 ** 30 ( )[1000()(1) ], 0.0,(1,1,...,1),(0, 0,..., 0). n iii i fxx xx fxx        Функция )(3xf взята из [14].

4
Крутиков, В. Н. Релаксационный метод минимизации с растяжением пространства в направлении субградиента / В. Н. Крутиков, Т. В. Петрова // Экономика и мат. методы. – 2003. – Т. 39. – Вып. 1. – С. 33 – 49.
Total in-text references: 3
  1. In-text reference with the coordinate start=9965
    Prefix
    Тогда, для Для обоснования сходимости алгоритма А1 нам k0,1,2,... имеют место оценки: (,)01kkp, (8) (,)(,)kkkkgp. (9) Доказательство проведем по индукции. В силу равенства kkgp при 0k выполнено (9). Учипотребуется следующий результат. Лемма 2
    Exact
    [4, 6, 7]
    Suffix
    . Пусть множество G удовлетворяет предположению 1. Тогда sS()Gk , если ||kGR/1||. (14) В следующей теореме обосновывается конечная сходимость алгоритма А1. Отметим, что полученные оценки полностью эквивалентны оценкам для алгоритма А0.

  2. In-text reference with the coordinate start=23683
    Prefix
    Первый из них используется для решения неравенств в пункте 2, а второй – в пункте 3, для коррекции направления спуска с помощью формулы (3) с целью обеспечения необходимого условия 0),(1iigs возможности спуска в направлении (1is). Как показано в
    Exact
    [3; 4; 6;7]
    Suffix
    итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ [3; 4; 6; 7], нет теоретических рекомендаций по улучшению решения системы неравенств.

  3. In-text reference with the coordinate start=23913
    Prefix
    Как показано в [3; 4; 6;7] итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ
    Exact
    [3; 4; 6; 7]
    Suffix
    , нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится. Хотя обоснование сходимости идеализированных версий РСМ [3 – 10] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется c процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличивать

5
Крутиков, В. Н. Семейство релаксационных субградиентных методов с двухранговой коррекцией матриц метрики / В. Н. Крутиков, Т. А. Горская // Экономика и мат. методы. – 2009. – Т. 45. – No 4. – С. 37 – 80.
Total in-text references: 1
  1. In-text reference with the coordinate start=22867
    Prefix
    В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ) [1], метода сопряженных градиентов (МСГ) [1, 2], алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжениемсжатием пространства (М2)
    Exact
    [5; 7]
    Suffix
    . В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией. В методах М0, М1, МШ и М2 используется одна и та же процедура одномерной минимизации. Исследование проводилось на следующих функциях: 1) * 11 1 * 0 ||,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 n k k fxkf xx n     ({ ,, , , }; OMx wg f h {,,,,,}). ii iii ii ii ii fggh  

6
Крутиков, В. Н. Релаксационные методы безусловной оптимизации, основанные на принципах обучения: учебное пособие / В. Н. Крутиков. – Кемерово: Кузбассвузиздат, 2004. – 171 с.
Total in-text references: 10
  1. In-text reference with the coordinate start=2073
    Prefix
    В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ
    Exact
    [3; 6; 7]
    Suffix
    . В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7]. Имеющиеся на настоящий момент РСМ с растяжением пространства [4 – 7; 10], основываются на взвешенной обучающей информации, собранной на всей траектории минимизации.

  2. In-text reference with the coordinate start=4683
    Prefix
    Пусть nRG принадлежит некоторой гиперплоскости, а его ближайший к началу координат вектор )(G является также и ближайшим к началу координат вектором гиперплоскости. Тогда решение системы (, ) 1,sgg G является также решением и для (1). Его можно найти как решение системы [4 – 7] ( , ),0,1,..., ,1.iiisg y ik y (2) В [3] (см. также
    Exact
    [6; 7]
    Suffix
    ) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2).

  3. In-text reference with the coordinate start=5037
    Prefix
    см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов
    Exact
    [3; 6; 7]
    Suffix
    . В случае ортогональности векторов ig в (2) метод (3) на последовательности уравнений из (2) сходится не более чем за n итераций [6 – 7]. Можно построить метод решения системы уравнений (2) на последовательной ортогонализации векторов ig.

  4. In-text reference with the coordinate start=7771
    Prefix
    Метод (3) дает приближение 1ks, удовлетворяющее уравнению 1),(kgs, т. е. последнему по       , (,)0.(b) (,) , (,)0,(a) 211 1 1 1 kkk k kk k kkk kggеслиg g gg g gеслиgg p (5)      где 4. Положить 1kk. Перейти на пункт 2. Алгоритм А1 отличается от алгоритма решения неравенств на основе алгоритма Качмажа (обозначим его А0)
    Exact
    [3; 6; 7]
    Suffix
    реализацией пункта 3. В А0 вместо (4), (5) используется формула (3). Согласно (4), (5) равенство 1),(1kkgs выполняется всегда, а равенство 1),(11kkgs сохраняется в случае преобразования (5 b), что соответствует точному решению двух последних равенств из (2).

  5. In-text reference with the coordinate start=9965
    Prefix
    Тогда, для Для обоснования сходимости алгоритма А1 нам k0,1,2,... имеют место оценки: (,)01kkp, (8) (,)(,)kkkkgp. (9) Доказательство проведем по индукции. В силу равенства kkgp при 0k выполнено (9). Учипотребуется следующий результат. Лемма 2
    Exact
    [4, 6, 7]
    Suffix
    . Пусть множество G удовлетворяет предположению 1. Тогда sS()Gk , если ||kGR/1||. (14) В следующей теореме обосновывается конечная сходимость алгоритма А1. Отметим, что полученные оценки полностью эквивалентны оценкам для алгоритма А0.

  6. In-text reference with the coordinate start=12937
    Prefix
    Если ki1, то перейти на пункт 2. 10. Если kkmqi, то перейти на пункт 2, иначе прейти на пункт 4. Алгоритм М1 отличается от известного метода 6; 7]. Пусть функцияnxxfR),( выпукла. Обознаминимизации
    Exact
    [3; 6; 7]
    Suffix
    , основанного на алгоритме речим d()ρ(()),(){R()()}zfxfxzDxfxn. Примечание 1. Для выпуклой на Rn функции, при ограниченности множества D()0x для точек ()0 * xDx , удовлетворяющих условию 0 d(*)dx шения неравенств А0 с формулой Качмажа (3) (назовем его М0), реализацией пункта 5, где вместо формул (4), (5) используется преобразование (3).

  7. In-text reference with the coordinate start=19619
    Prefix
    пунктов алгоритма М1 (9 или 10) произойдет обновление при некотором i = j, будет выполнено одно из неравенств (26), (27), где последний переход в неравенствах следует из определения величин 0E и 0M. Но (25) противоречит как (26), так и (27). Полученное противоречие доказывает теорему. 4. Реализация алгоритма минимизации Алгоритм М1 реализован согласно технике реализации РСМ
    Exact
    [3; 6; 7]
    Suffix
    . Рассмотрим версию алгоритма М1, включающую в себя процедуру одномерной минимизации вдоль направления s, функции которой заключаются в построении: а) текущего приближения минимума xm; б) точки y из окрестности xm, такой, что для )(1yfg выполняется неравенство (,)01gs.

  8. In-text reference with the coordinate start=23683
    Prefix
    Первый из них используется для решения неравенств в пункте 2, а второй – в пункте 3, для коррекции направления спуска с помощью формулы (3) с целью обеспечения необходимого условия 0),(1iigs возможности спуска в направлении (1is). Как показано в
    Exact
    [3; 4; 6;7]
    Suffix
    итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ [3; 4; 6; 7], нет теоретических рекомендаций по улучшению решения системы неравенств.

  9. In-text reference with the coordinate start=23913
    Prefix
    Как показано в [3; 4; 6;7] итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ
    Exact
    [3; 4; 6; 7]
    Suffix
    , нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится. Хотя обоснование сходимости идеализированных версий РСМ [3 – 10] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется c процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличивать

  10. In-text reference with the coordinate start=24635
    Prefix
    При этом минимальный шаг на итерации не может быть меньше некоторой доли начального шага, величина которой задана в (30) параметрами 1γq = 0.1 и γq = 0.2, приведенные значения которых использовались нами при расчетах. 5. Численный эксперимент Алгоритм М1 реализован согласно технике реализации алгоритма М0
    Exact
    [3; 6; 7]
    Suffix
    , в которой ключевое значение играют коэффициенты уменьшения 1mq и n 2) 22 * 22 1 * 0 ,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 fxkf   k  k  xx n  3) 1 22 311 1 ** 30 ( )[1000()(1) ], 0.0,(1,1,...,1),(0, 0,..., 0). n iii i fxx xx fxx        Функция )(3xf взята из [14].

7
Крутиков, В. Н. Обучающиеся методы безусловной оптимизации и их применение / В. Н. Крутиков. – Томск: Изд-во Том. гос. пед. ун-та, 2008. – 264 с.
Total in-text references: 11
  1. In-text reference with the coordinate start=2073
    Prefix
    В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ
    Exact
    [3; 6; 7]
    Suffix
    . В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7]. Имеющиеся на настоящий момент РСМ с растяжением пространства [4 – 7; 10], основываются на взвешенной обучающей информации, собранной на всей траектории минимизации.

  2. In-text reference with the coordinate start=4683
    Prefix
    Пусть nRG принадлежит некоторой гиперплоскости, а его ближайший к началу координат вектор )(G является также и ближайшим к началу координат вектором гиперплоскости. Тогда решение системы (, ) 1,sgg G является также решением и для (1). Его можно найти как решение системы [4 – 7] ( , ),0,1,..., ,1.iiisg y ik y (2) В [3] (см. также
    Exact
    [6; 7]
    Suffix
    ) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2).

  3. In-text reference with the coordinate start=5037
    Prefix
    см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов
    Exact
    [3; 6; 7]
    Suffix
    . В случае ортогональности векторов ig в (2) метод (3) на последовательности уравнений из (2) сходится не более чем за n итераций [6 – 7]. Можно построить метод решения системы уравнений (2) на последовательной ортогонализации векторов ig.

  4. In-text reference with the coordinate start=7771
    Prefix
    Метод (3) дает приближение 1ks, удовлетворяющее уравнению 1),(kgs, т. е. последнему по       , (,)0.(b) (,) , (,)0,(a) 211 1 1 1 kkk k kk k kkk kggеслиg g gg g gеслиgg p (5)      где 4. Положить 1kk. Перейти на пункт 2. Алгоритм А1 отличается от алгоритма решения неравенств на основе алгоритма Качмажа (обозначим его А0)
    Exact
    [3; 6; 7]
    Suffix
    реализацией пункта 3. В А0 вместо (4), (5) используется формула (3). Согласно (4), (5) равенство 1),(1kkgs выполняется всегда, а равенство 1),(11kkgs сохраняется в случае преобразования (5 b), что соответствует точному решению двух последних равенств из (2).

  5. In-text reference with the coordinate start=9965
    Prefix
    Тогда, для Для обоснования сходимости алгоритма А1 нам k0,1,2,... имеют место оценки: (,)01kkp, (8) (,)(,)kkkkgp. (9) Доказательство проведем по индукции. В силу равенства kkgp при 0k выполнено (9). Учипотребуется следующий результат. Лемма 2
    Exact
    [4, 6, 7]
    Suffix
    . Пусть множество G удовлетворяет предположению 1. Тогда sS()Gk , если ||kGR/1||. (14) В следующей теореме обосновывается конечная сходимость алгоритма А1. Отметим, что полученные оценки полностью эквивалентны оценкам для алгоритма А0.

  6. In-text reference with the coordinate start=12937
    Prefix
    Если ki1, то перейти на пункт 2. 10. Если kkmqi, то перейти на пункт 2, иначе прейти на пункт 4. Алгоритм М1 отличается от известного метода 6; 7]. Пусть функцияnxxfR),( выпукла. Обознаминимизации
    Exact
    [3; 6; 7]
    Suffix
    , основанного на алгоритме речим d()ρ(()),(){R()()}zfxfxzDxfxn. Примечание 1. Для выпуклой на Rn функции, при ограниченности множества D()0x для точек ()0 * xDx , удовлетворяющих условию 0 d(*)dx шения неравенств А0 с формулой Качмажа (3) (назовем его М0), реализацией пункта 5, где вместо формул (4), (5) используется преобразование (3).

  7. In-text reference with the coordinate start=19619
    Prefix
    пунктов алгоритма М1 (9 или 10) произойдет обновление при некотором i = j, будет выполнено одно из неравенств (26), (27), где последний переход в неравенствах следует из определения величин 0E и 0M. Но (25) противоречит как (26), так и (27). Полученное противоречие доказывает теорему. 4. Реализация алгоритма минимизации Алгоритм М1 реализован согласно технике реализации РСМ
    Exact
    [3; 6; 7]
    Suffix
    . Рассмотрим версию алгоритма М1, включающую в себя процедуру одномерной минимизации вдоль направления s, функции которой заключаются в построении: а) текущего приближения минимума xm; б) точки y из окрестности xm, такой, что для )(1yfg выполняется неравенство (,)01gs.

  8. In-text reference with the coordinate start=22867
    Prefix
    В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ) [1], метода сопряженных градиентов (МСГ) [1, 2], алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжениемсжатием пространства (М2)
    Exact
    [5; 7]
    Suffix
    . В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией. В методах М0, М1, МШ и М2 используется одна и та же процедура одномерной минимизации. Исследование проводилось на следующих функциях: 1) * 11 1 * 0 ||,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 n k k fxkf xx n     ({ ,, , , }; OMx wg f h {,,,,,}). ii iii ii ii ii fggh  

  9. In-text reference with the coordinate start=23683
    Prefix
    Первый из них используется для решения неравенств в пункте 2, а второй – в пункте 3, для коррекции направления спуска с помощью формулы (3) с целью обеспечения необходимого условия 0),(1iigs возможности спуска в направлении (1is). Как показано в
    Exact
    [3; 4; 6;7]
    Suffix
    итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ [3; 4; 6; 7], нет теоретических рекомендаций по улучшению решения системы неравенств.

  10. In-text reference with the coordinate start=23913
    Prefix
    Как показано в [3; 4; 6;7] итерация (3) в (32) при 1),~(1iigs не ухудшает текущее приближения is~ решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда 1),~(1iigs, условие 0),~(1iigs выполнено и, согласно результатам работ
    Exact
    [3; 4; 6; 7]
    Suffix
    , нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится. Хотя обоснование сходимости идеализированных версий РСМ [3 – 10] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется c процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличивать

  11. In-text reference with the coordinate start=24635
    Prefix
    При этом минимальный шаг на итерации не может быть меньше некоторой доли начального шага, величина которой задана в (30) параметрами 1γq = 0.1 и γq = 0.2, приведенные значения которых использовались нами при расчетах. 5. Численный эксперимент Алгоритм М1 реализован согласно технике реализации алгоритма М0
    Exact
    [3; 6; 7]
    Suffix
    , в которой ключевое значение играют коэффициенты уменьшения 1mq и n 2) 22 * 22 1 * 0 ,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 fxkf   k  k  xx n  3) 1 22 311 1 ** 30 ( )[1000()(1) ], 0.0,(1,1,...,1),(0, 0,..., 0). n iii i fxx xx fxx        Функция )(3xf взята из [14].

8
Wolfe, P. Note on a method of conjugate subgradients for minimizing nondifferentiable functions / P. Wolfe // Math. Programming. – 1974. – V. 7. – No 3. – P. 380 – 383.
Total in-text references: 2
  1. In-text reference with the coordinate start=1962
    Prefix
    Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например [1; 2]) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ)
    Exact
    [8; 9]
    Suffix
    -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7]. В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7].

  2. In-text reference with the coordinate start=6634
    Prefix
    Чем шире окрестность, тем больше продвижение в направлении к экстремуму, выше устойчивость метода к ошибкам округления, помехам и способность преодоления малых локальных экстремумов. В этой связи особую важность приобретают изучаемые в работе методы минимизации, в которых, в отличие от метода из
    Exact
    [8]
    Suffix
    и его модификации [9], встроенные алгоритмы решения систем неравенств допускают использование субградиентов достаточно широкой окрестности текущего приближения минимума и не требуют точного одномерного спуска. 2.

9
Демьянов, В. Ф. Недифференцируемая оптимизация / В. Ф. Демьянов, Л. В. Васильев. – М.: Наука, 1972. – 368 с.
Total in-text references: 8
  1. In-text reference with the coordinate start=1962
    Prefix
    Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например [1; 2]) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ)
    Exact
    [8; 9]
    Suffix
    -субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7]. В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7].

  2. In-text reference with the coordinate start=1994
    Prefix
    Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например [1; 2]) является единственным универсальным средством решения подобных гладких задач. В работах [3 – 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] -субградиентного типа
    Exact
    [9]
    Suffix
    для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7]. В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7].

  3. In-text reference with the coordinate start=3764
    Prefix
    Постановка задачи Пусть решается задача минимизации выпуклой на Rnфункции )(xf. В РСМ последовательные приближения строятся по формулам: xiiiisx1, )(minargiiisxf, где направление спуска is выбирается как решение системы неравенств
    Exact
    [9]
    Suffix
    : (sggG,0),. (1) Здесь множество )(ixfG –  – субградиентное множество в точке ix. Обозначим S()G – множество решений (1), )()(0xfxf – субградиентное множество в точке x.

  4. In-text reference with the coordinate start=6653
    Prefix
    Чем шире окрестность, тем больше продвижение в направлении к экстремуму, выше устойчивость метода к ошибкам округления, помехам и способность преодоления малых локальных экстремумов. В этой связи особую важность приобретают изучаемые в работе методы минимизации, в которых, в отличие от метода из [8] и его модификации
    Exact
    [9]
    Suffix
    , встроенные алгоритмы решения систем неравенств допускают использование субградиентов достаточно широкой окрестности текущего приближения минимума и не требуют точного одномерного спуска. 2.

  5. In-text reference with the coordinate start=14121
    Prefix
    Отметим, что в силу условия точного одномерного спуска вдоль направления (1is) в пункте 7, в новой точке xi+1 вектор gi+1f(xi+1), такой, что (gi+1,si+1)  0, всегда существует согласно необходимому условию минимума одномерной функции (см., например,
    Exact
    [9, с. 287]
    Suffix
    ). Следовательно, с учетом роста индекса i в пункте 8, условие (gi,si)  0 пункта 4 всегда удовлетворяется. Доказательство сходимости метода М1 опирается на следующую лемму. Лемма 3 [9]. Пусть функция )(xf строго выпукла на nR, множество )(0xD ограничено, а последовательность  {}0kkx такова, что ()min(())1 k1[0,1]kkk fxfxxx    . справедлива оценка[9, с. 291], ,

  6. In-text reference with the coordinate start=14299
    Prefix
    направления (1is) в пункте 7, в новой точке xi+1 вектор gi+1f(xi+1), такой, что (gi+1,si+1)  0, всегда существует согласно необходимому условию минимума одномерной функции (см., например, [9, с. 287]). Следовательно, с учетом роста индекса i в пункте 8, условие (gi,si)  0 пункта 4 всегда удовлетворяется. Доказательство сходимости метода М1 опирается на следующую лемму. Лемма 3
    Exact
    [9]
    Suffix
    . Пусть функция )(xf строго выпукла на nR, множество )(0xD ограничено, а последовательность  {}0kkx такова, что ()min(())1 k1[0,1]kkk fxfxxx    . справедлива оценка[9, с. 291], , (18) f()0dDfx где D – диаметр множества 0(),inf ().n xR Dxff x   Дадим описание метода минимизации на основе алгоритма А1 для нахождения точек n xR  , так

  7. In-text reference with the coordinate start=14460
    Prefix
    Доказательство сходимости метода М1 опирается на следующую лемму. Лемма 3 [9]. Пусть функция )(xf строго выпукла на nR, множество )(0xD ограничено, а последовательность  {}0kkx такова, что ()min(())1 k1[0,1]kkk fxfxxx    . справедлива оценка
    Exact
    [9, с. 291]
    Suffix
    , , (18) f()0dDfx где D – диаметр множества 0(),inf ().n xR Dxff x   Дадим описание метода минимизации на основе алгоритма А1 для нахождения точек n xR  , таких, что 0)(Exd, где 00E.

  8. In-text reference with the coordinate start=17593
    Prefix
    Допустим, что утверждение теоремы неверно: предположим, что подпоследовательность zx ks, но при этом найдется такое Обозначим (()).SSfx Выберем 0δ, такое, что ()()  xSxSxf. (23) Такой выбор возможен в силу полунепрерывности сверху точечно-множественного отображения )(xf d00, что будет выполняться неравенство (21). Как (см.
    Exact
    [9, с. 289]
    Suffix
    ). Выберем номер K, такой, что при Kks будет справедливо: δ2()  zxSsk, и ранее зададим εсогласно (22). Выберем 0δ такое, что будет выполнено (23). В силу условий (28), найдется такое 0K, что при k>0K будет выполняться соотношение: max{,(00})dmxRkk. (29) Обозначим 00dE и 0M – наименьшее значение km при k>0K.

10
Шор, Н. З. Методы минимизации недифференцируемых функций и их приложения / Н. З. Шор. – Киев: Наукова думка, 1979. – 199 с.
Total in-text references: 5
  1. In-text reference with the coordinate start=2289
    Prefix
    В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 – 7]. Имеющиеся на настоящий момент РСМ с растяжением пространства
    Exact
    [4 – 7; 10]
    Suffix
    , основываются на взвешенной обучающей информации, собранной на всей траектории минимизации. Они соизмеримы по скорости сходимости на гладких функциях с квазиньютоновскими методами и эффективны при решении негладких задач овражного типа [4 – 7; 10].

  2. In-text reference with the coordinate start=2517
    Prefix
    Имеющиеся на настоящий момент РСМ с растяжением пространства [4 – 7; 10], основываются на взвешенной обучающей информации, собранной на всей траектории минимизации. Они соизмеримы по скорости сходимости на гладких функциях с квазиньютоновскими методами и эффективны при решении негладких задач овражного типа
    Exact
    [4 – 7; 10]
    Suffix
    . В силу необходимости хранения и преобразования матриц их эффективность по затратам времени счета резко снижается на задачах высокой размерности. Существующие многошаговые РСМ [3; 6 – 9], не имеющие в своем составе матриц, используют незначительный объем памяти, необходимой для хранения, имеют незначительные вычислительные затраты на обслуживание итерации метода, что позволяет использ

  3. In-text reference with the coordinate start=21804
    Prefix
    Получить направление спуска. 1 111 ,(,)1, (1( ,))/(,),( ,)1. iii i i iii iiii sеслиsg s sg sgggеслиsg         (32) 11 4. Произвести одномерный спуск вдоль 1/2 1111),(  wiiiisss: 1 параметр. Например, в РСМ с растяжением пространства
    Exact
    [4 – 7, 10]
    Suffix
    выбирается qm = 0.8. Для гладких функций выбор этого параметра некритичен и его можно брать из интервала [0.8 – 0.98]. От параметра возрастания шага скорость сходимости практически не зависит, поэтому его можно взять постоянным qM1.5.

  4. In-text reference with the coordinate start=22409
    Prefix
    Например, тестирование на негладких функциях малой размерности из [14], показало что алгоритмы М0 и М1 при n = 50 практически не уступают в скорости сходимости известному методу с растяжением пространства в направлении разности субградиентов
    Exact
    [10]
    Suffix
    . Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным.

  5. In-text reference with the coordinate start=22814
    Prefix
    В таблицах приведены результаты для квазиньютоновского метода с формулой BFGS (КНМ) [1], метода сопряженных градиентов (МСГ) [1, 2], алгоритма с растяжением пространства в направлении разности субградиентов (МШ)
    Exact
    [10]
    Suffix
    и алгоритма с растяжениемсжатием пространства (М2) [5; 7]. В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией. В методах М0, М1, МШ и М2 используется одна и та же процедура одномерной минимизации.

11
Kaczmarz, S. Approximate solution of systems of linear equations / S. Kaczmarz // Internat. J. Control. – 1993. – V. 54. – No 3. – P. 1239 – 1241.
Total in-text references: 1
  1. In-text reference with the coordinate start=4780
    Prefix
    Его можно найти как решение системы [4 – 7] ( , ),0,1,..., ,1.iiisg y ik y (2) В [3] (см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа
    Exact
    [11]
    Suffix
    (см. также [12]): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов [3; 6; 7].

12
Цыпкин, Я. З. Основы теории обучающихся систем / Я. З. Цыпкин. – М.: Наука, 1981. – 251 с.
Total in-text references: 1
  1. In-text reference with the coordinate start=4796
    Prefix
    Его можно найти как решение системы [4 – 7] ( , ),0,1,..., ,1.iiisg y ik y (2) В [3] (см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также
    Exact
    [12]
    Suffix
    ): . (,) 1(,) 1k kk kk kkg gg sg ss   (3) ступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов [3; 6; 7].

13
Крутиков, В. Н. Алгоритмы обучения на основе ортогонализации последовательных векторов / В. Н. Крутиков, Я. Н. Вершинин // Вестник КемГУ. – 2012. – Вып. 2(50). – С. 37 – 42.
Total in-text references: 3
  1. In-text reference with the coordinate start=5658
    Prefix
    несовместности систем равенств, возможной линейной зависимости векторов ig, значительных вычислительных затрат на ортогонализацию и необходимости хранения системы векторов, прямые методы полной ортогонализации для решения системы (2) неприемлемы. При определенных ограничениях на ошибки в (2) алгоритмы решения системы равенств с последовательной ортогонализацией векторов kg предложены в
    Exact
    [13]
    Suffix
    . В настоящей работе для решения системы неравенств (1) используется схема коррекции направления спуска на основе точного решения двух последних равенств из (2) для пары индексов kk,1, что реализуется посредством использования на каждой итерации ортогонализации пары векторов 1,kkgg с последующим применением (3).

  2. In-text reference with the coordinate start=7128
    Prefix
    Метод решения неравенств В излагаемом ниже алгоритме строятся последовательные приближения решения системы неравенств (1) посредством коррекции текущего приближения, обеспечивающей точное решение двух последних равенств типа (2), что реализовано с использованием последовательной ортогонализации пар векторов, предложенной в
    Exact
    [13]
    Suffix
    для решения систем равенств. Алгоритм А1. 1. Положить 0k, 01kg. Задать начальное приближение nRs0. 2. Выбрать произвольно Ggk, удовлетворяющий условию 0),(kkgs, если такого вектора не существует, то GSsk, закончить работу алгоритма. 3.

  3. In-text reference with the coordinate start=31554
    Prefix
    В силу того, что практически важную задачу минимизации, как правило, приходится решать многократно, то параметр mq можно предварительно подобрать экспериментально. Заключение В работе итерационный метод решения системы равенств, использующий на итерации коррекцию решения, обеспечивающую точное решение двух последних из них
    Exact
    [13]
    Suffix
    , распространен на задачу решения множества неравенств. Разработанный метод обоснован теоретически, получены оценки его скорости сходимости. На основе предложенного метода сформулирован и обоснован новый релаксационный субградиентный алгоритм минимизации, который пригоден для решения, в том числе и невыпуклых задач.

14
Скоков, В. А. Варианты метода уровней для минимизации негладких выпуклых функций и их численное исследование / В. А. Скоков // Экономика и математические методы. – 1997. – Т. 33. – No 1.
Total in-text references: 2
  1. In-text reference with the coordinate start=22243
    Prefix
    Проведенное тестирование алгоритма М1 на известных негладких и невыпуклых малоразмерных функциях свидетельствует о его работоспособности и достижении задаваемой точности. Например, тестирование на негладких функциях малой размерности из
    Exact
    [14]
    Suffix
    , показало что алгоритмы М0 и М1 при n = 50 практически не уступают в скорости сходимости известному методу с растяжением пространства в направлении разности субградиентов [10]. Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным.

  2. In-text reference with the coordinate start=24920
    Prefix
    эксперимент Алгоритм М1 реализован согласно технике реализации алгоритма М0 [3; 6; 7], в которой ключевое значение играют коэффициенты уменьшения 1mq и n 2) 22 * 22 1 * 0 ,0.0, 10 1010 (0, 0,..., 0),(10,,,...,); 23 fxkf   k  k  xx n  3) 1 22 311 1 ** 30 ( )[1000()(1) ], 0.0,(1,1,...,1),(0, 0,..., 0). n iii i fxx xx fxx        Функция )(3xf взята из
    Exact
    [14]
    Suffix
    . В таблицах 1 и 2 приведено количество затраченувеличения 1Mq начального шага одномерного ных методом вычислений функции и субградиента, спуска на итерации. Значения qm близкие к 1 обеспечивают малую скорость убывания шага и, соответственно, малую скорость сходимости метода.