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

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

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

8.1.2.2. Сервисные программы. Бывают параметры, для которых нельзя подобрать хороших универсальных значений (уж очень они привязаны к задаче), но в то же время можно построить хорошие универсальные правила их вычисления. Как и параметры по умолчанию, их не включаюгг в список обязательно требуемых от пользователя, и, хотя лучше, если, хорошо понимай свою задачу и алгоритм, он определит нх сам, за ним оставляют право не делать этого и предусматривают специальные сервисные программы для их расчета. Значения, выданные сервисной программой, как правило, оказываются удачнее, чем «выбранные по нантню» неопытным пользователем.

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

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

8.1.3- ВЫБОР ПАРАМЕТРОВ П0ЛЬ30ВЛТЕ.ПЕМ Назначая параметры метода при обращении к стандартной программе, пользователь может «настраивать» его на свою задачу и передавать ему какую-то дополнительную полезную информацию.

Смысл одних параметров очевиден; чтобы понять роль других, надо хорошо знать метод. К первьш относится, например, началь-

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

Параметры второго типа имеют смысл управляющих. В восьми следующих разделах мы обсудим некоторые из них. Рекомендации по выбору конечно-разностных интервалов даны в разд. 8.6.

8.1.3.1. Точность вычисления функций. Часто от по.льзователя требуется оценка точности, с которой будут вычисляться функции :надачи. Она может понадобиться: (i) для подсчета ошибки условий при конечно-разностном приближении производных (разд. 4.6.1.1); (ii) д;]я масштабирования переменных (см. разд. 8.7); (iii) для критерия останова (знание этой точности позволяет существенно уменьшить вероятность преждевременного прерывания и ненужного затягивания счета) (см. разд. 8.2); (iv) для определения минимального просвета между проб1£ыми точками в процедуре одномерного поиска (разд. 4.3.2.1 и 8.4.2).

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

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

/; (F {x)) = F{x)+c, где а<е (см, разд, 2.1.6) или. что эквивалентно, \fl{F(x))-F{x)\Ej.

Пожалуй, более принято думать о точности в относительных терминах, а проще говоря, в терминах числа правильных значащих цифр в выданном машиной значении. Однако (см. разд. 8.5) соответствующая форма задания ошибки прн ма.лых по моду.лю F{x) не подходит. Все же д.тя некоторых F можно использовать и ее, характеризуя аккуратность расчетов верхней границей относительной поереишости; это - число ер, характерное тем, что из fHF(x))=F(x) (l-be)

следует неравенство [ е е,;.

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



здесь существенной роли не играют, и если есть основания полагать, что примерно г значащих цифр машинного значения F верны, то можно смело брать еЮ" и е,= 10"(1-(- F ). Аккуратные оценки точности важны при расчетах на машине с коротким словом; тут и излишний пессимизм, и неоправданный оптимизм чреваты серьезными потерями.

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

Бывает, что пользователь не может обоснованно оценить ак-курат1юсть вычисления своих функций. Тогда для определения надо применить сервисную программу (к вопросу о выборе Ед мы еще вернемся в разд. 8.5).

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

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

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

8.1.3.3. Точность одномерного поиска. Методом выбора шага стараются отыскать локальный минимум функции по направлению, и делают это с точностью, которая контролируется специальным параметром т] из диапазона 0г]<1 (см. разд. 4.3.2.1). Чсммеиьшё г], тем точнее будет выполняться одномерная минимизация. При


этом с уменьшением т), вообще говоря, возрастает среднее число пробных точек на одну основную итерацию и сокрагцается общее количество итераций, требуемых для удов]етворения критерию сходимости. Трудоемкость процесса в целом с приближением tj к нулю сначала убывает, а потом начинает расти. К примеру, при переходе от ti=6.9 к ri = 10" число основных итераций обычно уменьшится по крайней мере вдвое, а суммарное количество обращений к процедуре подсчеты целевой функции увеличится раза в полтора. Дальнейшее же уменьшение т, скажем до 10"", скорее всего приведет то.лько к увеличению количества вычислений функции, а на числе итераций практически ие отразится. Указанная тенденция особенно отчет.пива, когда одномерный поиск осуществляется на основе квадратичной аппроксимации по трем точкам; дело в том, что такая аппроксимация вблизи минимума по направлению теряет качество.

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

