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

За более чем тридцать лет, прошедших со времени появления быстродействующих ЭВМ, математическое программирование стало стандартным инструментом исследований в управлении, системном анализе и других областях науки и техники. Задачи математического программирования, т. е. нахождение условных экстремумов функций многих переменных, часто требуют для своего решения больших затрат вычислительной работы. Поэтому большое значение и актуальность приобретает анализ эффективности алгоритмов математического программирования. Хотя теория не в состоянии полностью обслужить практику и последняя часто включает эвристические и неформальные диалоговые приемы [Ъ5], 11^], важность и актуальность теоретического изучения эффективности алгоритмов в математическом программировании и алгоритмической сложности различных классов экстремальных задач не вызывает сомнений. Об этом, по-видимому, свидетельствует и резкое увеличение числа работ по теории сложности в математическом программировании — направлению, к которому может быть отнесена и настоящая работа.

Следует сразу же отметить, что понятия «эффективности», «сложности» алгоритма могут быть определены по-разному, см., например, [28]. Существует несколько критериев, по которым можно оценивать эффективность алгоритма. Однако два критерия, дающих информацию о вычислительных ресурсах, необходимых алгоритму по мере роста размера задачи, наиболее стандартны и используются в большинстве работ. Во-первых, это временная сложность алгоритма, т. е. гарантированная оценка = «Ь С Ь» } времени работы алгоритма в зависимости от длины входа Ь задачи — числа битов в ее входной записи. Во-вторых, это емкостная сложность алгоритма, т. е. гарантированная оценка Б — в С Ь ^ необходимого алгоритму битового объема памяти в зависимости от длины входа задачи, см., например, первую главу I 2, ]. В настоящей работе эффективность алгоритмов будет также оцениваться с помощью этих двух критериев.

Конечно, приведенные выше определения временной и емкостной сложности алгоритма носят весьма предварительный характер и должны быть уточнены на базе некоторой конкретной модели вычислительного устройства. Такое уточнение будет произведено ниже на базе равнодоступной адресной машины 17 8 3,12.], хотя в принципе для наших целей годятся любые другие стандартные модели вычислений, типа машины Тьюринга, автомата фон Неймана.

I Ъ 1 ] и т. п. Итак, под теоретическим анализом эффективности алгоритма в дальнейшем понимается изучение его временной и емкостной сложности или, содержательно, определение времени и памяти, необходимых алгоритму для решения задач данного размера в расчете на худший случай.

Начальным этапом теоретического изучения вычислительного алгоритма в математическом программировании можно, по-видимому, считать доказательство его сходимости. Однако сходимость алгоритма еще не означает его приемлемость на практике. С этим обстоятельством в математическом программировании столкнулись очень скоро, когда стали множиться примеры возникших из практики задач, решение которых, несмотря на наличие теоретически сходящихся алгоритмов, встречает серьезные вычислительные трудности из-за громадного увеличения объема вычислительной работы с ростом размера задачи, так что уже при скромных размерах входных данных решение становится невозможным даже на мощных ЭВМ. На основании опыта к таким практически трудным задачам в математическом программировании были отнесены, например, общая задача квадратичного программирования, т. е. задача минимизации / невыпуклого / квадратичного функционала при линейных ограничениях-неравенствах на вещественные неизвестные, такой ее частный случай, как минимизация квадратичного функционала на единичном кубе, общая задача линейного целочисленного программирования, общая задача 0,1 — линейного / булевого / программирования, большое число задач дискретной комбинаторной оптимизации, допускающих постановку в виде задач математического программирования — задача о покрытиях и об упаковках, задача коммивояжера и поиск гамильтонова цикла в графе, определение хроматического числа и нахождение максимальной клики или разреза в графе и т. д. Известные в настоящее время алгоритмы решения этих задач характеризуются тем, что имеют экспоненциальную временную сложность «Ъ ^ С^, т. е. могут требовать экспоненциально большого по размеру задачи числа операций / по поводу конкретных задач и алгоритмов см., например, I Ц 1, I 7 1, I 1 23, I? 2 3, [ 9 5 ] Л108 3, 1 116 3 > [125]/ На практике это приводит к тому, что, например, при решении задач невыпуклого квадратичного или линейного целочисленного программирования серьезные трудности начинаются уже при нескольких десятках неизвестных и ограничений.

В середине 60-х годов почти одновременно и независимо, хотя и с несколько разных позиций, в работах I 7 Ъ 3 и 18 4 1 в качестве альтернативы алгоритмам с экспоненциальной трудоемкостью было введено понятие полиномиального алгоритма. в I 8 Ц 1 такие алгоритмы назывались «хорошими» — другое распространенное название — степенной алгоритм.

— b.

Алгоритм называется полиномиальным, если его временная / а тогда, для разумных моделей, и емкостная / сложность ограничена сверху некоторым фиксированным полиномом «t ^ р (Lo от длины входа задачи. Это определение инвариантно относительно широких изменений моделей вычислительных устройств, поскольку стандартные модели взаимно моделируют друг друга с не более чем полиномиальным увеличением времени, см., например, 12.] или 127]. Интуитивно, алгоритм полиномиален, если для его реализации достаточен объем вычислений, ограниченный полиномом от размера задачи — битовой длины ее входной записи.

К полиномиальным алгоритмам относятся многие эффективные процедуры прикладной математики: алгоритм сложения и умножения целых чисел «столбиком», алгоритм Евклида нахождения наибольшего общего делителя целых чисел [19 1, L? 6 ] и полиномов с целыми коэффициентами [761, [ 19 1, Г 7 5 ], [ € 7 ]. алгоритм Штурма для изоляции вещественных корней полиномов с целыми коэффициентами [105], 1 ?€>], алгоритм Гаусса решения систем линейных уравнений с целыми коэффициентами в поле рациональных чисел, алгоритм кратчайших путей Форда и Фалкерсона нахождения максимального потока и минимального разреза в сети с целочисленными пропускными способностями [89], 111], алгоритм Эдмондса поиска минимального реберного покрытия и максимального паросочетания в графе с целочисленными весами на ребрах [85] и т. д. Входными данными задач, для которых предназначены эти алгоритмы, являются, как и всвду в дальнейшем, массивы целых чисел в двоичной записи и под длиной входа Ц задачи понимается полное число битов во входном массиве. Поэтому, например, полиномиальность алгоритма Гаусса в поле рациональных чисел объясняется не только тем, что для реализации алгоритма достаточно выполнить кубическое по числу неизвестных количество арифметических операций над рациональными числами, но также и тем, что число двоичных разрядов в числителях и знаменателях встречающихся в вычислениях рациональных чисел полиномиально / линейно / по входу.

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

