W dniu 2012-09-25 22:58, M.M. pisze:
> Na razie nic nie zrozumialem. Jutro sprobuje jeszcze raz
> przeczytac:)

Napisałem wersję bardziej przejrzystą.
Zobaczymy. Dziś też już wymiękam;)

W razie czego możesz uwierzyć w dowód na słowo
i, co najwyzęj sprawdzając numerycznie, że
wychodzi dobrze, po prostu stosować algorytm;)


[OT] Czy ja dwa lata temu nie nabijałem się mówiąc
'zatrudnijcie numeryka'? ;>

pzdr
bartekltg

do góry

W dniu wtorek, 25 września 2012 22:57:35 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-09-25 22:25, kenobi pisze:
>
> > ale jaka to bedzie konkretnie
>
>
>
> Konkretnie:
>
> Nie, nie zawsze rozwiązanie będzie kombinacją liniową z1,z2,z3.
>
>
>
> Nie, nie zawsze rozwiązanie będzie spełniać
>
> dot(x,z1) == dot(x,z2) == dot(x,z3)
>
>
>
> To ostatnie łatwo pokazać.
>
>
>
> z1 = [2,1,1,1,1,1,1,1]
>
> z2 = [5,5,5,5,5,5,5,5]
>
> z3 = [8,9,7,5,6,9,8,7]
>
>
>
> Optymalne x wynosi tam x=[1,0,0,0,0,0,0,0].
>

no moze.. ale nie jestem przekonany czy
jakny x nie bylo 'nachylone' bardziej w strone
z1 to czy dot(x,z1) nie byloby wieksze niz 2.0
- takie nachylanie moznaby kontynuowac do momentu
az iloczyn z ktoryms z pozostalych nie spadlby
nizej - wtedy trzebaby nachylic w jego strone i finalnie wyladowaloby to w przypadku
gdzie
" dot(x,z1) == dot(x,z2) == dot(x,z3)"

- ale moje rozumowanie jest oparte na prostej
trojwymiarowej analogi i to z trzema wektorami
z1, z2 , z3 ulozonymi w katy ostre, bo nie
rozwazalem innych kierunkow - ale jak bys
widzial w ktorym momencie ta analogia sie
sypie to chetnie bym uslyszal ;-)

do góry

W dniu 2012-09-25 23:17, kenobi pisze:

>
> no moze.. ale nie jestem przekonany czy
> jakny x nie bylo 'nachylone' bardziej w strone
> z1 to czy dot(x,z1) nie byloby wieksze niz 2.0

Nie. Zawsze dla x[i]>0 x*z1 < x*z2 oraz x*z1 < x*z2

Dla każdego x dozwolonego w zadaniu
dot(x,z1) < dot(x,z2)
dot(x,z1) < dot(x,z3)

z1 i z2 możemy w ogole wyrzucić, nie wchodzą do minimum
nigdzie.

> - takie nachylanie moznaby kontynuowac do momentu
> az iloczyn z ktoryms z pozostalych nie spadlby
> nizej - wtedy trzebaby nachylic w jego strone i finalnie wyladowaloby to w
przypadku gdzie

No i właśnie taka sytuacja nie zachodzi w dodatniej ćwiartce.

> - ale moje rozumowanie jest oparte na prostej
> trojwymiarowej analogi i to z trzema wektorami
> z1, z2 , z3 ulozonymi w katy ostre, bo nie
> rozwazalem innych kierunkow - ale jak bys
> widzial w ktorym momencie ta analogia sie
> sypie to chetnie bym uslyszal ;-)

Nasz napisane, gdzie się sypie.
Dostałęś przykłąd na palcach.

Ok, za dużo wymiarów. weź r2.

z1 = [3,2]
z2 = [5,5]
z3 = [7,9]

Tutaj spokojnie wszytko na kartce narysujesz.

Rozwiązaniem jest M.M.owego preoblemu jest x=[1,0].

równość między (dotami) nie zachodzi.

pzdr
bartekltg

do góry

W dniu 2012-09-25 22:58, M.M. pisze:
> W dniu wtorek, 25 września 2012 22:11:49 UTC+2 użytkownik bartekltg napisał:

