Методы отсечений с обновлением аппроксимирующих множеств для задач нелинейного программирования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Яруллин, Рашид Саматович

• Яруллин, Рашид Саматович
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Яруллин, Рашид Саматович

Оглавление

Введение

1 Методы отсечений с использованием процедур аппроксимации допустимой области

1.1 Метод отсечений на основе аппроксимации допустимой области семейством опорных плоскостей без вложения погружающих множеств

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

1.3 Метод проектирования точки, использующий аппроксимирующие множества

1.4 Метод отсечений, допускающий параллельные вычисления

1.5 Численные эксперименты

2 Методы отсечений с аппроксимацией надграфика целевой

функции

2.1 Метод отсечений для отыскания дискретного минимакса с отбрасыванием секущих плоскостей

2.2 Метод отсечений с обновлением аппроксимирующих множеств, использующий обобщенно-опорные элементы

2.3 Модифицированный метод уровней

2.4 Метод отсечений и построение на его основе смешанных алгоритмов минимизаций

2.5 Численные эксперименты

3 Методы отсечений с одновременной аппроксимацией допустимой области и надграфика целевой функции

3.1 Метод с аппроксимацией области ограничений и надграфика

на основе обобщенно-опорных отсекающих плоскостей

3.2 Метод с аппроксимацией допустимой области и надграфика, использующий обновление погружающих множеств

3.3 Численные эксперименты

Заключение

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

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

Введение

