Cтраница 2
Теорема 8.7. Если конечный вещественный функционал f ( x), заданный на открытом выпуклом множестве U с Е, имеет опорный функционал в каждой точке U, то f ( x) - выпуклый и слабо полунепрерывный снизу на U функционал. [16]
Если на открытом выпуклом множестве U В-пространства задан конечный выпуклый функционал / (), то в каждой точке v U он имеет опорный функционал и, следовательно, слабо полу-лепрерывен снизу. [17]
Как уже говорилось, везде далее предполагается, что источник информации, доступный методам, сообщает как значения, так и градиенты ( опорные функционалы) компонент задачи, возможно, с ошибками. Вычисление градиентов иногда представляет значительно большие трудности, чем вычисление значений. Соответственно важным в прикладном отношении является вопрос о-построении численных методов оптимизации, использующих оракул ( так мы ( будем называть источник информации) нулевого порядка, вычисляющий лишь значения, но не градиенты функционалов задачи. Остановимся коротко на этой проблеме. [18]
Данные эксперимента подтвердили естественное предположение о том, что время выполнения одного шага метода ( без учета времени, нужного на вычисление значений и опорных функционалов к компонентам задачи) пропорционально квадрату размерности задачи; коэффициент пропорциональности оказался равным 6ЫО-5 с. Зная время, расходуемое на каждом шаге источником информации, и имея теоретическую оценку трудоемкости ММЦТ, можно, используя экспериментальную оценку времени выполнения шага, оценить общее время работы метода при данных размерности и погрешности. [19]
Эксперимент подтвердил, что время, расходуемое на один шаг работы метода, пропорционально размерности задачи ( время на вычисление минимизируемой функции и ее опорного функционала при этом не учитывается. Коэффициент пропорциональности для метода Г есть 2 2 - 10 - 4 с, а для SO i, - 9 04 - 10 - 4 с. Эти данные можно использовать так же, как и соответствующие данные для ММЦТ. [20]
Теорема 8.8. Если на открытом выпуклом множестве U с Е задан конечный выпуклый функционал f ( x), то в каждой точке х е U он имеет опорный функционал. [21]
II ( Oil Заметим что данный опорный функционал не является непрерывным. [22]
В приложении к книге приводятся тексты программ, реализующих два основных из построенных выше численных методов выпуклого программирования - ММЦТ и ЗС. Приведенные алгоритмы предполагают возможность точного вычисления значений компонент задачи и их опорных функционалов; таким образом, они не охватывают случай, когда источник информации о задаче стоха-стичен. [23]
Поэтому важно научиться использовать все подходящие возможности косвенного вычисления градиентов или опорных функционалов характеристик условий задачи. [24]
Опорные функционалы и производные по направлению. Мы видели, что, когда выпуклая функция дифференцируема в точке л: 0, множество опорных функционалов М ( х0) состоит из единственного вектора - ее градиента. В противном случае связь между производными от / ( х) и опорными функционалами более сложна. [25]
В таких схемах диалога СПР предлагает оракулу определить значения функционалов качества и ограничений в некоторой точке области определения задачи и, возможно, значения соответствующих опорных функционалов в этой точке. Роль СПР сводится к рациональному выбору последовательности точек Хг, в которых накапливается локальная информация об условиях задачи, и к выдаче решения в момент, когда будет накоплена информация, достаточная для получения результата требуемого качества. Диалоговая процедура решения задач математического программирования, в которую укладываются различные задачи планирования и проектирования сложных систем, позволяет, таким образом, на основе заданной априорной информации о классе задач, к которому относится рассматриваемая проблема, целеустремленно уточнять ее, накапливая только необходимую для получения решения информацию. Изложению этого подхода, называемого диалоговым программированием, посвящены § 5, 6 настоящей главы. [26]
Опорные функционалы и производные по направлению. Мы видели, что, когда выпуклая функция дифференцируема в точке л: 0, множество опорных функционалов М ( х0) состоит из единственного вектора - ее градиента. В противном случае связь между производными от / ( х) и опорными функционалами более сложна. [27]
В непрерывных экстремальных задачах, в которых функционалы ачества и ограничений задачи и их производные удовлетворяют условиям Липшица, локальная информация о функционалах условий задачи ( их значения в некоторой точке) определяет и некоторую информацию об их поведении в окрестности этой точки. В выпуклых задачах локальная информация о функционалах задачи и их градиентах ( или опорных функционалах) определяет некоторую глобальную информацию о поведении этих функционалов. Именно на этом основаны экономные методы решения выпуклых задач оптимизации. [28]
Тогда h h ] f ( h) p ( h), где М -) - опорный функционал, а р ( -) - функционал Мннковского. [29]
Вычисление градиентов существенно упрощается, если известны с точностью до некоторых параметров аналитические выражения для функционалов, определяющих условия задачи. Наличие некоторого статистического материала о значениях неизвестных функций в достаточном количестве точек их области определения позволяет при оракуле нулевого порядка получить приближенные значения градиентов этих функций в анализируемой точке. В частных моделях выпуклого программирования удается с помощью искусственных приемов, определяемых спецификой задачи, вычислить градиенты или опорные функционалы функций, не имеющих полного аналитического описания. [30]