>> Nie wyzarzaniem;) Już zwykłe MC będzie lepsze:)
> Zgadza się. Moja wersja procedury optymalizacyjnej
> jest dość odlegla od wyzarzania, jednak nie wiem jak
> jak nazwac i mowie "odmiana wyzarzania".

Nadal to 4 sekundy na coś, co się na palcach robi;)

>> W dodatku wypukła/wklęsła.
> Raczej niewypukla/niewklesla. Ma dużo plaskich miejsc. Glupia procedura
> optymalizacyjna nie wie gdzie skoczyc gdy jest na plaskim miejscu.

A doczytaj definicję funkcji wypukłej;>
"Jak końce odcinka są w zbiorze => cały odcinek jest w zbiorze".

Kwadrat jest wypukły.

Linia prosta jest jak najbardziej funkcją wypukłą.
I wklęsłą:)

Max z kilku funkcji liniowych jest wypukły.
Min - wklęsły.



>> Im prostsza, tym lepsza. Matalbowskiego fminsearch trzeba nieco
>> podpuscić, aby to dobrze rozwiązywał.
> Gdy moja podpuszczalem przez rozne modyfikacje funkcji celu, to
> dzialalo ciut gorzej. Moze zle to robilem.

Na bojowo miałęm coś takeigo:

options =
optimset(optimset('fminsearch'),'TolFun',1e-20,'TolX
',1e-20,'MaxFunEvals',8*16000,'MaxIter',8*16000);

Dopieszczenie parametrów

x0=diff(sort([0;rand(7,1);1]));
[x,f]=
fminsearch( @(x)
-min([p1;p2;p3]*[x;1-sum(x)])+10000*sum(ff([x;1-sum(
x)])),x0(1:7) ,options)

Pierwsza linijka w sprytny sposób generuje wartości losowe o sumie 1.
dalej minimalizujemy, ale tylko po 7 parametrach, 8 jest wyliczany.
ff to funkcja, która na każdej współrzędnej jest odległością
(dwukrotnością odległośći) od odcinka [0,1], zdefiniowaną tak:
ff = @(x)abs(x)+abs(1-x)-1

Czasem dawałem sum(ff([x;1-sum(x)]))^2, tak samo zmieniał się
liczbowy parametr.

pi to nasze z[i]. Wektory leżące.

Mimo koszmarie mocnych parametrów czasem funkcja zatrzymywała
się szczęśliwa, że znalazła minimum, a do tego minimum był
jeszcze kawałeczek i trzeba bylo odpalać ją jeszcze kilkukrotnie,
za początkowe dane biorąc wcześniej uzyskane wyniki:

[x,f]=
fminsearch( @(x)
-min([p1;p2;p3]*[x;1-sum(x)])+10000*sum(ff([x;1-sum(
x)])),x(1:7) ,options)



Ale jak wspominałem, nie tędy droga.
fminsearch używa http://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_met
hod
i patrząc na nasza funkcję niespecjalnie dziwi, że mu kiepski idzie.


> Sprawdzalem, to zwodzi. Czesto jest f1=f2 i f3>f1 dla dowolnych x.

Ależ oczywiście. Bez problemu można napisać takie zi,
że nie będzie żadnej równości. Pytanie, ile wartości
przybiera wtedy ekstrema zakresu?

A czy czasem nie jesteś wtedy przybity do brzegu?

Dla jednej równości powinny być to 8-1-1,
dla dwóch(czyli trzech) 8-3 wartości (jeśli się
nie kopnąłem).
Pamiętaj, że nasze ekstrema to nie tylko zera.


>> Wybieramy jakiś wektor x z tej płaszczyzny, rzutujemy
>> na wektorki z1,z2,z3 i bierzemy najmniejszy rzut.
>> Bierzemy największy.
> Hmmm nie kumam.

Funkcja f1(p,x) = suma od 1 do N z1[j] * x[j];
to w istocie iloczyn skalarny wektora z1 i x.
A iloczyny skalarne i rzuty są dość spokrewnione:)

Ale to tylko ilustracja, nieistotne.

