W dniu 2012-09-26 10:35, M.M. pisze:
> 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 ?

Znów odwracamy problem.

Szukamy (najmniejszego) promienia sfery stycznej do figury.

min (p1*x, p2*x, p3*x)>=1
Do tego x[i]>=0

Hmm:
http://en.wikipedia.org/wiki/Quadratic_programming
:)

Naszą normą jest x^t * x. Q = Id. c=0.


Ale znów możemy popatrzeć, jak to wygląda.

p1*x >= 1
p2*x >= 1
p3*x >= 1
e1*x >=0 {to samo co x[1]>=0, e1 = [1,0,0..0] etc}
...
e8*x >=0

Częścią wspólną znów jest nasz dobrze zanany
'prawie' wielokąt wypukły (nikt go nie domknął od góry).

Teraz pompujemy balonik (sferę) w punkcie 0
i czekamy na pierwsze zetknięcie.

Sprawa jest ciut gorsza, bo o ile w wersji liniowej
rozwiązanie leżało na wierzchołkach (co najwyżej
cała płaszczyzna mogła być rozwiązaniem, również
wierzchołki), teraz rozwiązanie może leżeć
na płaszczyźnie wyznaczonej przez dowolny podzbiór
więzów typu pi*x==1.., ej*x==0

Czyli niecałe (3+8)! Kandydatów pod postacią hiperpowierzchni,
dla każdego liczysz rzut z początku układu współrzędnych,
sprawdzasz pozostałe warunki i wybierasz najmniejszy.

To jest bruteforce. W rzeczywistośći robi się to
lekko podgonionym simplexem albo metodami z barierę(*).



*) 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