Сказанное выше объясняет разумность, по крайней мере, на нынешнем этапе развития теории, разделения вычислительных задач по сложности на два класса, в зависимости от того, допускают ли они построение полиномиального разрешающего алгоритма, причем в этой классификации задачи, входящие в класс П полиномиально-разрешимых, считаются «простыми». Полиномиальная классификация содержательных задач по сложности является одной из основ*/ «Разумная рабочая гипотеза, которую впервые стал защищать Дж. Эдмондс [ в Ч1 в связи с проблемами теории графов и целочисленного программирования и которая поныне широко принята, состоит в том, что такого рода проблема может считаться легко решаемой тогда и только тогда, когда существует алгоритм ее решения со временем работы, которое ограничено полиномом от размера входных данных» 117 3 .

Разумеется, с практической точки зрения вычисления со сложностью Ь и 2 при 100 одинаковы — они невыполнимы, так что «простота» П не имеет «физического» смысла" I Ъ ® 1. ных проблематик. современной теории сложности вычислений и, применительно к математическому программированию, будет являться центральной в настоящей работе.

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

Важным шагом в направлении полиномиальной классификации содержательных задач по сложности явилась теория полиномиальной сводимости и полноты, развитая в начале 70-х годов в I 1 Ъ 1 и проиллюстрированная большим числом примеров в [17]. Одно из следствий этой теории состоит, в частности, в том, что все перечисленные на стр 7 трудные задачи математического программирования эквивалентны между собой в смысле полиномиальной классификации — либо все они полиномиально-разрешимы, либо, ни одна из них таковой не является. Поскольку в дальнейшем понадобятся такие понятия этой теории, как полиномиальная сводимость одной задачи к другой, принадлежность задачи распознавания / предиката, языка / к классам Р3 и N, понятияполной и N1= -трудной задачи, приведем здесь, не слишком формально, но с достаточной для дальнейшего степенью детализации, соответствующие определения.

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

Говорят, что задача, А ± полиномиально сводится к задаче, А г, если существует пара алгоритмов dl и jb, первый из которых преобразует за полиномиальное время входные данные задачи A i во входные данные задачи Аг, а второй преобразует за полиномиальное время решение получившейся задачи, А г в решение исходной задачи, А ± .

Если, А ^ полиномиально сводится к, А г, то для решения А^ можно сначала применить dL, затем решить получившуюся задачу A z, а после этого применить к найденному решению j!>. Поэтому временная сложность «t ^ С L решения первой задачи ограничена сверху суперпозицией р^ о «t^ о р^, где (L — временная сложность решения второй задачи и р^, р^ - пара полиномов. Например, если вторая задача полиномиально-разрешима, то это верно и для первой, если вторая задача разрешима за экспоненциальное по длине входа время «t ^ 2. ^ L ^ «где р — полином, то и первая является таковой. Ясно также, что отношение полиномиальной сводимости частично упорядочивает задачи по сложности. В частности, задачи называются полином I, а л ь н о —эквивалентными, если они взаимно полиномиально сводятся друг к другу.

Рассмотрим теперь задачи распознавания — задачи, в которых требуется распознать некоторое свойство входных данных и в зависимости от результата ответить либо «да», либо «нет». Будем по-прежнему считать, что входные данные задач задаются списками <х целых чисел в двоичной записи и называть длиной входа 1″ = 1-«(ЪО задачи число битов во входном списке*^. Вот два примера таких задач.

Задача, А. По произвольной системе линейных диофантовых неравенств, заданной списком 01 целочисленных коэффициентов в двоичной записи, определить ее совместность / «да» / или несовместность / «нет» / в целочисленных переменных.

Задача В. То же самое для систем линейных диофантовых равенств.

Пусть Р13 обозначает класс полиномиально-разрешимых задач распознавания, <= П. Например, известно [12 4 1, что задача В определения совместности систем линейных диофантовых равенств принадлежит Р-3, т. е. разрешима за полиномиальное по длине входа время.

Принадлежность к Р0 задачи, А распознавания совместности систем линейных диофантовых неравенств в настоящее время не известна и, более того, вызывает серьезные сомнения. Однако задача, А заведомо принадлежит к более широкому классу N Р3 задач распознавания, определяемому следующим образом.

Говорят, что задача распознавания принадлежит Nf: э, если таким образом, задача распознавания — это некоторый (рекурсивный) предикат, заданный на множестве сшйк&в *х. Иногда вместо задачи распознавания говорят о соответствующем языке, подразумевая под ним множество тех списков 01, для которых ответом является «да» .

1. На множестве входных списков сх и произвольных списков х целых чисел в двоичной записи определен некоторый предикат ОС сх, ос"), в дальнейшем называемый «ос является доказательством «да» для.

СХПри данном СХ ответ «да» дается тогда и только тогда, когда для сх существует некоторое доказательство ос .

2. Проверка «ос является доказательством «да» для сх «осуществима за полиномиальное по длине записи сх и X время, т. е. предикат 0(сх, о0 полиномиально-разрешим.

3. Если при данном входе сх ответом является «да», то существует доказательство ос, длина которого ограничена некоторым фиксированным полиномом ^ р (1д (сО)от длины входа <Х .

Иногда условия 1−3 коротко формулируют так: если ответ на вопрос сх оказывается «да», то существует короткое, т. е. полиномиальное по длине вопроса, доказательство ответа. Подчеркнем, что речь идет лишь о существовании полиномиального доказательства ос, при этом совершенно не ясно, можно ли за полиномиальное время.

— рс 1-(со) находить его среди? списков, длина которых удовлетворяет условию 3. Поэтому класс МЯ⁵ часто называют классом задач распознавания, разрешимых за полиномиальное по входу время на недетерминированных вычислительных устройствах, подразумевая при этом следующее: если для данного сх ответ положителен, то недетерминированная машина может сначала бит за битом угадать полиномиальное доказательство ос, а затем, действуя обычным детерминированным способом, за полиномиальное по входу время проверить О (схос) и продемонстрировать. правильность доказательства. Отметим, что недетерминированные вычисления в дальнейшем явно не используются и что другое распространенное название N Р10 — класс переборных задач распознавания.

Проиллюстрируем сказанное на примере задачи, А, доказав ее принадлежность к 1в53, 1112.3. Если система линейных диофантовых неравенств сх совместна, то доказательством ее совместности можно считать предъявление целочисленного решения ос. Поэтому в качестве 0(<�х, х) можно взять предикат «при подстановке целочисленного вектора «X, заданного своей двоичной записью, в систему линейных диофантовых неравенств сх, заданную двоичной записью коэффициентов, эта система удовлетворяется», выполнив, тем самым, условие I. Условие 2 очевидно, поскольку подстановка ос, в сх, выполняется за полиномиальное по длине записи сх и ос время. Справедливость условия 3 вытекает из следующей теоремы, Е&euro->5] ,[Юо]: совместная система линейных диофантовых неравенств сх обладает целочисленным решением X, длина двоичной записи которого линейна по длине двоичной записи ос. Итак, задача, А принадлежит МР3, тогда как ее принадлежность к Р10 не установлена, поскольку для этого фактически нужно нечто большее — предъявить способ нахождения линейного по длине входа решения ос за полиномиальное время.

Вот еще более простой пример такого рода, задача С о раскраске графов: по произвольному графу сх, заданному списком смежности вершин, выяснить, можно ли раскрасить вершины графа в заданное число цветов так, чтобы смежные вершины были выкрашены в разный цвет. Эта задача принадлежит NI—', потому что если ответом является «да», то существует короткое доказательство ответа — достаточно угадать раскраску 'Эс, а затем за полиномиальное время убедиться, что все пары смежных вершин выкрашены в разный цвет. Однако принадлежность этой задачи к I—^ не известна даже для случая ХШ> трехцветной раскраски планарных графов.

Класс NI—' является весьма широким и, включая в себя класс Р3 полиномиально-разрешимых задач, содержит также очень много известных трудных задач распознавания, которые исследовались на протяжении десятилетий и для которых все попытки построить полиномиальный разрешающий алгоритм остались безрезультатными. Кроме уже упоминавшихся задач, А, С и ТЭ, такими задачами из МР являются, например, задача Е распознавания выполнимости пропозициональных формул и ее частный случай Г — распознавание выполнимости конъюктивных нормальных форм, задача распознавания совместности систем булевых неравенств, задача Н распознавания изоморфной вложимости графов, задача I распознавания разрешимости в натуральных числах 'хе: [о > а-£ ] сравнений вида.

Хг С пг^>с1 а,^, задача 3 распознавания гамильтоновости графов, ее частный случай К — распознавание гамильтоновости пла-нарных графов и еще сотни других задач, чья принадлежность к классу Р3 не известна, тогда как их принадлежность к мр очевидна.

Ввиду широты класса 1МР=> тем более примечательно, что, как это было впервые показано в [2.&1, в этом классе имеются самые сложные задачи, называемые универсальными или МР — полными.

Говорят, что задача распознавания ИР3 -полна, если.

1. эта задача принадлежит к классу МР и.

О о.

2. все другие задачи из этого класса к ней полиномиально сводятся .

В частности, все ЫР3- полные задачи полиномиально — эквивалентны между собой и построение полиномиального алгоритма для хотя бы одной из них означало бы построение полиномиального алгоритма для всех задач из N Р3.

•* / здесь при желании можно считать алгоритм, фигурирующий в определении полиномиальной сводимости, тождественным, т. е. переводящим «да» в «да» и «нет» в «нет» .

Первые примеры NP — полных задач были построены в t.233 — это задачи распознавания Е, F" и И. Если некоторая известная полная задача полиномиально сводится к другой задаче из NF3, то последняя также является полной. С помощью этого приема, сводя одни задачи к другим, в дальнейшем доказали NP полноту задач, А, С, G, О [17], X) [981, 1 U51, К [99], а также большого числа других задач, см., например, [ S ], где приведена обширная библиография по этому вопросу, включающая более 500 работ и список, содержащий более 300 NF3 — полных задач из различных областей прикладной математики.

Хотя основной вопрос теории полиномиальной сводимости и полноты — совпадают ли классы и является открытой фундаментальной проблемой, сама теория активно используется в современных исследованиях по эффективности алгоритмов. Широко распространена гипотеза, что F33 Ф NP0, так что доказательство NF5 — полноты некоторой конкретной задачи считается весьма сильным доводом в пользу бесперспективности дальнейших поисков полиномиальных алгоритмов ее решения.

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

Задача / не обязательно распознавания / называется NF3 —трудной, если к ней полиномиально сводится некоторая NF13 — полная задача распознавания, т. е. трудные задачи не проще полных.

Очевидными примерами N ^ - трудных задач являются все N 1=3 — полные задачи распознавания. Другие примеры — это задачи математического программирования, включая перечисленные на стр. 7: задача линейного целочисленного программирования, задача булевого программирования, задача о рюкзаке, задача / невыпуклого / квадратичного программирования, задача о линейной дополнительности, задачи о покрытиях, разбиениях и упаковках, задача коммивояжера, задача Штейнера, много задач теории расписаний [ $ ] и т. д. Вообще, не будет преувеличением сказать, что большинство изучающихся в математическом программировании задач оказываются N1=3 — трудными и, таким образом, вопрос об из полиномиальной разрешимости упирается в тупик проблемы Р3 = N? Кроме 'того, известно немного видов полиномиально-разрешимых задач математического программирования и почти все они довольно узки и относятся к дискретной комбинаторной оптимизации и теории графов. Поэтому, не пытаясь охватить все множество направлений теоретических исследований по эффективности алгоритмов в математическом программировании, можно попытаться перечислить те из них, которые в настоящее время так или иначе связаны с возможностью получения полиномиальных сложностных оценок, следующим образом.

I. Неполиномиальные нижние оценки сложности алгоритмов.

Следует сразу же отметить, что в настоящее время для задач математического программирования не известно не только ни одной неполиномиальной, но даже, скажем, квадратичной нижней оценки временной сложности, справедливой в классе всех алгоритмов / например, на многоленточных машинах Тьюринга / Имеющиеся неполиномиальные нижние оценки временной сложности относятся к конкретным алгоритмам или, иногда, к некоторым довольно узким классам алгоритмов. Например, в уже упоминавшихся работах I Ц ] ,.

17], [11] Д7г], 1951, Г 1083 ,[1163, Г12 $ 1 показана экспоненциальная сложность некоторых специальных алгоритмов для^Р3 — трудных задач, в работе ПШ], а также [62], [?9] ,.

— 1Ь.

11 021 ,[107], [ Ш1] доказывалась экспоненциальная по числу ограничений и неизвестных сложность симплекс-метода и его модификаций для решения задач линейного программирования, в работе 11] этот же факт доказывался для венгерского метода и метода потенциалов решения транспортных задач, в работах [Ц6] и [101],[1Ъ6] «показывалась экспоненциальная по числу правильных знаков сложность игровых итеративных алгоритмов и релаксационных методов для приближенного решения задач линейного программирования и т. д.

2. Доказательство полиномиальной разрешимости конкретных задач.

К этой проблематике можно отнести, например, работу [11?], где был предложен полиномиальный алгоритм нахождения минимального остовного дерева графа, работу [ $ Ц ], где был построен полиномиальный алгоритм поиска минимального реберного покрытия и максимального паросочетания в графе, работы 18 9] ,[11], где была доказана полиномиальная разрешимость потоковых задач линейного программирования, работу [1241 «гДе был описан полиномиальный алгоритм решения систем линейных диофантовых уравнений, а также недавнюю работу [12.0]. в которой доказана полиномиальная разрешимость задач линейного целочисленного программирования с фиксированным числом неизвестных. Указанная проблематика составляет основное содержание глав 1−3 и 6- настоящей работы.

3. Улучшение верхних полиномиальных оценок сложности.

Когда полиномиальная разрешимость задачи установлена, стараются снизить степень полинома в оценке сложности и сделать алгоритм более быстрым по порядку. Например, первоначальная полиномиальная оценка [11?] для задачи поиска минимального остовного дерева графа улучшалась затем в 1ЪЦ1, CfOl, [i.40], алгоритм.

841 для задачи о паросочетаниях улучшался в (9 2], [94 1, а первоначальная полиномиальная оценка 18 9] для задачи о максимальном потоке в сети улучшалась по порядку не менее пяти раз в lili ,[16], [12*3,1541 Л 96] ,[951 • Этой проблематике и принципам построения «быстрых» алгоритмов посвящена обширная литература, см., например, обзоры [ Ъ9 ] и [ 4 31 и имеющуюся там библиографию, а также монографии [ 2 ] ,[191 «[Ъб].

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

4. Полиномиальная сводимость и полнота.

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

Наконец, к перечисленным выше пунктам можно добавить еще один, не относящийся непосредственно к теории сложности вычислений.

5. Изучение вспомогательных свойств задачи, связанных со сложностью ее решения.

Применение той или иной алгоритмической техники предполагает изучение определенных характеристик задачи, влияющих на оценки ее сложности, причем часто такое изучение имеет и самостоятельный интерес. Например, в дискретной оптимизации важную роль играют линейные описания комбинаторных многогранников, см., например, [151, I 2. Ц 1 .1 ЮЬ]. Г Iii ] > Для построения полиномиальных алгоритмов распознавания изоморфизма графов ограниченной валентности потребовалось изучение групп автоморфизмов таких графов [12.2]. [ 1Ъ], для изоляции корней полиномов необходимы оценки на границы решений и сепаратор [?6Д, [ i ъо 1 и т. д. В частности, глава 4 диссертации посвящена изучению границ решений некоторых задач математического программирования и хотя в дальнейшем результаты этой главы используются для получения сложностных оценок, в самой главе это понятие даже не упоминается.

Итак, получаемые в дальнейшем результаты могут быть отнесены к разделам 2−5. Перейдем к более конкретному изложению тематики диссертации и ее целей. Рассматриваемые в диссертации задачи могут быть в самом общем виде сформулированы как задачи полиномиального / алгебраического / программирования: минимизировать зависящий от п скалярных переменных полином f0 (ос1.)осГ1,> при условии выполнения системы «т полиномиальных неравенств.

Здесь «Р0, ,. ,^т — полиномы с целыми коэффициентами, причем всюду в дальнейшем предполагается, что задача задается стандартным образом — списком ненулевых целочисленных коэффициентов полиномов в двоичной записи. Два основных случая, изучаемых в математическом программировании и в настоящей работе, таковы: переменные вещественны осе П¹⁴ и переменные целочисленны х&euro- %п. Задачи полиномиального программирования с целочисленными переменными иногда называют задачами диофантового программирования.

Степенью с!, задачи называется максимальная из степеней / по совокупности переменных / входящих в нее полиномов, высотой Р1 задачи называется максимум модулей задающих ее целочисленных коэффициентов, а длиной входа Ь задачи называется, как и прежде, числа битов во входном списке коэффициентов. Не будет ошибкой считать, что длина входа — это сумма двоичных длин Ь (сО = ] + ^ «взятая по всем ненулевым коэффициентам а. задачи, хотя на самом деле, единственное свойство величины Ь, используемое в дальнейшем, состоит в выполнении неравенства Ь > таос | гх, т., км}. Смысл ЭТОГО неравенства прост: при стандартной записи задачи требуется хотя бы по одному биту на каждое неизвестное и ограничение, а также.

Ь (^ ^ битов для двоичной записи максимального по модулю коэффициента, т. е. высоты. Отметим также, что понятие длины входа будет в дальнейшем использоваться лишь для классов задач, в которых степень с! будет фиксироваться / задачи линейного программирования, задачи квадратичного программирования и т. д. /, так что в конкретизации записи мономов нет нужды.

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

IX/ Существуют конкретные диофантовы уравнения ,'зс1, «эс^ - О ' проблема распознавания совместности которых в целых числах «• • •,^п. при произвольных ае! алгоритмически неразрешима 12.91, [ЪО], см. также [26], стр. 64. В частности, поскольку любое диофантово уравнение сводится добавлением новых неизвестных к системе квадратичных диофантовых неравенств, не существует общего алгоритма определения совместности систем квадратичных диофантовых неравенств при достаточно больших фиксированных значениях т и т, см. по этому поводу также [66] и 1109] .

2 1С / Даже для одного квадратичного уравнения сх1'х^ +<�хг'Эсг = схъ с двумя натуральными неизвестными и 'Х г задача распознавания по натуральным коэффициентам сц, а, г, его разрешимости является М^-полной [25 1, другие примеры такого рода собраны в 1⁵¹.

3 / Определение совместности систем линейных диофантовых неравенств является, как указывалось выше, N1=3 -полной задачей. В частности, все известные в настоящее время алгоритмы ее решения имеют экспоненциальную по длине входа временную сложность.

I 1Й / В отличие от целочисленного случая, существуют алгоритмы определения совместности в вещественных переменных произвольных систем полиномиальных неравенств и алгоритмы, в определенном смысле точно решающие произвольные задачи полиномиального программирования с вещественными неизвестными. Речь идет о разрешающих процедурах для элементарной теории вещественно-замкнутых полей, т. е. для алгебры Тарского ГЬ53, , 7 Ц 1 [5]. Однако эти процедуры, предназначенные для решения гораздо более широкого, чем задачи программирования, класса проблем, весьма тяжеловесны и трудоемки, так что время работы даже лучшей из них [? 7 3 удается ограничить сверху лишь двойной экспонентой 2. длины входа, см. по этому поводу также 19¹ и 15] .

2 / Простейшие нелинейные задачи полиномиального программирования с вещественными переменными оказываются не проще дискретных задач булевого программирования, в которых переменные принимают значение 0 или I. Действительно, как было замечено в ЦЪ1], условие булевости переменных. ., ос^ может быть выражено в виде системы одного невыпуклого квадратичного и 2. П линейных ограничений.

0″ 1, ., 0″ 0сл*±-, + > + относительно вещественных переменных. В частности, поскольку определение совместности систем булевых линейных неравенств является МЯ113 — полной задачей, уже простейшая из нелинейных • задач полиномиального программирования — определение совместности в вещественных переменных систем линейных неравенств, отягченных одним квадратичным ограничением, также оказывается МР=>- полной. Отметим, что этот факт в определенном смысле переносится и на отыскание приближенных решений таких задач, см. § 7.

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

В первой главе рассматривается нахождение приближенных решений, задач выпуклого полиномиального программирования с вещественными неизвестными в предположении, что для задачи априорно задается радиус ^ шара с центром в начале координат, внутри которого находится некоторое решение. Оказывается, что если решение внутри шара действительно существует, то его можно найти с точностью? за время, ограниченное при фиксированной степени задачи полиномом от длины входа 1-" и от величины —, равной логарифму отношения радиуса локализации решения к требуемой кроме ставших уже классическими по своим приложениям задач линейного и выпуклого квадратичного программирования, в виде нелинейных задач выпуклого полиномиального программирования могут быть поставлены, например, некоторые задачи размещения центров обслуживания 190], 1911 ,[12?], [ 1Ъ7 ], детерминированные нелинейные эквиваленты задач линейного стохастического программирования 160], 11 г в ], задачи приближениям таблично-заданных функций линейными комбинациями других функций в различных нормах I 9 3, [12.91, задачи, возникающие в методах возможных направлений второго порядка IЪ Ъ ], [ 12 8 ] и некоторые другие {118 5 .

Ж * / с этого момента желательно знакомство с принятой в работе моделью вычислений, описанной сразу после введения на стр. 33−37. точности / конечно, в тексте главы приведены гораздо более детальные оценки / Излагаемый здесь алгоритм — это версия метода эллипсоидов, предложенного в 1611 и 15 8]. Имеется, однако, одно отличие, которое существенно усложняет изложение и заставляет несколько изменить сам алгоритм — речь идет об учете конечной точности вычислений и конечной разрядности двоично-рациональных чисел, с которыми оперирует алгоритм. Дело в том, что данные в.

161] и 15 3] описания метода эллипсоидов полностью игнорировали битовую структуру данных в вычислительной машине, т. е. исходили из распространенного в математическом программировании допущения, что имеется возможность хранить вещественные (а не двоично-рациональные) числа, точно С, а не приближенно «) выполнять над ними элементарные операции + , —, х, /, V и сравнения, а также точно вычислять значения функций^, $± ,., т и их градиентов. Для наших целей такой подход неприемлем, поскольку термин «алгоритм» понимается вскду в работе в строгом смысле.

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