>> x (po prostu z R^N)
>> popatrzmy na 'hipsometry'. Płaszczyzna stałęj wartośći.
>> Weźmy jakąś wartość. b.
>> Wyrysujmy
>> z1*x==b
>> z2*x==b
>> z3*x==b
> Jasne.
>
>> Wyjdą z tego trzy hiperpłaszczyzny. One nas
>> ograniczają. Jednocześnie próbujemy dostać
>> się jak najbliżej centrum.
> Dlaczego jak najblizej centrum?

Racja, zbytnie uproszczenie. W dodatku pomylilem kierunki;)
Dla danego promienia oczywiście najdalsza
(ale to też trzeba się wgryźć w ilustracje, olej)

>> Powstanie nam fragment wielościanu wypukłego.
>> [Ciach mętna interpretacja geometryczna]
> Bylo ciekawie :)

Dużo mętnego rysowania. Jak ogarniesz dowód,
sam sobie interpretacje odtworzysz.

>> Mamy tutaj zwyczajne zagadnienie programowania liniowego z warunkami:
>> Najpierw je zdefiniujemy, a potem pokażemy, że to to samo.
>> z1*x >= 1
>> z2*x >= 1
>> z3*x >= 1
> W oryginalne bylo zi*x >= 0. zi[j] może zawierac {0,1,p[j]}. Rozumiem
> ze zmieniasz w okreslonym celu.


Nic z tych rzeczy!
z1*x to była twoja funkcja f1.

Te nierówności to nie założenia, lecz droga ku zwycięstwu! :)

>> x>0 (w znaczeniu x[i] > 0)
> W oryginale x[i]>=0, ale ok.

tak, miałem na myśli >=


>> oraz funkcją celu [1,1,1,1, 1,1,1,1] *x i chcemy ją _minimalizować_
>> Z algorytmu simplex czy jakiejkolwiek innej metody uzyskujesz
>> rozwiązanie x_1 spełniające te warunki i maksymalizujące
>> funkcję celu.
> Nie wiem co oznacza ten zapis [1,1,1...1]*x.

Iloczyn skalarny wektora x i wektora jedynkowego.
Równoważnie można napisać sum_{i=1}^{8}(x[i]) albo
po firowemu dot (x, [1,1,1...1])


>> Rozwiązaniem oryginalnego problemu jest x_2 = x_1/(suma(x_1)).
>> Dlaczego? No to szkic dowodu:
>
>> Niech b = 1/suma(x1).
>> Po przeskalowaniu x-ów przez b mamy
>> suma(x_2)=1 i spełnia
>> z1*x_2 >= b
>> z2*x_2 >= b
>> z3*x_2 >= b
>> czyli min (fi,f2,f3)>=b;) Wiemy, że równe.
>
>> Niech inny x3, taki , ze suma(x3)=1
>> jest lepszym 'maksimum z minimum'
>> z1*x_3 >= c
>> z2*x_3 >= c
>> z3*x_3 >= c
>> c > b
>
>> Wtedy
>> x3/c spełnia nierówności z programowania liniowego
>> (zi * (x_3/c)) <= 1 oraz
>> sum (x_3/c) = 1/c < 1/b, czyli jest lepszym minimum
>> funkcji celul z programowania liniowego. To jest
>> sprzeczne z tym, że x2 jest rozwiązaniem programowania
>> liniowego.
> Na razie nic nie zrozumialem. Jutro sprobuje jeszcze raz
> przeczytac :)

Jak pisałem, obok masz post z lekko
posprzątaną wersją. Oba posty powinne
wszystko rozjaśnić [niekoniecznie w pierwszym czytaniu:]

> Solver liniowy w arkuszu nie rozwiazuje tego :/

Ale wsadzałeś oryginalny, czy zmodyfikowany problem?

pzdr
bartekltg

do góry

