-
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
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
Najnowsze wątki
- 2025-01-06 śnieg
- 2025-01-05 Żarówka do lampy z czujnikiem ruchu
- 2025-01-05 Rozkręcają się
- 2025-01-04 pozew za naprawę sprzętu na youtube
- 2025-01-04 gasik
- 2025-01-04 13. Raport Totaliztyczny: Powszechna Deklaracja Praw Człowieka Nie Chroni Przed Wyzyskiem Ani Przed Eksploatacją
- 2025-01-04 Zbieranie danych przez www
- 2025-01-04 reverse engineering i dodawanie elementów do istniejących zamkniętych produktów- legalne?
- 2025-01-04 w Nowym Roku 2025r
- 2025-01-04 Warszawa => Specjalista ds. IT - II Linia Wsparcia <=
- 2025-01-04 Warszawa => Java Developer <=
- 2025-01-04 Warszawa => Spedytor Międzynarodowy <=
- 2025-01-04 Warszawa => System Architect (Java background) <=
- 2025-01-04 Wrocław => Application Security Engineer <=
- 2025-01-04 Chrzanów => Specjalista ds. public relations <=