W dniu środa, 26 września 2012 10:35:52 UTC+2 użytkownik M.M. napisał:
> 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 ?
>

wtedy mz moze byc tak (nie jestem pewien ale
prawdopodobne) ze masz natychmiastowy wynik

for(int i=0; i<8; i++)
x[i] = h1 * z1[i] + h2 * z2[i] + h3 * z3[i];

gdzie h1, h2, h3 sa floatami obliczonymi
prostym wzorkiem z zaleznoci geometrycznej
(x[] ma byc po prostu rowno odlegly od z1[]
z2[] i z3[] w sensie iloczynu skalarnego
"dot(x,z1) == dot(x,z2) == dor(x, z3)"
ale odpadlem na wyznaczaniu tych wspolczynnikow
mimo ze to jest mz zadanie pewnie poziomu mw
ogolniaka

do góry

W dniu 2012-09-25 14:15, M.M. pisze:
> W dniu wtorek, 25 września 2012 13:30:44 UTC+2 użytkownik bartekltg napisał:
>> Ten zapis jest bez sensu.
>> Rozumiem, że chodzi o max_{zi} (min(f1,f2,f3))
>
> Trzeba zmaksymalizowac funkcje ff zmieniajac wartosci x.
> http://pastebin.com/papzUzaL
> Wartosci w p[j] sa losowe z przedzialu od 1 do P. Wartosci w z[i][j]
> sa rowne albo zero, albo jeden, albo p[j]. Suma wartosci x[i]
> msui byc rowna 1, ponadto kazdy x[i] >= 0.
>

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?

Znaczące są funkcje ,,move" i ,,maxff" reszta jest analogiczna jak
w zadaniu w C++.

Szybkościowo mieści się w założonym 0,03 s nawet w nieoptymalizowanym
lispie chociaż robi dużo nadmiarowych obliczeń :) - pytanie tylko czy
jest poprawne?



(defconstant +N+ 3)
(defconstant +M+ 8)

;;;; pomocnicze działania na wektorach

