THMMY.gr

4η Εργαστηριακή Άσκηση
28 Μαϊ 2014 12:32 μμ
Θεοδωρακόπουλος

Η  4η  εργαστηριακή  άσκηση  αναρτήθηκε  στο  Υλικό  Μαθήματος  ->  Ασκήσεις.

Προθεσμία  παράδοσης:  3/6/2014.

Μερικές ερωτήσεις για την μέθοδο ποινής. Αρχικά, πως θα ορίσω το r0 και ποια σχέση συνδέει το rk+1 με το rk, στην μέθοδο ποινής?? Στην μέθοδο φραγμού δίνει συγκεκριμένους τύπους, εδώ όμως δεν βρήκα κάτι σχετικά εκτός από ένα παράδειγμα, που βρίσκει την σχέση που συνδέει το xk* με το rk, όμως εκεί είναι συνάρτηση με έναν περιορισμό. Σχετικά, με αυτό βρήκα την παρατήρηση 6.3.1 σελ. 221. Εκεί αναφέρει ότι, ξεκινάμε από μικρές τιμές του rk και αυξάνουμε συνεχώς σε κάθε επανάληψη, συγκλίνοντας τελικά στο ελάχιστο για rk τείνει στο άπειρο. Άρα, στην μέθοδο ποινής έχω αυξητική σχέση για το rk+1, σε σχέση με το rk???
Δεύτερο, πρέπει να κανονικοποιήσω τους περιορισμούς όπως έκανα στην μέθοδο φραγμού??? Τέλος, η συνθήκη τερματισμού είναι κοινή και για τις δυο μεθόδους, ποινής και φραγμού???
Για την μέθοδο φραγμού είμαι εντάξει. Απλά, για την ποινής θέλω λίγο να ξεκαθαρίσω τα παραπάνω.

Για το r₀ δεν υπάρχει κάποια σχέση για να το διαλέξεις, οπότε βάλε απλά κάποιο αρκούντως μικρό που να κάνει τον αλγόριθμο να δουλεύει σωστά. Επίσης θα πρέπει το όριο του r_k, όσο το k πάει στο άπειρο, να πηγαίνει και αυτό στο άπειρο. Οπότε ναι, το r_k θα πρέπει να έχει αυξητική τάση.

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

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

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

Καμιά ιδέα για το πώς λύνουμε το σύστημα που προκύπτει από Karush-Kuhn-Tucker για την f;

με το χερι? δεν υπαρχει δυσκολια
και θα βρεις αν εχω σωστα (χ1,χ2)=(3,-5)
λ1=27
λ2=29
λ3=λ4=0

Σωστό σημείο βρήκες, εγώ όμως έχω:

• λ₁ = 0
• λ₂ = 17
• λ₃ = 23
• λ₄ = 0

Με περιπτώσεις δουλέψατε; το σημείο το βρήκα και εγώ αλλά δεδομένου ότι έχουμε περιορισμούς η κυρτότητα των συναρτήσεων δε μας εξασφαλίζει ότι το ελάχιστο είναι ολικό..
Τα λ μου συμφωνούν με του exomag

Ναι, με περιπτώσεις για το ποιό/ποιά λ είναι ίσα με μηδέν ή διάφορα του μηδενός.

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

όπως και να το έκανες, αν είναι σωστή διαδικασία (και άρα κατέληξες σε σωστό αποτέλεσμα) δεν έχει σημασία ;)

είσαι σίγουρος οτι είναι τόσο τα λ??
Έβαλα τις τιμές σου στις εξισώσεις και δεν βγαίνουν σωστά.

f = x1*x2 + 2*(x1-x2)^2
g1 =  x1 - 30  <= 0
g2 = -x1 + 3   <= 0
g3 =  x2 + 5   <= 0
g4 = -x2 - 25  <= 0


gradf = [x2+4(x1-x2)  x1-4(x1-x2)]'
gradg1 = [ 1  0]'
gradg2 = [-1  0]'
gradg3 = [ 0  1]'
gradg4 = [ 0 -1]'


