Главная  Методы условной оптимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [ 63 ] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

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


/" Ecmt / уверенность, / что граЗш

\ Верно

Рис. 8а. Схема выбора метода решения задачи безусловной минимизации с измеренным числом переменных.

МОМЕП

СТЕП

КНМБП

СГ + ОПБП

СГ + ОПВП

ппг момвп

- метол одноыерноп минимизации без вычисления производных

- программа формирования консчво-разностиыл иитериалоТ " Хщоизводаы™"" Р™™™ тиетоо-раавостноП оппроксимащ-" п°он™даы™"" ° "™ч««-Р»М"™-» алпрокс.мацие»

- °сГиГ;:го""зВОдг™ «vp0b ОДИОМ.РИОГО поисв.

~ ий™ьзТющ™ирои,вадтТ™ " """"WP"" м™"ерного поиска.

- программа проверки правильности вычислении гредиента

- метод одномерноП минимизации с вычислением производных 1?НМПГТ а. ппоп ~ дискретный метод ньютоновского типа

КИМВ1Ц. ОПВП - каазиньютоповский метод с вычислением градиентов и пооцелупой п„„г одномерного поиска. использующеП производаые проЦеДУрои

МН™ - программа лроеерви правильности вычисления матрицы Гессе

IfSvnn i г,пв„ ~ ньютоновского типа

КИМВП J. ОПБП - m»3H,MJOTOHO»CKBB „„од с вычислением граднентов , процеДуроВ одномерного поиска без вычисления производных. ..«.н"

Рщработка математического обеспечения для оптимизации при больших размерностях всегда была делом коммерческим в то время как методы и программы для небольших задач создавались Б «академических» целях. Отсюда ряд характерных различий. Ь частности, средства, ориентированные на большие задачи (особенно коммерчек;кие пакеты линейного программирования) намного удобнее в обращении.

Чтобы запустить библиотечную программу какого-то универсального метода, рассчитанного на рядовые размерности, пользователь обычно должен сам сформировать в памяти машины двумерный числовой массив, содержащий все (включая нулевые) элементы матрицы условий и вектора правь1Х частей. Кроме того, нередко требуется, чтобы он задал солидный список значений параметров метода (этот момент подробнее рассмотрен в разд. 8.1.3). Совсем иначе организуется общение с программами, предназначенными для больших задач. Здесь носителями исходной информации служат текстовые входные файлы, составляемые по специальным правилам. Наиболее распространенным правилом построения входных файлов является так называемьЕЙ MPS-формат. Его суть в следующем: ограничения и переменные именуются; матрица условий определяется последовательностью текстовых строк, каждая из которых отвечает одному коэффициенту и помимо записи его значения содержит соответствующую пару имен. При этом достаточно определить только ненулевые позиции матрнщл. Для всех параметров метода предусматриваются значения по улюлчанию. Если какие-нибудь из них пользователя не устраивают, он может их заменить; другие задавать не надо. Этот способ настройки избавляет от необходимости выбирать массу величин, многие из которых понятны только специалисту.

Средства решения ридовых и больших задач различаются также способами реализации. Первые обычно доступны в виде подпрограмм на общепринятых алгоритмических языках высокого уровня (чаще всего на ФОРТРАНе), которые можно вставлять в свою программу. Вторые же, как правило, реализуются на машинно-ориентированных языках (т. е. могут работать только в составе определенных вычислительных комплексов), причем их конкретная начинка составляет предмет собственности разработчиков и от пользователя скрыта. Методь! для задач большой размерности часто воплощают в составе систем математического программирования, куда помимо основных, оптимизирующих блоков входит много сервисных (например, генераторы отчетов). Как уже было сказано ранее, общение с методом в данном случае осуществляется не вызовом подпрограммы, а через входной п выходной файлы системы.

Выделяясь развитой сервисной частью, математическое обеспечение для больших оптимизационных задач проигрывает обычному в эффективности основных алгоритмов. Его ориентация требует экономного использовании памяти и тем самым исключает возможность применения самых совершенных и надежных схем выбора направлений поиска и оценивания множителей -Лагранжа (см. разд. 5.1.3 и 5.1.5). Поэтому, если нет уверенности, что задача достаточно хорошо обусловлена и размерность позволяет воспользоваться качественной программой, рассчитанной на рядовые случаи, то лучше обратиться к последней. Здесь уместно также напомнить о значительных «накладных расходах», отличающих



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

Из-за указанных выше различий между существующими программными средствами решения больших и обычных задач переключаться с одних на другие непросто. В будущем с появлением более совершенного математического обеспечения стуащш должна измениться. Принимая в расчет популярность и удобство для пользователей правил описания входных данных типа MPS-формата, в новые библиотеки процедур для задач небольшой размерности уже сегодня начинают включать вспомогательные программы, преобразующие буквенно-цифровые спсцификаш1и задач во внутренние структуры данных алгоритмов и выдающие результаты решения в терминах этих спецификаций. Беда только в том, что если писать эти программы ввода-вывода на языках типа ФОР-ТРАНа, то они неизбежно оказываются очень громоздкими.

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

Сказанное относится, в частности, к алгоритмам лтшейного программирования. Среди них есть такие, в которых все ограничения (включая простые) обрабатываются одинаково, а есть и иные, требующие постановки задачи в стандартной форме и учитывающие тфостые ограничения и ограничения общего вида по-разному (см. разд. 5.3.1 и 5.6.1). В случае когда число общих ограничений равно т, а число переменных п, причем для каждой указаны границы, алгоритмы первого типа будут работать с базисной ттхп-матрицей, а второго - о базисной m X т-натрицей. В зависимости от того, что больше - п или т, предпочтительными оказываются либо те, либо другие.

Возьмем для примера линейную задачу с 10 неравенствами общего вида и 100 переменными; в каждой ее вершине по меньшей мере 90 переменных принимают граничные значения. Метод, не отличающий простых ограничений от общих, для решения этой задачи потребует память под запись плотной ЮОх 100-матрицы. В то же время метод, рассчитанный на стандартную форлту, будет оперировать 10х 10-натрицей. С другой стороны, если в задаче 10 переменных и 100 общих неравенств, то ЮОх 100-матрица возникает во втором методе, а в первом - матрица размера 10х 10.

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

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

Методы нуль-пространства и ранг-пространства. Для маленьких задач трудоемкость вычисления нелинейной целевой функции и ее производных обычно значительно превышает трудоемкость алгебраических блоков оптимизационных процедур, и поэтому для них подбирать методы легко - можно не принимать во внимание специфики ограничений. Предпочтение в таких случаях следует отдавать методам нуль-пространства (см. разд. 5.2) как более надежным и устойчивым. Однако по мере увеличения размерности требуемые ими объемы памяти и вычислений быстро возрастают, так что в определенных ситуациях становится разумным использовать методы ранг-пространства. Рациональный выбор зависит в основном от числа активных в решении ограничений. (Сопоставление методов нуль- и ранг-пространства дано в разд. 5.4.)

Выбор метода, генерирующего допустимые точки. На практике нередко возникают задачи, целевые функции которых определены только в допустимых точках. Примером служит рассмотренная в разд. 1.1 задача о проектировании носовой части летательного аппарата - математическая теория подсчета лобового сопротивления (которое надо минимизировать) неприменима, если, скажем, нарушено условие неотрицательности объема (одно из ограничений). Бывает также, что целевая функция F определена всюду, но ее значения в недопустимой области бессмысленны. Здесь можно привести такой пример: пусть переменная х должна удовлетворять ограничениям -l.vl и входит в F через разность между опорной вьтичнной t/j и чебышевским разложением 2;а(7((х); поскольку полиномы {Ti(x)) обладают хорошими свойствами только на отрезке [-1, И, за его пределами смысла у значений F не будет, хотя F вычислима и там.

Если бы машина считала без погрешностей, в любом методе из гл. 5, не использующем конечно-разностной аппроксимации производных, целевая функция F автоматически вычислялась бы истшочительно в допустимых точках. Из-за ошибок округления невязки в ограничениях порядка машинной точности неизбежны, но больших проблем из-за этого не тюзникает - эти невязки можно «скомпенсировать», заранее подправив правые части ограничений должны.м образом. Сложнее дело обстоит с методами, в которых применяется численное дифференцирование. Здесь обращения к процедуре подсчета F возможны в точках, где нарушения ограничений намного больше машинной точности, причем избежать этого модификацией конечно-разностных формул можно лишь в том случае, когда все ограничения простые (си. разд. 5.5.1). Следовательно, если важно, чтобы вычислений F в недопустимых точках не бьшо, для решения задачи надо взять программу, оперирующую аналитическими производными.



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

Из методов допустимой точки для задач с нелинейными ограничениями наибалее распространен метод барьерных функций (см. разд. 6.2.1.2). Правда, «в чисто,\1 виде» он применим лишь при условии, что все ограничения являются неравенствами. Если в задаче есть также линейные равенства, то в качестве метода, сохраняющего допустимость, можно взять какую-нибудь процедуру, построенную на базе барьерного преобразования и обрабатывающую эти равенства приемами гл. 5.

Когда в списке общих ограничений задачи есть t нелинейных равенств и больше ничего иег, возникает соблазн «исключить» их простым приемом: разбить вектор переменных х на две составляющие Ха и X, размерностей t и ;j-( соответственно и вести минимизацию по х„ все время подбирая х как «решение» системы ограничений. (Данный подход лежит в основе методов типа приве-денных градиентов; см. разд. 6.3.) Однако мы считаем, что поддаваться подобному соблазну не стоит. Как отмечалось в разд. 6.3, стремление выдерживать нелинейные равенства в течение всего процесса поиска часто оказывается причиной мед.тенной сходимости. Кроме того, если помимо «исключаемых» равенств в задаче есть простые ограничения на х,, учесть их при рассматриваемом подходе не просто. В общем здесь лучше не экспериментировать, а применить какую-нибудь библиотечную программу минимизации при нелинейных равенствах.

8.1.2. РОЛЬ ПОЛЬЗОВАТЕЛЯ

Иногда высказывается мнение, что цель математического обеспечения - «избавить пользователя... от всякой необходимости думать над решением своей задачи» (Дэвис и Рабинович, 1967) Для некоторых классов вычислительных задач эта цель достижима (в той степени, которую допускают погрешности машинной арифметики). Однако класс задач оптимизации к таковым не относится. Только самые легкие из них не требуют обдумывания. Обычно же

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

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

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

Коль скоро значение какого-то параметра пользователем не зафиксировано, оно должно выбираться автоматически. Делается это одним из двух способов: либо параметр получает «дежурное» значение, либо он вычисляется по какому-то правилу в соответствии с известными значениями других параметров и характеристик задачи.

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

Например, для всех «хорошо отмасштабированных задач» (см. разд. 8.7) безусловной минимизации функций, вычисляемых с полной машинной точностью, можно взять едтшый порог в критерии останова (о критериях останова речь пойдет в разд. 8.2.3).

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [ 63 ] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]

0.0011