Метод проекции градиента: Метод проекции градиента онлайн

Метода – проекция – градиент

Cтраница 1

Методы проекции градиента очевидно применимы к задачам дискретного оптимального управления; при этом вычисление производных осуществляется точно тем же способом, что и в случае метода возможных направлений. За подробностями мы отсылаем читателя к разд.  [1]

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

Однако для частных классов задач метод проекции градиента был предложен намного раньше. Эти частные классы выделяются тем, что задача проектирования, аналогичная задаче ( 11) – ( 13), оказывается более простой и решается привычными вычислительными методами.

 [3]

Примеры численного решения задач оптимального проектирования методами проекции градиента будут приведены в гл.  [4]

Показать, что выражения, определяющие множители Лагранжа в методе проекции градиента ( см. (2.64)) и методе, использующем критерий оптимальности ( см. (4.104)), совпадают.  [5]

Сравнивая (4.116) с выражением для множителей Лагранжа, используемым в методе проекции градиента ( см. (2.64)), получим, что эти два выражения совпадают.  [6]

Это направление впервые было предложено Розеном ( I960) в его методе проекции градиента и составляет основу непосредственного обобщения классической схемы наискорейшего спуска на задачу минимизации при линейных ограничениях.  [7]

J ( u) на множестве ИфЕт, близкий по своей идее к методу проекции градиента.  [8]

Результаты для случая ( I) показаны в табл. 3.3. Решения подзадачи получены с использованием того же метода проекции градиента, который использовался для внешней процедуры. Было замечено, что ограничение на смещение по 22 при угле нагрузки а90 близко к нарушению. Для обоих ограничений на смещение происходит выход на ограничение при а 0 и а 90 соответственно. В табл. 3.3 и 3.4 угол а дан в радианах, а величина байтах служит для контроля сходимости решений внутренних задач методом проекции градиента.  [9]

К сожалению, этот метод не обеспечивает заведомой сходимости даже в тех случаях, когда гарантирована сходимость как метода градиентного спуска, так и метода проекции градиента. Известный элементарный пример задачи одномерной минимизации х на положительной полуоси х 0 служит тому подтверждением.  [10]

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

диагональная весовая матрица, вообще говоря, задается в начале процесса проектирования и остается неизменной для всех итераций.  [11]

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

Хорошие результаты при решении этой задачи дает метод проектирования сопряженных градиентов. Этот метод отличается от изложенного ранее метода проекции градиента тем, что на множество u 0 проектируют не градиенты минимизируемой функции, а сопряженные градиенты.  [13]

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

методы проекции градиентов и другие методы, более подробно рассмотренные в следующей главе.  [14]

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

 [15]

Страницы:      1    2

“Метод проекции градиента (метод Розена) для решения задач нелинейного программирования”, Прикладная математика

КурсоваяПомощь в написанииУзнать стоимостьмоей работы

Список использованной литературы. Заключение. Приложения A. Приложения Б. Графоаналитический метод решения задачи условной оптимизации. Вычислительная часть2. 1. Метод проекции градиента (метод Розена). Введение. Графоаналитический метод решения задачи условной оптимизации. Теоретическая часть1. 1. Градиентные методы решения задач нелинейного программирования1. 1. 1. Метод проекции градиента… Читать ещё >

• Содержание
• Выдержка
• Литература
• Другие работы
• Помощь в написании

Содержание

• org/CreativeWork”>Введение
• 1. Теоретическая часть
  • 1. 1. Градиентные методы решения задач нелинейного программирования
    • 1. 1. 1. Метод проекции градиента (метод Розена)
  • 1. 2. Графоаналитический метод решения задачи условной оптимизации
• 2. Вычислительная часть
  • 2. 1. Метод проекции градиента (метод Розена)
  • 2. 2. Графоаналитический метод решения задачи условной оптимизации
• org/CreativeWork”>Заключение
• Список использованной литературы
• Приложения A
• Приложения Б

Метод проекции градиента (метод Розена) для решения задач нелинейного программирования (реферат, курсовая, диплом, контрольная)

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

Показать весь текст

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

