[Затупил][Ниасилил] Помогите оптимизовать функцию

> [Затупил][Ниасилил]

Можно просто писать [Питонщик]

Я так и на С++ и на жабе не смогу оптимизовать. Проблема в том, что когда-то давно пропарил весь курс лекций по оптимизации -_-

Ты бы это, привел ее сначала в стандартную форму, что ли.

Добавил формулу

Я так понял - это задача на условную оптимизацию? Почему решаешь перебором? Есть ведь разные методы решения.

Перебором пытался, действенно, прямолинейно, но очень долго.

Пытался ко всему этому делу прикрутить функцию fmin из пакета scipy - но ничего не выходит. Ругается, понимаешь, из-за того, что у меня в некоторых местах резко нули всплывают.

Да нет же. Я имел в виду привести к виду, годному для решения одним из методов линейного программирования.

Но я затупил, на линпрог это не похоже. Как это должно решаться я уже забыл, с интересом подожду более памятливых товарищей.

А что мешает запрограммировать самому известные алгоритмы условной оптимизации? Или попрообуй использовать другие методы вместь fmin.

кстати во втором уравнении можно не брать корень, а возводить 0.15 в квадрат

Много чего мешает. Мне бы просто пример практический, к моему посту, а не теорию =)

+1. Еще можно x**2 сделать так:

a=x; res=a*a;

Ну да, можно и так. Хмм, в принципе тогда можно к линейному свести попробовать.

Хотя не прокатит.

третий шаг можно перенести на первое место и переделать так:

x[0] = 1 - x[1] -x[2] - x[n]

но другое все равно так не вычислить же.

Другое - в смысле то выражение с корнем, даже если корен перенести через равно.

oh noes. это квадратичное программирование получается

Читать http://window.edu.ru/window_catalog/redir?id=27054&file=apr03049.pdf Составляй функцию Лагранжа и вперед.

лезу конечно не в свои ворота, но почему бы не свернуть два явных и три неявных for в один?

def toOpt(x, rsk, doh):
    a = 0
    b = 0
    c = 0

    for i in range(len(x)):
        a += doh[i]*x[i]
        b += rsk[i]*(x[i]**2)
        c += x[i]

    if c != 1
        return 0

    if b > 0.15 * 0.15:
        return 0

    return a

PS: python не знаю, посему за pseudo-C-Python код не бить :)

О, спасибо, дельная инфа. Прочитаю.

Но не мог бы ты пока показать как составить функцию Лагранжа применимо к моей теме? :)

Можно и так, просто для наглядности разбито +)

да, но эта наглядность замедляет твой код в гипотетические пять (а то и больше) раз.

замедляет твой код

Здесь речь идет не оптимизации скорости работы.

Ну это поправимо. Хотя твой вариант более компактный. Вобщем все равно ускорение делать после того, как все работает, а не до +)

всё, молчю :)

Хорошее пособие, на моем факультете такого даже близко не было.

Но не мог бы ты пока показать как составить функцию Лагранжа применимо к моей теме? :)

Влом, почитай сам. Несколько подсказок:

1) Во-первых, задача может быть неразрешима из-за пустоты допустимого множества(смотри ограничение задачи).

2) Во-вторых, не написаны ограничения на иксы. Предполагаю, что больше или равны нуля.

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

Ну и напоследок, если все правильно составишь, то должно получиться квадратное уравнение.

>Влом, почитай сам. Несколько подсказок:

Извечная проблема когда разбираться во всем особо времени нет. Примерчик бы наглядный.

2) Во-вторых, не написаны ограничения на иксы.

0 < x < 1

В-третьих, неравенство смело меняй на равенство

Дык, если неравенства не будет отсеку огромное количество возможно верных решений.

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

Дык, если неравенства не будет отсеку огромное количество возможно верных решений.

Максимум, если допустимое множество не пусто, будет точно на границе, поскольку у тебя допустимое множество выпуклое.

Извечная проблема когда разбираться во всем особо времени нет. Примерчик бы наглядный.

Держи болезный финальные уравнения

doh_{i}-2 * risk_{i}x_{i}y_{1} - y_{2} = 0, i от 1 до n

\sum_{i=1}^{n} risk_{i} x_{i}^{2} = 0.0225

\sum_{i=1}^{n} x_{i} = 1.

Из первых n уравнений выражай x_{i}, подставляй в последние. Из последнего равенства варажай y_{1} и результат подставляй в предпоследнее. Получится квадратное уравнение относительно y_{2}.