— необходимый аспект описания алгоритма, доказательства сходимости и оценки его сложности. Грубо говоря, такой подход предполагает, что при извлечении квадратного корня из скаляра нужно указывать число разрядов до и после запятой в позиционной записи скаляра и результата и всвду в дальнейшем учитывать «шлейф ошибок», возникший из-за того, что запомненный в машине результат.

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

Вторая глава диссертации посвящена одному из наиболее стандартных разделов математического программирования — линейному программированию. Ясно, что разрешимая задача линейного программирования с вещественными неизвестными всегда имеет рациональное решение — ведь речь идет о задачах с целыми коэффициентами. Основной результат этой главы состоит в том, что можно проверить разрешимость задачи и найти ее точное рациональное решение за полиномиальное по входной длине время, тогда как ранее были известны лишь алгоритмы с экспоненциальными оценками трудоемкости в расчете на худший случай. Временная сложность излагаемого здесь полиномиального алгоритма точного решения задач линейного программирования ограничена на машинах РАМ величиной порядка гг^а/хС^т^т^а^^,^)'^^г С^,^-) ] «ГДе^. ^ и Рг — число неизвестных, ограничений и высота задачи (оценки числа элементарных операций, ячеек памяти и их двоичной длины приводятся в тексте главы. В частности, за указанное выше время можно точно решать системы линейных неравенств в поле рациональных чисел. Помимо полиномиального алгоритма линейного программирования во второй главе также описывается полиномиальный алгоритм дробно-линейного программирования и кратко обсуждаются некоторые приложения 110 Ъ 1, [ ± 1 Ъ 1 этих теоретических результатов и метода эллипсоидов в дискретной комбинаторной оптимизации.