1. Кузнецов Ю. Н. и др. Математическое программирование. Учеб. пособие для вузов. М.: «Высш. школа». 1976. 352 с.
2. Д. Химмельблау. Прикладное нелинейное программирование. Перевод с англ. И. М. Быховской, Б. Т. Вавилова. Под ред. М. Л. Быховского. М.: Изд-во «Мир», 1975. 534 с.
3. Методические указания к курсовой работе по дисциплине Методы оптимизации для студентов дневной формы обучения специальностей Прикладная математика, Системный анализ и управление / Сост. Ю. М. Бородавко Харьков: ХТУРЭ, 1999. 24 с.

Заполнить форму текущей работой

Скачать выдержку (⥥) html

Другие работы

Методы построения прогностических моделей

При некоторых значениях параметров и (величина описана ниже). Это — теоретическая модель. А практически известны исходные данные — набор пар чисел, где — значения независимой переменной (например, времени), а — значения зависимой переменной (например, индекса инфляции, курса доллара США, объема месячного производства или размера дневной выручки торговой точки). Предполагается, что переменные…

Реферат

Подробнее…

8 задач по математике

h2 — событие, состоящее в том, что конкурент не выпустит в продажу аналогичный товар,. h3, событие, состоящее в том. что конкурент выпустит в продажу аналогичный товар. Для определения вероятности события A применим формулу полной вероятности. A — событие, состоящее в том, что товар будет иметь успех; По условию задачи нам известны вероятности. P (a|h2)=0.52, p (a|h3)=0.2, p (h3)=0.62. Обозначим…

Контрольная

Подробнее…

5 программ по вычислительной математике

Function Seidel (n:integer; a: Matrix3x3; b: VectorStolbec3; var x: VectorStolbec3; e: Real) :Boolean; Данную задачу решим на языке программирования Pascal. VectorStolbec3= array of real; {Вектор-столбец свободных членов}. B, x: VectorStolbec3;{Вектор-столбец свободных членов}. Matrix3x3= array of array of real; {Матрица 3×3}. Код программы на языке Pascal: A: Matrix3x3;{Матрица 3×3}. Program…

Контрольная

Подробнее…

Изучение различных численных методов

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

Контрольная

Подробнее…

Описание и развитие бизнеса с помощью case-средств

В настоящее время предприятие часто рассматривается не просто как организационная структура, а как система взаимосвязанных бизнес-процессов, направленных на достижение определенных целей. Организация бизнеса на принципиально новой основе дает возможность решить ряд важнейших для конкурентного предприятия задач — от сокращения непроизводительных расходов и наиболее полного использования ресурсов…

Дипломная

Подробнее…

9 задач по высшей математике

Таким образом, первоначальный ряд сходится (абсолютно) в интервале это и есть интервал сходимости данного ряда. Исследуем сходимость ряда на конце интервала сходимости. Область сходимости ряда: При x=-2,8 получаем ряд: Данный ряд сходится.

Контрольная

Подробнее…

8 Задач по теории вероятности и мат статистике

Все испытания независимы, то есть вероятность того, что каждая из нефтеразведок не зависит от того, успешными или нет были другие нефтеразведки. Очевидно, что случайная величина X подчиняется биномиальному закону распределения с параметрами n=6 и p=0. 2. Вероятность «успеха» постоянна и равна p=0.2. Вероятность «неудачи» q=1−0.2=0.8. Перечислим все возможные значения случайной величины X: 0, 1, 2…

Контрольная

Подробнее…

Курсовая работа по прикладной матматике. Препод. Кутернин. ГУУ 1 курс

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

Курсовая

Подробнее…

Прикладная математика

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

Учебник

Подробнее. ..

Модели целочисленного булевого программирования. Алгоритм последовательного анализа вариантов решения

Предположим, что любой коэффициент есть целое число (этого всегда можно добиться, выбрав правильный масштаб целевой функции при условии, что исходные значения коэффициентов заданы рациональными числами). Модели распределения капиталовложений часто можно представить в виде (1.1) (1.3). Кроме того, многие полностью целочисленные задачи можно преобразовать таким образом, чтобы каждая пере. Многие…

Курсовая

Подробнее…

18 задач по высшей математике

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

Контрольная

Подробнее. ..

5 задач по высшей математике

Поскольку угол между прямой и плоскостью есть угол между прямой и ее проекцией на плоскость, мы можем рассмотреть угол, дополняющий α до π/2. Это угол между нормалью к плоскости и АD. В качестве нормали возьмем векторное произведение AB и AC.

