THMMY.gr

2η Εργαστηριακή Άσκηση
1 Μαϊ 2014 8:04 μμ
Θεοδωρακόπουλος

Η  2η  εργαστηριακή  άσκηση  αναρτήθηκε  στο  Υλικό  Μαθήματος  ->  Ασκήσεις.
Προθεσμία  παράδοσης:    18/5/2014.

Η  εργασία  είναι  διπλή  και  θα  βαθμολογηθεί  ανάλογα.

Απαιτεί  αρκετό  χρόνο  γι'  αυτό  μην  την  αφήσετε  τελευταία  στιγμή,  αλλά  αξιοποιείστε  ολόκληρο  το  διαθέσιμο  διάστημα.  Παράταση  δεν  προβλέπεται  λόγω  πίεσης  χρόνου.

Υ.Γ.  Λάβετε  υπόψη  σοβαρά  το  "αξιοποιείστε  ολόκληρο  το  διαθέσιμο  διάστημα".

Διευκρίνηση:
Το  σκέλος  "γ)  μεταβλητό  βάσει  κάποιου  ευριστικού  κανόνα  που  θα  επιλέξετε  εσείς,  π.χ.  αν..."  να  υλοποιηθεί  με  κάποιο  ευριστικό  τρόπο  αυξομοίωσης  του  βήματος  που  θα  σκεφτείτε  εσείς,  δηλ.  να  μη  χρησιμοποιηθεί  κάποιος  έτοιμος  κανόνας.

Την έχει δει κανείς??
Έχω κολλήσει στην αρχή μου βγάζει πρόβλημα με την γραφική παράσταση της f  :(

Πες τι έκανες/τι πρόβλημα βγάζει/κλπ

λοιπόν κάνω


Και μου βγάζει πρόβλημα με την εντολή Z=f(X,Y)
Error using f (line 4)
Both arguments should be real numbers.

Προφανώς θα σου βγάζει λάθος. Οι πίνακες X, Y που δημιουργείς μέσω του meshgrid έχουν διαστάσεις 9x9, και πας να τους δώσεις σαν όρισμα στη συνάρτηση f(x,y) που θα έπρεπε να δέχεται δύο πραγματικούς αριθμούς σαν ορίσματα.

ααα δεν τα παίρνει δηλαδή ένα ένα??

Αν είναι έτσι τότε θα κάθομαι να δίνω μια μια τις τιμές?

for loop θα ήταν μια καλή ιδέα ;)

μα και με το for loop δλδ 2 for στη σειρά αν έχω πίνακα χ και y 1x10 τότε το f(x,y) θα είναι 100. όταν το έκανα αυτό μετά με το Plot3 ή το surf μου έβγαζε οτι πρέπει να είναι ίδιο το μέγεθος των πινάκων

Στον κώδικα που έγραψες παραπάνω, οι πίνακες X και Y είναι 9x9. Με ένα διπλό loop μπορείς να φτιάξεις έναν πίνακα Z  9x9 που να περιέχει τιμές της συναρτησης για τις διάφορες τιμές των x (γραμμές) και y (στήλες).

Μια ερώτηση για τα ερωτήματα β). Μας ζητάει να βρούμε τιμή του γκ τέτοια ώστε να ελαχιστοποιείται η τιμή του F(Χk+1) =F(Xk+γk*dk), ως προς γκ . Έχει παραδείγματα τέτοια το βιβλίο, όμως εκεί για τον προσδιορισμό του γκ, σε κάθε επανάληψη, χρησιμοποιεί τον αναλυτικό τύπο της F και βάση αυτού λύνει μια ανίσωση και προσδιορίζει την τιμή του. Εμείς, εδώ δεν έχουμε τον αναλυτικό τύπο της Φ, μόνο την γραφική παράσταση. Πως θα κάνουμε λοιπόν τα ερωτήματα β ????




btw... στην μέθοδο newton, για σταθερό γκ , βγάζει ότι να 'ναι αποτελέσματα, δηλαδή ψάχνει μια παράγωγο που προσεγγίζει  το 0 αλλά αντί να καταλήξει στο ελάχιστο καταλήγει στα σημεία πέρα από αυτό που είναι σχεδόν ισοϋψή, δηλαδή στα προς τα έξω σημεία του γραφήματος, ισχύει αυτό?

