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