-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: zadanie optymalizacyjne
Date: Wed, 26 Sep 2012 01:28:26 +0200
Organization: ATMAN - ATM S.A.
Lines: 194
Message-ID: <k3temt$ok3$1@node2.news.atman.pl>
References: <2...@g...com>
<k3t365$gu3$1@node1.news.atman.pl> <k3t4im$iem$1@node1.news.atman.pl>
<2...@g...com>
NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1348615709 25219 85.222.69.144 (25 Sep 2012 23:28:29
GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Tue, 25 Sep 2012 23:28:29 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:15.0) Gecko/20120824
Thunderbird/15.0
In-Reply-To: <2...@g...com>
Xref: news-archive.icm.edu.pl pl.comp.programming:199598
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 26.09.12 01:31 kenobi
- 26.09.12 01:43 bartekltg
- 26.09.12 01:52 kenobi
- 26.09.12 10:23 M.M.
- 26.09.12 10:32 M.M.
- 26.09.12 10:35 M.M.
- 26.09.12 10:46 kenobi
- 26.09.12 12:53 Piotr Chamera
- 26.09.12 14:35 bartekltg
- 26.09.12 14:42 M.M.
- 26.09.12 14:48 Edek Pienkowski
- 26.09.12 14:55 Edek Pienkowski
- 26.09.12 15:15 bartekltg
- 26.09.12 15:18 bartekltg
- 26.09.12 16:21 bartekltg
Najnowsze wątki z tej grupy
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
- C++. Podróż Po Języku - komentarz
Najnowsze wątki
- 2025-07-08 Router LTE z możliwością zmian MTU
- 2025-07-08 Re: Pożar w Ząbkach a polscy dyletanci
- 2025-07-08 Trójmiasto => Head of Social Media <=
- 2025-07-08 Warszawa => MENA New Business Manager <=
- 2025-07-08 Środa Wielkopolska => SAP FI/CO Internal Consultant <=
- 2025-07-08 Warszawa => Customer Service with Spanish + translation <=
- 2025-07-08 Warszawa => Senior Account Manager <=
- 2025-07-08 Parkometry bez podstawy prawnej
- 2025-07-07 Re: Ząbki się spaliły jak wiejskie, drewniane stodoły sprzed 50 lat
- 2025-07-06 Kup szybko nową ładowarkę do smartfona
- 2025-07-07 TV z Play (dawniej UPC) -- potrzebny dekoder?
- 2025-07-06 Kup szybko nową ładowarkę do smartfona
- 2025-07-07 mija rok jeżdzenia po lewej
- 2025-07-06 Elektryki jednak są NIEBEZPIECZNE
- 2025-07-08 Fajny film widziałem...