Απ' ότι θυμάμαι για να λύσεις την εξίσωση ως προς το γκ χρησιμοποιούσες μια από τις μεθόδους που είχες υλοποιήσει στην πρώτη εργασία..πρόσεχε ποια απ' όλες θα επιλέξεις όμως, γιατί θυμάμαι ότι πχ. εμένα με την μέθοδο της διχοτόμου μου έβγαζε ό,τι να ναι αποτελέσματα και μετά δεν βγαίνανε τα επόμενα ερωτήματα

Ευχαριστώ. Πραγματικά δεν σκέφτηκα καθόλου να το συνδέσω με την πρώτη εργασία, παρόλο που στην πρώτη υλοποιούσαμε μόνο μεθόδους εύρεσης ελαχίστου :)  . Βέβαια, στην πρώτη εργασία μιλούσαμε για αυστηρά σχεδόν κυρτές συναρτήσεις και ήταν συναρτήσεις μιας μεταβλητής. Θα κάνω μερικές δοκιμές για το ποια μέθοδο να χρησιμοποιήσω και  ελπίζω να είμαι οκ.

Έριξα μια ματιά στις εργασίες μου και είδα ότι το είχα υλοποιήσει με τη μέθοδο του χρυσού τομέα τελικά. Ο Αχιλλέας το είχε αναφέρει πέρσυ σε κάποιο μάθημα ασκήσεων, ότι μέσα στο loop που θα τρέχει για κάθε βήμα του αλγορίθμου θα καλούμε μια από τις μεθόδους της 1ης εργασίας, ίσως φέτος δεν δόθηκε αφορμή να το αναφέρει  :P

Δυστυχώς, έχασα το τελευταίο μάθημα των ασκήσεων την τετάρτη. Ίσως, το είπε εκεί, πολύ πιθανόν δηλαδή και γι' αυτό δεν το είχα καν υπόψη. Ευχαριστώ, πολύ και πάλι για την διευκρίνιση.

Και κάτι τελευταίο αν γίνεται. Στην πρώτη εργασία κάναμε υλοποίηση μεθόδων εύρεσης ελαχίστων για συναρτήσεις μιας μεταβλητής. Εδώ, έχουμε συνάρτηση F, δύο μεταβλητών, δηλαδή F(x,y). Πως ακριβώς κάνω την επέκταση για μια μέθοδο, για παράδειγμα της μεθόδου χρυσού τομέα,  από μια  συνάρτηση μιας μεταβλητής στην νέα συνάρτηση δυο μεταβλητών ???

Μπορεί να μου εξηγήσει κάποιος πως θα χρησιμοποιήσω τα παλιά για να βρω το γ_κ???

Η συνάρτηση f(x_k+γ_kδ_k) που καλείσαι να ελαχιστοποιήσεις ως προς γ_k, προκειμένου να βρεις το βήμα σου, είναι συνάρτηση μιας μεταβλητής.

Δεν μας νοιάζει που η f μας είναι συνάρτηση 2 μεταβλητών?

Μα, εσύ θες να ελαχιστοποιήσεις τη συνάρτηση h(γ_k) = f(x_k+γ_kδ_k), που είναι συνάρτηση μιας μεταβλητής!

Ωραία και όταν εγώ ελαχιστοποιώ την f(x,y) Και στο χ και στο y θα βάζω το ίδιο γ?

Ε προφανώς, x_k+γ_kδ_k είναι διανυσματική σχέση!

όσοι πήγατε όντως στα μαθήματα ασκήσεων, ανέφερε κάποια συγκεκριμένη μέθοδο για την ελαχιστοποίηση? θέλει σώνει και καλά χρυσού τομέα δηλαδή?

Όχι, λογικά κανείς ότι θέλεις αρκεί να δουλεύει.

άλλη μία ερώτηξη, ανέφερε αν θέλει να βάλουμε όριο βημάτων στις μεθόδους?

Όχι, αλλά γενικά είναι καλή τακτική.

Στο 1ο ερώτημα για τα (1,2,4) σημεία ο αλγόριθμος δεν κάνει καμία επανάληψη έτσι πρέπει να έιναι ή κάνω κάτι λάθος?

Για τα σημεία 1 και 2 έχεις δίκιο, για το 4 θα κάνει επαναλήψεις αν βάλεις πολύ μικρή σταθερά ε.

η μέθοδο levenberg συγκλίνει με αρχικό σημείο το (-2,-1) ??

Ναι, και για σταθερό γ_κ και για μεταβλητό.

Εμένα για σταθερό γ_κ συγκλίνει μόνο για 0,15:0,05:0,4 , 0,45:0,05:0,85 και 0,95:0,05:1,4 ....
Εσένα συγκλίνει π.χ. και για 0,1 ή 0,4?

