Применение комбинированного метода выпуклого программирования в задачах финансовой математики
Рассматриваются особенности применения комбинированного метода выпуклого программирования для решения указанного в названии класса задач. Спецификой этих задач является кусочнолинейный характер используемых функций при очень большом количестве аппроксимирующих плоскостей. Описываются настройки и про...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/12711 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Применение комбинированного метода выпуклого программирования в задачах финансовой математики / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 146-152. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-12711 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-127112010-10-21T12:01:42Z Применение комбинированного метода выпуклого программирования в задачах финансовой математики Бойко, В.В. Кузьменко, В.Н. Рассматриваются особенности применения комбинированного метода выпуклого программирования для решения указанного в названии класса задач. Спецификой этих задач является кусочнолинейный характер используемых функций при очень большом количестве аппроксимирующих плоскостей. Описываются настройки и процедуры метода, а также приводятся сравнительные результаты вычислительных экспериментов. Розглядаються особливості застосування комбінованого методу опуклого програмування для розв’язування класу задач, що вказані у назві. Специфікою цих задач є кусково-лінійний характер функцій, що використовуються, при значній кількості лінійних апроксимуючих площин. Описуються настройки та процедури методу, наводяться порівняльні результати обчислювальних експериментів. The paper considers features of using mixed convex programming method for solving problems of pointed class. The main feature of these problems is using linear peacewise functions with much number of linear peaces. Ajustments and procedures of the method are discribed, comparison results of computational experiments with other methods are given. 2008 Article Применение комбинированного метода выпуклого программирования в задачах финансовой математики / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 146-152. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/12711 519.8 ru Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматриваются особенности применения комбинированного метода выпуклого программирования для решения указанного в названии класса задач. Спецификой этих задач является кусочнолинейный характер используемых функций при очень большом количестве аппроксимирующих плоскостей. Описываются настройки и процедуры метода, а также приводятся сравнительные результаты вычислительных экспериментов. |
| format |
Article |
| author |
Бойко, В.В. Кузьменко, В.Н. |
| spellingShingle |
Бойко, В.В. Кузьменко, В.Н. Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| author_facet |
Бойко, В.В. Кузьменко, В.Н. |
| author_sort |
Бойко, В.В. |
| title |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| title_short |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| title_full |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| title_fullStr |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| title_full_unstemmed |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| title_sort |
применение комбинированного метода выпуклого программирования в задачах финансовой математики |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/12711 |
| citation_txt |
Применение комбинированного метода выпуклого программирования в задачах финансовой математики / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 146-152. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT bojkovv primeneniekombinirovannogometodavypuklogoprogrammirovaniâvzadačahfinansovojmatematiki AT kuzʹmenkovn primeneniekombinirovannogometodavypuklogoprogrammirovaniâvzadačahfinansovojmatematiki |
| first_indexed |
2025-07-02T14:45:42Z |
| last_indexed |
2025-07-02T14:45:42Z |
| _version_ |
1836546832614817792 |
| fulltext |
146 Теорія оптимальних рішень. 2008, № 7
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматриваются особенности
применения комбинированного ме-
тода выпуклого программирова-
ния для решения указанного в на-
звании класса задач. Спецификой
этих задач является кусочно-
линейный характер используемых
функций при очень большом коли-
честве аппроксимирующих плос-
костей. Описываются настройки
и процедуры метода, а также
приводятся сравнительные ре-
зультаты вычислительных экспе-
риментов.
В.В. Бойко, В.Н. Кузьменко,
2008
ÓÄÊ 519.8
Â.Â. ÁÎÉÊÎ, Â.Í. ÊÓÇÜÌÅÍÊÎ
ÏÐÈÌÅÍÅÍÈÅ
ÊÎÌÁÈÍÈÐÎÂÀÍÍÎÃÎ ÌÅÒÎÄÀ
ÂÛÏÓÊËÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
 ÇÀÄÀ×ÀÕ ÔÈÍÀÍÑÎÂÎÉ
