W dniu 2012-09-26 14:42, M.M. pisze:

> Moja poprzednia metoda daje takie wyniki:
> https://rapidshare.com/files/330997453/dane.html

Rozwiązania ok.

Solver LP z oo calc dla 'zmodyfikowanego' i przeskalowaniu
podaje praktycznie te same. Małe różnice na korzyść calca,
np w 3 rozwiązanie
0 0 0 0 0.44427410497 0 0.55572589503 0
i wynik
2.79714937844 ( w linko było 2,7970190403)

pzdr
bartekltg


pzdr
bartekltg

do góry

M.M. <m...@g...com> wrote:
> W dniu środa, 26 września 2012 12:53:27 UTC+2 użytkownik Piotr Chamera napisał:
>> Po przeczytaniu, co napisali przedpiścy, spróbowałem napisać
>> proste rozwiązanie iteracyjne (w Common Lispie).
>> W założeniu zaczynam z wektorem x na wierzchołku hiperkostki
>> jednostkowej i poruszam się w jej wnętrzu po płaszczyźnie
>> wyznaczonej przez jej narożniki ruchami w kierunku tego wierzchołka
>> kostki, który daje aktualnie największy gradient funkcji celu.
>> Kiedy nie ma już możliwości ruchu zmniejszam krok o połowę
>> (a la szukanie binarne). To chyba powinno działać? - możecie
>> zweryfikować czy się gdzieś nie machnąłem?
>
> Moja poprzednia metoda daje takie wyniki:
> https://rapidshare.com/files/330997453/dane.html
> Warunek stopu to 500tys iteracji bez poprawy rozwiazania.
> Czas to okolo 0.05s na i3. Dokladnosc obliczen jak widac :)
> Mozna porownac czy podobne sa wyniki.
> Pozdrawiam

Wyniki linprogiem w octave (wszystkie minimalnie lepsze od Twoich):
CPU=0.004001 s suma(x)-1= 0.000000000000
(new-old)=(3.170567443334-3.170034951200)=0.00053249
2134
CPU=0.004000 s suma(x)-1= 0.000000000000
(new-old)=(3.373006654139-3.372657667300)=0.00034898
6839
CPU=0.004000 s suma(x)-1= -0.000000000000
(new-old)=(2.797149378443-2.797019040300)=0.00013033
8143
CPU=0.004000 s suma(x)-1= -0.000000000000
(new-old)=(1.320463591122-1.320396145600)=0.00006744
5522

do góry

W dniu środa, 26 września 2012 20:15:07 UTC+2 użytkownik Miroslaw Kwasniak napisał:
> Wyniki linprogiem w octave (wszystkie minimalnie lepsze od Twoich):
Wszystko sie zgadza.
Pozdrawiam

do góry

W dniu środa, 26 września 2012 12:53:27 UTC+2 użytkownik Piotr Chamera napisał:
> W założeniu zaczynam z wektorem x na wierzchołku hiperkostki
> jednostkowej i poruszam się w jej wnętrzu po płaszczyźnie
> wyznaczonej przez jej narożniki ruchami w kierunku tego wierzchołka
> kostki, który daje aktualnie największy gradient funkcji celu.
> Kiedy nie ma już możliwości ruchu zmniejszam krok o połowę
> (a la szukanie binarne).
> To chyba powinno działać? - możecie
Jesli zmieniasz dlugosc korku, to rozumiem ze pracujesz na oryginalnym
zadaniu a nie na zmodyfikowanym. Nie dziala dlatego ze oryginalna
funkcja min(f1,f2,f3) ma plaskie miejsca, gradient czesto wynosi zero.
Zdaje sie ze identycznym algorytmem probowalem to ugryzc za pierwszym razem :)
Pozdrawiam

do góry

W dniu piątek, 28 września 2012 13:34:35 UTC+2 użytkownik M.M. napisał:
> > To chyba powinno działać? - możecie
> Jesli zmieniasz dlugosc korku, to rozumiem ze pracujesz na oryginalnym
> zadaniu a nie na zmodyfikowanym. Nie dziala dlatego ze oryginalna
> funkcja min(f1,f2,f3) ma plaskie miejsca, gradient czesto wynosi zero.
> Zdaje sie ze identycznym algorytmem probowalem to ugryzc za pierwszym razem :)
> Pozdrawiam
Chyba bzdure napisalem. Jesli gradient jest rowny zero to mamy rozwiazanie.
Zdaje sie ze to jest wypukle w calej przestrzeni (nie tylko gdy suma = 1).
W takim razie dlaczego ogolne procedury optymalizacyjne tak slabo sobie z
tym radza?
Pozdrawiam

do góry

W dniu 2012-09-28 14:13, M.M. pisze:
> W dniu piątek, 28 września 2012 13:34:35 UTC+2 użytkownik M.M. napisał:
>>> To chyba powinno działać? - możecie
>> Jesli zmieniasz dlugosc korku, to rozumiem ze pracujesz na oryginalnym
>> zadaniu a nie na zmodyfikowanym. Nie dziala dlatego ze oryginalna
>> funkcja min(f1,f2,f3) ma plaskie miejsca, gradient czesto wynosi zero.
>> Zdaje sie ze identycznym algorytmem probowalem to ugryzc za pierwszym razem :)
>> Pozdrawiam
> Chyba bzdure napisalem. Jesli gradient jest rowny zero to mamy rozwiazanie.
> Zdaje sie ze to jest wypukle w calej przestrzeni (nie tylko gdy suma = 1).
> W takim razie dlaczego ogolne procedury optymalizacyjne tak slabo sobie z
> tym radza?


p1,
p2,
p3

1)
Jesteś na p1 x==p2 x < p3 x

Jak Twoja procedura liczy gradient.
Dlaczego jest nim p1 lub p2, a nie
taki wektor, by obie wartosći rozły jednakowo?
:)

2)
Jesteś na p1 x < p2 x, ale niewiele,
czyli jesteśmy blisko 'dziubka'

Jak Twoja procedura liczy gradient.
Gdzie ląduje kolejny x? Dlaczego 'wpizdu'
poza dziobem?
:)


To, że mamy ten szpikulec min (x,-x)
jest jeszcze gorsze niż standardowe
http://en.wikipedia.org/wiki/Rosenbrock_function


Podobny problem jest w rozwiązywaniu programowania liniowego.
Ale można go uładnić, wtdy procedury zaczynają działać.
Są nawet konkurencyjne dla Simplexa:

> *) a właśnie. Pisałem o próbach zaatakowania tego zwykłym
> solverem. Źle się do tego zabrałem. Prawidłowo robi się
> to tak:
>
> http://www.math.umbc.edu/~potra/talk0930.pdf
> http://www.stanford.edu/class/ee364a/lectures/barrie
r.pdf
> http://en.wikipedia.org/wiki/Interior_point_method
> http://en.wikipedia.org/wiki/Logarithmic_barrier_fun
ction
>
> Idea: Nasz problem jest wypukły, a ta bariera ładnie wszytko
> wygładza. Łazimy po wnętrzu, bariera słabnie, aż lądujemy
> w rozwiązaniu na brzegu.



pzdr
bartekltg

do góry