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

[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]

ВОПРОСЫ и ОТВЕТЫ

Вопросы и отвспил

Во время великих собьипий обище принципы не помогают, Г. Гегель (1832)

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

81. Могу ЛИЯ рассчитывать на то, что машина нашла точку глобального минимума?

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

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

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

83. Я решил свою задачу безусловной минимизации квазиньютоновским алгоритмом без вычисления производных и теперь хочу увеличить число переменных. К каким изменениям числа итераций

и количества обращений к процедуре подсчета целевой функции это приведет?

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

84. Я собираюсь решать задачу с нелинейными ограничениями-неравенствами, причем про некоторые из них я знаю, что в решении онн будут активными. Следует ли определить эти ограничения как равенства, или лучше задать их алгоритму как неравенства?

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

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

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



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

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

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

87. Мне надо оценить параметры некой модели, и я собираюсь воспользоваться программой метода наименьших квадратов. Исходные данные, по которым я «настраиваю» модель, надежны лишь в двух старших разрядах. Разумно ли потребовать такую же точность численного решения?

07. Не всегда! Относительные ошибки вычисления целевой функции вашей задачи о наименьших квадратах скорее всего будут существенно меньше чем Ю"», т. е. предельная точность численного решения будет намного выше. Когда запрашивается значительно более низкая точность, во-первых, есть риск получить совсем неверный ответ, а во-вторых, не исключено, что программа сама изменит значение соответствующего параметра (см, разд. 8.2.3.6).

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

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

89. Для своей многомерной задачи на безусловный минимум я хочу применить метод с сопоставлением значений функция. Как я смогу убедиться, что он дал правильный ответ?

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

чальное приближение: если он даст прежнюю точку, доверие к ней естественно возрастет.

810. Программа безусловной минимизации сообщила об успешном завершении счета, хотя в точке, которую она иашла, составляющие градиента довольно велики. Не означает ли это, что в программе есть ошибка?

010. Если задача плохо отмасштабирована, градиент может быть большим даже для вполне подходящего приближенного решения, В критериях останова норма градиента обычно соотносится с модулем целевой функции (см. разд. 8.2.3).

ВН. Значении моей целевой функции и ее граднеита вычисляются очень громо:1ДКой и сложной подпрогралшой. Я пытался отыскать минимум с помощью квазиньютоновского алгоритма, но сходимость была крайне медленной н ощутимого уменьшения целевой функции получить не удалось. Чем это можно объяснить?

011. Одна из наиболее вероятных причин - ошибка в модуле вычисления производных. Вам следует оттестировать этот модуль, используя технику, описанную в разд. 8,1.4.2, Вторая возможная причина - разрывы градиента. Эти разрывы часто удается выявить сравнением правых и левых конечно-разностных приближений его компонент (см. разд. 8.4.2.4).

812. В моей задаче есть набор нелинейных ограничений-равенств, и я могу применить быстрый специальный алгоритм, который позволит выдерживать нх, вычисляя значение одних («зависимых») переменных по значениям других («независимых») переменных. Стоит ли делать это?

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

813. Целевая функция моей задачи гладкая, но очень нелинейная. Я слышал, что ньютоновские и квазиньютоновские алгоритмы для таких функций работают плохо и что в подобных случаях имеет смысл использовать алгоритмы прямого поиска. Верно ли это?

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



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

014. Иногда ньютоновский ажоритм находит очень хорошее приближение, а условия нормального останова не соблюдаются (см. разд. 8.2.3). Если при этом полученная точка оказывается численно неулучшаемой, происходит аварийный останов в блоке выбора шага.

815. Просматривая распечатку решения задачи с линейными ограничениями, я заметил, что несколько множителей Лагранжа получились почти нулевыми. Значит ли это, что соответствующие ограничения избыточны и что их можно снять?

015. Не обязательно! (См. рис. 8е и 81 в гл. 8.)

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

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

817. Я хочу подобрать параметры своей модели, минимизируя уклонение предсказываемых ею величин от данных наблюдений. Какую норму уклонений лучше использовать - квадратичную, норму /i или норму 1?

017. Если никаких содержательных доводов в пользу тон или иной нормы нет, мы рекомендуем квадратичную. При использовании двух других норм возникают негладкие задачи безусловной минимизации. Хотя для них разработаны специальные методы, минимизировать квадратичную норму все же намного проще (см разд. 4.2.3 и 6.8.1).

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

018. Ответ на этот вопрос зависит от нескольких факторов. Если запрограммировать функции ограничений (и, возможно, их

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

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

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

520. Каковы общие характеристики задачи, существенные для выбора алгоритма решения?

020. Список основных факторов, которые должны приниматься во внимание прн выборе алгоритма, выглядит так:

a) число переменных;

b) наличие простых ограничений иа переменные (см. разд. 5.5.1);

(c) гладкость функций задачи и их производных (см. разд. 4.2.1 и 6.8);

(d) порядок производных, поддающихся эффективному вычисле нию (см. разд. 8.1.1);

(e) доли ненулей в матрице Гессе целевой функции и в матрице Якоби функций офаничений (это надо учитывать при больших размерностях; см. разд. 4.8, 5.6 и 6.7);

(1) отношение числа линейных ограничений общего вида к числу переменных и ожидаемое количество активных в решении ограин-чений (см, разд.5.4 и 5.5.2);

(g) определенность целевой функции за пределами допустимой области и осмысленность соответствующих йначении (см, разд. 6.2.1.1 н 8.1.1.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.001