В третьей главе диссертации рассматривается другая стандартная задача математического программирования — задача квадратичного программирования, состоящая в минимизации выпуклого квадратичного полинома при линейных ограничениях — неравенствах на вещественные неизвестные. В случае разрешимости эта задача также имеет рациональное решение и, оказывается, это решение можно точно найти вместе с проверкой разрешимости задачи за полиномиальное по ее входу время Сп + гл^п5 бо², Кгх (оценки числа элементарных операций, ячеек и их двоичной длины приведены в тексте главы }. Кроме доказательства полиномиальной разрешимости выпуклого квадратичного программирования, в третьей главе получено следующее обобщение этого результата**'': задача распознавания совместности в вещественных неизвестных систем линейных неравенств, отягченных произвольным фиксированным числом выпуклых квадратичных ограничений, полиномиально-разрешима, сравни с невыпуклым случаем, описанным в пункте 2 ГСЗ. В третьей главе также рассмотрена задача о нахождении минимального накрывающего шара для заданной системы точек в евклидовом пространстве и описан полиномиальный алгоритм ее точного решения.

В четвертой главе вновь, как и в первой, рассматриваются произвольные задачи выпуклого полиномиального программирования, причем как с вещественными, так и с целочисленными неизвестными. Однако, если в первой главе предполагался априорно заданным радиус В. шара с центром в начале координат, внутри которого находится некоторое решение задачи, если таковое вообще существует, то четвертая глава посвящена как раз отысканию верхней оценки этого радиуса через число переменных, ограничений, сте / полиномиальная разрешимость выпуклого квадратичного программирования была доказана С с худшими оценками сложности «) совместно с М. К. Козловым и С. П. Тарасовым I 2о], 1211. это обобщение, а также результаты глав 4 и 5 получены совместно с С. П. Тарасовым 1Ш]. пень и высоту задачи. Полученная здесь оценка границ решений задач выпуклого полиномиального программирования справедлива не только для задач с вещественными и/или целочисленными неизвестными, но и в более общей ситуации, когда вектор неизвестных пробегает произвольное множество я вещественных векторов, инвариантное относительно сдвигов на целые векторы (такие множества названы в диссертации периодическими «). Отметим, что при фиксированной степени задачи с1 ^ 2. найденная граница решений оказывается дважды экспоненциальной по минимуму из числа неизвестных и ограничений тлггС^,"^) р р р полином т. е. дважды экспоненциальной по длине входа задачи, однако это соответствует действительности и в работе указываются простые примеры выпуклых полиномиальных задач, для которых дважды экспоненциальный рост величины решения достижим в любом периодическом множестве. При нахождении границ решений задач выпуклого полиномиального программирования в периодических множествах, в четвертой главе диссертации получены также два результата вспомогательного характера, представляющие, возможно, самостоятельный интерес. Во-первых, предложен простой и эффективный алгоритм построения рецессивных конусов £Ъ71 выпуклых полиномов, другие, более сложные алгоритмы см. в I Ъ 1, [ 1Ъ9] • Во-вторых, по аналогии с положительно определенными квадратичными формами, получены оценки степени обусловленности произвольных выпуклых гладких форм, в которых аналогом детерминанта квадратичной формы указанный в тексте главы. служит среднее значение гессиана выпуклой формы в единичном, евклидовом шаре.