Επίσης έχει καταφέρει κανείς την σχεδόν Newton εφαρμόζοντας τον αλγόριθμο του βιβλίου?

Ναι. Δοκίμασα και όλες τις τιμές στο 0.1:0.1:1 και συγκλίνει. (Και για γ_κ=1 ή 2 επίσης.)

Η σχεδόν Newton δεν μου δουλεύει ακόμα αλλά άλλοι πχ. Exomag την έχουν βγάλει.

To μ_κ κάνεις κάποια επιπλέον δουλειά για να βρεις πόσο κοντά στη μέγιστη απόλυτη ιδιοτιμή θα το πάρεις?

Μπα, απλά μέγιστη + 1 το έχω.

Εγώ παίρνω τη μεγαλύτερη ιδιοτιμή και την αυξάνω συνέχεια κατά 0.1 έως ότου γίνει ο πίνακας θετικά ορισμένος.

Η συνάρτηση που θέλουμε να ελαχιστοποιήσουμε ξέρουμε αν είναι τετραγωνική; Και αν είναι μπορούμε να το καταλάβουμε από κάπου;

Στη μέθοδο Newton, με σημείο εκκίνησης το (-2,-1), ο άλγοριθμός μου συγκλίνει στο (-2.5,-1.2) που είναι μακριά από το πραγματικό ελάχιστο. Καμιά ιδέα;

edit: ο εσσιανός σε αυτό το σημείο είναι αρνητικά ορισμένος.

Σύμφωνα με το βιβλίο ο πίνακας είναι θετικά ορισμένος για οποιοδήποτε μ_κ > της μεγαλύτερης ιδιοτιμής.

Ε ναι, το μόνο που πρέπει να επιλέξεις εσύ είναι ποσό μεγαλύτερο της μεγαλύτερης ιδιοτιμής θα είναι. Άμα συγκλίνει στην τελική ο αλγόριθμος, τότε είσαι οκ.

Α οκ, δεν ήξερα ότι η ακριβής τιμή του μ_κ μπορεί να κάνει τον αλγόριθμο να μην συγκλίνει (εφόσον ο πίνακας βγαίνει πάντα θετικά ορισμένος).

Στη μέθοδο Levenberg για σταθερό γκ πρέπει να ελέγχουμε και αν ικανοποιούνται τα κριτήρια 3 και 4;

Στη μέθοδο των συζυγών κλίσεων κάνω κάτι λάθος?

xk  = -2;
yk = -1;
dk = -gradf(xk,yk);
p = gradf(xk,yk);


while p(1,1) ~= 0 && p(2,1) ~= 0
    c= gold(xk,yk,dk(1,1),dk(2,1));  Μέθοδος του χρυσού τομέα
    temp1 = xk;
    temp2 = yk;
    xk = xk + c*dk(1,1);
    yk = yk + c*dk(2,1);
   
    bk = (transpose(gradf(xk,yk))*gradf(xk,yk))/(transpose(gradf(temp1,temp2))*gradf(temp1,temp2));
    dk = -gradf(xk,yk) + bk*dk;
   
    p = gradf(xk,yk);
   
 end   
   
disp(xk)
disp(yk)

Η μέθοδος Newton σας συγκλίνει γενικά πέρα από σημεία κοντά στο ελάχιστο ;  :-\

Λογικό είναι να μη συγκλίνει, γιατί τίποτα στον αλγόριθμο δε σου εγγυάται ότι ο εσσιανός πίνακας είναι θετικά ορισμένος.

Πάλι καλά.  :D

Edit: Στις σχεδόν Newton αφού για να συγκλίνει η μέθοδος, το γ(κ) πρέπει να έχει τιμή που να ικανοποιεί συγκεκριμένη συνθήκη δεν είναι άτοπο να βάλουμε σταθερό βήμα;

Στα ερωτήματα 3 που λέει να βρούμε ενα δικό μας ευριστικό κανόνα, εννοεί αυτός ο κανόνας να προέλθει απο μελέτη για καλή λειτουργία και επιτυχία του αλγορίθμου ή να είναι εντελώς τυχαίος?

κ αυτό απαντήστε, κ αυτό!

Κάποιος; :P

Στο μάθημα δεν το είχε αναφέρει καν αυτό όταν εξηγούσε την μέθοδο, οπότε λογικά δεν πρέπει να το βάλεις.

Εγώ κατάφερα να την κάνω να συγκλίνει, οπότε δε νομίζω ο αλγόριθμος του βιβλίου να έχει κάποιο πρόβλημα.