Само собой разумеется, встречаются и задачи с существенно отличающимися от значения по умолчанию оптимальными rj. В частности, к ним относятся задачи с простыми функциями. Для них предпочтитепьные tj меньше «среднего», поско.льку его принято подбирать по таким функциям, трудоемкость минимизации которых в основном определяется необходимостью их вычисления в пробных.точках. В простых же случаях увеличение при заниженном г] числа обращений к процедуре подсчета функции с лихвой окупится экономией суммарных затрат а.пгебраических блоков метода (имеются в виду решение линейных систем, пересчет матричных разложений и т. д.).

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

Труднее всего подбирать параметр т] в алгоритмах сопряженных градиентов (см. разд. 4.8.3). Для них оптимальные rj, отвечающие разным задачам, разбросаны особенно сильно. Поэтому, если при помощи программы метода сопряженных градиентов предполагается решить большую серию схожих задач, то для определения хорошего 1] имеет смысл поставить специальньЕЙ численный эксперимент.



8.1.3.4. Максимальная длина шага. Во многих алгоритмах полезно ограничивать изменение х, допускаемое на одной итерации (см. разд. 4.3.2.1). Соответствующее ограничение вводит через пара-Meip Д, подчиняя длину шага а. вдоль выбранного направления р неравенству llaplKU.

Существует ряд причин, по которым выбор Д разумно предоставить пользователю. Хорошо понимая свою задачу, назначением правильного Д он может

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

2) повысить эффективность поиска, обеспечив вычисление функций только в «разумных точках»;

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

4) стимулировать сходимость к решению, лежащему вблизи начальной точки.

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

8.1.3.5. Максимальное число обращений к процедуре подсчета целевой функции- Данный параметр вводится для того, чтобы дать пользователю возможность остановить метод после вычисления определенного количества значений целевой функции. Эта возможность полезна во всех тех ситуациях, когда нет уверенности, что избранным методом можно решить задачу. Бывает, например, что, запуская программу безусловной минимизации, мы не знаем, ограничена функции снизу илн нет, н, коль скоро она не ограничена, а прер1.1вание не предусмогрено, машина может долго и бессмысленно считать - до тех пор, пока не прои.зойдет переполнение.

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

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

придется вычислить по меньшей мере одни раз. Значит, всего потребуется не менее n-1-l вычислений. То же можно сказать и в отношении неквадратичных функций, (На самом деле в квазиньютоновских методах их обычно приходится вычислять более чем в 5х ХП точках.)

) 8.1.3.6. Локальный поиск. Если вторые производные недоступны, то проверить, соблюдаются ли в найденной точке достаточные условия оптимальности (см. гл. 3), вообще говоря, нельзя, и есть риск, что она будет седловой, а не оптимальной. В связи с этим иногда прибегают к локальному поиску - попытке уменьшить значение целевой функции с помощью средств, радикально отличающихся от реализованиь1Х в ос:новЮМ методе. Ее безрезультатность считают признаком истггнностн проверяемого численного решения.

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

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

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

Поскольку оптимальное значение р зависит от матрицы Гессе функции Лагранжа в искомой точке, хороших универсальных рекомендаций по выбору р не существует. Можно лишь сказать, что для практических задач (с правильно отмасштабнрованными функциямгг) более-менее прнем.лемым обычно является р = тах jlO, 1б I F (х„) I). Ясно также, что если при заведомо хорошем начальном приближении х„ нет возможности точно оценить множители Лагранжа, то р лучше взять большим (чтобы метод не удаля.лся от х„).

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



[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.0009