Диссертация (1149594), страница 9
Текст из файла (страница 9)
,=1Более того,Ψ(,) =∑︁[︀]︀2, (, ) − (,̂︀, ) .(3.14),=13.4Численные алгоритмы для построения -оптимальных плановВ работе [13] был предложен численный алгоритм для построения локальных -оптимальных планов, основанный на многомерной чебышевской аппроксимации. Этот алгоритм достаточно сложен как с точки зрения описания, так ис точки зрения реализации, поэтому в этом параграфе он не приводится. Такжеон требует существенных вычислительных ресурсов (смотри в [13] параграф 7с численными результатами), из-за чего применять его можно только в случаенебольшего количества попарных сравнений между конкурирующими моделями в критерии (3.5). В этом параграфе мы опишем более эффективный метод,способный вычислить план даже в случае большего числа попарных сравнений.
Как уже отмечалось в параграфе 3.2, этот алгоритм также можно будетиспользовать для построения байесовских планов при дискретных априорныхраспределениях.Если выполнено предположение 4, то по теореме 8 существует точка ∈ , такая чтоΨ(,) > P (),для любого плана , который не является локальным -оптимальным, гдефункция Ψ(,) определяется в (3.13), а P () в (3.5). Алгоритм, предложенный в [6], использует похожее свойство для того, чтобы построить последовательность планов, сходящуюся к -оптимальному. Приведем аналог этого алгоритма для случая -оптимальных планов.Алгоритм 2 (аналог алгоритма из [6]). Пусть 0 — некоторый начальныйплан и ( )∞=0 — последовательность положительных вещественных чисел,52удовлетворяющая условиям lim→∞ = 0,∑︀∞=0 = ∞,для = 0,1, .
. . поочередно выполняем два шага:1. Находим +1 = arg max∈ Ψ(, ),2. Берем +1 = (1 − ) + (+1 ).∑︀∞2=0 < ∞. ТогдаКак уже говорилось ранее, условие остановки для всех алгоритмов в работе:достижение планом +1 заранее заданной нижней границы эффективности,получаемой из теоремы эквивалентности. Относительно сходимости этого алгоритма известен следующий результат:Теорема 9.
Пусть выполнено предположение 4 и пусть { }=0,1,... — этопоследовательность планов, получаемая с помощью алгоритма 2. Тогдаlim P ( ) = P ( * ),→∞где * — локальный -оптимальный план.Доказательство этой теоремы аналогично доказательству теоремы 3 из главы 1.Основная проблема алгоритма 2 состоит в том, что он порождает последовательность планов с постоянно возрастающим количеством опорных точек,поэтому и финальный план, получаемый после остановки, имеет очень большойноситель. Проблему для финального плана можно решить с помощью кластеризации или через нахождение экстремумов функции Ψ(, ), где — это номеритерации, на которой произошла остановка, но с увеличением числа точек вносителе во время итерационного процесса бороться гораздо сложнее. Длядостижения финальным планом нужной эффективности может потребоватьсянесколько сотен итераций алгоритма, что влечет большую сложность при вычислении оптимальных значений∫︁̂︀, = arg inf, ∈Θ]︀2[︀ (, ) − (, , ) ()(3.15)в критерии (3.5).
Также в работе [13] было показано, что алгоритм 2 может несходится в том случае, если в критерии (3.5) слишком много попарных сравнений.Далее предлагается альтернативный алгоритм, который также подразумевает последовательное выполнение двух шагов: раздельной максимизации53критерия по опорным точкам (шаг 1) и по весам (шаг 2). Первый шаг не представляет затруднений и подробно мы его описывать не будем. Для второго шагапредложены несколько вариантов оптимизационных процедур, которые мы опишем ниже по тексту в параграфах 3.4.1 и 3.4.2.Алгоритм 3. Пусть 0 — некоторый начальный план.
Тогда для = 0,1, . . .поочередно выполняем два шага:1. Пусть [] — носитель плана . Найдем множество ℰ[] всех локальных максимумов функции Ψ(, ) на и определим [+1] = [] ∪ ℰ[] .2. Определим = {[+1] , } как план с носителем [+1] и векторомвесов . Теперь вычислим локальный -оптимальный план в классевсех планов с носителем [+1] , то есть найдем такой вектор [+1] ,который доставляет максимум() = P ({[+1] ,}, 1 , . .
. , )∑︁∑︁ [︀]︀2=, inf (, ) − (,, ) ,,=1, ∈Θ∈[+1]где — это вес в точке ∈ [+1] . Уберем из множества [+1]те точки, которым в полученном оптимальном векторе весов [+1]соответствуют нули, и получим новый носитель, который такжеобозначим [+1] . Наконец, определим план +1 как план с носителем[+1] и соответствующими ненулевыми весами из [+1] .На первом шаге каждой итерации все локальные максимумы функции Ψ(, )добавляются к множеству возможных опорных точек плана +1 . Накапливания точек в носителе не происходит благодаря следующему важному свойствуфункции Ψ(,+1 ):Лемма 3. Пусть выполнены предположения 4 и 5.
В конце каждой итерацииалгоритма 3 функция Ψ(,+1 ) принимает одно и то же значение во всехопорных точках плана +1 .Доказательство леммы 3 можно найти в [15]. Из этой леммы сразу следуетТеорема 10. Пусть выполнены предположения 4 и 5. Тогда в конце каждойитерации алгоритма 3 число точек в носителе [+1] плана +1 не превосхо54дит максимального числа корней уравненияΨ(,+1 ) = , ∈ [0, max Ψ(,+1 )].∈В программной реализации на каждом шаге из носителя промежуточного планаисключаются те точки, итоговый вес которых после решения оптимизационнойзадачи по весам меньше, чем 0.25 , где = 2.2 × 10−16 — самое маленькоечисло с плавающей запятой в R.Для алгоритма 3 верен следующий результат о сходимости:Теорема 11. Пусть выполнено предположение 4 и пусть { }=0,1,... — этопоследовательность планов, получаемая с помощью алгоритма 3.
Тогдаlim P (+1 ) = P ( * ),→∞где * — локальный -оптимальный план.Доказательство. Очевидно, что неравенствоP ({[] ,[] }) ≤ P ({[+1] ,[+1] })выполнено для всех , так как [] ⊆ [+1] , то есть последовательность P ( ), = 0, 1, . . . — неубывающая. Более того, эта последовательность также ограничена сверху величиной P ( * ), а значит она имеет предел. Обозначим этотпредел как P** . Существует подпоследовательность планов , = 1,2, . . ., которая сходится к некоторому плану ** . Функция является полу-непрерывной сверху как инфимум непрерывной функции, поэтому P ( ** ) = P** . Теперьпредположим, чтоP ( ** ) < P ( * ).Тогда ** не является локальным -оптимальным планом и по теореме 7 существует константа > 0, такая чтоsup (, ** ) − P ( ** ) = 2,55где функция определяется в формуле (3.12). Поэтому при достаточно больших , таких что ≥ для некоторого заранее фиксированного , получаем(используя тот факт, что функция sup (,) является полунепрерывной снизу)sup (, ) − P ( ) > ,при всех ≥ .
Так как по построению последовательность P ( ), = 0, 1, . . .не убывает, верно неравенствоP (+1 ) − P ( ) ≥ P ( +1 ) − P ( ).(3.16)Чтобы оценить правую часть этого неравенства, определим при ≥ и ∈[0,1] план˜+1 () = (1 − ) + ,где — это мера, на которой функция (, ) достигает своего максимального значения на множестве всех планов, сосредоточенных в точках локальныхмаксимумов функции Ψ(, ), и+1 = arg max P (˜+1 ()).0≤≤1По построению план +1 — это лучший план, сосредоточенный на множестветочек supp( ) ∪ supp( ), поэтомуP ((+1) ) ≥ P ( +1 ) ≥ P (˜+1 (+1 )).Введем обозначениеℎ(,) = P (˜ ()),и заметим, чтоP (˜+1 ()) ⃒⃒= ( , ) − P ( ) = sup (, ) − P ( ) > .⃒=0(3.17)56Теперь, используя разложение Тейлора, получаем[︀]︀ℎ( + 1,+1 ) − ℎ( + 1,0) = max P (˜+1 ()) − P (˜+1 (0))∈[0,1][︁ (˜ ()) ⃒1 2 ]︁P +1⃒− ≥ max ⃒=02∈[0,1][︁1 2 ]︁2> max − =,22∈[0,1]где — это верхняя оценка для второй производной.
Поэтому из уравнения (3.17) получаемP (+1 ) − P ( ) ≥ P ( +1 ) − P ( )≥ P (˜ ) − P ( )+12.= ℎ( + 1,+1 ) − ℎ( + 1,0) ≥2Теперь просуммируем последнее выражение по от до − 1 > при > + 1 и получим−1∑︁]︀[︀2.P ((+1) ) − P ( ) = P (() ) − P ( ) ≥ [ − ]2=Левая часть последнего неравенства стремится к конечному значению ( ** ) − ( ), а правая часть стремится к бесконечности при → ∞.
Мы пришлик противоречию, а значит наше исходное предположение о том, что P ( ** ) <P ( * ) неверно, что завершает доказательство теоремы 11.С практической точки зрения эффективное решение оптимизационной задачи на втором шаге алгоритма 3, то есть нахождение максимума функции(), является самым важным. Далее описаны два метода оптимизации по весам. Будем считать, что выполнены предположения 4 и 5.3.4.1Квадратичное программированиеПусть [+1] = {1 , .
. . , } обозначает множество, получаемое на первомшаге -й итерации алгоритма 3. Определим как план с носителем [+1] ивесами 1 , . . . , , которые и предстоит определить на втором шаге итерации57алгоритма посредством максимизации функции() =∑︁,,=1∑︁[︀]︀2 ( , ) − ( , ̂︀, ) ,=1где ̂︀, = ̂︀, () определяются в (3.15).
Для этой цели предлагается линеаризовать функции ( ,, ) в окрестности точек ̂︀, . Рассмотрим функцию() ==∑︁,=1∑︁,=1, min, ∈R, min, ∈R∑︁=1[︁]︁2⃒ ( ,, ) ⃒̂︀ ( , ) − ( ,, ) − ,, =̂︀,,[︀ T T]︀, J, ΩJ, , − 2 T R, , + T,,где — это размерность множества возможных параметров -й модели Θ ,Ω = diag(1 , . . . , ),а матрицы J, ∈ R× , R, ∈ R× и векторы , ∈ R задаются как)︁(︁ ( , ) ⃒ , ⃒,J, =⃒, =̂︀, =1,...,,)︁(︁ ( ,, ) ⃒⃒̂︀R, = [ ( , ) − ( ,, )],⃒, =̂︀, =1,...,,)︁(︁2̂︀, = [ ( , ) − ( ,, )],=1,...,соответственно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