Пятая глава диссертации посвящена изучению алгоритмической сложности приближенного решения систем выпуклых полиномиальных неравенств с вещественными неизвестными, а также изучению алгоритмической сложности решения систем выпуклых полиномиальных нера-веств в целочисленных неизвестных. Поскольку решения таких систем имеют, вообще говоря, двадцы экспоненциальную по длине входа норму, то для двоичной выдачи ответа требуются экспоненциальные по входу время и память. Для преодоления этой трудности вводится понятие аддитивно-показательной записи решения, т. е. представления его в виде 'Эс •= 'Х^З. х, эсг-2., где векторы 'Эс^ ,.. ., «ЗСр, и натуральные скаляры В^, .. , § г представлены в обычном двоичном виде. Оказывается, что если разрешить печатать ответ в аддитивно-показательном виде, то, во-первых, вещественное решение систем выпуклых полиномиальных неравенств произвольной ограниченной степени находится, в случае его существования, с точностью 6 Со, О за время, ограниченное полиномом определения совместности и нахождения целочисленного решения систем выпуклых диофантовых неравенств произвольной ограниченной степени станет полиномиально-эквивалентной той же задаче для систем линейных диофантовых неравенств. Грубо говоря, результаты пятой главы можно сформулировать так: с точки зрения полиномиальной сводимости решать системы выпуклых полиномиальных неравенств произвольной ограниченной степени не труднее, чем решать системы линейных неравенств, причем как для случая вещественных, так и для случая целочисленных переменных. По-видимому, здесь уместно напомот длины входа и и от величины и, во-вторых, задача нить, что для общих систем полиномиальных неравенств ситуация совершенно иная, см. пункты 2 ИЗ и I Ц, а также § 7.