x2 +4(x1-x2) +λ1 -λ2 = 0
x1  -4(x1-x2) +λ3 -λ4 = 0
λ1( x1 - 30) = 0
λ2(-x1 +  3) = 0
λ3( x2 +  5) = 0
λ4(-x2 - 25) = 0
λ1,λ2,λ3,λ4 >= 0


λ1x1  = 30λ1 :    x1 = 30     ή λ1 = 0
-λ2x1 = -3λ2  :    x1 =  3      ή λ2 = 0
λ3x2  = -5λ3  :    x2 = -5      ή λ3 = 0
-λ4x2 = 25λ4 :    x2 = -25    ή λ4 = 0


x1 = 30, x2 = -5, λ2  = 0, λ4 = 0
-5 + 4(35) + λ1 = 0 => λ1 = -135
30 - 4(35) + λ3 = 0 => λ3 = +110


x1 = 3, x2 = -25, λ1 = 0, λ3 = 0
-25 + 4(28) - λ2 = 0 => λ2 = 112-25 = 87
3 - 4(28) - λ4 = 0 => λ4 = -112 +3 = -109


x1 = 3, x2 = -5, λ1 = 0, λ4 = 0
-5 +4(8)  - λ2 = 0 => λ2 = +(32-5) = +27,  λ2 = +27>0  δεκτή
 3  -4(8)  +λ3 = 0 => λ3 = +32 -3  = +29,   λ3 = +29>0   δεκτή


x1 = 30, x2 = -25, λ2 = 0, λ3 = 0
-25 + 4(55) + λ1 = 0 => λ1 = -220+25 = -195
30 - 4(55) - λ4 = 0 => λ4 = -220+30 = -190

Μετά από αυτό το στάδιο πως διαλέγω ποιο από τα 4 είναι σωστό?
Εντάξει τελικά μάλλον είναι όντως το (+3,-5), απλά είχα κάποια λάθη στις πράξεις.

κοιτας λ>=0
και οτι χ βρισκεις να ειναι μεσα στους περιορισμους

επιπλεον
για  το ΚΚΤ πρεπει να δειξεις οτι η f,g ειναι κυρτες με hessian>=0 το πιο απλο
,κυρτοι οι περιορισμοι ,  και υπεραποτελουμενο και μετα βρισκεις εφικτο σημειο και
λ (λιγο αχταρμα αλλα καταλαβες οτι δεν πρεπει να θεωρησεις οτι ισχυουν και να
παρεις ξερα ΚΚΤ)
 

Τελικά βρίσκω λ₂=27 και λ₃=29..

τόσο είναι...εγώ έβαλα τις εξισώσεις στο MATLAB και τόσο έβγαλε..

όντως, λάθος είχα εγώ, 27 και 29 είναι!

κατι αλλο, στις γραφικες παραστασεις τους περιορισμους πως τους βαζετε;

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

Ζορίζεσαι γιατί οι μέθοδοι φραγμού δεν είναι κατάλληλοι για αυτήν την περίπτωση, και το λύνεις με μέθοδο ποινής. (Αν δεν κάνω λάθος δηλαδή.)

Ξέρει κανείς πως μετασχηματίζουμε το πρόβλημα ελαχιστοποίησης στη μορφή

Αx < b    

δηλαδή πως βρίσκουμε τον πίνακα Α NxN του συστήματος, και το διάνυσμα b?

για μεθοδο φραγμου, για την f πρεπει να συγκλινει στο (3,-5)?

όχι..εμένα φτάνει κοντά στο μηδέν.Η φραγμού δεν λειτουργεί όταν το ελάχιστο είναι πάνω στα όρια.

 α και μενα το ιδιο, εχω 5 ωρες και ψαχνω τη λαθος κανω

ρε παιδια ενας να μου πει πως βαζει περιορισμους στις γραφικες παραστασεις
υπαρχει?