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

• Автор: Хачиян, Леонид Генрихович
• Шифр специальности: 05.13.02
• Научная степень: Докторская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 252 c. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

ГЛАВА I МЕТОД ЭЛЛИПСОИДОВ ДЛЯ ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПОЛИНОМИАЛЬНОГО ПРОГРАММИРОВАНИЯ С

ЗАДАННЫМИ ГРАНИЦАМ РЕШЕНИЙ В К п

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

2 Вспомогательные построения для метода эллипсоидов

геометрия .

3 Вспомогательные построения для метода эллипсоидов

позиционная арифметика

4 Описание алгоритма АВПП .
5 Доказательство сходимости
6 Оценки трудоемкости приближенного решения задач
выпуклого полиномиального программирования с
заданными границами решений .
7 0 сложности приближенного решения невыпуклых
задач полиномиального программирования с заданными границами решений
ГЛАВА 2 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ ЛИНЕЙНОГО И
ДРОБНОЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Ь
8 Постановка задачи и результаты
9 Границы решений, мера несовместности, критерий
ограниченности и чувствительность минимального значения от свободных членов в задачах линейного программирования .
Алгоритм АЛН точного решения систем линейных
неравенств
II Алгоритм АЛЛ точного решения задач линейного
программирования
Полиномиальная разрешимость линейного
программирования
Полиномиальная разрешимость дробнолинейного
программирования. Алгоритм АДЛП
ГЛАВА 3 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ КВАДРАТИЧНОГО
ПРОГРАММИРОВАНИЯ
Постановка задачи и результаты
Границы решений, критерий ограниченности и
чувствительность минимального значения от свободных членов в задачах квадратичного
программирования
Полиномиальная разрешимость квадратичного
программирования. Алгоритм АКП.
Определение совместности систем линейных и
выпуклых квадратичных неравенств в
Задача о центре системы точек .
ГЛАВА 4 ГРАНИЦЫ РЕШЕНИИ ЗАДАЧ ВЫПУКЛОГО ПОЛИНОМИАЛЬНОГО
ПРОГРАММИРОВАНИЯ В ПЕРИОДИЧЕСКИХ МНОЖЕСТВАХ
Постановка задачи и результаты.
Рецессивные конусы выпуклых полиномов .
Обусловленность выпуклых полиномиальных форм . .
Системы с тривиальным рецессивным конусом . . .
Системы, рецессивный конус которых
подпространство .
Доказательство теоремы .1 о границах решений систем выпуклых полиномиальных неравенств в
периодических множествах .
Доказательство теоремы .2 о границах решений задач выпуклого полиномиального программирования в периодических множествах
ГЛАВА 5 АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ РЕШЕНИЯ СИСТЕМ
ВЫПУКЛЫХ ПОЛШОШАЛЬНЫХ И ДИОФАНТОВЫХ НЕРАВЕНСТВ I
Постановка задачи и результаты
Регуляризация систем выпуклых полиномиальных неравенств в периодических множествах и
аддитивнопоказательная запись решений
Алгоритмическая сложность решения систем
выпуклых диофантовых неравенств .
Приближенное решение систем выпуклых полиномиальных неравенств с вещественными неизвестными
ГЛАВА 6 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ ЗАДАЧ ВЫПУКЛОГО ДИ0ФАНТ0В0Г0 ПРОГРАММИРОВАНИЯ С ФИКСИРОВАННЫМ ЧИСЛОМ
НЕИЗВЕСТНЫХ .
Постановка задачи и результаты
Доказательство теоремы ЗОЛ
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ I
ПРИЛОЖЕНИЕ 2
ЛИТЕРАТУРА


При построении полиномиальных алгоритмов в настоящей работе будем также стремиться к получению возможно более низких по порядку сложностных оценок, улучшая в главах 1-3 некоторые опубликованные ранее результаты [] ,[] Д*Л] Л^8] > хотя такое улучшение оценок будет сопряжено с заметным усложнением описаний и обоснований алгоритмов по сравнению с их первоначальными принципиальными версиями. Отметим, что описываемые в работе алгоритмы имеют наинизший известный в настоящее время порядок сложности. Полиномиальная сводимость и полнота. Все необходимое по поводу этой тематики было сказано выше. В настоящей работе определение класса N? Наконец, к перечисленным выше пунктам можно добавить еще один, не относящийся непосредственно к теории сложности вычислений. Изучение вспомогательных свойств задачи, связанных со сложностью ее решения. Применение той или иной алгоритмической техники предполагает изучение определенных характеристик задачи, влияющих на оценки ее сложности, причем часто такое изучение имеет и самостоятельный интерес. Например, в дискретной оптимизации важную роль играют линейные описания комбинаторных многогранников, см. Ъ] , для изоляции корней полиномов необходимы оценки на границы решений и сепаратор [ ] # [ 1ЪО] и т. Итак, получаемые в дальнейшем результаты могут быть отнесены к разделам 2-5. Перейдем к более конкретному изложению тематики диссертации и ее целей. Здесь ? Задачи полиномиального программирования с целочисленными переменными иногда называют задачами диофантового программирования. Степенью с1 задачи называется максимальная из степеней / по совокупности переменных / входящих в нее полиномов, высотой задачи называется максимум модулей задающих ее целочисленных коэффициентов, а длиной входа Ь задачи называется, как и прежде, число, битов во входном списке коэффициентов. Не будет ошибкой считать, что длина входа - это сумма двоичных длин Ь(сО = ^Ео^а) ] + 1 # взятая по всем ненулевым коэффициентам а задачи, хотя на самом деле, единственное свойство величины Ь , используемое в дальнейшем, состоит в выполнении неравенства Ь ^ то/х | , т , им}. Отметим также, что понятие длины входа будет в дальнейшем использоваться лишь для классов задач, в которых степень с1 будет фиксироваться / задачи линейного программирования, задачи квадратичного программирования и т. Перечислим некоторые из них. Существуют конкретные диофантовы уравнения 1Та ,'Х1, 'х ^ =. О » проблема распознавания совместности которых в целых числах 'Эс* , . Г1 при произвольных ае! IЪО3 , см. В частности, поскольку любое диофантово уравнение сводится добавлением новых неизвестных к системе квадратичных диофантовых неравенств, не существует общего алгоритма определения совместности систем квадратичных диофантовых неравенств при достаточно больших фиксированных значениях т и гп , см. Определение совместности систем линейных диофантовых неравенств является, как указывалось выше, N-полной задачей. В частности, все известные в настоящее время алгоритмы ее решения имеют экспоненциальную по длине входа временную сложность. I (К / В отличие от целочисленного случая, существуют алгоритмы определения совместности в вещественных переменных произвольных систем полиномиальных неравенств и алгоритмы, в определенном смысле точно решающие произвольные задачи полиномиального программирования с вещественными неизвестными. Речь идет о разрешающих процедурах для элементарной теории вещественнозамкнутых полей, т. I 5 ] . ПЗ / Простейшие нелинейные задачи полиномиального программирования с вещественными переменными оказываются не проще дискретных задач булевого программирования, в которых переменные принимают значение 0 или I. В частности, поскольку определение совместности систем булевых линейных неравенств является МР3 - полной задачей, уже простейшая из нелинейных «задач полиномиального программирования - определение совместности в вещественных переменных систем линейных неравенств, отягченных одним квадратичным ограничением, также оказывается - полной. Отметим, что этот факт в определенном смысле переносится и на отыскание приближенных решений таких задач, см.