Наконец в шестой, последней, главе диссертации доказана полиномиальная разрешимость задач выпуклого диофантового программирования произвольной ограниченной степени с фиксированным числом неизвестных, что является обобщением результата 112о] о полиномиальной разрешимости задач линейного целочисленного программирования с фиксированным числом неизвестных.

Логическая зависимость между главами такова:

1 \ Ъ.

Ссылка С2> • 2. указывает на вторую формулу третьего параграфа. Внутри третьего параграфа эта формула и ссылка на нее обозначается просто (2.) •.

Основные результаты диссертации докладывались на Общем собрании Отделения математики АН СССР в декабре 1981 г., на заседании Московского математического общества, на семинарах лаборатории математической логики Ленинградского отделения Математического института АН СССР им. В. А. Стеклова, кафедры исследования операций факультета вычислительной математики и кибернетики и кафедры математической логики механико-математического факультета МГУ им. М. В. Ломоносова, лаборатории алгебры Института математики АН БССР, отдела прикладной математики и дискретной оптимизации Центрального экономико-математического института АН СССР, в Институте проблем управления АН СССР, во Всесоюзном научно-исследовательском институте системных исследований ГКНТ и АН СССР, на советско-польском научном семинаре по математическим методам в планировании и управлении экономикой, Пущино, 1979, на Юбилейной научной конференции Вычислительного центра АН СССР, Москва, 1980, на Сибирской школе-семинаре по методам оптимизации, Иркутск, 1980, на Всесоюзной школе-семинаре по математическим методам оптимизации и их приложениям в больших экономических и технических системах, Баку, 1980, на 1-й ереванской школе по теории игр, Ереван, 1981, на 5-м Всесоюзном семинаре по комбинаторному анализу, Москва, 1981, на семинаре «Оценки сложности вычислений», Ленинград, 1981, и неоднократно на семинарах лаборатории Теории и проектирования больших систем Вычислительного центра АН СССР.

Все результаты диссертации получены впервые и опубликованы в работах Г, [г±-1, 1411, 142] ,[ч?] ,[48] ,.

491, [ 5О3 ,[513,1521.

Автор глубоко благодарен члену-корреспонденту АН СССР профессору Гермогену Сергеевичу Поспелову за постоянное внимание и поддержку в работе.

ОБОЗНАЧЕНИЯ.

Перечислим некоторые обозначения, используемые на протяжении всей работы. ir, ах.

IRn, Qn.

1L lLn.

HOC II hi ли.

L (oO.

— множества действительных, рациональных и целых чисел;

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

— множество полиномов с целыми коэффициентами от и переменных;

— евклидова норма вектора, •+ ГС* У г;

— минимальное / максимальное / целое, не меньшее / не большее / действительного числа ;

— двоичный логарифм;

— число битов в двоичной записи натурального числа, а, т. е. L (oV± и L (а)-[Ео j, а J +1 .

Это обозначение будет иногда использоваться и для действительных чисел, для которых по определению полагаем Li^^L^Tl^M^ ;

— «не превосходит по порядку», т. е. запись fC*) < ^ ^ ^ означает, что для всех значений аргумента I f С^ I ^ Coast" • Отметим, что величины константных множителей будут «скромными» и нигде не будут превосходить нескольких десятков;

— конец доказательства. I.

МОДЕЛЬ ВЫЧИСЛЕНИЙ.

В качестве модели вычислений в настоящей работе удобно взять модель равнодоступной адресной машины, сокращенно — РАМ, являющуюся абстракцией цифровой вычислительной машины общего назначения. Подробное описание этой модели можно найти в 123, 1Ъ8], 1?83,а приводимое ниже описание скомпиллировано из [21, [ Ъ 8 ] с некоторыми непринципиальными изменениями.

Адресная машина имеет память, составленную из ячеек, занумерованных всеми двоичными натуральными числами 1=1, 10, 11,. Номер I ячейки называется ее адресом. Обычно считают, что ячейки могут хранить целые числа в двоичной записи. Нам будет удобно считать, что ячейки могут хранить не только целые, но и двоично-рациональные числа в позиционной записи. Например, число, — 11? / Ъ 2. будет представлено в ячейке словом -11,10 101 Длина ячейки — это число Е двоичных разрядов, необходимых для записи ее содержания-, в нашем примере 1−7. Текущая длина различных ячеек неодинакова и может меняться от шага к шагу. Содержимое ячейки с адресом I обозначается через КО. Ячейка с адресом I = 1 называется сумматором. В двух следующих ячейках будут храниться натуральные числа УСЮ) и и («11), назначение которых станет понятным из дальнейшего.

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

Обозначение команды Комментарии ггСО и<4) Засылка в сумматор содержимого ячейки с адресом I. ггС!} ггс>-гс". О ичи — 4- ггс 1) ггС17^* ичЧ")> где через * обозначен один из символов арифметических операций + , —, х, / .

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

В ячейку с адресом I записывается содержимое сумматора.

Косвенная адресация при записи. Если числог-С О не является натуральным, происходит остановка.

Арифметическая операция производится над содержимыми ячеек с адресами V и 1//, а результат записывается в сумматор. Операция производится приближенно, с точностью гУСю> правильных знаков после запятой. Если происходит деление на ноль или для записи результата требуется больше гт С 4.1 > знаков перед запятой, происходит остановка.

Приближенное извлечение квадратного корня из числа г-СI> с точностью и С1 ознаков после запятой и запись результата в сумматор. Если подкоренное выражение отрицательно, происходит остановка.

Сравнение содержимого ячеек с адресами.

I' и I «и условный переход к команде, помеченной меткой ^.

В сумматор записывается число знаков перед запятой числа гСО .

В сумматор записывается номер первого ненулевого разряда после запятой числа и С I).

Запятая в содержимом ячейки с адресом.

I сдвигается на 15(¡-О разрядов влево или вправо в зависимости от знака 1ГС1}. Если число УС*} не является целым, происходит остановка.

Остановка.

На самом деле, обозначения команд и точный способ их исполнения для дальнейшего не принципиальны. Важно только, что в репертуаре адресной машины имеются команды, позволяющие осуществлять обмен содержимым ячеек с помощью прямой и косвенной адресации, приближенно выполнять операции + ,-,*,/, с предписанным числом разрядов до и после запятой, осуществлять сравнения ^ между содержимым ячеек и условный переход, а также считать разряды внутри ячеек и сдвигать там запятую. Отметим, что операции + , —, х могут по желанию программиста выполняться точно и что можно было обойтись без приближенной операции, промоделировав ее выполнение приближенными операциями + , —, х, /, однако для простоты изложения эта операция будет сохранена. исI") ^ г<4″).