(defun add (va vb) ; suma
(let ((vr (make-array +M+ :element-type 'float)))
(dotimes (i +M+)
(setf (aref vr i) (+ (aref va i) (aref vb i))))
vr))

(defun sub (va vb) ; różnica
(let ((vr (make-array +M+ :element-type 'float)))
(dotimes (i +M+)
(setf (aref vr i) (- (aref va i) (aref vb i))))
vr))

(defun smul (va s) ; mnożenie ze skalarem
(let ((vr (make-array +M+ :element-type 'float)))
(dotimes (i +M+)
(setf (aref vr i) (* (aref va i) s)))
vr))

(defun check-in-1-box (vx) ; sprawdzenie czy wektor mieści się kostce
(every (lambda (x) (and (<= x 1.0)
(>= x 0)))
vx))

;;;; inicjalizacje parametrów zadania

(defun frand ()
(random 1.0))


(defun initP ()
"Utwóż wektor losowych p takich, że p >=1 i p <= 5"
(let ((p (make-array +M+ :element-type 'float)))
(dotimes (i +M+)
(setf (aref p i) (+ 1.0 (* (frand) 5.0))))
p))

(defun initZ (vp)
"Utwóż losową tablicę współczynników dla funkcji f na podstawie vp"
(let ((mz (make-array +N+)))
(dotimes (i +N+)
(let ((mzi (make-array +M+ :element-type 'float)))
(dotimes (j +M+)
(setf (aref mzi j) (ecase (random 3)
(0 0)
(1 1)
(2 (aref vp j)))))
(setf (aref mz i) mzi)))
mz))

(defun initX (&optional (vx nil))
"Utwórz wektor losowych x takich, że x >= 0 i sum(x) = 1"
(when (null vx)
(setf vx (make-array +M+ :element-type 'float)))
(dotimes (i +M+)
(setf (aref vx i) (random 1.0)))
(let ((sum (reduce #'+ vx)))
(dotimes (i +M+)
(setf (aref vx i) (/ (aref vx i) sum))))
vx)


(defun initDir ()
"Utwórz zbiór narożników hiperkostki"
(let ((dir (make-array +M+)))
(dotimes (i +M+)
(let ((vdir (make-array +M+ :element-type 'float :initial-element
0.0)))
(setf (aref vdir i) 1.0)
(setf (aref dir i) vdir)))
dir))


(defun asert (vx)
"Sprawdz czy vx spełnia warunki x >= 0 i sum(x) = 1"
(when (some (lambda (x) (< x 0))
vx)
(error "x mniejsze od zera"))
(when (> (abs (- 1.0 (reduce #'+ vx)))
0.00001)
(error "błąd sumy x większy od 0.00001"))
t)

;;;; zadanie

(defun f (z x &aux (sum 0.0))
(dotimes (i +M+)
(setf sum (+ sum
(* (aref z i) (aref x i)))))
sum)


(defun ff (mz x)
(asert x)
(let ((min nil))
(dotimes (i +N+)
(let ((tmp (f (aref mz i) x)))
(when (or (null min)
(> min tmp))
(setf min tmp))))
min))

;;;; rozwiązanie

(defun move (mz vx step dir)
(let ((max (ff mz vx))
(max-vx vx))
(dolist (s (list step (- step))) ; sprawdz ruchy w obu kierunkach
(dotimes (i +M+) ; po wszystkich osiach układu
współrzędnych
(let ((v (add vx (smul (sub (aref dir i) vx) s)))) ; idziemy po linii
vx - dir o współczynnik s
(when (check-in-1-box v)
(let ((p-max (ff mz v)))
(when (> p-max max) ; zapisz najlepszy znaleziony ruch
(setf max p-max
max-vx v)))))))
(values max-vx max)))

(defun maxff (mz)
(let* ((vx (let ((v (make-array +M+ :element-type 'float
:initial-element 0.0)))
(setf (aref v 0) 1.0)
v)) ; początkowy x i aktualizowny na bieżąco najlepszy
(max 0.0) ; początkowe maksimum i aktualizowne na bieżąco najlepsze
(dir (initDir)) ; tablica wierzchołków kostki (wektory typu [1 0 0 ... 0])
(step 0.5) ; aktualny krok modyfikacji
(epsilon 0.00001)) ; żądana dokładność maksimum
(do () ((< step epsilon) ())
(multiple-value-bind (p-vx p-max) (move mz vx step dir)
(if (> (- p-max max) epsilon)
(setf max p-max
vx p-vx)
(setf step (/ step 2.0)))))
(values vx max)))



; // TODO: zmaksymalizować funkcję ff( z , x ) zmiejąc x (nie zmieniając z)

Można tego użyć np tak: (maxff (initZ (initP)))

do góry

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

:)

> 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?

No, musisz jeszcze pokazać, że to nadal najlepsze rozwiązanie.
Tak, to oczywiste;), ale wolałem dopisać dowód (zresztą, dowodząc
tego znalazłem błąd w pierwszej wersji).


Sprawdziłem przerobioną wersję na oo calc. Nie tylko
znalazł rozwiązanie, ale i okazało się, że fminsearch
zaplątał się i był gorszy o parę %.


Wpadłem rano, jak w miarę prosto 'algebraicznie'
rozwiązywać pierwotny problem, ale algorytm
jest dość podobny, w pewnym momencie radośnie sobie
rzutujemy na jądro pewnej macierzy ograniczeń;)
a do simpleksu jeśli nawet nie masz juz biblioteki,
to łatwiej znaleźć gotowca czy materiały.


W każdym razie szłoby to tak (szkic i nieprzetestowane):

Mamy jakąś propozycję dla x.

Uaktualniamy ją. Nawet o gradeint g = pi, gdzie
pi odpowiada najmniejszej funkcji w x. Tylko teraz
wrzucamy ograniczenia. Pierwszym jest
równość g[1] +.. +g[8] = 0 - to gwarantuje
pozostanie na naszej płaszczyźnie.
Jeśli mamy pi*x == pj*x i jest to najmniejsza
wartość ze wzyctkich pk*x, dodajemy równania
pi[1]*g[1] +.. +pi[8]*g[8]==0
pj[1]*g[1] +.. +pj[8]*g[8]==0

Rzutujemy nasz gradient na jądro mcierzy opisującej
te warunki (kod wygląda lepiej niż to brzmi:).
Dzięki temu nie uciekamy z płaszczyzny oraz nie
zmnijeszamy fi kosztem innych równych co do wartości fj.

Dalej, dla każdej współrzędnej x[i]==0
i g (już ten nowy gradient) g[i]<0
dodajemy warunek g[i]==0.

Powiększamy naszą macierz warunków i powtarzamy operację.

Teraz gorsza część.

patrzymy na wetkro x'=x + t*g. t to skalr.
Rozwiązujemy wszystkie kolizje ze ściankami,
oraz potójne równości pi*x' == pj*x' == pk*x'

Wybieramy najmniejsze dodatnie t, podstawiamy
x< x+t*g
goto start:)


Da się. Jest upierdliwe. Nadal polecam przepisać
simplex z wiki;)


pzdr
bartekltg

do góry

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




>
>
>
> Znaczące są funkcje "move" i "maxff" reszta jest analogiczna jak
>
> w zadaniu w C++.
>
>
>
> Szybkościowo mieści się w założonym 0,03 s nawet w nieoptymalizowanym
>
> lispie chociaż robi dużo nadmiarowych obliczeń :) - pytanie tylko czy
>
> jest poprawne?
>
>
>
>
>
>
>
> (defconstant +N+ 3)
>
> (defconstant +M+ 8)
>
>
>
> ;;;; pomocnicze działania na wektorach
>
>
>
> (defun add (va vb) ; suma
>
> (let ((vr (make-array +M+ :element-type 'float)))
>
> (dotimes (i +M+)
>
> (setf (aref vr i) (+ (aref va i) (aref vb i))))
>
> vr))
>
>
>
> (defun sub (va vb) ; różnica
>
> (let ((vr (make-array +M+ :element-type 'float)))
>
> (dotimes (i +M+)
>
> (setf (aref vr i) (- (aref va i) (aref vb i))))
>
> vr))
>
>
>
> (defun smul (va s) ; mnożenie ze skalarem
>
> (let ((vr (make-array +M+ :element-type 'float)))
>
> (dotimes (i +M+)
>
> (setf (aref vr i) (* (aref va i) s)))
>
> vr))
>
>
>
> (defun check-in-1-box (vx) ; sprawdzenie czy wektor mieści się kostce
>
> (every (lambda (x) (and (<= x 1.0)
>
> (>= x 0)))
>
> vx))
>
>
>
> ;;;; inicjalizacje parametrów zadania
>
>
>
> (defun frand ()
>
> (random 1.0))
>
>
>
>
>
> (defun initP ()
>
> "Utwóż wektor losowych p takich, że p >=1 i p <= 5"
>
> (let ((p (make-array +M+ :element-type 'float)))
>
> (dotimes (i +M+)
>
> (setf (aref p i) (+ 1.0 (* (frand) 5.0))))
>
> p))
>
>
>
> (defun initZ (vp)
>
> "Utwóż losową tablicę współczynników dla funkcji f na podstawie vp"
>
> (let ((mz (make-array +N+)))
>
> (dotimes (i +N+)
>
> (let ((mzi (make-array +M+ :element-type 'float)))
>
> (dotimes (j +M+)
>
> (setf (aref mzi j) (ecase (random 3)
>
> (0 0)
>
> (1 1)
>
> (2 (aref vp j)))))
>
> (setf (aref mz i) mzi)))
>
> mz))
>
>
>
> (defun initX (&optional (vx nil))
>
> "Utwórz wektor losowych x takich, że x >= 0 i sum(x) = 1"
>
> (when (null vx)
>
> (setf vx (make-array +M+ :element-type 'float)))
>
> (dotimes (i +M+)
>
> (setf (aref vx i) (random 1.0)))
>
> (let ((sum (reduce #'+ vx)))
>
> (dotimes (i +M+)
>
> (setf (aref vx i) (/ (aref vx i) sum))))
>
> vx)
>
>
>
>
>
> (defun initDir ()
>
> "Utwórz zbiór narożników hiperkostki"
>
> (let ((dir (make-array +M+)))
>
> (dotimes (i +M+)
>
> (let ((vdir (make-array +M+ :element-type 'float :initial-element
>
> 0.0)))
>
> (setf (aref vdir i) 1.0)
>
> (setf (aref dir i) vdir)))
>
> dir))
>
>
>
>
>
> (defun asert (vx)
>
> "Sprawdz czy vx spełnia warunki x >= 0 i sum(x) = 1"
>
> (when (some (lambda (x) (< x 0))
>
> vx)
>
> (error "x mniejsze od zera"))
>
> (when (> (abs (- 1.0 (reduce #'+ vx)))
>
> 0.00001)
>
> (error "błąd sumy x większy od 0.00001"))
>
> t)
>
>
>
> ;;;; zadanie
>
>
>
> (defun f (z x &aux (sum 0.0))
>
> (dotimes (i +M+)
>
> (setf sum (+ sum
>
> (* (aref z i) (aref x i)))))
>
> sum)
>
>
>
>
>
> (defun ff (mz x)
>
> (asert x)
>
> (let ((min nil))
>
> (dotimes (i +N+)
>
> (let ((tmp (f (aref mz i) x)))
>
> (when (or (null min)
>
> (> min tmp))
>
> (setf min tmp))))
>
> min))
>
>
>
> ;;;; rozwiązanie
>
>
>
> (defun move (mz vx step dir)
>
> (let ((max (ff mz vx))
>
> (max-vx vx))
>
> (dolist (s (list step (- step))) ; sprawdz ruchy w obu kierunkach
>
> (dotimes (i +M+) ; po wszystkich osiach układu
>
> współrzędnych
>
> (let ((v (add vx (smul (sub (aref dir i) vx) s)))) ; idziemy po linii
>
> vx - dir o współczynnik s
>
> (when (check-in-1-box v)
>
> (let ((p-max (ff mz v)))
>
> (when (> p-max max) ; zapisz najlepszy znaleziony ruch
>
> (setf max p-max
>
> max-vx v)))))))
>
> (values max-vx max)))
>
>
>
> (defun maxff (mz)
>
> (let* ((vx (let ((v (make-array +M+ :element-type 'float
>
> :initial-element 0.0)))
>
> (setf (aref v 0) 1.0)
>
> v)) ; początkowy x i aktualizowny na bieżąco najlepszy
>
> (max 0.0) ; początkowe maksimum i aktualizowne na bieżąco najlepsze
>
> (dir (initDir)) ; tablica wierzchołków kostki (wektory typu [1 0 0 ... 0])
>
> (step 0.5) ; aktualny krok modyfikacji
>
> (epsilon 0.00001)) ; żądana dokładność maksimum
>
> (do () ((< step epsilon) ())
>
> (multiple-value-bind (p-vx p-max) (move mz vx step dir)
>
> (if (> (- p-max max) epsilon)
>
> (setf max p-max
>
> vx p-vx)
>
> (setf step (/ step 2.0)))))
>
> (values vx max)))
>
>
>
>
>
>
>
> ; // TODO: zmaksymalizować funkcję ff( z , x ) zmiejąc x (nie zmieniając z)
>
>
>
> Można tego użyć np tak: (maxff (initZ (initP)))

do góry

Dnia Tue, 25 Sep 2012 04:22:59 -0700, M.M. napisal:

> Jest N-elementowy ciag parametrow p[1..N] i N-elementowy ciag argumentow
> x[1..N]. W moim problemie obecnie N jest rowne 8, ale potem bedzie
> wieksze. Zarowno parametry jak i argumenty to liczby rzeczywiste.
> Parametry p sa z przedzialu 1 <= p <= P, gdzie P z reguly jest mniejsze
> od 10. Suma argumentow x zawsze musi byc rowna zero z dokladnoscia
> przynajmniej czterech miejsc po przecinku (najlepiej szesciu). Ponadto
> kazdy argument x musi byc wiekszy lub rowny zero.
>
> Jest kilka funkcji liniowych (obecnie mam trzy, ale bedzie wiecej):
> f1(p,x) = suma od 1 do N z1[j] * x[j];
> f2(p,x) = suma od 1 do N z2[j] * x[j];
> f3(p,x) = suma od 1 do N z3[j] * x[j];
> gdzie zi[j] moze przyjmowac wartosc zero, jeden, albo p[j].
>
> Ciagi p i z sa danymi w zadaniu. Szukamy takiego ciagu x ktory
> zmaksymalizuje minimum:
> max( min( f1, f2 , f3 )).
>
> Dostosowalem do tego zdania symulowane wyzarzanie. Znajduje rozwiazanie
> po okolo 50mln iteracji, co zajmuje na procesorze i3 okolo 4-5 sekund.
> Niestety dopuszczalny czas to 0.03s.
>
> Da sie to jakos szybciej policzyc?

Jak masz dużo zadań tego typu i nie robisz tego "dla sportu",
może ściągnij ppl.

--
Edek

do góry

Dnia Wed, 26 Sep 2012 12:48:31 +0000, Edek Pienkowski napisal:

> Dnia Tue, 25 Sep 2012 04:22:59 -0700, M.M. napisal:
...
>>
>> Dostosowalem do tego zdania symulowane wyzarzanie. Znajduje rozwiazanie
>> po okolo 50mln iteracji, co zajmuje na procesorze i3 okolo 4-5 sekund.
>> Niestety dopuszczalny czas to 0.03s.
>>
>> Da sie to jakos szybciej policzyc?
>
> Jak masz dużo zadań tego typu i nie robisz tego "dla sportu",
> może ściągnij ppl.

Zauważyłem, że to niezbyt jednoznaczny skrót.
Oczywiście nie M$ PPL, bo to nie wiem co jest, tylko convex hull
polyhedra.

--
Edek

do góry

W dniu 2012-09-26 10:23, M.M. pisze:

> 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.

Nie nie. My go nie ignorujemy. Jak całkiem zignorujesz,
nijak nie rozpoznasz, czy wartość funkcji jest lepsza,
czy tylko 'pierwsza norma' wektora większa.

To ograniczenie przeszło w funkcję celu postaci
x1 + x2 + x3...+x8.

Raz _trzymamy_ x1 + x2 + x3...+x8 = 1
i _maksymalizujemy_ min (p1*x,p2*x,p3*x),

drugim razem "_trzymamy_", w formie ograaniczenia
p1*x>=1
p2*x>=1
p3*x>=1
a _minimalizujemy_ 'x1 + x2 + x3...+x8'

Ty jest pełna dualność, o niczym nie zapominamy.


Gdyby równanie naszej hiperpłaszczyzny było inne,
inna również musiałaby być funkcja celu, aby
odpowiadała temu samemu zadaniu.

pzdr
bartekltg

do góry

W dniu 2012-09-26 15:15, bartekltg pisze:
> W dniu 2012-09-26 10:23, M.M. pisze:
>
>> 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.
>
> Nie nie. My go nie ignorujemy. Jak całkiem zignorujesz,
> nijak nie rozpoznasz, czy wartość funkcji jest lepsza,
> czy tylko 'pierwsza norma' wektora większa.
>
> To ograniczenie przeszło w funkcję celu postaci
> x1 + x2 + x3...+x8.
>
> Raz _trzymamy_ x1 + x2 + x3...+x8 = 1
> i _maksymalizujemy_ min (p1*x,p2*x,p3*x),
>
> drugim razem "_trzymamy_", w formie ograaniczenia
> p1*x>=1
> p2*x>=1
> p3*x>=1

Co równoważnie możemy zapisać jako

min (p1*x, p2*x, p3*x) >= 1 //min. po prostu z 3 funkcji
:)


> a _minimalizujemy_ 'x1 + x2 + x3...+x8'
>
> Ty jest pełna dualność, o niczym nie zapominamy.
>
>
> Gdyby równanie naszej hiperpłaszczyzny było inne,
> inna również musiałaby być funkcja celu, aby
> odpowiadała temu samemu zadaniu.

pzdr
bartekltg

do góry

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

do góry

W dniu 2012-09-26 12:53, Piotr Chamera pisze:...
> 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?
>
> Znaczące są funkcje ,,move" i ,,maxff" reszta jest analogiczna jak
> w zadaniu w C++.
>
> ... pytanie tylko czy jest poprawne?

nie jest :(

do góry