Όταν χρησιμοποιείς εσωτερική βελτιστοποίηση,στην 1η επανάληψη χρειάζεται γ μεγαλύτερο του 1 ή είσαι πάλι στο (0,1];
Εμένα δουλεύει,μόνο αν στην 1η βάλω αρκετά μεγαλύτερη τιμή,αλλιώς ο Δ_κ+1 δεν είναι θετικά ορισμένος.

Δεν νομίζω πως λέει πουθενά ότι το βήμα πρέπει να είναι αυστηρά στο διάστημα (0,1].

Ο σχεδόν Newton συγκλίνει για το (-2,-1) ??

Κομπλέ τότε.  :)

Πρέπει να συγκλίνει, για βήμα που προέκυψε απο εσωτερική ελαχιστοποίηση, ναι.

τι εννοείς εσωτερική ελαχιστοποίηση;

Αφού επιλέξεις κατεύθυνση κίνησης ελαχιστοποιείς την f ως προς γ.  :)

Εννοείτε ότι πρέπει να συγκλίνει στην περίπτωση B που επιλέγουμε το γ ελαχιστοποιώντας την f(x(k+1)) ?

Ναι.  ;)

Τέλεια..εμένα σε όλες πάει στο ίδιο σημείο άσχετο απο το ελάχιστο.

Στη μέθοδο συζυγών κλίσεων όταν λέει επανεκκινούμε τον αλγόριθμο εννοεί πως πρέπει να αλλάξουμε κάτι στις αρχικές μας συνθήκεσ?Γιατί αλλιώς πάντα τα ίδια αποτελέσματα θα έχω!

στη Levenberg με σταθερό γ, το γ περιορίζεται στο (0,1) ή μπορώ να το επιλέξω και πάνω από 1;

για την Levengerg παλι,για αρχικο σημειο (-2,-1) εμενα μου συγλινει σε
σημεια  5.4269    2.3353       για βηματα  0.1
           12.8537    5.6706                        0.2
           20.2806    9.0058                        .
           27.7075   12.3411                       .
           35.1344   15.6764                       .
           42.5612   19.0117                       .
           49.9881   22.3470                       .
           57.4150   25.6822                       .
           64.8418   29.0175
           72.2687   32.3528                      1
κανω κατι λαθος ? πρεπει να μου συγκλινει στο (-0.5,-0.5)?

νομίζω ότι πρέπει  συγκλίνει στο (-0.5,-0.5)

ναι εχεις δικιο μια στα8ερα για το (μ) τν ειχα βαλει 0.001 και μετα που την εβαλα 0.1
ηταν κομπλε

Δες εδω
http://radio.feld.cvut.cz/matlab/toolbox/nnet/backpr58.html
Powell-Beale Restarts
και εδω
http://en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method
β=max{0,β}

αν το κανω σωστα ,για σταθερο βημα στο (-2,-1) συγκλινει
αλλα εκφυλιζεται ουσιαστικα σε steepest descent

για την εσωτερικη ελαχιστοποίηση κανω τετοιες συγκρισεις στην μεθοδο χρυσου τομεα

f(x-x1(k)*dif(1),y-x1(k)*dif(2))>f(x-x2(k)*dif(1),y-x2(k)*dif(2))

οπου χ1(κ),χ2(κ) ειναι το γ

της μορφης δηλ f(x+γd)....  είναι σωστο?
και επίσης τα ακρα για την αναζήτηση πως τα επιλεγετε?

Σωστά μου φαίνονται αυτά που γράφεις! ;)

Για το διάστημα αναζήτησης, μπορείς να το έχεις σταθερό εφόσον ο αλγόριθμος δουλεύει και συγκλίνει χωρίς πρόβλημα. Αλλιώς, θα μπορούσες να βρεις κάποιον ευριστικό τρόπο εύρεσης των ορίων αναζήτησης.

οκ thnx

Και κατι αλλο αν μπορεις,
 ειπες οτι στην σχεδον Νewton συγκλινεις στο (-0.5,-0.5)
για εσωτερικη ελαχιστοποιηση (βημα)?

Ναι! Αν δεν σου συγκλίνει, παίζει να φταίει αυτό πιυ ανέφερες πριν, το ότι δεν έχεις κατάλληλο διάστημα στην ελαχιστοποίηση του βήματος.

Εχεις δικιο μολις το βρηκα δοκιμαζα διαστηματα και εβαλα -100,100
και συγκλινε
thnx παντως