Полная версия

Главная arrow Информатика arrow Введение в курс метрической теории и метрологии программ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Информационная сложность решения задач

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

Задача математического программирования формулируется следующим образом: требуется вычислить «-мерный вектор х, оптимизирующий критерий качества решения /0(х) при ограничениях

Заранее известным предполагается некоторое замкнутое подмножество С «-мерного векторного пространства, в котором следует искать решение х. В краткой записи задача имеет вид

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

Пусть {/, С) - семейство задач математического программирования, заданное вместе с источником информации об индивидуальных задачах класса или вспомогательным алгоритмом, называемым оракулом. Последний определяется множеством X допустимых вопросов к нему, множеством У возможных ответов и функций наблюдения ф(х,/), ставящей в соответствие каждому вопросу х&Х по индивидуальной задаче / ответ у е У.

Решение задачи численным методом при таком подходе производится итерациями, на каждой из которых «задается вопрос» хе! оракулу, дающему ответ у = (р(х,/) е У. Всякий новый вопрос

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

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

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

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

Пусть

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

где С(п, к) - некоторая константа. Обычно к = 1.. .2, так что при больших п и малых е Ще) астрономически велика. Теория информационной сложности, следовательно, показывает бесперспективность поиска

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

Теория информационной сложности показала, что быстрый рост

Ще) с увеличением п и обусловлен не столько многоэкстремально-

стью задач, сколько их невыпуклостью. Даже при одном экстремуме информационная сложность уменьшается незначительно:

3.2.2. Класс массовых выпуклых задач достаточно представителен в нелинейном программировании, в него укладываются многие практические проблемы. Одновременно для него характерна приемлемая трудоемкость решения. В этом случае область G - выпуклое множество, а критерий /0(х) и fi (х), j = 1, т - ограничения, выпуклые функции. Напомним, что множество выпукло, если отрезок, соединяющий любые две его точки, целиком принадлежит этому множеству. Функция fix) выпукла на таком множестве, если хорда, соединяющая любые две точки графика fix), лежит полностью в надграфике. Такие функции на выпуклом множестве обладают следующим свойством. Какова бы ни была точка х0, лежащая внутри G, всегда можно через нее провести, по крайней мере, одну гиперплоскость, которая разделит G на две части так, что в одной из них гарантируется выполнение неравенства Разделяющая гиперплоскость определяется локальной

информацией об fix) в точке . Если в точке х0

не существует градиента (/(х) - негладкая функция), то его роль играет так называемый опорный функционал, т. е. любой вектор, определяющий направление гиперплоскости, проходящей через х0и не пересекающей графиках). Поэтому, если одно из ограничений задачи не выполняется в точке х0 (при допустимой погрешности s), т. е. f j (х) > в, то через х0 можно провести гиперплоскость, которая разделит G на две части, в одной из которых ограничение не будет выполняться - Если требуется найти точку х е (7, где

Дх0) достигает минимума, то информация о поведении /0(х) в точке х0 позволяет провести через х0 гиперплоскость, отсекающую от С часть, в которой минимум не может быть достигнут. Это свойство используют некоторые быстрые методы выпуклого программирования.

3.2.3. Рассмотрим один метод решения общих выпуклых задач, называемый методом центра тяжести (МЦТ). Он является аналогом минимизации одномерной функции, известным как дихотомия.

Рис. 3

Чтобы найти минимум /(х)на отрезке [а, Ь, определим его середину х0 (рис. 3). Вправо от нее /(х) растет, значит, на отрезке [х0, Ь] функция достигнуть минимума не может. Затем [а, х0] делим точкой xj снова пополам и отбрасываем ту его половину, в которой /(х) > /(xj). Продолжая этот процесс, можно с любой точностью найти min /(х).

Ранее было сказано, что выбирая точку х0 внутри G, можно по локальным характеристикам /.? (х), соответствующим нарушенным в ней ограничениям, делить область G гиперплоскостью, отбрасывая ту часть, где заведомо не удовлетворяются условия задачи. Если в х0 не нарушается ни одно из ограничений, можно снова, используя локальные характеристики /0(х) в х0, отбросить часть области О, в которой значения целевой функции заведомо превышают /00). Обозначим оставшуюся часть О через Ох. Последняя также выпукла. Выберем в ней точку X! и проведем через нее гиперплоскость, отсекающую ту часть Ох, в которой не выполняются условия задачи или (если все ограничения задачи в х1 не нарушены) часть Ох, в которой не может быть локализован минимум /0 (х). Обозначим оставшуюся часть Ох через С/2 и продолжим итерации. Тогда, последовательно выбирая точки xi внутри 01, можно сокращать область локализации решения выпуклой задачи. Наиболее эффективным оказывается выбор в качестве хг центра тяжести G?. В этом случае отношение объемов

Отвечающий этому правилу метод центров тяжести гарантирует выполнение неравенства

где - та из допустимых точек х0, х1? ..., х,-, на которой достигается наименьшее значение /о(х). Прологарифмировав последнее неравенство и разрешив его относительно шагов / = М(г), получим

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

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

где . Отсюда вытекает, что трудоемкость метода эллипсоидов

где С - некоторая константа.

В 1980 г. было показано, что вместо эллипсоида на каждом шаге можно использовать симплекс, координаты центра тяжести которого являются средним арифметическим координат вершин симплекса [17]. Трудоемкость метода в этом случае оценивается как

Метод эллипсоидов и метод симплексов являются единственными известными универсальными методами решения массовых выпуклых

задач полиномиальной по п и трудоемкости и полиномиальной по п

вычислительной сложностью шага.

Вопросы к гл. 3

  • 1. Поясните понятия легкорешаемых и труднорешаемых переборных задач. В чем смысл деления последних на массовые и индивидуальные?
  • 2. Дайте определения полиномиальной проверяемости и полиномиальной сводимости таких задач. Что такое универсальная задача?
  • 3. В чем заключается принципиальная трудность конструирования приближенных алгоритмов решения данных задач? Допустим ли риск поиска «быстрых алгоритмов» в рамках реализации конкретного проекта ИС?
  • 4. Какой вариант экспертизы труднорешаемости, на ваш взгляд, более предпочтителен: а) использование каталогов труднорешаемых задач; б) консультация квалифицированного математика?
  • 5. Объясните, почему в приближенных алгоритмах решения данного класса задач всегда используется генератор случайных чисел.

  • [1] В литературе последний термин иногда употребляют в смысле объемапамяти, необходимого для решения задачи, т. е. вместо сигнализирующейфункции емкости. Отождествление этих понятий, как видно будет из дальнейшего изложения, некорректно.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>