Контрольная

Подробнее…

Решение задач линейного программирования

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

Курсовая

Подробнее…

Курсовая работа по прикладной математике

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известны технологическая матрица, А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли. Получена задача на нахождение условного экстремума. Для ее решения систему неравенств (1) при помощи дополнительных неизвестных х5, х6, х7 заменим системой линейных…

Курсовая

Подробнее…

Методы градиентной проекции

— Руководство по NEOS

См. также: Ограниченная оптимизация Ограниченная оптимизация с ограничениями

Методы градиентного проекта — это методы решения связанных задач оптимизации с ограничениями . При решении задач оптимизации со связанными ограничениями методы активного набора подвергаются критике, поскольку рабочий набор изменяется медленно; на каждой итерации к рабочему набору добавляется или удаляется не более одного ограничения. Если в начальном \(W_0\) активно \(k_0\) ограничений, но в решении активно \(k_\theta\) ограничений, то требуется не менее \(| k_\theta – k_0 |\) итераций.

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

Алгоритм проецирования градиента является прототипом метода, позволяющего вносить большие изменения в рабочий набор на каждой итерации. При заданном \(x_k\) этот алгоритм выполняет поиск по кусочно-линейному пути

\[P[x_k – \alpha \nabla f(x_k)], \alpha \geq 0,\] где \(P\) — проекция на допустимое множество. Новая точка
\[x_{k+1} = P[x_k – \alpha_k \nabla f(x_k)]\] получается, когда найдено подходящее \(\alpha_k > 0\). Для задач со связанными ограничениями проекцию можно легко вычислить, установив
\[[P(x)]_i = \, mid \{x_i, l_i, u_i \},\] где mid\( \{ \cdot \}\) — средний (медианный) элемент множества. Поиск \(\alpha_k\) должен выполняться осторожно, так как функция
\[\phi(\alpha) = f(P[x_k – \alpha_k \nabla f(x_k)])\] только кусочно дифференцируема.