ТНЕИ СО ТО .ЛЧ гГСО Е ггс I 6Н1ГТ гга).

И, А ЦТ.

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

Предположим, что в память адресной машины были записаны некоторые входные данные и машина, выполнив конечное число к шагов, остановилась-, причем в процессе ее работы были задействованы ячейки с номерами вплоть до I .В дальнейшем будем рассматривать только такие вычисления, для которых К > I и называть их временной сложностью «Ь и емкостной сложностью Б величины = К с Е + и о, * = «Л, где И, — максимальная длина ячеек в процессе счета. Отметим, что описанная таким образом адресная машина полиномиально — эквивалентна машине Тьюринга, для которой временная сложность вычисления — это просто число тактов управляющей головки, см., например, 113.

Прокомментируем только что данные определения величин «Ъ и Б. Смысл величины в достаточно прозрачен — это оценка битового объема памяти, достаточного для реализации вычисления. Что касается величины 1, то в ее определении предполагается, что временной вес команд. +. ~ «* > / > * ^ «* «Е «6 ИI ГТ «выполняемых над числами, имеющими до и после выполнения команды не более? разрядов, ограничен величиной I и двоичной длиной адресов. Это — т.н. логарифмический весовой критерий, см. [21. Частичным оправданием такого допущения может служить тот факт, что операции х, / над I! -разрядными числами с точностью Р разрядов могут быть выполнены на такой простой «механической» модели вычислений, как машина Тьюринга, за число тактов, ограниченное по порядку величиной Е, см., например, 15 €>3, 1Ъ9], не говоря уж об остальных командах. Некоторые авторы, однако, предпочитают в определении временной сложности приписывать операциям *, /, временной вес I *, считая его более реалистичным с точки зрения имеющихся машинных реализаций 17&euro->т, 11 ±9 1, а также более детально учитывать двоичную длину адресов I 1 1 .В дальнейшем будем пользоваться данным выше простым определением временной сложности, основанном на логарифмическом весовом критерии и иногда называть величину просто временем вычисления. Однако, имея ввиду указанные варианты, в тех случаях, когда не безразличен порядок роста времени, будем давать оценки трудоемкости алгоритмов в физически более осмысленных параметрах к ,.

I и Е, от которых легко перейти к любому из этих полиномиально-эквивалентных вариантов. Напомним, что эти параметры задают, соответственно, число шагов, число ячеек и их максимальную двоичную длину в процессе вычисления. Более того, для всех описываемых в работе алгоритмов число шагов, на которых выполняются команды т~*" по обмену информацией, не превосходит числа шагов, на которых выполняются операции + , —, х, , «[ и сравнения^, а число шагов, на которых выполняются команды Г, Г и SHIFT вообще в п раз меньше, где П — число неизвестных в задаче математического программирования. Поэтому в оценках трудоемкости будут учитываться только сравнения ^ и операции +, — ,*,/,, в дальнейшем называемые элементарными. Именно, мы будем писать, что некоторый алгоритм требует для своего выполнения. элементарных операций и сравнений над числами, имеющими не более. двоичных разрядов, а также память для хранения. таких чисел.

Отметим в заключение, что алгоритмы будут описываться на обычном языке без фактического построения РАМ-программ.

ЗАКЛЮЧЕНИЕ

.

Перечислим основные результаты диссертации.

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

2 / Доказано, что следующие задачи математического программирования точно разрешимы за полиномиальное время:

— линейное, дробно-линейное и выпуклое квадратичное программирование в поле рациональных чисел;

— определение совместности в вещественных переменных систем линейных неравенств с фиксированным числом выпуклых квадратичных ограничений;

— выпуклое полиномиальное программирование с фиксированным числом целочисленных неизвестных.

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

4 / Получена оценка обусловленности гладких выпуклых форм через среднее значение гессиана в единичном евклидовом шаре.

5 / Введено понятие аддитивно-показательной записи решения и описан использующий это понятие алгоритм регуляризации систем выпуклых полиномиальных неравенств в периодических множествах.

6 / Получены результаты, отмеченные звездочкой в следующей таблице, характеризующей влияние выпуклости на алгоритмическую сложность решения систем полиномиальных неравенств: неизвестные неизвестные целочисленны вещественны системы задача МРЭ-трудна задача точно * линейных [ 1? 3 и разрешима разрешима за неравенств за экспоненциальное полиномиальное время 165]. При время, глава 2 фиксированном числе неизвестных разрешима за полиномиальное время 1120 3. системы * задача полиномиально задача может быть * выпуклых сводима к линейной, приближенно решена полиномиальных глава 5. При фиксирос точностью? за неравенств фиксированной ванном числе неизвестных полиномиально — время, полиномиальное по входу и? степени — разрешима, глава 6 глава 5. системы задача алгоритмически задача МРэтрудна полиномиальных неразрешима при [1Ъ1], причем неравенств фиксированном числе даже при заданных или уравнений неизвестных и ограниграницах решений в степени 1 2. чений 1 2.9 3 приближенной постановке § 7.

Доказательство неравенства (2. 6. Пусть сЛ и ^ - полуоси эллипсоида «V/». Замечая, что.

Л = ± ехр

П+1 г.

Л + 1.

Г Ч1^ (1 ^.

4. +) < ехр

7 * -1 г получаем ех 1) что совпадает с С 2. 6 ^ О О.

Доказательство неравенства С а. 1 «>. Замечая, что ^ > 1 и > 1, получаем из (1 > и X ^ 1 л] 1' 100 Пг X.

Юо 1чг Л (1+ Ль (1+ ЛN .

У 4 ЮОп. г Г^ 6Чпг П юопг- < ехр

Х-Сгх1-!") 64 П2, ±-оо.

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

Последнее неравенство выполнено при всех п ^ г ¦

Доказательство неравенства С х. 1ъ) Замечая, что гъ-О* * С1+ —) п е-хр

I- 1 получаем из (г.) сгл-о п еос.

Р.

Л- -V А. 1.

ЪЯгг ] и поэтому для доказательства (х.1 ъ) достаточно показать, что подэкспоненциальное выражение не превосходит величинуили, что-то же самое,.

4 Л. > Д. о.. .