ÌÀÒÅÌÀÒÈÊÈ
Введение. В настоящей работе описываются
особенности применения комбинированного
метода выпуклого программирования [1, 2]
к задачам финансовой математики. Такие за-
дачи имеют разнообразные постановки, но
все они так или иначе учитывают неопреде-
ленность, связанную с будущими курсами
валют, стоимостью акций, вероятностью вы-
игрыша или потерь, эффективностью порт-
фелей акций и другими финансовыми пока-
зателями [3–5].
Теоретически предполагается, что неопре-
деленные величины имеют некоторые не-
прерывные вероятностные распределения, на
основании чего строятся зависимости, кото-
рые используются при формулировке задач.
При выполнении расчетов и решении опти-
мизационных задач используются дискрет-
ные распределения, полученные на основа-
нии обработки статистики. В результате за-
висимости представляются в виде кусочно-
линейных функций с большим числом ли-
нейных частей. Для эффективного примене-
ния комбинированного метода необходимо
учитывать эти особенности и разработать со-
ответствующие процедуры метода. К ним
относятся: регулирование параметров внут-
ренней подзадачи, критерии остановки мето-
да, правила отсева аппроксимирующих
плоскостей. Использование соответствую-
щих процедур позволяет существенно уско-
рить работу метода.
ПРИМЕНЕНИЕ КОМБИНИРОВАННОГО МЕТОДА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ …
Теорія оптимальних рішень. 2008, № 7 147
Функции, используемые в финансовых моделях. Рассмотрим некоторую
функцию ),( qxf , которая в финансовой модели будет определять потери или
выигрыш, аргумент x которой – это вектор управляющих решений, а q – слу-
чайный вектор, связанный с будущим состоянием системы. Положительные
значения ),( qxf будут обозначать потери, а отрицательные – выигрыш. Функ-
ция распределения для ),( qxf в общем виде задается следующим образом:
]),([),( ξ≤=ξΨ qxfPx .
При моделировании и оценке финансовой деятельности используется ряд
производных функций, которые получаются на основе случайной функ-
ции ),( qxf . Одной из таких функций, которые используются в финансовых
расчетах, является функция, задающая величину потерь для заданного уровня
вероятности α (Value-at-risk – VaR). Она определяется как обратная функция к
),( ξΨ x при фиксированном x , если такая существует, в общем случае – как α -
квантиль от ),( qxf :
{ }α≥ξΨ=
∈ξ
α ),(minarg)( xxV
R
.
Близкая по смыслу функция, которая является оценкой сверху для )(xVα ,
есть функция средних потерь (Conditional Value-at-Risk – CVaR) [6], превы-
шающих или равных значению )(xVα=ξ . Эта функция определяется следую-
щим образом:
ξξ⋅ξ
α−
= ∫
α≥ξ
α dxpxC
xV )(
),(
1
1
)( ,
где ),( ξxp – плотность вероятности случайной функции ),( qxf .
Другой используемой функцией является частичный момент для заданного
уровня значений w функции потерь (Partial Moment)
ξξ⋅−ξ= ∫
≥ξ
dxpwxP
w
w ),()()( .
Связь между функциями )()(),( xPxCxV wиαα при заданном уровне вероятно-
сти α выражается формулой ( ) )()()()1( )( xPxVxC xVα
=−⋅α− αα , а при заданном
уровне w потерь – ( ) )()()()1( xPxVxC ww ww
=−⋅α− αα , где ),( wxw Ψ=α .
Также используются моменты абсолютных значений ),( qxf (Mean-
Absolute Penalty и Mean-Absolute Deviation):
( )),()( qxfExM = и ( ))),((),()(0 qxfEqxfExM −= .
Линейные аппроксимации функций. В качестве функции ),( qxf чаще
всего рассматривается линейная функция ∑
∈
+=
Ii
ii xqqqxf 0),( , где I – множе-
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
148 Теорія оптимальних рішень. 2008, № 7
ство финансовых инструментов; ix – средства, вложенные в i -й финансовый
инструмент; iq – случайная величина, задающая потери или выигрыш по фи-
нансовому инструменту; 0q – случайные потери или выигрыш, не связанный с
финансовыми инструментами.
Количество рассматриваемых финансовых инструментов I в реальных за-
дачах может достигать нескольких тысяч.
Вероятностные характеристики случайного вектора q оцениваются, как
правило, на основании статистики. При этом выборки могут иметь значитель-
ный объем. Например, они могут содержать сотни тысяч реализаций kq ,
510, ≈∈ KKk . Как правило, вероятности kp реализаций kq рассматриваются
как равные, но в общем случае их можно считать различными.
Вышеописанные функции в этом случае приближенно представляются сле-
дующим образом.
Величина потерь (VaR) для заданного уровня вероятности α
),()( α=α
k
qxfxV ,
где реализация αk
q находится следующим образом. Реализации k
q , Kk ∈ упо-
рядочиваются по возрастанию значений ),( kqxf . Для каждого порядкового но-
мера m вычисляется сумма вероятностей ∑
=
=
m
i
i
sum
m pp
1
по всем меньшим и рав-
ным реализациям. В качестве αk
q берется первая реализация с номером αm , та-
кая, что α≥
α
sum
mp .
Остальные функции вычисляются следующим образом:
( )∑
α≥
α ⋅⋅
α−
=
)(),(
,
1
1
)(
xVqxf
k
k
k
pqxfxC ,
( )∑
≥
⋅−=
wqxf
k
k
w
k
pwqxfxP
),(
),()( ,
( )∑
∈
⋅=
Kk
k
k
pqxfxM ,)( , ( ) k
Kk
k
pxAqxfxM ⋅−= ∑
∈
)(,)(0 ,
где ( )∑
∈
⋅=
Kk
k
k
pqxfxA ,)( – среднее значение.
Функции AMMPC w ,,,, 0α – выпуклые не зависимо от способа их вы-
числения. При приближенном вычислении они являются также кусочно-
линейными. Функция )(xVα в общем случае не выпукла.
ПРИМЕНЕНИЕ КОМБИНИРОВАННОГО МЕТОДА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ …
Теорія оптимальних рішень. 2008, № 7 149
Формулировки задач, как правило, достаточно простые. Они включают до
10 содержательных ограничений и, возможно, систему линейных ограничений
на вектор x .
Пример задачи оптимизации:
min)(1 →α xC
PxP w ≤)(2 ,
AxA ≤)(3 ,
JjLxLL jjj ∈≤≤ ,)( ,
Iixxx iii ∈≤≤ , .
Индексами 1, 2, 3 обозначено то, что вычисление соответствующих функ-
ций APC w ,,α основано на использовании различных функций потерь-
выигрышей 321 ,, fff , а значит на использовании различных случайных векто-
ров 321 ,, qqq и их реализаций.
Комбинированный метод. Напомним, что комбинированный метод [1, 2]
используется для решения задач выпуклого программирования. В процессе ре-
шения строится последовательность точек, включающая подпоследователь-
ность, сходящуюся к решению, используя следующую итерационную
процедуру.
Очередная точка последовательности 1+kx , а также используемые на сле-
дующей итерации множество точек аппроксимации задачи 1+kX и штрафной
множитель 1+kN определяются в конце k-го шага по результату решения такой
подзадачи:
ξ+ξ+−
ξξ
21
2
,,
~
2
1
min
21
kk
x
Nxx
u
, (1)
kiiii Xxxxxfxf ∈∀ξ≤−′+ ,)),(()( 1 , (2)
kiiii Xxxxxx ∈∀ξ≤−ϕ′+ϕ ,)),(()( 2 , (3)
Mx ∈≥ξ ,02 , (4)
где }:)(min{arg~
kkk XxxFx ∈= – точка минимума штрафной функции
)}(;0max{)()( xNxfxF kk ϕ+= на множестве kX ; подмножество линейных ог-
раничений (2) – кусочно-линейная аппроксимация целевой функции; подмноже-
ство линейных ограничений (3) – кусочно-линейная аппроксимация обобщенно-
го ограничения }1:)({max)( mjxfx j
j
≤≤=ϕ , где mjxf j ≤≤1:)( – ограниче-
ния исходной задачи; M – многогранник, задаваемый линейными ограниче-
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
150 Теорія оптимальних рішень. 2008, № 7
ниями; )(),( xxf ϕ′′ – элементы субдифференциалов )(),( xxf ϕ∂∂ ; функции
jff , – выпуклые и непрерывные на M ; 0>u – параметр, регулирующий вес
квадратичной добавки.
Применение комбинированного метода. При практической реализации
комбинированного метода возникает необходимость разработки и использова-
ния дополнительных процедур метода: регулирование веса квадратичной добав-
ки u/1 ; определение критериев остановки алгоритма; замена множеств kX на
подмножества kk XY ⊆ путем отсева точек аппроксимации, которые на после-
дующих итерациях не будут влиять на решение подзадач (1)–(4). При этом не-
обходимо отметить, что для эффективного решения задач различных типов сле-
дует учитывать особенности этих задач и применять различные способы регу-
лировки, критерии остановки и процедуры отсева аппроксимирующих точек.
В работе [1] описан один из способов регулирования параметра u и отсева
точек аппроксимации, который приводит к уменьшению количества итераций и
ускоряет работу метода на отдельных итерациях. Этот способ дает существен-
ное улучшение для гладких задач.
При решении задач, в которых функции задаются в виде большого числа ку-
сочно-линейных аппроксимаций, используются несколько иные процедуры, ко-
торые оказываются более эффективными, чем описанные в [1]. При этом учиты-
вается, что схема алгоритма решения квадратичной подзадачи (1)–(4) в опреде-
ленном смысле соответствует схеме алгоритма рассматриваемого комбиниро-
ванного метода: алгоритм решения подзадачи (1)-(4) реализует прямо-
двойственный метод Гольдфарба и Индани [7] для задач квадратичного про-
граммирования. На каждом шаге алгоритм формирует список активных ограни-
чений и минимизирует целевую функцию. Список активных ограничений на
каждой итерации обновляется. В него добавляются ограничения, нарушенные в
текущей точке, и выводятся неактивные. Если в текущей точке нет нарушенных
ограничений, то подзадача (1)–(4) является решенной.
Из этого описания видно, что формирование новой квадратичной подзадачи
(1)–(4) можно рассматривать как варьирование предыдущей и продолжение ее
решения: добавление двух новых линейных ограничений (2), (3), полученных по
точке 1+kx , соответствует увеличению списка активных ограничений внутрен-
ней подзадачи. Изменение параметров u , kN и точки kx~ соответствует измене-
нию только линейной части целевой функции подзадачи (1)–(4), если предста-
вить ее в виде
+ξ+ξ+−
ξξ
2
21
2
,,
~
2
1
)~,(
2
1
min
21
k
kk
x
xNuuxxx .
Отсев точек множества kX осуществляется с учетом наличия активных то-
чек в конце решения подзадачи (1)–(4): все активные точки сохраняются.
ПРИМЕНЕНИЕ КОМБИНИРОВАННОГО МЕТОДА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ …
Теорія оптимальних рішень. 2008, № 7 151
В список точек, которые могут быть удалены из множества kX , включаются
только неактивные точки, для которых выполняется условие
kiii pxxxfxf δ−ξ≤−′+ 1)),(()( , (5)
где δ – параметр порядка 10
-2
; kkk xxp ~
1 −= + – смещение на итерации k .
Количество точек, которые удаляются, ограничивается двумя-тремя. Уда-
ляются те точки, для которых левая часть оценки (5) минимальна.
Вычислительные эксперименты. Эффективность работы комбинирован-
ного метода на задачах финансовой математики была проверена на примерах (в
таблице приведены некоторые сравнительные результаты). Так как зависимости
AMMPC w ,,,, 0α являются кусочно-линейными функциями с явно описан-
ными линейными частями, то они могут быть представлены в виде систем ли-
нейных неравенств. Поэтому рассматриваемые задачи были представлены также
в виде задача линейного программирования и решены соответствующими мето-
дами. Для сравнения эти задачи были решены также r-алгоритмом (время реше-
ния приведено в секундах).
Количество Метод
Задача переменных реализаций комбиниро-
ванный
линейный
r-алгоритм
1 100 10000 24,6 45,8 56,7
2 125 20000 59,2 96,7 58,1
3 82 48000 152,3 420,6 180,4
4 14 100000 140,1 958,6 86,9
5 240 20000 283,2 581,3 365,9
Заключение. В результате выполненной работы разработаны процедуры
комбинированного метода выпуклого программирования, которые позволили
построить эффективный алгоритм для решения задач определенного типа. Этот
алгоритм может применяться для любых задач, в которых функции, используе-
мые в ограничениях и в цели, представляются как кусочно-линейные с большим
количеством линейных аппроксимаций. Тестовые расчеты показали, что пред-
ложенный алгоритм существенно эффективней, по сравнению с методами ли-
нейного программирования, решает задачи, в которых число линейных аппрок-
симаций измеряется сотнями тысяч. Развитие работы будет направлено на по-
строение алгоритмов эффективного решения других типов задач.
В.В. БОЙКО, В.Н. КУЗЬМЕНКО
152 Теорія оптимальних рішень. 2008, № 7
В.В. Бойко, В.М. Кузьменко
ЗАСТОСУВАННЯ КОМБІНОВАНОГО МЕТОДУ ОПУКЛОГО ПРОГРАМУВАННЯ
В ЗАДАЧАХ ФІНАНСОВОЇ МАТЕМАТИКИ
Розглядаються особливості застосування комбінованого методу опуклого програмування для
розв’язування класу задач, що вказані у назві. Специфікою цих задач є кусково-лінійний ха-
рактер функцій, що використовуються, при значній кількості лінійних апроксимуючих пло-
щин. Описуються настройки та процедури методу, наводяться порівняльні результати обчис-
лювальних експериментів.
V.V. Boyko, V.M. Kuzmenko
USING MIXED CONVEX PROGRAMMING METHOD FOR SOLVING FINANTIAL
MATHEMATIC PROBLEM
The paper considers features of using mixed convex programming method for solving problems of
pointed class. The main feature of these problems is using linear peacewise functions with much
number of linear peaces. Ajustments and procedures of the method are discribed, comparison re-
sults of computational experiments with other methods are given.
1. Пшеничный Б.Н., Ненахов Э.И., Кузьменко В.Н. Комбинированный метод решения общей
задачи выпуклого программирования // Кибернетика и системный анализ. – 1998. – № 4. –
С. 121–134.
2. Кузьменко В.Н., Бойко В.В. О применении комбинированного метода выпуклого про-
граммирования // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М. Глушкова
НАН України, 2003. – С. 19–24.
3. Markowitz H.M. The Optimization of a Quadratic Function Subject to Linear Constraints // Na-
val Research Logistics Quarterly. – 1956. – 3. – P. 111–133.
4. Huang C.F., Litzenberger R.H. Foundations for Financial Economics. – Elsevier Science Pub-
lishing Co., Inc., 1988. – 347 p.
5. Elton E., Gruber M., Brown S. Modern Portfolio Theory and Investment Analysis. – John
Wiley and Sons, 6th edition, 2003. – 589 p.
6. Rockafellar R.T., Uryasev S.P. Optimization of Conditional Value-at-Risk // J. of Risk. – 2000.
– 2. – P. 21–41.
7. Goldfarb D., Idnani A. A numerically stable method for solving strictly convex quadratic pro-
grams // Mathematical Programming. – 1983. – 27. – P. 1–33.
Получено 25.03.2008
|