При правильной реализации метод проекции градиента гарантированно идентифицирует активное множество в решении за конечное число итераций. После определения правильного активного набора алгоритм проекции градиента сводится к алгоритму наискорейшего спуска на подпространстве свободных переменных. В результате этот метод неизменно используется в сочетании с другими методами с более высокой скоростью сходимости. 9С)\). Подобный подход используется в VE08 и PORT 3. В коде со связанными ограничениями в LANCELOT область доверия определяется нормой \(l_{\infty} \) и \(D_k = I\), что дает эквивалентная подзадача
\[\min \{ q_k(s) : \max (l-x_k, \Delta_ke \leq s \leq \min(u-x_k, \Delta_ke) \} \] где \(е\) — вектор всех единиц.

Преимущество стратегий, сочетающих метод проекции градиента с методами доверительной области, заключается в том, что рабочий набор может быстро изменяться, но в конечном итоге становится рабочим набором для решения. LANCELOT использует этот подход вместе со специальными структурами данных, использующими (групповую) частично разделимую структуру \(f\), для решения больших задач со связанными ограничениями.

Вариантные методы проекции градиента для задач минимизации

На этой странице

АннотацияВведениеПредварительные сведенияБлагодарностиСсылкиАвторское правоСтатьи по теме

Алгоритм проекции градиента играет важную роль в решении задач выпуклой минимизации с ограничениями. В общем случае алгоритм проекции градиента имеет лишь слабую сходимость в бесконечномерных гильбертовых пространствах. Недавно HK Xu (2011) представил два модифицированных алгоритма проецирования градиента, которые имеют сильную сходимость. Вдохновленные работой Сюй, в настоящей статье мы предлагаем три более простых варианта метода проекции градиента, чтобы гарантировать сильную сходимость.

1. Введение

Позвольте быть реальным гильбертовым пространством и непустым замкнутым и выпуклым подмножеством . Пусть    — вещественнозначная выпуклая функция. Теперь рассмотрим следующую задачу выпуклой минимизации с ограничениями: Предположим, что (1.1) непротиворечиво; то есть у него есть решение, и мы используем его для обозначения множества решений. Если дифференцируема по Фреше, то решает (1.1) тогда и только тогда, когда удовлетворяет следующему условию оптимальности: где обозначает градиент . Заметим, что (1.2) можно переписать в виде Это показывает, что минимизация (1.1) эквивалентна задаче с фиксированной точкой: где – произвольная константа, – ближайшая проекция точки из на . Используя это соотношение, алгоритм проекции градиента обычно применяется для решения задачи минимизации (1.1). Этот алгоритм генерирует последовательность через рекурсию: где начальная догадка выбирается произвольно и представляет собой последовательность размеров шагов, которые можно выбирать по-разному. Алгоритм проекции градиента (1.5) является мощным инструментом для решения задач выпуклой оптимизации с ограничениями и хорошо изучен в случае постоянных размеров шагов для всех .

Читатель может обратиться к [1–9]. Недавно он был применен для решения проблем о возможности разделения, которые находят применение в реконструкции изображений и лучевой терапии с модулированной интенсивностью (см. [10–17]).

Известно [3], что если имеет липшиц-непрерывный и сильно монотонный градиент, то последовательность может сильно сходиться к минимуму в . Если предполагается, что градиент только непрерывен по Липшицу, то он может быть слабо сходящимся только в том случае, если он бесконечномерен. Это естественно вызывает вопрос.

Вопрос 1. Как соответствующим образом модифицировать алгоритм проецирования градиента, чтобы иметь сильную сходимость?

Для этой цели недавно Сюй [18] впервые ввел следующую модификацию: где последовательности и удовлетворяют следующим условиям: (i), и ; (ii) и . Сюй [18] доказал, что последовательность сильно сходится к минимуму (1.1).

Примечание 1.1. Модификация Сюй (1.6) представляет собой выпуклую комбинацию алгоритма проекции градиента (1. 5) и самоотображения, которое обычно называют так называемым элементом вязкости.

В [18] Xu представил следующую модификацию: Следовательно, Сюй [18] доказал, что сильно сходится и алгоритм (1.7), к которому решается задача минимизации (1.1).

Примечание 1.2. Уравнение (1.7) включает дополнительные проекции, которые связывают метод проекции градиента (1.5) с так называемым методом CQ.

Следует отметить, что модификации Сюй (1.6) и (1.7) интересны и дают нам направление для решения (1.1) в бесконечномерных гильбертовых пространствах.

Руководствуясь работой Сюй, в настоящей статье мы предлагаем три варианта метода проекции градиента, чтобы гарантировать сильную сходимость для решения (1.1) в бесконечномерных гильбертовых пространствах. Наши мотивы в основном в двух отношениях.

Причина 1. Решение задачи минимизации (1.1) не всегда единственно, поэтому решений задачи может быть много. В этом случае особое решение (например, решение минимальной нормы) должно быть найдено среди возможных решений. Проблема минимальной нормы мотивирована следующим решением методом наименьших квадратов линейной обратной задачи с ограничениями: где – непустое замкнутое выпуклое подмножество вещественного гильбертова пространства, – ограниченный линейный оператор из в другое вещественное гильбертово пространство, – сопряженное к и – заданная точка в. Решение наименьших квадратов (1.8) есть минимизатор наименьших норм задачи минимизации: Некоторые родственные работы см. у Солодова и Свайтера [19].], Гебель и Кирк [20] и Мартинес-Янес и Сюй [21].

Причина 2. Проекционные методы широко используются в различных методах теории оптимизации. Помимо теоретического интереса, основным преимуществом проекционных методов, которое делает их успешными в реальных приложениях, являются вычислительные возможности (см. [22–31]). В этом отношении (1.7) особенно полезно. Но заметим, что в (1.7) участвуют два полупространства и . Если множества и достаточно просты, то и легко выполняются. Но может быть и усложнить, чтобы проекция не была легко выполнена. Это может серьезно повлиять на эффективность метода. Отсюда интересно, что можно расслабиться или из (1.7).

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

2. Предварительные сведения

Пусть – непустое замкнутое выпуклое подмножество вещественного гильбертова пространства . Отображение называется нерасширяющим, если Напомним, что проекция (ближайшей точки или метрики) из на , обозначаемая , ставит в соответствие каждой единственной точке со свойством Хорошо известно, что метрическая проекция на обладает следующими основными свойствами: (i) для всех ; (ii) для каждого ; (iii) для всех , . Далее мы принимаем следующие обозначения: (i) означает, что сильно сходится к ; (ii) означает, что слабо сходится к ; (iii) есть слабое -предельное множество последовательности .