W dniu środa, 26 września 2012 00:36:55 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-09-25 23:17, kenobi pisze:
>
>
>
> >
>
> > no moze.. ale nie jestem przekonany czy
>
> > jakny x nie bylo 'nachylone' bardziej w strone
>
> > z1 to czy dot(x,z1) nie byloby wieksze niz 2.0
>
>
>
> Nie. Zawsze dla x[i]>0 x*z1 < x*z2 oraz x*z1 < x*z2
>
>
>
> Dla każdego x dozwolonego w zadaniu
>
> dot(x,z1) < dot(x,z2)
>
> dot(x,z1) < dot(x,z3)
>
>
>
> z1 i z2 możemy w ogole wyrzucić, nie wchodzą do minimum
>
> nigdzie.
>
>
>
> > - takie nachylanie moznaby kontynuowac do momentu
>
> > az iloczyn z ktoryms z pozostalych nie spadlby
>
> > nizej - wtedy trzebaby nachylic w jego strone i finalnie wyladowaloby to w
przypadku gdzie
>
>
>
> No i właśnie taka sytuacja nie zachodzi w dodatniej ćwiartce.
>
>
>
> > - ale moje rozumowanie jest oparte na prostej
>
> > trojwymiarowej analogi i to z trzema wektorami
>
> > z1, z2 , z3 ulozonymi w katy ostre, bo nie
>
> > rozwazalem innych kierunkow - ale jak bys
>
> > widzial w ktorym momencie ta analogia sie
>
> > sypie to chetnie bym uslyszal ;-)
>
>
>
> Nasz napisane, gdzie się sypie.
>
> Dostałęś przykłąd na palcach.
>
>
>
> Ok, za dużo wymiarów. weź r2.
>
>
>
> z1 = [3,2]
>
> z2 = [5,5]
>
> z3 = [7,9]
>
>

albo cos zle zrozumialem albo zanianie polegalo na wyszukaniu x dla ktorego
najmnijszy z wektorow jest jak najwiekszy
tutaj dla x = 1,0
wyniki sa : max(3, 5, 7 ) czyli 3
a dla x = {sqrt(1/2), sqrt(1/2)}
okolo
0.7*3 + 0.7*2 = 2.1 + 1.4 = 3.5
10*0.7 = 7.0
4.9 + 6.3 = 10.2 czyli x = {1,0} nie jest rozwiazaniem




>
> Tutaj spokojnie wszytko na kartce narysujesz.
>
>
>
> Rozwiązaniem jest M.M.owego preoblemu jest x=[1,0].
>
>
>
> równość między (dotami) nie zachodzi.
>
>
>
> pzdr
>
> bartekltg

do góry

W dniu 2012-09-26 01:31, kenobi pisze:

>> Nasz napisane, gdzie się sypie.
>> Dostałeś przykład na palcach.
>>
>> Ok, za dużo wymiarów. weź r2.
>>
>> z1 = [3,2]
>> z2 = [5,5]
>> z3 = [7,9]
>>

> albo cos zle zrozumialem

Treść zadania. Na dwóch grupach wytykam ten błąd.

> albo zanianie polegalo na wyszukaniu x dla ktorego najmnijszy z wektorow jest jak
najwiekszy
> tutaj dla x = 1,0
> wyniki sa : max(3, 5, 7 ) czyli 3
> a dla x = {sqrt(1/2), sqrt(1/2)}

A dla x = {666,666} jeszcze więcej!

Suma składników x ma się sumować do 1.

sqrt(1/2) + sqrt(1/2) to jakieś 1.41, zdecydowanie więcej niż 1.

> okolo
> 0.7*3 + 0.7*2 = 2.1 + 1.4 = 3.5

666*3 + 666*2 = 3330

> 10*0.7 = 7.0
> 4.9 + 6.3 = 10.2 czyli x = {1,0} nie jest rozwiazaniem

Weź w końcu przeczytaj zadanie.


pzdr
bartekltg

do góry

W dniu środa, 26 września 2012 01:43:41 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-09-26 01:31, kenobi pisze:
>
>
>
> >> Nasz napisane, gdzie się sypie.
>
> >> Dostałeś przykład na palcach.
>
> >>
>
> >> Ok, za dużo wymiarów. weź r2.
>
> >>
>
> >> z1 = [3,2]
>
> >> z2 = [5,5]
>
> >> z3 = [7,9]
>
> >>
>
>
>
> > albo cos zle zrozumialem
>
>
>
> Treść zadania. Na dwóch grupach wytykam ten błąd.
>
>
>
> > albo zanianie polegalo na wyszukaniu x dla ktorego najmnijszy z wektorow jest jak
najwiekszy
>
> > tutaj dla x = 1,0
>
> > wyniki sa : max(3, 5, 7 ) czyli 3
>
> > a dla x = {sqrt(1/2), sqrt(1/2)}
>
>
>
> A dla x = {666,666} jeszcze więcej!
>
>
>
> Suma składników x ma się sumować do 1.
>
>
>
> sqrt(1/2) + sqrt(1/2) to jakieś 1.41, zdecydowanie więcej niż 1.
>
>
>
> > okolo
>
> > 0.7*3 + 0.7*2 = 2.1 + 1.4 = 3.5
>
>
>
> 666*3 + 666*2 = 3330
>
>
>
> > 10*0.7 = 7.0
>
> > 4.9 + 6.3 = 10.2 czyli x = {1,0} nie jest rozwiazaniem
>
>
>
> Weź w końcu przeczytaj zadanie.
>

