- tikka
- Постоялец
Как то неудобно получилось:) сорри:)
tikka
>>но заметь, необходимость минимизации вытекает только из идеальности.
согласен
>>А, все до меня дошло. Ты наверно убираешь нулевой член из ряда? Наверно я это в твоих постах упустил. А в статье нулевой член >>присутствует, и я думал у тебя такая же формула. Если так, то по поводу ряда претензии снимаются:)
Именно!
В статье было, но статья Экспина, и косячная.
>>правомерно-неправомерно... нет, я все обосновываю. все логично. ну не знаю как еще расписать. Если бы я писал пейпер, >>возможно, получилось бы внятнее.
Ну смотри, вот было:
Primal feasibility:
с_e = 0 (6)
c_i >= 0 (7)
Complementary slackness:
lambda_i_t * c_i = 0 (8)
Вот что стало:
Дифференцируем Primal feasibility:
Jе * V = 0 (6)
Ji * V >= 0 (7)
Дифференцируем Complementary slackness:
lambda_i_t * (J i * V) = 0 (8)
Вопрос к твоему подходу: как ты обосновываешь допустимость этого перехода? Почему при такой трансформации 6, 7, 8 этот набор ограничений все еще будет критерием точки оптимума?
Рассмотрим, для простоты, непрерывно дифференцируемую функцию f: R -> R.
(эта функция - мгновенное условие, которому надо удовлетворять)
Рассмотрим произвольный отрезок [a, b].
Выберем dt и посторим ломаную приближенную траекторию, шагая по касательным, начиная из точки f(a)
(в начале стоим точно на решении).
Обозначим максимальное отклонение ломаной от точной траектории err_t (total error)
Теорема: При стремлении delta_x (то есть dt) к нулю, err_t стремится к нулю.
Доказательство этой самопальной теоремы приведено ниже. Говоря проще устремив dt к нулю мы сколь угодно точно приблизим ломаную к точному решению на отрезке. Из этого следует, что при посторении ломаной, устремив dt к нулю, мгновенное условие можно заменить на его производную. В следствии дискретизации, просто увеличится err_t. По такому принципу работает тот же интегратор Эйлера.
Доказательство:
из непрерывной дифференцируемости:
delta_f / delta_x - df/dx может быть сделана сколь угодно малой в окрестности любой точки. Отсюда:
delta_f = df/dx * delta_x + E * delta_x
где E может быть сделано сколь угодно малым, подбором delta_x.
err_t = Sum(err_i) <= n * Max(|err_i|) <= n * Max(|delta_f - df/dx * delta_x|) <= n * E * delta_x = (b-a) * E
где n - кол-во отрезков разбиения, E может быть сделано сколь угодно малым, выбором delta_x.
Отсюда для любого Et > 0, существует E = Et / (b-a), такое, что подобрав достаточно малое delta_x получим:
err_t <= (b-a) * E = (b-a) * Et / (b-a) = Et
Доказали.
А вообще в моей голове ряд Тейлора из 1 члена == производная. Не понимаю как упоминане Тейлора сделает это более обоснованным. Ну да ладно.
Еще раз: если мы хотим просто однократно удовлетворить условиям оптимума, тогда да, нужно удовлетворять условиям нулевого порядка. Но если мы уже стоим на правильном решении, можно перейти от условий нулевого порядка, к условиям на приращения устремив dt к нулю.
tikka
Ну что ж, это вполне обоснованные рассуждения, меня просто смущало, что ты их не озвучивал.
Моя идея с рядом Тейлора с исключением 0 члена может быть обоснована аналогично, но проще. При стремлении dt->0 отклонение разложение тейлора до первой производной (вместе с 0 членом) от собственно исходной функции стремится к 0 (это, мне кажется, можно выдернуть из определения разложения Тейлора). Поэтому если мы из удовлетовряющей ограничениям точки n переходим в точку n+1, используя приближение по Тейлору и пользуясь шагом dt->0, то и в точке n+1 отклонение от исходной функции будет стермиться к 0, и константный член разложения по Тейлору в точке n+1 будет стремиться к 0 и может буть исключён ввиду порядка малости. Я как-то подхордил к этому делу, хотя твое обоснование вполне годное, ИМХО.
Кстати, возвращаясь к зависимости dr от Fc.
Можно доказать (нестрого), что невозможно построить функцию f(x) = Integral(g(s, f)). То есть, где подынтегральное выражения зависимо от интеграла. Там в итоге цепочки рассуждений приходим к тому, что для некоторой точки x0, значение функции f(x0) выражается само через себя. Типа противоречие. Вроде как не можем поставить аргументу в соответствие какое либо значение.
Нестрого, потому что на этом я остановился пока.
И еще одна (уже последняя:) хрень:
>>Нет, g у нас - константная часть ограничения. То есть если ограничение 5 * x0 + 6 * x1 = 7, то c(e) = 5 * x0 + 6 * x1, а g = 7. Мутно, согласен. c(x) я использую кое-где для скорости для обозначения действий, общих для c_i и с_e. Можно его считать объединением c= {c_e, c_i}.
странно, вроде если посмотреть на условия ККТ
http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
то там лагранжиан
L(x, lambda) := f(x) + Sum(a * lambda) + Sum(b * lambda)
и разделение на 2 суммы именно потому что для a и b разные ограничения даются:
a <= 0
b = 0
то есть a(x) это как раз c_i(x) со знаком минус, b(x) == c_e(x)
>>g у нас - константная часть ограничения.
очень странно.
>>[я]Если уж избавляться то избавляться от обоих сразу, как я понял вы аппроксимируете только c_i. И что получится в итоге, если добавить c_e, система из неравентва и равенства?
>>[ты]Нет, оба аппроксимируем одинаковым образом, и с_e, и c_i
очень странно. вы что с_e и c_i загоняете в одно неравенство?
tikka
Да лажа с обозначениям ив статье.
Начинали с того, что
c_i >= 0
c_e = g
Потом по ходу статьи и уж точно в моих рассуждених, g уплыло в состав c_e
ну вот, разворотили всю статью:) Пущай XperienS исправит:)
Так-с, давайте по пунктам.
1) Замена Даламбера-Лагранжа на (Даламбера + идеальные ограничения) -- зачем? Суть-то вроде та же.
2) Удивительно g всплыл, хаха, нада убрать. Сюда же - дописать условия ККТ и сделать полную запись приведенной LCP.
3) Насчет c0 - вообще корректнее было бы его убрать, потому что действительно мы предполагаем что стоим на решении.
4) По поводу дифференцирования/Тейлора, персонально tikka: рискуя поднять очередную волну срача, скажу что действительно в итоге равноценно, но ряд Тейлора существует как раз для приближения функции. Так зачем отходить от него и говорить, что вот тут вот "возможно заменить производной потому что...", если Тейлор уже сказал это за нас?
5) По поводу ci и ce - дело в том, что там производятся действия правомерные как для неравенств, так и для равенств, это наверное стоит указать явно в статье.
Я ничего не упустил?
>>1) Замена Даламбера-Лагранжа на (Даламбера + идеальные ограничения) -- зачем? Суть-то вроде та же.
нет.
У тебя: идеальные связи => Даламбера-Лагранжа => минимизация
Я предлагаю: идеальные связи => минимизация
убираем бессмысленное лишнее звено.
просто Даламбера можно по желанию добавить что бы обосновать F = ma
>>2) Удивительно g всплыл, хаха, нада убрать. Сюда же - дописать условия ККТ и сделать полную запись приведенной LCP.
не очень понял что имеешь в виду, но ты поправь статью, а потом уже будем смотреть.
>>3) Насчет c0 - вообще корректнее было бы его убрать, потому что действительно мы предполагаем что стоим на решении.
>>4) По поводу дифференцирования/Тейлора, персонально tikka: рискуя поднять очередную волну срача, скажу что действительно в итоге равноценно, но ряд Тейлора существует как раз для приближения функции. Так зачем отходить от него и говорить, что вот тут вот "возможно заменить производной потому что...", если Тейлор уже сказал это за нас?
мне видится вся это конструкция весьма хлипкой, нестрогой. Тейлор сказал что приближение будет если оставить c0. Если его оставить все более менее целостно. Если убрать, то надо уже делать допущение что мы на каждом кадре стоим на решении, и c0 обнуляется, а это уже какие то умственные завихрения. Мой пост с теоремой доказывает все строго.
SoRRow писал:
>>Моя идея с рядом Тейлора с исключением 0 члена может быть обоснована аналогично, но проще. При стремлении dt->0 отклонение разложение тейлора до первой производной (вместе с 0 членом) от собственно исходной функции стремится к 0 (это, мне кажется, можно выдернуть из определения разложения Тейлора).
ну да, вроде логично. Но получается что мы вводим Тейлора, только что бы оставить один 1 член и воспользоваться выдернутым свойством. Получается что мы не раскладываем функцию (для чего Тейлор и нужен), а просто приближаем смещение за dt. Как то это ну не знаю... Мне мой вариант больше нравится:)
>>5) По поводу ci и ce - дело в том, что там производятся действия правомерные как для неравенств, так и для равенств, это наверное стоит указать явно в статье.
а то что в конце статьи и для ci и для ce составляется 1 общее неравенство, это правомерно по твоему?
>>Я ничего не упустил?
А, там еще непонятное что то с приближением матрицы якоби. Не знаю что ты этим хотел сказать:)
О!
SoRRoW
> При стремлении dt->0 отклонение разложение тейлора до первой производной
> (вместе с 0 членом) от собственно исходной функции стремится к 0 (это, мне
> кажется, можно выдернуть из определения разложения Тейлора). Поэтому если мы из
> удовлетовряющей ограничениям точки n переходим в точку n+1, используя
> приближение по Тейлору и пользуясь шагом dt->0, то и в точке n+1 отклонение от
> исходной функции будет стермиться к 0, и константный член разложения по Тейлору
> в точке n+1 будет стремиться к 0 и может буть исключён ввиду порядка малости.
Но в этом случае мы рассматриваем бесконечно большое кол-во отрезков n, так как погрешность накапливается от отрезка к отрезку. Получается бесконечно большая величина n умножить на бесконечно малую err. Это неоднозначность.
Нужно еще доказать что n*err можно сделать бесконечно малой. Моя теорема это и делает.
tikka
если ты делаешь бесконченое число шагов, то в твоем доказательстве (b-a) будет бескончено большим отрезком, и (b-a) * E тоже вызовет неоднозначность. Твое доказательство работает только для конечного отрезка. Если же число шагов конечно, то для можно подобрать достчточно малый dt, чтобы на последнем шаге ошибка стремилась к 0
>>если ты делаешь бесконченое число шагов, то в твоем доказательстве (b-a) будет бескончено большим отрезком, и (b-a) * E тоже вызовет неоднозначность. Твое доказательство работает только для конечного отрезка.
да нет же. Отрезок (a, b) конечен, но ты разбиваешь его бесконечным множеством точек, и получаешь бесконечно много малых отрезков.
>>Если же число шагов конечно, то для можно подобрать достчточно малый dt, чтобы на последнем шаге ошибка стремилась к 0
число отрезков зависит от dt:
n = (b - a) / dt
У тебя:
dt -> 0
следовательно:
n = (b - a) / dt -> infinity
Это ж элементарная теория бесконечно малых, ее моему даже в школе проходят.
tikka
ну если число точек бескончено, то твое n * E * delta_x все равно образует неопределенность inf * 0, не так ли?
Не знаю нужно ли вам это еще, но вот мысль в голову пришла.
Я писал.
>Кстати, возвращаясь к зависимости dr от Fc.
>Можно доказать (нестрого), что невозможно построить функцию f(x) = Integral(g(s, f)). То есть, где подынтегральное выражения >зависимо от интеграла. Там в итоге цепочки рассуждений приходим к тому, что для некоторой точки x0, значение функции f(x0) >выражается само через себя. Типа противоречие. Вроде как не можем поставить аргументу в соответствие какое либо значение.
>Нестрого, потому что на этом я остановился пока.
Очень важный момент, на котором все держится, это факт что f(x) - определенный интеграл (интегральная сумма от 0 до t). В случае неопределенного интеграла существует одна функция которая удовлетворяет f(x) = Integral(g(s, f)) - экспонента:
exp(t) = Integral(exp(t))
Но, абсурдно говорить что между экспонентой и экпонентой есть какая то зависимость. Просто экспонета - это функция, скорость роста которой совпадает с ней самой.
Тема в архиве.