Лемма 2. 1 (см. [32] (принцип полузамкнутости)). Позвольте быть замкнутым и выпуклым подмножеством гильбертова пространства, и пусть будет неэкспансивное отображение с . Если последовательность в слабо сходится к и сильно сходится к , то
В частности, если , то .

Лемма 2.2 (см. [33]). Позвольте быть замкнутым выпуклым подмножеством . Позвольте быть последовательностью в и . Если таков, что и удовлетворяет условию затем .

Лемма 2.3 (см. [34]). Предположим, что это последовательность неотрицательных действительных чисел, такая что где – последовательность в и – последовательность такая, что (1) ; (2) или . Тогда .

Лемма 2.4 (см. [35]). Пусть и будут ограниченными последовательностями в банаховом пространстве , и пусть будет последовательность в с Предполагать для всех, и Затем, .

3. Основные результаты

В этом разделе мы сформулируем и докажем наши основные результаты.

Теорема 3.1. Позвольте быть замкнутым выпуклым подмножеством реального гильбертова пространства. Пусть — вещественнозначная дифференцируемая по Фреше выпуклая функция. Предположим, что множество решений (1.1) непусто. Предположим, что градиент является -липшицевым. Позвольте быть -сокращение с . Пусть будет последовательность, сгенерированная следующим алгоритмом проекции гибридного градиента: где последовательности и удовлетворяют следующим условиям: (i) и ; (ii) и . Тогда последовательность, порожденная (3.1), сходится к минимизатору (1.1), который является единственным решением следующего вариационного неравенства:

Доказательство. Возьми любой . Поскольку решает задачу минимизации (1.1) тогда и только тогда, когда решает уравнение с неподвижной точкой для любого фиксированного положительного числа . Итак, у нас есть для всех. Его можно переписать как Из условия (ii) существуют две константы и такие, что при достаточно больших ; без ограничения общности можно считать для всех . Так как без ограничения общности можно считать, что для всех . Так, . Следовательно, не является экспансивным.
Из (3.1) получаем Таким образом, по индукции получаем, что Это указывает на то, что последовательность ограничена, как и последовательности и . Тогда мы можем выбрать такую ​​константу, что Далее оцениваем. В силу (3.1) имеем Тогда мы можем объединить последнее неравенство и лемму 2.3, чтобы заключить, что Теперь покажем, что слабый предел множества . Выберите любой . Тогда должна существовать подпоследовательность такая, что . В то же время действительная числовая последовательность ограничена. Таким образом, существует подпоследовательность, которая сходится к . Без ограничения общности можно считать, что . Обратите внимание, что . Так, . То есть как . Далее нам нужно только показать, что . Во-первых, из (3.8) имеем, что . Тогда у нас есть Так как , является неэкспансивным. Тогда из леммы 2.1 (принцип полузамкнутости) следует, что . Следовательно, из-за . Так, .
Наконец, докажем, что , где – единственное решение ВИ (3. 2). Во-первых, мы показываем, что . Заметим, что существует подпоследовательность удовлетворяющих Поскольку ограничено, существует подпоследовательность такой, что . Без ограничения общности считаем, что . Затем мы получаем Используя свойство (ii) функции , имеем Следует, что Из леммы 2.3, (3.11) и (3.13) получаем, что . Это завершает доказательство.

Из теоремы 3.1 сразу получаем следующую теорему.

Теорема 3.2. Позвольте быть замкнутым выпуклым подмножеством реального гильбертова пространства. Пусть — вещественнозначная дифференцируемая по Фреше выпуклая функция. Предполагать . Предположим, что градиент является -липшицевым. Пусть будет последовательность, сгенерированная следующим алгоритмом проекции гибридного градиента: где последовательности и удовлетворяют следующим условиям: (i) , и ; (ii) и . Тогда последовательность, порожденная (3.14), сходится к минимизатору (1.1), который является минимальным элементом нормы в .

Доказательство. В теореме 3.1 мы замечаем, что это несамостоятельное отображение из во все пространство . Следовательно, если мы выбрали для всех , то алгоритм (3.1) сводится к (3.14). И сильно сходится последовательность, к которой, очевидно, есть элемент минимальной нормы в . Доказательство завершено.

Далее мы предлагаем другой простой алгоритм для отбрасывания предположения .