Последнее неравенство выполнено при г? 5. Проверка неравенства (г. 1 ъ для оставшихся значений ъ —, ъ ц была произведена на компьютере ¦

Итак, пусть пмерный вектор ос и, а х аматрица Ь записаны на < у I у > -лентах, у^ЬСгО+Ъ .а ненулевой пмерный вектор <| записан на | ^ > -лентах. При описании алгоритма 3 ~ вычислений по формулам (2. 2. о «) приближенные значения точных величин будут обозначаться чертой над идентификатором соответствующей точной величины. Далее, помимо ранее введенного обозначения удобно также ввести обозначение.

V 1 и ц и.

1> поскольку лишь единичный вектор ^ входит в формулы (г. I о } Ш, а г I — точное вычисление вектора^. т.

Умножаем матрицу В) на вектор ^ Ч1 + ЬОг) I + ^ > — ВТ<�М> I у > • < ^ I у ^ ^ при этом умножений и п1- п. сложений производим точно. Если оказывается, что «» [ = о, то матрица В заведомо вырождена. В этом случае производим остановку алгоритма Э «». В дальнейшем полагаем ф о.

Шаг 2 — приближенное вычисление вектора ^.

Поскольку вектор ^ не меняется при умножении на произвольный нормирующий множитель, можно сдвигать одновременно во всех компонентах массива < + Ь 60 I + > запятую на одинаковое число позиций влево или вправо. Сдвигом запятой добьемся того, чтобы ненулевой массив принял вид + ^ + и хотя <зы в одной компоненте.

1 и В пеРВ0М разряд6 перед запятой находилась единица. Итак, массив записан + —лентах и, А ^ И ^ и <

Вычисляем приближенное значение и ^ «г квадрата нормы.

Иг|Нг<�Ъ + Ь (п)1 + ^ Ь + ?¦ >

Г1 1 причем «ч возведений в квадрат производим приближенно с точностью знаков после запятой, а Ь — 1 сложение производим точно. В получившейся величине нг правилен ур у — 1? -й знак, после запятой, т. е.

I — г! ^ - ч> - ч" ¦"¦ 4 I* - * иц"г — | < 1 т г.

СМ.

Извлекаем из и иг квадратный корень игр < г + 1 Ь (п) | ^ + у — ± и4? > лГ II*]"1 + I 4> + у 4 ± 7 > с точностью «у — 1 + ^ знаков после запятой.

Из С Ъ} и (м «) следует.

П[". — «у» I «.

Делим каждую компоненту вектора ^ на н^ ••.

1 *р ± ± ЬСМ + 6 > причем выполняем кавдое из делений с точностью + ^.

— - («» О + € знаков после запятой.

Из (5 ^ и (б) имеем.

И| «ТУ'Т' I * +.

J ^ 1 откуда с учетом обозначения (2.) следует.

II г — ^ II ^ - ч>-ч> + - 5.

11 1 1 «<. (?).

Итак, в результате выполнения второго шага найден вектор +, приближающий точный вектор с точностью {? «).

Шаг 3 — приближенное вычисление вектора В^.

Умножаем матрицу Б на найденный вектор ^.

В 1Ц) > * ^ < 1 I + у — * Ь О-о + 6 >

При умножении матрицы на вектор п умножений выполняем приближенно с точностью — ЬСгО + 5 знаков после запятой, а сложений производим точно. Каждая компонента вектора отличается от соответствующей компоненты вектора В ^ не более.

Л и> + 5 I. (п — 5 чем на 2. т г «» и поэтому и Г^ - Ц и *. с".

С другой стороны, из (7 имеем н в^ - н * нвн и^-^ и * + <9) и поэтому из (8} и (9) получается.

10) п е^ - в^ и *.

Таким образом, вектор В" ^ < I у-^ЬСп^+Б > приближает точный вектор В ^ с точностью (ю) .

Шаг 4 — приближенное вычисление векторов В ^ и ^ В ^.

Вычисляем значения констант v1 и V ^ по формулам (2.19) с точностью + ^ + Ь знаков после запятой.

I — ^ I * Г" «''1, (ю.

Заметим, что, а константа /<п+1 ^ также не превосходит по модулю величину ъ /. Поскольку ^ ^ Ь (гО + Ъ, из (11 > имеем Гп ^ *, 1.1,ъ. <и>

— 234.

Умножаем константы V • на вектор В> ^.

-— < 11 + у + г > • В^ < ч> + 1 I — | +5 > причем 2п умножений производим приближенно с точностью — ± + 1 знаков после, запятой.

Из (ю) и (12) имеем.

V. в г — ^ В* И * | V:! II ^ В* || ^.

II, а из (ц) вытекает.

Поэтому из ,(1Ц> и следует.

— *. ^.

В результате выполнения четвертого шага найдена пара векторов V-< | у — > + ± >, приближающих векторы.

•о. В с погрешностью < ± б «> •.

Шаг 5 — вычисление вектора ос'. Полагаем причем н сложений производим точно. Из (Чб> имеем и.

— у + Ь (п) ос'- (ос +) и ^ г (17>

На пятом шаге найден вектор 'ЭС/< ^ + 1 | >, который приближает вектор ос + ^ В ^ с точностью < ±?) .

Шаг 6 — приближенное вычисление матрицы V В .

Вычисляем значение константы. по формуле (г. 19) с точностью Ч> + Ч> знаков после запятой, а затем умножаем матрицу Ь покомпонентно на скаляр

VlB> у > ^<4.1 у + В <ср| ^ > причем п умножений производим приближенно с точностью Ч> знаков после запятой н^Ь-^В и ^ +.

Из (18) следует.

И^В- ^ВИ ^ I^гИЬи ^ + Ь (г° и поэтому.

В результате шестого шага найдена матрица v2B<^f> + ll >, приближающая матрицу V г В с точностью (19) •.

Шаг 7 — приближенное вычисление матрицы ^^^ В ^ •• Умножаем вектор-столбец на вектор-строку.

В^У <ц>+±-| цо причем И умножений производим приближенно с точностью ^ знаков после запятой.

Из (16 видно, что й 111ЛЦ- ^ И * аТ" «» 1-^ (.

ГС Ч / У — ^ ч Чь Ь II и. I 1 V Л1 Г-Ч г II > Л I '— -/ -I- ^ а поскольку & ъ/а.гг, из С? вытекает.

11 В, ЙТ —^ЧТ 11 4 IVВ" — «VI „“ г» .

Поэтому из (2.о" >, а!^ и <12." > получается.

На седьмом шаге найдена матрица + | приближающая матрицу с точностью (2г).

Шаг 8 — вычисление матрицы Полагаем причем п. сложении производим точно. Из (?9) и С2. з>") следует л ' / г" ГУ, а — Ц/ + ЬСкО 42 и & - (««ч&- + В^) я ^ ^ ' (но и поэтому нетрудно видеть, что для записи В действительно хватает + 1 знаков перед запятой. В результате выполнения восьмого шага найдена матрица Ь'<1р+± I ^ >, приближающая матрицу vlB + с точностью •.

Описание алгоритма Э ~ завершено. Из <1?") и (гследует, что найденные на пятом и восьмом шагах массивы и В'<^44.|у> удовлетворяют с учетом обозначения (г.) неравенству (Ъ.Ъ), т. е. вычисления <2,. г о") действительно произведены с точностью о = 2. т. Прямой подсчет числа элементарных операций + , —, X, /, , потребовавшихся для реализации Э^, показывает, что их числом составляет? пг +^п, причем эти операции выполнялись над не более чем { -разрядными числами, где величина £*задается формулой (Ъ.5). Наконец, для выполнения ^ достаточна полная память, включая и входную информацию, для хранения.

П1 + таких Рразрядных чисел, при условии, что после выполнения Э входная информация пропадает.