Ага. Вообще этот пример легко и просто реализуется солвером из оффтоп-экселя(да да), нашел небольшой пример по ссылке http://stackoverflow.com/questions/4634317/excel-solver-in-python но что-то не до конца еще разобрался.

Проще взять какой-нибудь градиентный метод или взять барьерные методы или методы штрафов.

Можно и градиентный, только он предполагает наличие допустимой точки. А тут ее может и не быть.

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

Че то такое уже когда то тут терли....

Хмм, чувствую тут таки прийдется залезать в дебри и без знаний об принципах оптимизации не обойтись )

Подожду пока другого решения, может кто со scipy поможет.

А подумать? Вы работаете с на пересечении плоскости и элиппсоида,

В зависимости от параметров задачи пересечения может и не быть ;-)

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

Абсолютно верно! функция простая, ничего за границы элипсоида не выходит. Можно даже показать на графике, какое соотношение нужно найти http://img849.imageshack.us/img849/5428/017m.png я просто не знаю как это сделать =)

> В зависимости от параметров задачи пересечения может и не быть ;-)

Тогда просто не будет решения, удовлетворяющего неравенству и посл. у-ю.

> Абсолютно верно! функция простая, ничего за границы элипсоида не выходит. Можно даже показать на графике, какое соотношение нужно найти http://img849.imageshack.us/img849/5428/017m.png я просто не знаю как это сделать =)

Ну батенька... экономист похоже?;-))) заменяем неравенство равенством, выражаем оттуда x1, подставляем в спол у-е, выражаем оттуда х2, подставляем и то и то в целевую ф-ю и запускаем любую оптимизационную процедуру.

Некоторое время назад я точно так же отвечал тут на точно такой же вопрос. Ы?

>Ну батенька... экономист похоже?;-)))

Метко :D

заменяем неравенство равенством, выражаем оттуда x1, подставляем в спол у-е, выражаем оттуда х2, подставляем и то и то в целевую ф-ю и запускаем любую оптимизационную процедуру.

Ну дык, если я заменю неравенство - у меня же из этого ничего хорошего может не выйти. Ведь есть вариант что при показателе mris 0.7 может выйти tmax больший, чем при другом наборе иксов но mris 0.15.

Кажись нашел, что вот здесь решается именно то, что мне надо http://abel.ee.ucla.edu/cvxopt/examples/book/portfolio.html

Только пока не могу разобраться какие переменные в том примере за что отвечают.

> Ну дык, если я заменю неравенство - у меня же из этого ничего хорошего может не выйти. Ведь есть вариант что при показателе mris 0.7 может выйти tmax больший, чем при другом наборе иксов но mris 0.15.

Неравенство меняете на РАВЕНСТВО, потому что экстремум будет ВСЕГДА наблюдаться на границе эллипсоида.

>>> [Затупил][Ниасилил]

Можно просто писать [Питонщик]

Я так и на С++ и на жабе не смогу оптимизовать.

Так я и говорю: питонщик. Ничего не может, только ноет.

>Неравенство меняете на РАВЕНСТВО, потому что экстремум будет ВСЕГДА наблюдаться на границе эллипсоида.

Дошло однако =)

> Так я и говорю: питонщик. Ничего не может, только ноет.

Этот хотя б по делу ноет, а ты тока троллишь. Т.е. лоровский анонимус куда хуже питонщика однако...

Что-то все равно косячок выходит:

Допустим мы высчитали:

x0 = 1 - sum(x) - это нам реализует условие, что сумма всех x равна единице.

потом мы высчитываем x0 в формуле про риски , для этого привели ее в такой вид:

x0 = \sqrt{0.15^2 - \sum_{i=1}^n R_i x_i^2 \over R_0}

выходит при его вычислении мы заменим предыдущий x0 и сумма всех иксов уже не будет равна единице.

ЧЯДНТ?

> анонимус куда хуже питонщика

Зато умнее.

> ЧЯДНТ?

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

> Зато умнее.

ТС-питонщик озвучил задачу и пытается ее решить в меру своих сил, а ты тока троллишь, так что не видно чем именно ты умнее. Троллее - с этим я согласен.

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

У меня deja vu. Полгода назад тот же персонаж, аналогичная задача, аналогичные проблемы.Какой-то siado нереалистический slow.

maxima?

Дык все времени никак не находилось взяться да доделать =)