Теорема 3.3. Позвольте быть замкнутым выпуклым подмножеством реального гильбертова пространства. Пусть — вещественнозначная дифференцируемая по Фреше выпуклая функция. Предполагать . Предположим, что градиент является -липшицевым. Пусть будет последовательность, сгенерированная следующим алгоритмом проекции гибридного градиента: где – константа, а последовательности удовлетворяют следующим условиям: (1) ; (2) . Тогда последовательность, порожденная (3.15), сходится к минимизатору (1.1), который является минимальным элементом нормы в .

Доказательство. Утверждение 1. Последовательность ограничена.
Возьми. Тогда у нас есть По индукции
Претензия 2. и .
Рассуждая так же, как в [18, стр. 366], мы можем написать где неэкспансивный и . Тогда мы можем переписать (3.15) в виде где Следует, что Так, Отсюда вместе с леммой 2.4 следует, что Таким образом, Обратите внимание, что Поэтому, Теперь, повторяя доказательство теоремы 3.1, заключаем, что .
Претензия 3. где – элемент минимальной нормы в .
Заметим, что существует подпоследовательность удовлетворяющих Поскольку ограничено, существует подпоследовательность такой, что . Без ограничения общности считаем, что . Затем мы получаем
Претензия 4. . Из (3.15) имеем Очевидно, что . Тогда мы можем применить лемму 2.3 к последнему неравенству, чтобы заключить, что . Доказательство завершено.

Далее мы предлагаем другой алгоритм с дополнительными проекциями, примененными к алгоритму проекции градиента. Покажем, что этот алгоритм имеет сильную сходимость.

Теорема 3.4. Позвольте быть замкнутым выпуклым подмножеством реального гильбертова пространства. Пусть — вещественнозначная дифференцируемая по Фреше выпуклая функция. Предполагать . Предположим, что градиент является -липшицевым. Позволять . Для и задайте последовательность следующим образом: где последовательность удовлетворяет условию . Тогда последовательность, порожденная (3.30), сходится к .

Доказательство. Очевидно, что выпукло. Для любого имеем Это подразумевает, что . Следовательно, . Из , мы имеем Так как у нас есть Итак, для имеем Следовательно, Отсюда следует, что оно ограничено.
Из и имеем Следовательно, и поэтому Это означает, что
Из (3.36) и (3.39) получаем По факту получаем Поэтому из (3.40) и (3.41) выводим Теперь (3.42) и лемма 2.1 гарантируют, что каждая слабая предельная точка является неподвижной точкой . То есть, . В то же время, если выбрать в (3.35), имеем Этот факт и лемма 2.2 обеспечивают сильную сходимость к . Это завершает доказательство.

Теперь мы дадим несколько замечаний по нашим вариантным методам проекции градиента.

Замечание 3.5. При одних и тех же параметрах управления все методы проекции градиента (3.1) и (1.6) являются сильно сходящимися. Однако (3.1), по-видимому, имеет больше преимуществ, чем (1.6), поскольку не является самоотображением.

Примечание 3.6. Метод проекции градиента (3.14) аналогичен (1.5) за счет использования вместо . Но (3.1) имеет сильную сходимость, и особенно (3.1) сильно сходится к минимальному элементу нормы .

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

Примечание 3.8. Метод проекции градиента (3.30) проще, чем (1.7).

Благодарности

Ю. Яо был частично поддержан NSFC 11071279 и NSFC 71161001-G0105. Ю.-К. Лю был частично поддержан NSC 100-2221-E-230-012. С.-Ф. Вен был частично поддержан NSC 100-2115-M-037-001.

Ссылки

1. Э. М. Гафни и Д. П. Берцекас, «Методы двухметрической проекции для оптимизации с ограничениями», SIAM Journal on Control and Optimization , vol. 22, нет. 6, стр. 936–964, 1984.

   Посмотреть по адресу:

   Сайт издателя | ученый Google | Zentralblatt MATH

2. П. Х. Каламаи и Дж. Дж. Море, «Методы прогнозируемого градиента для задач с линейными ограничениями», Mathematical Programming , vol. 39, нет. 1, стр. 93–116, 1987.

   Посмотреть по адресу:

   Сайт издателя | ученый Google | Zentralblatt MATH