ok, juz sie wyjasnilo, blednie przeczytalem
ze x ma byc znormalizowany do jedynki jak wektor a nie ze to ma byc zwykla suma
skladowych, spox, skoro tak to sie nie wtracam ;-)

do góry

W dniu wtorek, 25 września 2012 22:58:16 UTC+2 użytkownik Kacper Rzepecki napisał:
> Chyba sie jednak nie myle, dlaczego to nie mialby byc problem PL?
> Wszystkie ograniczenia i funkcja celu sa w postaci liniowej.
Tak, masz racje, ta droga tez jest dobra. I wyglada na to ze
wystarczy jedno zadanie, nie trzeba tyle zadan ile jest funkcji.

Maksymalizujemy tylko jedna funkcje, np. f_1.
Czyli szukamy MAX(f_1).
Pozostale funkcje dla wygody przerabiamy na warunki:
f_1 <= f_i co daje: f_1 - f_i <= 0 dla i>1
Sume x ograniczamy dowolna dodatnia liczba:
suma x1,x2...xn <= epsilon
ostatni warunek na niejuemnosc:
xi >= 0.

Teraz mozemy najzywczaniej poruszac sie od ograniczenia
do ograniczenia aby maksymalizowac funkcje celu. Nie
martwimy sie ze ograniczenia sie zmieniaja wraz ze zmiana
wartosci funkcji celu. Defacto zmieniaja sie liniowo, wiec
to zaden problem.


Kluczowy jest fakt, ktorego bez pomocy Bartka jakos nie
umialem wykorzystac, a mianowicie ze ograniczenie na
sume xi == 1 mozemy na chwile zignorowac, aby potem bez
zadnych zlych konsekwencji odtworzyc.

Pozdrawiam!

do góry

W dniu wtorek, 25 września 2012 22:35:35 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-09-25 22:11, bartekltg pisze:
> Rozwiązujemy następujące zadnienie zmodyfikowane:
> [programowanie liniowe]
> x*z1 > = 1
> x*z2 > = 1
> x*z3 > = 1
> x*zn > = 1
> z minimalizowaną funkcją celu sum(x)
> (czy jak kto woli x*[1,1,....1] )
> Za standardowym warunkiem x_i > 0

Tego potrzebowalem zeby zrozumiec :)


Bartek dziekuje, po raz kolejny mi pomogles.
Nie moge zatrudnic numeryka, czego bardzo tego zaluje.
Ale moge sie materialnie odwdzieczyc, napisz na
prywatny e-mail - ja tez nie zartuje :)

A co do dowodu poprawnosci. Czy nie wystarczy ze:
1) jest to poprawnie zefiniowane zadanie z programowania,
2) podczas odtworzenia warunku suma x_i = 1 funkcje skaluja
sie liniowo (bo sa liniowe), a wiec wszystkie inne warunki
liniowe nadal beda obowiazywaly?

Pozdrawiam i napisz na priv!

do góry

W dniu środa, 26 września 2012 01:52:21 UTC+2 użytkownik kenobi napisał:
> ok, juz sie wyjasnilo, blednie przeczytalem
> ze x ma byc znormalizowany do jedynki jak wektor a nie ze to ma byc zwykla suma
> skladowych, spox, skoro tak to sie nie wtracam ;-)
Tak, w tym zadaniu najzywklejsza suma xi == 1.

Ale poruszyles ciekawy temat, da sie to jakos latwo rozwiazac
gdy norma ||xi|| = 1 ?

Pozdrawiam :)

do góry