Довольно часто в различных областях прикладной математики возникают оптимизационные задачи, которые решаются методами нелинейного программирования. В связи с этим разработка методов условной минимизации с удобной численной реализацией продолжает пользоваться вниманием специалистов в области математического программирования. К настоящему времени накоплено значительное число методов решения задач нелинейного программирования. Различные подходы к построению таких методов были предложены в [3] - [6], [11], [12], [17], [24] - [31], [33] - [42], [45] - [53|, [55] - [60], [62} - [66], [68], [72] - [78], [82] - [84], [86] - [92], [95] - [ 100], [103| - [110|, [112] -[117], [119], [124], [126], и этот перечень работ можно существенно расширить. Среди упомянутых — работы, посвященные построению методов минимизации выпуклых и невыпуклых, дифференцируемых и недифференцируемых функций. Сложилась и определенная классификация этих методов. Например, в отдельные классы выделились методы штрафных и барьерных функций, методы возможных направлений, методы типа линеаризации, квазиньютоновские методы, субградиентные и c-субградиентные методы, методы типа приведенных градиентов, методы центров и другие.

Известный и довольно широкий класс образуют методы отсечений, которые используются как для задач целочисленного программирования, так и для задач непрерывной оптимизации. Построению методов отсечений, предназначенных для решения задач целочисленного программирования, посвящены, например, работы [67], [69] - [71], [101], [111], [118], [120] - [123], [127|, [148] - [153]. Пожалуй, большее число работ посвящено методам отсечений для задач нелинейного программирования. Разные подходы к построению таких методов можно найти в [2], [7] - [10|, [13] - [15], [18] - [23|, [79| - [811, [102], [125], [161], [163].

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

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

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

Ранее в некоторых работах (см., напр., [1], [16], |21], |23], [160]) уделено внимание попытки решению проблемы отбрасывания накапливающихся отсечений в методах с аппроксимацией допустимой области. Так, в методе [21], где для построения аппроксимирующих множеств используются конусы обобщенно-опорных векторов, заложена возможность отбрасывания отсечений. Однако, сходимость этого метода обоснована только для сильно выпуклой целевой функции.

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

Наряду с уже упомянутыми известными методами отсечений существует значительное число алгоритмов этого класса, которые используют аппрокси-

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

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

Далее, в последнее время появилась возможность в объединении группы компьютеров в единую мощную вычислительную систему с целыо использования параллельных вычислений, которые значительно сокращают время решения задач. Возможность использования параллельных вычислений в некоторых методах математического программирования обоснована, например, в работах [32]. [43], [44], [93], [94]. В диссертации показано, что параллельные вычисления можно применять и в методах отсечений. Большинство предлагаемых в диссертации методов позволяют использовать параллельные вычисления при построении как вспомогательных, так и основных итерационных точек. Например, распараллеливание вычислений при нахождении основных итерационных точек в этих методах может происходить следующим образом. Различными алгоритмами параллельно строится некоторая совокупность вспомогательных точек, а затем из них в качестве итерационной точки выбирается рекордная.

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

В первой главе разрабатываются методы отсечений для решения задач нелинейного программирования и задачи отыскания проекции точки па вы-

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

В § 1.1 предлагается общий метод решения задачи

пни{./(■''} : .Г С />}, (0.0.1)

где }'{х) - непрерывная в п-мерном евклидовом пространстве Я,п функция, а множество I) С Яд выпукло и замкнуто.

Предлагаемый метод отсечений вырабатывает вспомогательную последовательность приближений {уг}. г К = {0,1,...}, и фиксирует основную итерационную последовательность {х^}, к Е К, в виде подпоследовательности {угк} последовательности {уг}. На ¿-ом шаге (у > 0) для построения точки у1 приближенно решается вспомогательная задача минимизации функции f(x) на аппроксимирующем область ограничений множестве Мг. Если точка ■уг в определенном смысле оказалась близка к множеству И, то фиксируются номер г = '/д- и точка :с/с = у1к, и происходит обновление аппроксимирующего множества Мг = М1к. В противном случае считается, что качество аппроксимации области Б множеством Мг является неудовлетворительным, и на основе Мг строится очередное аппроксимирующее множество М+1 путем отсечения от Мг точки у.ь с использованием обобщенно-опорных элементов. Далее в множестве Мг+\ указанным выше способом находится очередное приближение уг+] вспомогательной последовательности.

В том же параграфе приведено сравнение предложенного метода с идейно близким методом опорных множеств [21], построенным для задачи (0.0.1) с выпуклой целевой функцией ¡{х). Принципиальное отличие предложенного метода от метода [21] состоит в том, что в нем заложен критерий оценки качества аппроксимирующего множества, позволяющий вводить процедуры обновления погружающих множеств за счет периодического отбрасывания любого числа любых отсекающих плоскостей.

Далее, в § 1.2 предлагается метод отсечений для решения задачи (0.0.1),

в которой область ограничений имеет более общий вид:

П = 0'[)0", (0.0.2)

где В\ В" - выпуклые замкнутые в Яп множества, причем второе из них может заведомо иметь пустую внутренность.

Метод отличается от разработанного в § 1.1 метода, в частности, способами построения аппроксимирующих множеств. А именно, погружающее множество Мг+1 строится путем отсечений от Мг точки уг плоскостями, построенными с помощью субградиентов функции, определяющей множество В'. Кроме того, в этом методе по сравнению с предыдущим предусмотрены более широкие возможности для выбора итерационных точек основной последовательности. За счет этих возможностей допустимо построение на основе этого метода отсечений некоторых смешанных алгоритмов. Сходимость таких смешанных алгоритмов будет гарантирована сходимостью предложенного метода отсечений. Метод из § 1.2 характерен тем, что также предусматривает возможность периодического обновления аппроксимирующих множеств на тех итерациях, где качество аппроксимирующего множества становится удовлетворител ьны м.

В § 1.3 главы 1 предлагается метод отсечений для нахождения проекции точки у 6 Яп на выпуклое множество О. заданное в виде (0.0/2). На каждой итерации метода определенным образом строится многогранное множество, аппроксимирующее область О', и приближение получается путем проектирования точки у на пересечение этого аппроксимирующего множества с множеством Ю". В случае, если О" задано системой линейных уравнений или неравенств, то построение приближения не вызывает большого труда-, так как задача проектирования решается известными алгоритмами за конечное число шагов. Как и в методах из предыдущих параграфов, в этом проекционном методе тоже заложена возможность обновления аппроксимирующих область О' множеств за счет отбрасывания дополнительных ограничений.

В § 1.4 для задачи (0.0.1) строится еще один метод отсечений с аппроксимацией области ограничений, который отличается от методов из §§ 1.1,1.2 тем, что допускает возможность распараллеливания процесса отыскания итерационных точек. В этом методе для построения основных итерационных точек сначала некоторым способом строится определенное число многогранных множеств, аппроксимирующих область ограничений исходной задачи. Далее в каждом из этих множеств находится вспомогательная точка приближенного минимума целевой функции. Наконец, в качестве основной итерационной точки выбирается рекордная из найденных вспомогательных точек. Заметим, что эти вспомогательные точки могут находится параллельно различными ал го р ит м ам и м и н и м изаци и.

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

Первый параграф второй главы посвящен решению задачи минимизации выпуклой в Яа дискретной функции максимума/(л) на выпуклом замкнутом множестве В С Я„. Предлагаемый для решения задачи метод заключается в следующем. На ?-ом шаге (? > 0) находится решение (уг,ъ) следующей задачи:

7 —» тш,

(х,7)емг. хеС\, 7 >т7,

где М1 — множество, аппроксимирующее падграфик целевой функции. С, — некоторое подмножество области В.

7,< г = шш{/(ф ьео]

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

Заметим, что метод обладает большими возможностями в выборе начального аппроксимирующего множества Л^о, множеств С'? и чисел 7,. За счет вида целевой функции задачи у метода есть значительные возможное!и и

для построения отсекающих плоскостей, которые формируют аппроксимирующие множества.

В параграфе 2.2 предлагается метод отсечений для решения задачи (0.0.1) с выпуклой функцией /(;г), который также использует аппроксимацию над-графика целевой функции. Главные отличия этого метода от метода из § 2.1 заключаются в следующем. Во-первых, в нем заложена возможность построения на его основе смешанных алгоритмов с привлечением любых релаксационных сходящихся или эвристических методов условной минимизации без дополнительного обоснования сходимости таких смешанных алгоритмов. Во-вторых, метод позволяет привлекать параллельные вычисления при построении приближений. Кроме того, отметим, что в данном методе применяется способ построения отсекающих плоскостей, отличный от используемого в предыдущем методе.

В § 2.3 предлагается модификация известного метода уровней (|82|. |158|) для решения задачи (0.0.1), где /(.г) — выпуклая функция, a D — выпуклое ограниченное замкнутое множество. Главное отличие предлагаемого метода от известного заключается в том, что в нем заложена возможность периодического отбрасывания накапливающихся в процессе счета отсекающих плоскостей, что делает метод привлекательным с практической точки зрения. Другое немаловажное отличие этого метода от ([82], [158]) заключается в более общем способе задания итерационных точек. В частности, в предлагаемом методе при построении приближений можно привлекать параллельные вычисления.

Далее в § 2.4, основываясь на способе построения аппроксимирующих множеств из § 2.2, разрабатывается еще один мет од отсечений для задачи (0.0.1). В методе при построении итерационных точек происходит' аппроксимация множествами Мг падграфика не целевой функции /(т), а некоторой вспомогательной функции д(х). Существенным отличием предлагаемого метода от методов, построенных в предыдущих параграфах, является заложенный г. нем новый критерий качества аппроксимирующих множеств Мг, а значит, и критерий отбрасывания отсекающих плоскостей. А именно, как только итерационная точка из Мг становится достаточно близка к надграфику функции д{х), качество аппроксимации считается присмлимым, и происходит обновление множества М7.

Данный метод за конечное число шагов позволяет найти s-решение задачи (0.0.1). Если же после нахождения s-решсния процесс построения приближений продолжается, то любая предельная точка итерационной последовательности будет принадлежать множеству решений. Отметим, что данный метод, как и многие предыдущие, позволяет строить смешанные алгоритмы с при-

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

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

В § 3.1 предлагается общий метод отсечений для задачи (0.0.1), где f(.i) — выпуклая функция. Метод строит последовательность приближений следующим образом. На 7-ом шаге метода находится точка {yL.^L) как решение1 задачи

7 —» min,

(.т,7)еМг, zeG„ 7 > а,

где Мг С R-n+i ~ множество, аппроксимирующее иадграфик целевой функции, Gt С Rn - множество, аппроксимирующее область ограничений в окрестности решения исходной задачи, а - нижняя оценка значения /*. Компонента уи найденной точки, принимается за текущую итерационную точку. Далее строятся очередные аппроксимирующие множества М1+\ и Gl+\. Первое из них — путем отсечения от множества М7 точки (уг, уг). а второе — на основе отсечения от Gz приближения уг в случае уг ^ D. Предлагаются различные варианты выбора начальных погружающих множеств, а также различные способы построения отсекающих плоскостей.

На основе идеи одновременной аппроксимации надграфика целевой функции и области ограничений в § 3.2 предлагается метод отсечений для задачи выпуклого программирования (0.0.1) с областью D, заданной в виде (0.0.2). Принципиальная особенность предлагаемого метода, выделяющая его среди всех методов диссертации, заключается в следующем. В метод заложены два критерия оценки качества аппроксимирующих множеств. Первый из них основан на оценке близости итерационной точки к множеству D' и позволяет отслеживать качество аппроксимации допустимой области. Второй из указанных критериев основан на оценке близости текущих значений целевой функции /(х) к ее оптимальным значениям на множествах, аппроксимирующих область D', и характсрезует качество аппроксимации надграфика. Об-

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

В параграфах 1.5, 2.5 и 3.3 представлены результаты численных экспериментов, которые проводились с целью исследования методов, разработанных в §§ 1.1, 1.2, 2.1, 2.2, 3.2. Указанные методы программно реализованы на языке программирования С-Н- в среде Microsoft Visual Studio 2008. Методы из §§ 1.1, 1.2, 3.2 тестировались на задачах, в которых допустимая область задавалась нелинейными функциями. Остальные из указанных методов исследовались на примерах, в которых область ограничений являлась многогранником, а целевая функция выбиралась нелинейной. Исследуемыми методами решено значительно число тестовых примеров с различным количеством переменных (до 50) и ограничений (до 50). Каждая задача решалась тестируемым методом как с использованием процедур отбрасывания отсечений, так и без привлечения процедур обновления аппроксимирующих множеств. Рассчеты показали, что применение в каждом из исследованных методов определенных процедур обновления способствовало значительному ускорению решению всех тестовых задач. Кроме того, результаты численных экспериментов позволили выработать рекомендации по заданию некоторых параметров методов.

Автор выражает благодарность научному руководителю профессору ка,-федры анализа данных и исследования операций Казанского (Приволжского) федерального университета И.Я. Заботину за постоянное внимание и помощь в работе над диссертацией, а также сотрудникам кафедры анализа данных и исследования операций за полезные обсуждения и замечания в ходе работы над диссертацией.

Глава 1

Методы отсечений с использованием процедур аппроксимации допустимой области

Глава посвящена методам отсечений для решения задач нелинейного программирования и задачи отыскания проекции точки на выпуклое множество, основанным на аппроксимации допустимой области. Последовательности приближений в предлагаемых методах строятся с использованием операции частичного погружения допустимой области в аппроксимирующие ее многогранные множества. В разработанных методах, которые предложены в параграфах 1.1 — 1.3, не требуется вложения каждого из аппроксимирующих множеств в предыдущее. Такая особенность методов дает возможность периодического отбрасывания любых полученных в процессе решения дополнительных ограничений. В параграфе 1.4 предлагается метод отсечений, допускающий параллельные вычисления. Обосновываются сходимость методов, обсуждаются их реализации, приводятся оценки точности решен и /I и скорости сходимости. Основные результаты этой главы опубликованы в работах [129] - [131], [133], [135], [136|, [138], [141] - [144], [146].

1.1 Метод отсечений на основе аппроксимации допустимой области семейством опорных плоскостей без вложения погружающих множеств

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

Пусть }'3{х). J £ ■J = {1 .....т}, — выпуклые в 7?,-мерном евклидовом

пространстве Rn функции,

D = {xeRn:f1(x)< 0, je J}, (1.1.1)

f(x) — непрерывная достигающая на D минимального значения функция, и для всех j £ J множества

D3 = {xeRn:fJ{j:)<Q} (1.1.2)

имеют непустую внутренность intD^. Решается задача

min{f{x) : х £ D}. (1.1.3)

Положим F{x) = max fj(х), De = {х £ Rn : F{x) < e], где e > 0,

/* = min{f(x) : 2' £ D}, X* = {.r £ D : f{x) = /*}, E* = {x £ Rn fH < /*}, Wl{x,Dj) = {a £ Rn : <a. г - r> < 0 V; £ Dy |M| - 1} -множество нормированных обоб1ценно-опорпых векторов для множества D} в точке х £ Я,г, К = {0,1,. . .}.

Сразу отметим, что в (1.1.3) внутренность множества D может быть пустой.

Предлагаемый метод решения задачи (1.1.3) вырабатывает последовательности приближений {уг], 1 £ К, {.¿'/J, к £ К, и заключается в следующем.

Метод 1.1. Строится выпуклое замкнутое множество Mq С Rn, содержащее хотя бы одну точку множества X*, например, точку г*. Выбираются точки V1 £ int Dj для всех j £ J. Задается число eq > 0. Полагается к = 0. ? = 0.

1. Находится точка

(11.4)

2. Формируется множество

■Л = 0 D,}.

Если J% = 0, то yt £ X*. и процесс завершается.

3. Если уг ^ DSl, то выбирается выпуклое замкнутое множество С1 С Rn. содержащее точку х*, полагается

Ql = Mi^\CJ1 (1.1.5)

и следует переход к п. 4. В противном случае полагается = г,

п = (1-1.6)

и выбирается выпуклое замкнутое множество Qt = Q?k такое, что

x-eQ,. (1.1.7)

Задается число e¡c+i > 0, значение к увеличивается па единицу, и следует переход к очередному пункту.

4. Для каждого j Е J% в интервале (V,?/,) выбирается точка z] так, чтобы z\ ^ int Dj и при некотором q¡ Е [1, g], q < +оо, для точки

Vi = У1 + ÚW - у,) (1.1.8)

выполнялось включение у'г Е Dr Для всех ; Е J \ .]г полагается z\ — у{ = i/,.

5. Выбирается множество Н, С -Л так, чтобы выполнялось включение ]г Е Я,, где номер удовлетворяет условию

\\у, - z¡'\\ = тах||уг - z¡\\. (1.1.9)

jeJ,

6. Для каждого j Е Ii, выбирается конечное множество А\ С Wl{z]. D¡), полагается

Мг+1 = Ql П G Д» : М - J) < 0 Va Е .4^}, (1.1.10)

jen,

и следует переход к п. 1 при г, увеличенном па единицу.

Сделаем некоторые замечания, касающиеся данного метода.

Замечание 1.1.1. Если. на, таге 2 .метода выполняется, условие -J, -- 0. то согласно (1.1.4) точка уt, действительно, является решет ¡ем ■исходной, задачи.

Замечание 1.1.2. Мноэ/сество М, р) Е* содерэ/сит. но крапп,ей, мере, точку х*, а значит, выбор уг из условия. (1.1.4) возмоо/сеп. В частности, 'точку •уг MOOICHO находить согласно равенству

){уг) = min{/(T) : .т € М,} (1.1.11)

Замечание 1.1.3. В случае, когда f(.r) выпукла, i = {1}. // = и Е mil). причем, int D т^ 0; £о = 0 и точки у^ выбраны, согласно (1.1.11). то предлагаемый метод идейно близок к известному методу погруэюений В.Г1. Булатова (напр., [21]) для задам,и выпуклого программирования.

Список литературы диссертационного исследования кандидат наук Яруллин, Рашид Саматович, 2015 год

Литература

[1] Абрамов, B.B. Об одном алгоритме решения задачи выпуклого программирования с параллелепипедпыми ограничениями |Текст] / В.В. Абрамов, В.П. Булатов, J1. А. Крумм // Тезисы докладов конференции по оптимальному планированию. - Новосибирск, 1965.

[2] Александров, И.А. К методам центрированных сечений / H.A. Александров, Е.Г. Анциферов, В.П. Булатов //Тез. докл. конф. но матем. программмированию. - Свердловск: МММ УНЦ АН СССР. - 1981. - С. 162 - 163.

[3] Андрианова, A.A. Алгоритмы в методе центров с аппроксимацией множества допустимых решений [Текст] / A.A. Андрианова, Я.И. Заботин // Изв. вузов. Матем. - 2001. - N 12. - С. 41 - 45.

[4] Антипин, A.C. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лаграпжа [Текст| / A.C. Антипин. - М.: Изд - во Всесоюзн. науч. - исследов. института системы, исследований, 1979. - 74 с.

[5] Антипин, A.C. Об оценках скорости сходимости метода проекции градиента [Текст| / А. С. Антипин // Изв. вузов. Матем. - 1995. - N 6. -С. 16 - 24.

[6] Антипин, A.C. Трехшаговый метод линеаризации для задач минимизации [Текст] / A.C. Антипин. А. Недич, М. Ячимович // Изв. вузов. Матем. - 1994. - N 12. - С. 3 - 7.

[7] Анциферов, Е.Г. Алгоритм симплексных погружений в выпуклом программировании [Текст] / Е.Г. Анциферов, В.II. Булатов // Ж. вычисл. матем. и матем. физ. - 1987. - Т. 27, N 3. - С. 377 - 384.

[8] Анциферов, Е.Г. Об одной модификации метода опорного конуса для решения общей задачи выпуклого программирования [Текст| / Е.Г. Анциферов, Ю.Я. Данилснко // Прикл. математика. - Иркутск, 1978. -Вып. 8. - С. 18 - 22.

[9] Анциферов, Е.Г. Решение задачи выпуклого программирования модифицированным методом опорного конуса [Текст] / Е.Г. Анциферов, ЬО.Я. Даниленко // Методы оптимизации и их приложения. - Новосибирск: Наука. Сиб. отд-ие, 1982. - С. 35 - 52.

[10] Апекина,, Е. В. Модифицированный метод симплексных погружений с одновременным введением нескольких секущих плоскостей [Текст| / Е.В. Апекина, О.В. Хамисов // Изв. вузов. Матем. - 1997. - N 12. - С. 16 - 24.

[11] Ащепков, Л.Т. Методы решения задач математического программирования и оптимального управления [Текст| / Л.Т. Ащепков, Б.И. Белов, В.Г1. Булатов, О.В. Васильев, В.А. Срочко, Н.В. Тарасенко. - Новосибирск: Наука, 1984. - 233 с.

[12] Бахвалов, Я.С. Численные методы. Анализ, алгебра, обыкновенные дифференциальные уравнения (Текст] / Н. С. Бахвалов. - М.: Наука, 1973. - 631 с.

[13] Белых, Т.И. Методы опорных конусов и симплексов в выпуклом программировании и их приложения 15 некоторых физико-химических системах |Текст] / Т.И. Белых, В.II. Булатов // Ж. вычисл. матем. и матем. физ. - 2008. - Т. 48, N 11. - С. 1952 - 1967.

[14] Белых, Т.И. Методы чебышевских точек выпуклых множеств и их приложения |Текст) / Т.И. Белых, В.П. Булатов, Э.Н. Яськова // Ж. вычисл. матем. и матем. физ. - 2008. - Т. 48, /V 1. - С. 18-32.

[15] Белых Т. П. Эффективные методы решения задач выпуклого программирования |Текст| / Т. И. Белых, В. П. Булатов, Э. Н. Яськова // Дискрета. анализ и исслед. опер. - 2008. - Т. 15. - N 3. - С. 3-10.

[16] Верьщпский, Я.М. Метод обратной матрицы для решения обобщенной задачи линейного программирования |Текст| / Я.М. Берщанский // Математические методы в экономических исследованиях. - М., 1974.

[17] Булавекий, В.А. Об одном типе проекционных методов в математическом программировании |Текст| / В.А. Булавекий // Оптимизация. -Новосибирск: Наука, 1972. - С. 11 - 22.

[18] Булатов, В.П. Методы аппроксимации при решении выпуклых экстремальных задач [Текст| / В.П. Булатов // Сборник трудов ВЦ ИГУ. -Иркутск, 1968.

[19] Булатов, В.Л. Метод ортогональных симплексов и его приложения в выпуклом программировании / В.Г1. Булатов // Ж. вычисл. матем. и матем. физ. - 2008. - Т. 48, N 4. - С. 610 - 622.

[20] Булатов, В.П. Метод отсечения в Еп+1 для решения задач глобальной оптимизации на одном классе функций [Текст] / В.П. Булатов, О.В. Хамисов // Ж. вычисл. матем. и матем. физ. - 2007. - Т. 47, N 11. - С. 1830 - 1842.

[21] Булатов, В.П. Методы погружения в задачах оптимизации [Текст] / В.П. Булатов. - Новосибирск: Наука, 1977. - 161 с.

[22] Булатов, В.П. Об одном эффективном методе выпуклого программирования [Текст] / В.П. Булатов, Н.И. Федурипа // Дискретн. анализ и исслед. опер., сер. 2. - 2004. - Т. 11, ДМ. - С. 51 - 61.

[23] Булатов, В. П. О некоторых методах аппроксимации для задач выпуклого программирования |Текст| / В.П. Булатов. - Методы математического моделирования в энергетике. - Иркутск, 1966.

[24] Васильев, Ф.П. Методы оптимизации: В 2-ух кн. [Текст] / Ф.Г1. Васильев. - М.: МЦНМО, 2011. - Кн. 1.- 620 с.

|25] Васильев, Ф.П. Об итеративной регуляризации метода условного градиента и метода Ньютона при неточно заданных исходных данных [Текст| / Ф.П. Васильев, М.Д. Ячимович // Докл. АН СССР. - 1980. - Т. 250, N 2.- С. 265 - 269.

[26] Васильев, Ф.П. Численные методы решения экстремальных задач [Текст] / Ф.П. Васильев. - М.: Науки, 1988. - 552 с.

[27] Васин, В.В. Операторы и итерационные процессы фейеровекого типа (теория и приложения) [Текст] / В.В. Васин, И.И. Еремин. - Москва - Ижевск: Институт компьютерных исследований, НИЦ «Регулярная и хаотичная динамика», 2005. - 200 с.

[28] Галиев, Ш.И. Нахождение приближенных решений минимаксных задач [Текст| / Ш.И. Галиев // Жури, вычисл. матем. и матем. физ. - 1997. -Т. 37, N 12. - С. 1439 - 1448.

129] Галиев, Ш.И. Нахождение приближённого решения максимина со связанными переменными и кратного максимина [Текст| / Ш.И. Галиев // Журн. вычисл. матем. и матем. физ. - 1986. - Т. 26. N 10. - С. 1455 -1467.

(30] Галиев, Ш.И. Нахождение субоптимальных решений максиминных задач [Текст] / Ш.И. Галиев // Журн. вычисл. матом, и матем. физ. -1985.'- Т. 25. - N 11. - С. 1738.

[31] Галиев, Ш.И. Численное решение некоторых минимаксиминных задач [Текст| / Ш.И. Галиев // Журн. вычисл. матем. и матем. физ. - 1988.

- Т. 28, N 7. - С. 1000 - 1011.

132] Гарано1са, В.А. Параллельная реализация метода Ныотона для решения больших задач линейного программирования |Текст| / В.А. Гаранжа, А.И. Голиков, Ю.Г. Евтушенко, М.Х. Нгуен // Журн. вычисл. матем. и матем. физ. - 2009. - Т. 49, N 8. - С. 1369 - 1384.

133] Голиков, А.И. Две модификации метода линеаризации в нелинейном программировании [Текст] / А.И. Голиков, В.Г. Жадан // Журн. вычисл. матем. и матем. физ. - 1983. - Т. 23, N 2. - С. 314 - 325.

[34] Голиков, А.И. Обобщенный метод Ныотона для задач линейной оптимизации с ограничениями-неравенствами [Текст) / А. И. Голиков,. Ю. Г. Евтушенко // Тр. ИММ УрО РАН. - 2013. - Т. 19, N 2. - С. 98 - 108.

[35] Голыитейи, Е.Г. Градиентный метод минимизации и алгоритмы выпуклого программирования, связанные с модифицированными функциями Ланранжа, |Текст) / Е.Г. Голыитейн, Н.В. Третьяков // Экономика и матем. методы. - 1975. - Т. 11, N 4. - С. 730 - 742.

[36] Данилин. Ю.М. Минимизация нелинейных функционалов в задачах с ограничениями |Текст] / Ю.М. Данилин // Кибернетика. - 1970. - N 3.

- С. 93 - 100.

[37] Демьянов. В.Ф. Введение в минимакс |Текст| / В.Ф. Демьянов, ЕЗ.Н. Малоземов. - М.: Наука, 1972. - 368 с.

[38] Демьянов, В.Ф. Недифференцируемая оптимизация [Текст) / В.Ф. Демьянов, Л.В: Васильев. - М.: Наука, 1981. - 384 с.

139] Демьянов, В.Ф. Приближенные методы решения экстремальных задач [Текст| / В.Ф. Демьянов, A.M. Рубинов. - Л.: Изд - во ЛГУ, 1968. - 180 с.

[40] Дикин, 14.И. Итеративное решение задач математического программирования [Текст] / И.И. Дикин, В.И. Зоркальцев. - Новосибирск: Наука, 1980. - 144 с.

[41] Евтушенко, Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации [Текст] / Ю. Г. Евтушенко. - М.: Наука, 1982. - 432 с.

[42] Евтушенко, Ю.Г. Метод половинных делений для глобальной оптимизации функции многих переменных [Текст| / Ю.Г. Евтушенко, В.А. Ратькин // Технич. кибернетика. - 1987. - N 1. - С. 119 - 127.

[43] Евтушенко, Ю.Г. Параллельный поиск глобального экстремума функций многих переменных [Текст'] / Ю.Г. Евтушенко, В.У. Малкова, А.-И.А. Станевичюс // Ж. вычисл. матем. и матем. физ. - 2009. - Т. 49, N 2. - С. 255 - 269.

[44] Евтушенко, Ю. Г. Распараллеливание процесса поиска глобального экстремума [Текст] / Ю.Г. Евтушенко, В.У. Малкова, А.-И.А. Станевичюс // Автомат, и телемех. - 2007. - N 5. - С. 46 - 58.

[45] Евтушенко, Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) [Текст| / Ю.Г. Евтушенко // Журн. вычисл. матем. и матем. физ. - 1971. Т. 11, N 6. - С. 1390 -1404.

[46] Еремин, PI.И. ЕЗведение в теорию линейного и выпуклого программирования |Текст| / 14.И. Еремин, Н.Н. Астафьев. - М.: Наука, 1976. - 192 с.

[47] Ерм,олъев, Ю.М. Математические методы исследования операций [Текст] / Ю.М. Ермольев, И.И. Ляшко, B.C. Михалевич, В.И. Тюптя. -Киев: Вища школа, 1979. - 312 с.

[48] Жадан, В.Г. Об одном классе итеративных методов решения задач выпуклого программирования |Текст| / В.Г. Жадан // Журн. вычисл. матем. и матем. физ. - 1984. - Т. 24, N 5. - С. 665 - 676.

[49] Заботин, И.Я. Алгоритм второго порядка с параметризованными направлениями для задач условной оптимизации [Текст11 / И.Я. Заботин // Изв. вузов. Математика. - 1997. - N 12. - С. 62 - 72.

[50] Заботин, И.Я. Вариант параметризованного метода центров [Текст] / И.Я. Заботин, Ё.А. Князев // Изв. вузов. Математика. - 1995. - N 12. - С. 26 - 32.

[51] Заботин, И.Я. Метод условного £ - субградиента |Тексг| / И.Я. Заботин, А.И. Кораблев // Изв. вузов. Математика. - 1983. - N 9. - С. 22 - 26.

|52] Забот,ии, Я.Я. Метод условной минимизации с параметрическим заданием подходящих направлений [Текст| / И.Я. Заботин // Изв. вузов. Математика. - 1996. - N 12. - С. 17 - 29.

[53] Заботин, Я.Я. Об устойчивости алгоритмов безусловной минимизации псевдовыпуклых функций [Текст] / И.Я. Заботин // Изв. вузов. Математика. - 2000. - N 12. - С. 33 - 48.

[54] Заботин, Я.Я. О некоторых алгоритмах погружений-отсечений для задачи математического программирования [Текст| / И.Я. Заботин // Изв. Иркутского гос. ун-та. Сер. «Математика» - 2011. - Т. 4. N 2.

- С. 91 - 101.

[55] Заботин, И.Я. Проекционные алгоритмы с параметризованными направлениями спуска в псевдовыпуклом программировании |Текст| / И.Я. Заботин // Исслед. по прикл. ма.тем. и информатике - Казань: Изд - во Казанск. матем. общества, 2001. - Вып. 23. - С. 67 - 81.

[56] Заботин, И.Я. Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций |Текст| / И.Я. Заботин // Изв. вузов. Математика. - 2003. - N 12. - С. 62 - 70.

157] Заботин, Я.И. К сходимости методов отыскания мипимакса |Текст| / Я.И. Заботин, М.И. Крейнин // Изв. вузов. Математика. - 1977. - А' 10.

- С. 56 - 64.

[58] Заботин,, Я.Я. Минимаксный метод решения задачи математического программирования [Текст) / Я.И. Заботин // Изв. вузов. Математика.

- 1975. - N6.- С. 36 - 43.

|59] Заботят, Я.И. О минимизации квазивыпуклых функционалов |Текст| / Я.И. Заботин, А.И. Кораблев, Р.Ф. Хабибуллин // Изв. вузов. Математика. - 1972. - N 10. - С. 27 - 33.

[60] Заботин, Я.Я. Об одной модификации метода сдвига штрафов для за,-дач нелинейного программирования [Текст] / Я.И. Заботин, И.А. Фукин // Изв. вузов. Математика. - 2000. - N 12. - С. 49 - 54.

[61] Заигвилл, У.И. Нелинейное программирование [Текст] / У.И. Зангвплл.

- М.: Сов. радио, 1973. - 312 с.

[62] Зойнгендейк, Г. Методы возможных направлений |Текст) / Г. Зойтсн-дейк. - М.: Ин. лит., 1963. - 176 с.

[63] Зоркалъцев, В.И. Семейство проективных алгоритмов [Текст] / В.И. Зоркальцев // Оптимизация: модели, методы, решения. - Новосибирск: Наука, 1992. - С. 90 - 116.

[64] Зуховицкий, С.PI. Численный метод для решения задачи выпуклого программирования в гильбертовом пространстве |Текст| / С.И. Зуховицкий, P.A. Поляк, М.Е. Примак // Докл. АН СССР. - 1965. - Т. 163, N 2. - С. 282 - 284.

[65] Ижуткин, B.C. Методы приведенных направлений для задачи нелинейного программирования |Текст| / B.C. Ижуткин, М.Ю. Кокурин // Журн. вычисл. матем. и матем. физ. - 1988. - Т. 28, N 12. - С. 1799 -1814.

[66] Карма,нов. В.Г. Математическое программирование [Текст] / ЕЗ.Г. Карманов. - М.: Наука, 1986. - 288 с.

[67] Кивистик, Л. Об ускорении полностью целочисленного алгоритма Го-мори [Текст] / Л. Кивистик // Изв. АН Эстонской ССР. Сер. физика и математика. - 1986. - Т. 34. - N 1. - С. 11-19.

[68] Кокурин, М.Ю. Об одном подходе к коррекции несовместных вариационных неравенств [Текст| / М. Ю. Кокурин // Изв. вузов. Математика. - 1991. - N 4. - С. 16 - 24.

[69] Колоколов, A.A. Исследование некоторых задач целочисленного программирования на основе упимодулярных преобразований и регулярных разбиений [Текст| / A.A. Колоколов, Т.Г. Орловская // Тр. ИММ УрО РАН. - 2013. - N 1. - С. 193 - 202.

[70] Колоколов, A.A. Построение и анализ оценок числа итераций для алгоритмов целочисленного программирования с использованием метода регулярных разбиений |Текст] / A.A. Колоколов, Л.А. Заозерская // Изв. вузов. Математика. - 2014. - N 1. - С. 41 - 54.

[71] Колоколов, A.A. Регулярные разбиения и отсечения в целочисленном программировании |Текст] / A.A. Колоколов // Сиб. журн. исслед. операций. - 1994. - Т. 1, N 2. - С. 18 - 39.

[72] Конное. И.В. Метод спуска с неточным линейным поиском для негладких равновесных задач [Текст| / И.В. Коннов. О.В. Пинягина, // Ж. вычисл. матем. и матем. физ. - 2008. - Т. 48, N 10. - С. 1812 - 1818.

[73] Конное, И.В. Метод типа сопряженных субградиентов для минимизации функционалов [Текст] / И.В. Коннов // Исслед. по прикл. матем.

- Казань: Изд - во КРУ, 1984. - Вып. 12. - С. 59 - 62.

[74] Коннов, И.В. Метод типа условного градиента для задач негладкой оптимизации [Текст] / И. В. Коннов // Исслед. по прикл. матем. - 1984.

- N 10. - С. 95 - 101.

[75] Коннов, И.В. Нелинейная оптимизация и вариационные неравенства [Текст] / И.В. Коннов - Казань: Казанский ун-т. 2013. - 508 с.

|76] Коннов, И.В. Применение метода штрафов к нестационарной аппроксимации задачи оптимизации |Тексг] / И.В. Коннов // Изв. вузов. Матем.

- 2014. - N 8. - С. 60 - 68.

[77] Кораблев, А.И. е - субградиентный метод решения нелинейных экстремальных задач [Текст] / А.И. Кораблев // Исслед. по прикл. матем. -Казань: Изд - во КРУ. 1979. - Вып. 7. - С. 3 - 11.

[78] Куликов, А.А. Выпуклая оптимизация с заданной точностью |Текст| /А. Н. Куликов. В. Р. Фазылов // Жури, вычисл. матем. и матем. физ.

- 1990. - Т. 30, N 5. - С. 663 - 671.

|79] Левин, 10.Я. Об одном алгоритме минимизации выпуклых функций / Ю.Я. Левин // Докл. АН СССР. - 1965. - Т. 160, N 6. - С. 1244 - 1247.

|S0] Левитин, Е.С. Методы минимизации при наличии ограничений |Текст| / Е.С. Левитин, В.Т. Поляк // Жури, вычисл. матем. и матем. физ. -1966. - Т. 6, N 5. - С. 787 - 823.

[81] Ненахов, Э.И. Метод чебышевских центров в модели отыскания экономического равновесия / Э.И. Ненахов, М.Е. Примак // ИК АН УССР.

- 1983.

[82] Нестеров, 10. Е. Введение в выпуклую оптимизацию [Текст] / Ю.Е. Нестеров. - М.: МЦНМО, 2010. - 263 с.

[83] Нестеров, Ю.Е. Об одном подходе к построению оптимальных методов минимизации гладких выпуклых функций [Текст] / Ю.Е. Нестеров //' Экономика и матем. методы. - 1988. - Т. 24, Вып. 3. - С. 509 - 517.

[84] Нестеров, Ю.Е. Эффективные методы в нелинейном программировании [Текст] / Ю. Е. Нестеров. - М.: Радио и связь, 1989. - 383 с.

[85] Нурминский, Е.А. Метод отделяющих плоскостей с ограниченной памятью для решения задач выпуклой негладкой оптимизации [Текст] / Е.А. Нурминский // Вычисл. методы и программирование. - 2006. - Т. 7. - С. 133 - 137.

[86] Нурминский, Е.А. Об одном классе методов выпуклого программирования [Текст| / Е.А. Нурминский // Журн. вычисл. матом, и матем. физ.

- 1986. - Т. 26, N 8. - С. 1150 - 1159.

[87] Нурминский, Е.А. Численные методы решения детерминированных и стохастических минимаксных задач [Текст] / Е.А. Нурминский. - Киев: Наукова думка, 1979. - 158 с.

[88] Пиявский, С.А. Один алгоритм отыскания абсолютного экстремума функции |Текст] / С.А. Пиявский // Жури, вычисл. матем. и матем. физ. - 1972. - Т. 12, N 4. - С. 888 - 896.

[89] Поля,к, Б. Т. ЕЗведение в оптимизацию [Текст] / Б.Т. Поляк. - М.: Наука. 1983. - 384 с.

|90] Полях, Б. Т. Минимизация негладких функционалов |Текст| / Б.Т. Поляк // Журн. вычисл. матем. и матем. физ. - 1969. - Т. 9, N 3. - С. 509

- 521.

[91] Полях, Б. Т. Сравнение скорости сходимости одпошаговых и многошаговых алгоритмов оптимизации при наличии помех [Текст| / Б.Т. Поляк // Технпч. кибернетика. - 1977. - N 1. - С. 9 - 12.

[92] Попов, Л.Д. Об одной модификации метода логарифмических барьерных функций в линейном и выпуклом программировании |Текст) / Л.Д. Попов //Тр. МММ УрО РАН. - 2008. - Т. 14, N 2. - С. 103 - 114.

[93] Попов, Л.Д. Опыт организации гибридных параллельных вычислений в методе Евтушенко-Голикова для задач с блочио-апгулярной структурой ограничений [Текст] / Л. Д. Попов // Автомат, и телемех. - 2014. - А; 4. - С. 38 - 50.

[94] Попов, Л.Д. Опыт многоуровневого распараллеливания метода ветвей и границ в задачах дискретной оптимизации [Текст) / Л.Д. Попов // Автомат, и телемех. - 2007. - N 5. - С. 171 - 181.

[95] Попов, Л.Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода |Текст| / Л.Д. Попов // Автомат, и телемех. - 2012. - А' 3. - С. 3 - 11.

[96] Потапов, М.М. Аппроксимация и регуляризация задач параметрической минимизации |Текст| / М.М. Потапов. С. А. Нестеров // Изв. вузов. Матем. - 1988. - N 6. - С. 73 - 75.

[97] Потапов, М.М. Об оценках точности методов регуляризации в задачах квадратичной минимизации на полупрострапствеи [Текст] / М.М. Потапов // Журн. вычисл. матем. и матем. физ. - 2004. - Т. 44. N 2. - С. 255 - 264.

[98] Пшеничный, Б.П. Выпуклый анализ и экстремальные задачи [Текст] / Б.Н. Пшеничный. - М.: Наука, 1980. - 319 с.

[99] Пшеничный, Б.Н. Метод линеаризации [Текст| / Б.Н. Пшеничный. -М.: Наука, 1983. - 136 с.

[100] Пшеничный, Б.Н. Численные методы в экстремальных задачах |Текст| / Б.Н. Пшеничный, 10.М. Данилин. - М.: Наука, 1975. - 320 с.

[101] Сайко, Л.А. Исследование одного класса разбиений в целочисленном программировании [Текст] / J1.A. Сайко // Управляемые системы. -1989. - Вып. 29. - С. 72 - 82.

[102] Семен,ей, П. Т. Об одной модификации метода опорного конуса / П.Т. Семеней, О.В. Хамисов // Тез. докл. копф. но матем. программирова,-нию. - Свердловск: И ММ УНЦ АН СССР, 1987. - С. 101 - 102.

[103] Скарин, В.Д. О методе регуляризации для противоречивых задач выпуклого программирования |Текст| / В.Д. Скарин // Изв. вузов. Математика. - 1995. - N 12. - С. 81 - 88.

[104] Стрекало в ский, A.C. Минимизирующие последовательности в задачах с d.с.-ограничениями [Текст| / А. С. Стрекаловский // Ж. вычисл. матем. и матем. физ. - 2005. - Т. 45, N 3. - С. 435 - 447.

[105] Стрекаловский, A.C. О минимизации разности выпуклых функций па допустимом множестве |Текст| / A.C. Стрекаловский // Ж. вычисл. матем. и матем. физ. - 2003. - Т. 43, N 3. - С. 399 - 409.

[106] Стрекаловский, A.C. 11олима.тричные игры и задачи оптимизации [Текст] / A.C. Стрекаловский, Р. Энхбат // Автомат, и телемех. - 2014. - AM. - С. 51 - 66.

[107] Стрекаловский. A.C. Элементы невыпуклой оптимизации |Текст| / A.C. Стрекаловский. - Новосибирск: Наука, 2003. - 356 с.

[109 [110 [111 [112

[113

[114

[115 [116

[117

[118

Срочко, В. А. Модернизация методов градиентного типа в задачах оптимального управления |Текст] / В.А. Срочко // Изв. вузов. Матем. -2002. - N 12. - С. 66 - 78.

Стропгин, Р.Г. Численные методы в многоэкстремальных задачах [Текст] / Р.Г. Стронгип. - М.: Наука, 1978. - 240 с.

Сухарев. А.Р. Курс методов оптимизации |Текст] / А.Г. Сухарев, A.B. Тимохов, В.В. Федоров. - М.: Наука, 1986. - 328 с.

Схрейвер, А. Теория линейного и целочисленного программирования: Т. 2 [Текст] / А. Схрейвер. - М.: Мир, 1991. - 342 с.

Тихонов, А.Я. О регуляризации задач минимизации на множествах, заданных приближенно |Текст] / А.Н. Тихонов, Ф.Г1. Васильев, М.М. Потапов, А.Д. Юрий // Вестник МГУ. Сер. вычисл. матем. и киберн. -1977. - АЛ. - С. 4 - 19.

Третьяков, A.A. Две схемы нелинейного метода оптимизации в экстремальных задачах [Текст] / A.A. Третьяков // Журн. вычисл. матем. и матем. физ. - 1984. - Т. 24, N 7. - С. 986 - 992.

Фазылов, В.Р. Отыскание мипимакса, с заданной точностью |Текст| / В.Р. Фазылов // Журн. вычисл. матем. и матем. физ. - 1994. - Т. 34, N 5. - С. 793 - 799.

Федоров, В.В. Численные методы максимина [Текст] / В.В. Федоров. -М.: Наука, 1979. - 280 с.

Xамисов, О.В. Алгебраическое решение задач невыпуклого квадратичного программирования |Текст] /' О.В. Хамитов // Автоматика и телемеханика. - 2004. - АГ2.-С.41-60.

Хамисов, О.В. Глобальная оптимизация функций с вогнутой минорантой [Текст] / О.В. Хамисов // Журн. вычисл. матем. и матем. физ. -2004. - Т. 44, N 9. - С. 1552 - 1563.

Хамисов, О. В. Глубокие отсечения в вогнутом и линейном 0-1 программировании |Текст] / О.В. Хамисов // Тр. МММ УрО РАН. - 2014. - V. 20. N 2. - С. 294 - 304.

[119] Хим.м,елъблау, Д. Прикладное нелинейное программирование |Текст] /' Д. Химмельблау. - М.: Мир. 1975. - 536 с.

[120] Ху, Т. Целочисленное программирование и потоки в сетях |Текст| / Т. Ху. - М.: Мир, 1974. - 513 с.

[121] Червак, Ю.Ю. Об одном методе отсечений для дискретных задач [Текст| / Ю.Ю. Червак // Укр. мат. журн. - 1971. - N 8. - С. 839 - 843.

[122] Червак, Ю.Ю. Поиск лексиграфически максимальной дискретно определенной точки выпуклого множества |Текст| / Ю.Ю. Червак // Математические методы решения экономических задач. - 1979. - Вып. 8. -С. 69 - 75.

[123] Шевченко, В.Н. Выпуклые многогранные конусы, системы сравнений и правильные отсечения в целочисленном программировании / В.Н. Шевченко // Комбинаторные алгебраические методы в прикладной математике. - 1979. - С. 109 - 119.

[124] IIIop, Н.З. Методы минимизации недифференцируемых функций и их приложения |Текст[ / Н.З. Шор. - Киев: Наукова думка, 1979. - 199 с.

[125] Шор, Н.З. Методы отсечения с растяжением пространства для решения задач выпуклого программирования / Н.З. Шор // Кибернетика. - 1977. - N 1. - С. 94 - 95.

[126] Юдин, Д.Б. Информационная сложность и эффективные методы выпуклого программирования [Текст] / Д.Б. Юдин, A.C. Немировский. -М.: Наука, 1977. - 460 с.

[127] Юдковская, Е.М. Алгоритм и программа решения задачи целочисленного квадратичного программирования |Текст| / Е.М. Юдковская // Отчет по программе, фонд СЭИ. - 1967.

[128] Яруллин,, P.C. Алгоритм отсечений с аппроксимацией надграфика [Текст] / И.Я. Заботим, P.C. Яруллин // Учен. Зап. Казан. Ун-та. Сер. Физ.-матем. науки. - 2013. - Т. 155, N4.- С. 48 - 54,

1129] Яруллин, P.C. Алгоритмы отсечений без вложения погружающих множеств [Текст] / И.Я. Заботин. P.C. Яруллин // Проблемы оптимизации и экономические приложения : материалы V Всероссийской конференции (Омск, 2-6 июля 2012 г.). - Омск: Изд-во Ом. Гос. Ун-та, 2012. -С. 177.

[130] Яруллин, P.C. Алгоритм отсечений для задачи математического программирования, допускающий параллельные вычисления |Текст| /' И.Я. Заботин, P.C. Яруллин // Сборник трудов всероссийской конференции

«Статистика. Моделирование. Оптимизация» (28 нояб. - 3 дек. 2011 г.). - Челябинск: Издат. Центр ЮУрГУ. - 2011. - С. 114 - 117.

[131] Яруллин, P.C. Алгоритмы отсечений без вложения аппроксимирующих множеств и оценки точности решения [Текст] / И.Я. Заботим, P.C. Яруллин// Междунар. конференция «Дискретная оптимизация и исследование операций (DOOR - 2013)» (Новосибирск, 24 - 28 июня 2013). -Новосибирск: Изд-во Ин-та математики, 2013, - С. 48.

[132] Яруллин, P.C. Алгоритм отсечений на основе одновременной аппроксимации допустимой области и надграфика целевой функции |Текст| /' P.C. Яруллин// Труды X Международной конференции «Сеточные методы для краевых задач и их приложения» (Казань, 2014 г.). - Казань: Казан, ун-т, 2014. - С. 683 - 687.

[133] Яруллин, P.C. Метод отыскания проекции точки, основанный на процедурах отсечений [Текст] / И.Я. Заботим, О.Н. Шульгина, P.C. Яруллин// Труды X Международной конференции «Сеточные методы для краевых задач и их приложения» (Казань, 2014 г.). - Казань: Казан, ун-т, 2014. - С. 300 - 304.

[134] Яруллин, P.C. Алгоритм отсечений с аппроксимацией надграфика без вложения погружающих множеств [Электронный ресурс] / И.Я. За.бо-тин, P.C. Яруллин // 37-ая конференция-школа молодых ученых «Информационные технологии и системы (ИТиСТЗ)» (г. Калининград, 1 -6 сентября 2013г.). М.: ИПНИ РАН. - 2013. - С. 8 -11. - Режим доступа: http://itas2013.iifcp.ru/ru/search .html (да,та обращения: 22.10.2014).

[135] Яруллин., P.C. Алгоритм проектирования точки, использующий аппроксимирующие множества [Текст1] / И.Я. Заботим, P.C. Яруллин// Труды девятой Всероссийской конференции «Сеточные методы для краевых задач и их приложения» (Казань, 17 - 22 сентября 2012 г.). - Казань: Казан, ун-т, 2012. - С. 131 - 136.

[136] Яруллин, P.C. Алгоритм условной минимизации, допускающий параллельные вычисления [Текст] / P.C. Яруллин // Итоговая научно-образовательная конференция студентов Казанского университета 2011 года. - 2011. - С. 110 - 111.

[137] Яруллин, P.C. Метод отсечений с аппроксимацией надграфика и оценка точности решения |Текст] / И.Я. Заботин, P.C. Яруллин // XVII международная конференция «Проблемы теоретической кибернетики» (Казань, 16 - 20 июня 2014 г.). - Казань: Отечество, 2014. - С. 92 - 95.

[138] Яруллин, P.C. Метод отсечений с обновлением погружающих множеств и оценки точности решения [Текст] / И.Я. Заботин, P.C. Яруллин // Физико-математические науки. Учен. зап. Казан, гос. ун-та. Сер. Физ.-матем. науки. - 2013. - Т. 155, N 2. - С. 54 - 64.

[139] Яруллин, P.C. Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами [Текст| / И.Я. Заботин, P.C. Яруллин // Тезисы докладов XVI Байкальской международной школы-семинара «Методы оптимизаций и их приложения» (Байкал, 30 июня - 6 июля 2014 г.), г. Иркутск, ИСЭМ СО РАН, 2014. - С. 106.

[140] Яруллин, P.C. Метод отсечений с обновлением аппроксимирующих множеств и его комбинирование с другими алгоритмами [Текст] / И.Я. Заботин, P.C. Яруллин // Известия Иркутского гос. ун-та. ( лзр. «Матома.-тика». - 2014. - Т. 10. - С. 13-26.

[141] Яруллин, P.C. Некоторые процедуры гюгружений-отсечений и их применение в методах условной минимизации |Текст| / И.Я. Заботин, P.C. Яруллин // Информационная бюллетень Ассоциации матем. программирования . 12. - тезисы докл. XIV Всерос. Конф. «Математическое программирование и приложения» (28 фев. - 4 мар. 2011 г.). - Екатеринбург: У НЦ У ПИ. - 2011. - С. 40.

[142] Яруллин, P.C. Об одном подходе к построению алгоритмов отсечений с отбрасыванием отсекающих плоскостей [Текст] / И.51. Заботин, P.C. Яруллин // Изв. вузов. Матем. - 2013. - N 3. - С. 74 - 79.

[143] Яруллин, P.C. Об одном методе отсечений с отбрасыванием отсекающих плоскостей [Текст| / И.Я. Заботин, P.C. Яруллин // X Всероссийская конференция ММРО-16 (г. Казань, 6-10 октября 2013 г.). Казань, 2013. М.: Торус Пресс. - С. 81.

[144] Яруллин, P.C. Об одном методе отсечений с обновлением погружающих множеств и его численном исследовании / P.C. 51руллин // Республиканский конкурс научных работ студентов и аспирантов па соискание премии Н.И.Лобачевского (Казань, 9 - 12 апреля 2013 г.). РМОО «Лига студентов Республики Татарстан». - 2013. - С. 34 - 36.

[145] Яруллин, P.C. Об одном методе отсечений на основе аппроксимации надграфика с отбрасыванием секущих плоскостей и его численном исследовании / P.C. Яруллин // Республиканский конкурс научных работ

студентов и аспирантов на соискание премии Н.И.Лобачевского (Казань, 2014 г.), РМОО «Лига студентов Республики Татарстан». - 2014.

- С. 65 - 67.

[146] Яруллин, Р. С. Об одном методе условной минимизации, допускающем параллельные вычисления |Текст] / И.Я. Заботим, P.O. Яруллин // Труды XV Байкальской Между нар. Школы-семинара «Методы оптимиза,-ции и их приложения» (Байкал, 23 - 29 июня 2011 г.) - Т. 2, «Математическое программирование» - Иркутск: РИО ИДСТУ СО РАН. - 2011.

- С. 87-91.

[147] Яруллин, Р. С. Об одном алгоритме отсечений для задачи выпуклого программирования [Электронный ресурс] / И.Я. Заботин, Р.С. Яруллин // 38-ая конференция-школа молодых ученых «Информационные технологии и системы (ИТиС'14)» (г. Нижний Новгород, 1 - 5 сентября 2014 г.). М.: ИПГП4 РАН. - 2014. - С. 2 - 5. Режим доступа: http://itas2014.iitp.ru/iti/searcli.html (дата обращения 22.10.2014).

[148] В alas, Е. An additive algorithm for solving linear programs with zero-one variables [Text] / E. Balas // J. ORSA. - 1965. - V. 13, N 4,- P. 517 - 546.

[149] Balas, E. Intersection cuts - a new type of cutting planes for integer programming [Text] / E. Balas // Operations Research. - 1971. - V. 19.

- P. 19-39.

[150] Dantzig, G. B. Note on solving linear programs in integers |Text| / G.B. Dantzig // Naval. Res. Log. Quart. - 1959. - V. 6, N 1. - P. 75 - 76.

[151] Gornory, R.E. An algorithm for integer solutions to linear programs, in R.L. Graves and P. Wolfe eds. |Text] / R.E. Gomory // Recent Advances in Mathematical Programming, McGraw-Hill, New York. - 1963. - P. 269 -302.

[152] Gomory, R.E. Outline of an algorithm for integer solutions to linear programs [Text] / R.E. Gomory // Bulletin of the American Mathematical Society. - 1958. - V. 64, N 5. - P. 275 - 278.

[153] Grotschel, M. Geometric algorithms and combinatorial optimization [Text| / M. Grotschel, L. Lovasz, A. Schrijver// Berlin a.o.: Springer. - 1988. -XII. - 362 p.

[154] Kelley, J.E. The cutting-plane method for solving convex programs / J.E. Kellev // SI AM J. Control. - 1960. - V. 8, N 4. - P. 703 - 712.

[155] Kiwiel, K.C. An ellipsoid trust region bundle method for nonsmooth convex minimization [Text] / K. C. Kiwiel // SIAM Journal on Control and Optimization. - 1989. - V. 27, N 4. - P. 737 - 757.

156

157

158

159

160

161

162

Kiwiel, K.C. Exact penalty functions in proximal bundle methods for constrained convex nonclifferentiable minimization [Text] / K.C. Kiwiel // Mathematical Programming. - 1991. - V. 52, N 2, Ser. B. - P. 285 - 302.

Kiwiel, K.C. Proximity control in bundle methods for convex nondifferentiable minimization [Text] / K. C. Kiwiel // Mathematical Programming. - 1.990. - V. 46, N. 1. - P. 105 - 122.

Lemarechal, C. New variants of bundle methods |Text] / C. Lemarechal, A. S. Nemirovskii, Yu. E. Nesterov // Mathematical Programming. - 1995. -V. 69. - P. Ill - 148.

Lemarechal, C. Variable metric bundle methods: From conceptual to implementable forms |Text] / C. Lemarechal, C. Sagastizabal // Mathematical Programming. - 1997. - V. 76. - P. 39.3 - 410.

Topkis, D.M. Cutting plane methods without nested constraint sets / D.M. Topkis // Operat. Res. - 1970. - N 3.

Veinot, A.F. The supporting hyperplane method lor unimodal programming / A. F. Veinot // Operat. Res. - 1967. - V. 15, N 1. - P. 147 - 152.

Yarullin, R.S. A cutting method for finding discrete minima,x with dropping of cutting planes |Electronic resource (SCOPUS)| /' I.Ya. Zabotin, R.S. Yarullin // Lobachevskii .Journal of Mathematics. - 2014. - V. 35, N 2. -P. 157- 163. - URL: http://www.springer.com/mathematics/journal/12202 (дата обращения: 22.10.2014).

[163] Zoutendijk, С. Nonlinear programming: a numerical survey / G. Zoutendijk // SIAM J. Control. - 1966. - V. 4, /V 1. - P. 194 - 210.