3. Левитин Е.С., Поляк Б.Т. Методы минимизации с ограничениями. 6, нет. 5, pp. 1–50, 1966.

   Посмотреть по адресу:

   Google Scholar

4. Б. Т. Поляк, Introduction to Optimization , Optimization Software, New York, NY, USA, 1987.

   902

   A. Ruszczyński, Nonlinear Optimization , Princeton University Press, Princeton, NJ, USA, 2006.

5. C. Wang and N. Xiu, «Сходимость метода проекции градиента для обобщенной выпуклой минимизации», Computational Optimization и Приложения , том. 16, нет. 2, стр. 111–120, 2000.

   Посмотреть по адресу:

   Сайт издателя | ученый Google | Zentralblatt MATH

6. Н. Сю, К. Ван и Дж. Чжан, «Свойства сходимости методов проекции и сжатия для задач вариационного неравенства», Прикладная математика и оптимизация , том. 43, нет. 2, стр. 147–168, 2001.

   Посмотреть по адресу:

   Сайт издателя | ученый Google | Zentralblatt MATH

7. N. Xiu, C. Wang, and L. Kong, «Примечание о методе проекции градиента с точным правилом размера шага», Journal of Computational Mathematics , vol. 25, нет. 2, стр. 221–230, 2007.

   Посмотреть по адресу:

   Google Scholar | Zentralblatt MATH

8. М. Су и Х. К. Сюй, «Замечания по алгоритму проекции градиента», Журнал нелинейного анализа и оптимизации , том. 1, стр. 35–43, 2010.

   Просмотр по адресу:

   Google Scholar

9. Ю. Цензор и Т. Эльфвинг, «Алгоритм мультипроекции с использованием проекций Брегмана в пространстве продукта», Численные алгоритмы , том . 8, нет. 2–4, стр. 221–239, 1994.

   Посмотреть по адресу:

   Сайт издателя | ученый Google | Zentralblatt MATH

10. C. Byrne, «Единая обработка некоторых итерационных алгоритмов в обработке сигналов и реконструкции изображений», Обратные задачи , том. 20, нет. 1, стр. 103–120, 2004 г.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

11. Y. Censor, T. Elfving, N. Kopf, and T. Bortfeld, «Проблема о возможности разделения множественных наборов и ее приложения для обратных задач», Inverse Problems , vol. 21, нет. 6, стр. 2071–2084, 2005.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

12. Y. Censor, T. Bortfeld, B. Martin, and A. Trofimov, «Единый подход к проблемам инверсии в лучевой терапии с модулированной интенсивностью», Физика в медицине и биологии , вып. 51, нет. 10, стр. 2353–2365, 2006.

    Посмотреть по адресу:

    Сайт издателя | Google Scholar

13. Х.-К. Сюй, «Алгоритм Красносельского-Манна с переменными параметрами и проблема осуществимости с разделением множества наборов», , обратные задачи, , том. 22, нет. 6, стр. 2021–2034, 2006.

    Посмотреть по адресу:

    Сайт издателя | Google Scholar

14. Х. -К. Сюй, «Итерационные методы решения проблемы о разделенной допустимости в бесконечномерных гильбертовых пространствах», Обратные задачи , том. 26, нет. 10, ID статьи 105018, 2010 г.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

15. Г. Лопес, В. Мартин и Х.-К. Сюй, «Методы возмущения для неэкспансивных отображений с приложениями», Нелинейный анализ: приложения реального мира , том. 10, нет. 4, стр. 2369–2383, 2009.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

16. Г. Лопес, В. Мартин и Х. К. Сюй, «Итерационные алгоритмы для решения проблемы осуществимости разделения нескольких наборов», в Биомедицинская математика: перспективные направления в визуализации, планировании терапии и обратных задачах , Ю. Цензор, М. Цзян и Г. Ван, ред., стр. 243–279, Издательство медицинской физики, Мэдисон, Висконсин, США, 2009.

    Посмотреть по адресу:

    Google Scholar

17. Х.-К. Сюй, «Усредненные отображения и алгоритм проекции градиента», Journal of Optimization Theory and Applications , vol. 150, нет. 2, стр. 360–378, 2011.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt МАТЕМАТИКА

18. М. В. Солодов и Б. Ф. Свайтер, «Новый проекционный метод для задач вариационного неравенства», SIAM Journal on Control and Optimization , vol. 37, нет. 3, стр. 765–776, 1999.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

19. K. Goebel and WA Kirk, Topics in Metric Fixed Point Theory , vol. 28 из Кембриджских исследований по высшей математике , издательство Кембриджского университета, Кембридж, Великобритания, 1990.

    Посмотреть по адресу:

    Сайт издателя

20. К. Мартинес-Янес и Х.-К. Сюй, «Сильная сходимость метода CQ для итерационных процессов с фиксированной точкой», Нелинейный анализ: теория, методы и приложения , том. 64, нет. 11, стр. 2400–2411, 2006.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

21. H.-K. Сюй, «Итерационные алгоритмы для нелинейных операторов», Journal of the London Mathematical Society , том. 66, нет. 1, стр. 240–256, 2002.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

22. Т. Судзуки, «Теоремы сильной сходимости для бесконечных семейств нерасширяющих отображений в общих банаховых пространствах», Теория фиксированной точки и приложения , том. 2005, нет. 1, стр. 103–123, 2005 г.

    Посмотреть по адресу:

    Google Scholar | Zentralblatt MATH

23. С. Райх и Х.-К. Сюй, «Итеративный подход к задаче наименьших квадратов с ограничениями», Реферативный и прикладной анализ , вып. 8, стр. 503–512, 2003 г.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

24. А. Сабхарвал и Л. К. Поттер, «Выпукло ограниченные линейные обратные задачи: итерационные методы наименьших квадратов и регуляризация», IEEE Transactions on Signal Processing , vol. 46, нет. 9, стр. 2345–2352, 1998.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

25. HK Xu, «Итеративный подход к квадратичной оптимизации», Journal of Optimization Theory and Applications , vol. 116, нет. 3, стр. 659–678, 2003.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

26. F. Cianciaruso, G. Marino, L. Muglia и Y. Yao, «Алгоритм гибридной проекции для поиска решений смешанной задачи равновесия и проблемы вариационного неравенства», Fixed Point Theory and Applications , vol. . 2010, Артикул ID 383740, 19страницы, 2010.

    Посмотреть по адресу:

    Академия Google | Zentralblatt MATH

27. F. Cianciaruso, G. Marino, L. Muglia и Y. Yao, «О двухэтапном алгоритме для иерархических задач с фиксированной точкой и вариационных неравенств», Journal of Inequalities and Applications , vol. 2009 г., идентификатор статьи 208692, 13 страниц, 2009 г.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

28. Ю. Яо, Ю. Дж. Чо и Ю.-К. Лиу, «Алгоритмы общих решений для вариационных включений, смешанных задач равновесия и задач с неподвижной точкой», Европейский журнал операционных исследований , том. 212, нет. 2, стр. 242–250, 2011.

    Посмотреть по адресу:

    Сайт издателя | Google Scholar

29. Ю. Яо, Ю.-К. Лиоу и С.М. Канг, «Двухшаговые проекционные методы для системы задач вариационного неравенства в банаховых пространствах», Journal of Global Optimization . В прессе.

    Посмотреть по адресу:

    Сайт издателя | Google Scholar

30. Ю. Яо, Р. Чен и Ю.-К. Лиу, «Единый неявный алгоритм решения тройной иерархической задачи оптимизации с ограничениями», Математическое математическое и компьютерное моделирование , том. 55, стр. 1506–1515, 2012.

    Посмотреть по адресу:

    Сайт издателя | Google Scholar

31. Х. Х. Баушке и Дж. М. Борвейн, «Об алгоритмах проектирования для решения выпуклых задач осуществимости», SIAM Review , vol. 38, нет. 3, стр. 367–426, 1996.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

32. K. C. Kiwiel and B. Łopuch, «Методы суррогатных проекций для нахождения неподвижных точек твердо не расширяющих отображений», Журнал SIAM по оптимизации , том. 7, нет. 4, стр. 1084–1102, 1997.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

33. KC Kiwiel, “Эффективность методов субградиентной проекции для выпуклой оптимизации. I. Методы общего уровня», SIAM Journal on Control and Optimization , vol. 34, нет. 2, стр. 660–676, 1996.

    Посмотреть по адресу:

    Сайт издателя | ученый Google | Zentralblatt MATH

34. KC Kiwiel, “Эффективность методов субградиентной проекции для выпуклой оптимизации.