ყველაზე ციცაბო დაღმართის მეთოდი არის ცვლადი საფეხურის გრადიენტური მეთოდი. ყოველი გამეორებისას საფეხურის მნიშვნელობა k ირჩევა f(x) ფუნქციის მინიმუმის მდგომარეობიდან დაღმართის მიმართულებით, ე.ი.
ეს მდგომარეობა ნიშნავს, რომ მოძრაობა ანტიგრადიენტის გასწვრივ ხდება მანამ, სანამ f (x) ფუნქციის მნიშვნელობა მცირდება. მათემატიკური თვალსაზრისით, ყოველი გამეორებისას აუცილებელია ფუნქციის მიმართ ერთგანზომილებიანი მინიმიზაციის პრობლემის გადაჭრა.
()=f(x(k)-f(x(k)))
ამისათვის ჩვენ ვიყენებთ ოქროს მონაკვეთის მეთოდს.
ყველაზე ციცაბო დაღმართის მეთოდის ალგორითმი შემდეგია.
მოცემულია x (0) საწყისი წერტილის კოორდინატები.
x (k) , k = 0, 1, 2, ... წერტილში გამოითვლება f (x (k)) გრადიენტის მნიშვნელობა.
ნაბიჯის ზომა k განისაზღვრება ფუნქციის მიმართ ერთგანზომილებიანი მინიმიზაციის გზით
()=f(x(k)-f(x(k))).
x (k) წერტილის კოორდინატები განისაზღვრება:
x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.
შემოწმებულია განმეორებითი პროცესის შეჩერების პირობა:
||f(x(k+1))|| .
თუ დაკმაყოფილებულია, მაშინ გამოთვლები ჩერდება. წინააღმდეგ შემთხვევაში, 1-ლ საფეხურზე გადასვლა ხორციელდება. ყველაზე ციცაბო დაღმართის მეთოდის გეომეტრიული ინტერპრეტაცია ნაჩვენებია ნახ. ერთი.
ბრინჯი. 2.1. ყველაზე ციცაბო დაღმართის მეთოდის ბლოკ-სქემა.
მეთოდის დანერგვა პროგრამაში:
ყველაზე ციცაბო დაღმართის მეთოდი.
ბრინჯი. 2.2. ყველაზე ციცაბო დაღმართის მეთოდის განხორციელება.
დასკვნა: ჩვენს შემთხვევაში, მეთოდი 7 იტერაციაში გადავიდა. წერტილი A7 (0,6641; -1,3313) არის უკიდურესი წერტილი. კონიუგატური მიმართულებების მეთოდი. კვადრატული ფუნქციებისთვის შეგიძლიათ შექმნათ გრადიენტური მეთოდი, რომელშიც კონვერგენციის დრო იქნება სასრული და ტოლი n ცვლადების რაოდენობაზე.
ჩვენ ვუწოდებთ ზოგიერთ მიმართულებას და ვუკავშირდებით ზოგიერთ პოზიტიურ განსაზღვრულ ჰესის მატრიცას H, თუ:
მაშასადამე, H ერთეულით, კონიუგატური მიმართულება ნიშნავს მათ პერპენდიკულურს. ზოგად შემთხვევაში, H არატრივიალურია. ზოგადად, კონიუგაცია არის ჰესის მატრიცის გამოყენება ვექტორზე - ეს ნიშნავს ამ ვექტორის ბრუნვას რაიმე კუთხით, მის გაფართოებას ან შეკუმშვას.
და ახლა ვექტორი ორთოგონალურია ვექტორთან, ანუ კონიუგატი არ არის ვექტორების ორთოგონალურობა, არამედ ბრუნვითი ვექტორის ორთოგონალურობა.ი.ი.
ბრინჯი. 2.3. კონიუგირებული მიმართულებების მეთოდის ბლოკ-სქემა.
მეთოდის დანერგვა პროგრამაში: კონიუგატური მიმართულებების მეთოდი.
ბრინჯი. 2.4. კონიუგატური მიმართულებების მეთოდის დანერგვა.
ბრინჯი. 2.5. კონიუგატური მიმართულებების მეთოდის ნახატი.
დასკვნა: წერტილი A3 (0.6666; -1.3333) ნაპოვნია 3 გამეორებაში და არის ექსტრემალური წერტილი.
3. შეზღუდვების არსებობისას ფუნქციის მინიმალური, მაქსიმალური მნიშვნელობის განსაზღვრის მეთოდების ანალიზი
შეგახსენებთ, რომ პირობითი ოპტიმიზაციის ზოგადი პრობლემა ასე გამოიყურება
f(x) ® min, x О W,
სადაც W არის Rm-ის სათანადო ქვესიმრავლე. პრობლემების ქვეკლასი თანასწორობის ტიპის შეზღუდვებით გამოირჩევა იმით, რომ სიმრავლე მოცემულია ფორმის შეზღუდვებით.
f i (x) = 0, სადაც f i: R m ®R (i = 1, …, k).
ამრიგადW = (x О R m: f i (x) = 0, i = 1, …, k).
ჩვენთვის მოსახერხებელი იქნება f ფუნქციისთვის ინდექსი „0“ დავწეროთ. ამრიგად, ოპტიმიზაციის პრობლემა თანასწორობის ტიპის შეზღუდვებით იწერება როგორც
f 0 (x) ® წთ, (3.1)
f i (x) = 0, i = 1, …, k. (3.2)
თუ ახლა F-ით აღვნიშნავთ Rm ფუნქციას R k-ში მნიშვნელობებით, რომლის კოორდინატთა აღნიშვნას აქვს ფორმა f(x) = (f 1 (x), …, f k (x)), მაშინ (3.1)–( 3.2) ასევე შეიძლება ჩაიწეროს ფორმაში
f 0 (x) ® min, f(x) = Q.
გეომეტრიულად, ტოლობის ტიპის შეზღუდვების პრობლემა არის f 0 ფუნქციის გრაფიკის ყველაზე დაბალი წერტილის პოვნის პრობლემა მრავალფეროვნებაზე (იხ. სურ. 3.1).
პუნქტებს, რომლებიც აკმაყოფილებენ ყველა შეზღუდვას (ანუ სიმრავლის წერტილებს) ჩვეულებრივ უწოდებენ დასაშვებს. დასაშვებ წერტილს x* ეწოდება f 0 ფუნქციის პირობითი მინიმუმი f i (x) = 0, i = 1, ..., k (ან ამოცანის ამოხსნა (3.1)–(3.2) შეზღუდვების ქვეშ, თუ ყველა დასაშვები წერტილისთვის x f 0 (x *) f 0 (x). (3.3)
თუ (3.3) დაკმაყოფილებულია მხოლოდ x* წერტილის V x*-ის რომელიმე უბანში მდებარე დასაშვებ x-ზე, მაშინ საუბარია ლოკალურ პირობით მინიმუმზე. პირობითი მკაცრი ლოკალური და გლობალური მინიმუმების ცნებები ბუნებრივი გზით არის განსაზღვრული.
პრობლემის ფორმულირება
დაუშვით ფუნქცია f(x) R n
საჭირო f(x) X = Rn
ძიების სტრატეგია
x k
} , k = 0,1,...,
ისეთივე როგორც 
, k = 0.1,...
. თანმიმდევრობის წერტილები ( x k
) გამოითვლება წესით
სად არის წერტილი x 0 დაყენებულია მომხმარებლის მიერ; ნაბიჯის ზომა ტ კ განსაზღვრულია თითოეული მნიშვნელობისთვის კ მდგომარეობიდან
პრობლემა (3) შეიძლება გადაწყდეს აუცილებელი მინიმალური პირობის გამოყენებით, რასაც მოჰყვება საკმარისი მინიმალური პირობის შემოწმება. ეს გზა შეიძლება გამოყენებულ იქნას ან საკმაოდ მარტივი ფუნქციის შესამცირებლად, ან საკმაოდ რთული ფუნქციის წინასწარი დაახლოებისთვის. 
მრავალწევრი P(tk)
(ჩვეულებრივ, მეორე ან მესამე ხარისხის), შემდეგ კი მდგომარეობა იცვლება პირობით, ხოლო მდგომარეობა პირობით 
მიმდევრობის აგება ( x k )
წერტილით მთავრდება x k
, რისთვის , სად ε
არის მოცემული მცირე დადებითი რიცხვი, ან k ≥ M
, სად მ
- გამეორებების ზღვრული რაოდენობა, ან ორი უტოლობის ორი ერთდროული შესრულებით 
, 
სადაც ε 2
მცირე დადებითი რიცხვია. საკითხავია თუ არა წერტილი x k
ჩაითვალოს სასურველი ლოკალური მინიმალური წერტილის ნაპოვნი მიახლოებით x *
, მოგვარებულია დამატებითი კვლევებით.
მეთოდის გეომეტრიული ინტერპრეტაცია n=2 ნახ. 4.
საკოორდინაციო დაღმართის მეთოდი
პრობლემის ფორმულირება
დაუშვით ფუნქცია f(x) , შემოსაზღვრულია ქვემოდან გადასაღებ მოედანზე R n და აქვს უწყვეტი ნაწილობრივი წარმოებულები მის ყველა წერტილში.
f(x) დასაშვები ხსნარების კომპლექტზე X = Rn , ე.ი. იპოვეთ ისეთი წერტილი, რომ
ძიების სტრატეგია
პრობლემის გადაჭრის სტრატეგია შედგება პუნქტების თანმიმდევრობის აგებაში ( x k
} , k = 0,1,...,
ისეთივე როგორც , k = 0.1,...
. თანმიმდევრობის წერტილები ( x k
) გამოითვლება ციკლებით წესის მიხედვით
(4)
სადაც ჯ - გაანგარიშების ციკლის ნომერი; j = 0,1,2,...; კ - გამეორების ნომერი მარყუჟის შიგნით, k = 0,1,...,n - 1; e k +1, k = 0,l,...,n - 1 - ერთეული ვექტორი, (k+1) -რომლის პროექცია უდრის 1-ს; წერტილი x 00 მომხმარებლის მიერ დაყენებული, ნაბიჯის ზომა ტ კ მდგომარეობიდან შერჩეული
ან 
.
თუ შერჩეული მდგომარეობა მიმდინარე ტ კ
არ არის შესრულებული, ნაბიჯი განახევრებულია და წერტილი 
გადაითვლება. ადვილი მისახვედრია, რომ ფიქსირებული j-ისთვის რიცხვთან ერთ გამეორებაში კ
იცვლება მხოლოდ ერთი წერტილის პროექცია x jk
, რომელსაც აქვს ნომერი k + 1
და მთელი ციკლის განმავლობაში რიცხვით ჯ
, ე.ი. დაწყებული k = 0
და დამთავრებული k=n-1
, იცვლება წერტილის ყველა n პროგნოზი x j0
. ამ მომენტის შემდეგ x jn
მიანიჭა ნომერი x j + 1.0
, და იგი აღებულია, როგორც საწყისი წერტილი გამოთვლებისთვის j + 1
ციკლი. გაანგარიშება მთავრდება წერტილში x jk
როდესაც დათვლის დასასრულის სამი კრიტერიუმიდან ერთი მაინც დაკმაყოფილებულია: 
, ან , ან უტოლობების ორმაგი შესრულება .
გამოთვლების შედეგად მიღებული ქულები შეიძლება ჩაიწეროს მიმდევრობის ელემენტებად (xl), სადაც l=n*j+k - პუნქტის სერიული ნომერი,
მეთოდის გეომეტრიული ინტერპრეტაცია n = 2-ისთვის ნაჩვენებია ნახ. 5.
4. ფრანკ-ვოლფის მეთოდი .
დაე, საჭირო გახდეს ჩაზნექილი ფუნქციის მაქსიმალური მნიშვნელობის პოვნა
პირობებში
ამ პრობლემის დამახასიათებელი თვისება ის არის, რომ მისი შეზღუდვების სისტემა შეიცავს მხოლოდ წრფივ უტოლობას. ეს თვისება საფუძვლად უდევს საკვლევი წერტილის სიახლოვეს არაწრფივი ობიექტური ფუნქციის წრფივით ჩანაცვლებას, რის გამოც საწყისი ამოცანის ამოხსნა მცირდება წრფივი პროგრამირების ამოცანების თანმიმდევრულ გადაწყვეტამდე.
პრობლემის გადაჭრის პროცესი იწყება წერტილის განსაზღვრით, რომელიც მიეკუთვნება დასაშვები გადაწყვეტილებების არეალს.
270
დაჩები. დაე, ეს იყოს წერტილი X(k)
მაშინ ამ დროს გამოითვლება ფუნქციის (57) გრადიენტი
და შექმენით წრფივი ფუნქცია
შემდეგ ამ ფუნქციის მაქსიმალური მნიშვნელობა გვხვდება შეზღუდვებში (58) და (59). მოდით, ამ პრობლემის გადაწყვეტა განისაზღვროს წერტილით Z(k)
. შემდეგ წერტილის კოორდინატები X(k+1)
:
სად λ კ - რომელიღაც რიცხვი, რომელსაც უწოდებენ გამოთვლის საფეხურს და დადებულია ნულისა და ერთის შორის (0<λk < 1). Это число λ კ მიიღოს თვითნებურად ან განსაზღვროს
ისე, რომ ფუნქციის მნიშვნელობა წერტილში X (k + 1) f(X (k + 1)) დამოკიდებულია λ კ , იყო მაქსიმუმი. ამისათვის თქვენ უნდა იპოვოთ განტოლების გამოსავალი და აირჩიოთ მისი ყველაზე პატარა ფესვი. თუ მისი ღირებულება ერთზე მეტია, მაშინ λ კ=1 . ნომრის დადგენის შემდეგ λ კ იპოვნეთ წერტილის კოორდინატები X(k+1) გამოთვალეთ მასში ობიექტური ფუნქციის მნიშვნელობა და გაარკვიეთ ახალ წერტილში გადასვლის აუცილებლობა X(k+2) . თუ არსებობს ასეთი საჭიროება, მაშინ გამოთვალეთ წერტილი X(k+1) ობიექტური ფუნქციის გრადიენტი, გადადით შესაბამის წრფივ პროგრამირების ამოცანაზე და იპოვეთ მისი ამოხსნა. განსაზღვრეთ წერტილის კოორდინატები და X(k+2) და გამოიკვლიეთ შემდგომი გამოთვლების საჭიროება. სასრული რაოდენობის ნაბიჯების შემდეგ, საწყისი პრობლემის გადაწყვეტა მიიღება საჭირო სიზუსტით.
ასე რომ, პრობლემის გადაჭრის პროცესი (57) - (59) ფრანკ-ვოლფის მეთოდით მოიცავს შემდეგ საფეხურებს.:
1. პრობლემის საწყისი შესაძლო გადაწყვეტის განსაზღვრა.
2. იპოვეთ ფუნქციის (57) გრადიენტი შესაძლებელი ამოხსნის წერტილში.
3. შექმენით ფუნქცია (60) და იპოვეთ მისი მაქსიმალური მნიშვნელობა (58) და (59) პირობებში.
4. განსაზღვრეთ გაანგარიშების ნაბიჯი.
5. ფორმულების (61) გამოყენებით მოიძებნება ახალი შესაძლებელი გადაწყვეტის კომპონენტები.
6. შეამოწმეთ მომდევნო მისაღებ გადაწყვეტაზე გადასვლის აუცილებლობა. საჭიროების შემთხვევაში გადადით მე-2 სტადიაზე, წინააღმდეგ შემთხვევაში ნაპოვნია ორიგინალური პრობლემის მისაღები გამოსავალი.
საჯარიმო ფუნქციების მეთოდი.
განვიხილოთ ჩაზნექილი ფუნქციის მაქსიმალური მნიშვნელობის განსაზღვრის პრობლემა
f (x 1, x 2, .... x n)პირობებში g i (x 1, x 2, .... x n) ≤ b i (i=l, m) , x j ≥ 0 (j=1, n) , სად g i (x 1, x 2, .... x n) ამოზნექილი ფუნქციებია.
ამ პრობლემის უშუალოდ გადაჭრის ნაცვლად, იპოვეთ ფუნქციის მაქსიმალური მნიშვნელობა F (x 1, x 2, ...., x n) \u003d f (x 1, x 2, ...., x n) +H(x 1, x 2, ...., x n) რომელიც არის პრობლემის ობიექტური ფუნქციისა და ზოგიერთი ფუნქციის ჯამი
H(x 1, x 2, ...., x n), განსაზღვრულია შეზღუდვების სისტემით და ე.წ საჯარიმო ფუნქცია. საჯარიმო ფუნქციის აგება შესაძლებელია სხვადასხვა გზით. თუმცა, ყველაზე ხშირად ის იღებს ფორმას
მაგრამ a i > 0
- რამდენიმე მუდმივი რიცხვი, რომელიც წარმოადგენს წონის კოეფიციენტებს.
საჯარიმო ფუნქციის გამოყენებით, ერთი თანმიმდევრულად გადადის ერთი წერტილიდან მეორეზე, სანამ მისაღები გამოსავალი არ მიიღება. ამ შემთხვევაში, შემდეგი წერტილის კოორდინატები გვხვდება ფორმულით
ბოლო მიმართებიდან გამომდინარეობს, რომ თუ წინა წერტილი არის თავდაპირველი ამოცანის შესაძლო გადაწყვეტილებების არეში, მაშინ კვადრატულ ფრჩხილებში მეორე წევრი ნულის ტოლია და შემდეგ წერტილზე გადასვლა განისაზღვრება მხოლოდ გრადიენტით. ობიექტური ფუნქცია. თუ მითითებული წერტილი არ მიეკუთვნება შესაძლებელი გადაწყვეტილებების რეგიონს, მაშინ ამ ტერმინის გამო, შემდგომი გამეორებების დროს, მიიღწევა დაბრუნება შესაძლებელი გადაწყვეტილებების რეგიონში.
გადაწყვეტილებები. თუმცა, რაც უფრო ნაკლები ა ი
რაც უფრო სწრაფად მოიძებნება მისაღები გამოსავალი, მაგრამ მცირდება მისი განსაზღვრის სიზუსტე. ამიტომ, განმეორებითი პროცესი ჩვეულებრივ იწყება შედარებით მცირე მნიშვნელობებით ა ი
და, ამის გაგრძელებით, ეს მნიშვნელობები თანდათან იზრდება.
ასე რომ, საჯარიმო ფუნქციის მეთოდით ამოზნექილი პროგრამირების პრობლემის გადაჭრის პროცესი მოიცავს შემდეგ ნაბიჯებს:
1. განსაზღვრეთ საწყისი შესაძლებელი გადაწყვეტა.
2. აირჩიეთ გაანგარიშების ნაბიჯი.
3. ყველა ცვლადისთვის ნაპოვნია ობიექტური ფუნქციისა და ფუნქციების ნაწილობრივი წარმოებულები, რომლებიც განსაზღვრავენ პრობლემის დასაშვები გადაწყვეტილებების არეალს.
4. ფორმულით (72) იპოვეთ იმ წერტილის კოორდინატები, რომელიც განსაზღვრავს პრობლემის შესაძლო ახალ გადაწყვეტას.
5. შეამოწმეთ, აკმაყოფილებს თუ არა ნაპოვნი წერტილის კოორდინატები ამოცანის შეზღუდვების სისტემას. თუ არა, მაშინ გადადით შემდეგ ეტაპზე. თუ აღმოჩენილი წერტილის კოორდინატები განსაზღვრავენ პრობლემის შესაძლო გადაწყვეტას, მაშინ განიხილება საჭიროება გადავიდეთ შემდეგ შესაძლო გადაწყვეტაზე. საჭიროების შემთხვევაში გადადით მე-2 სტადიაზე, წინააღმდეგ შემთხვევაში ნაპოვნია ორიგინალური პრობლემის მისაღები გამოსავალი.
6. დააყენეთ წონა და გადადით მე-4 საფეხურზე.
ისარი-ჰურვიცის მეთოდი.
საჯარიმო ფუნქციის მეთოდის გამოყენებით არაწრფივი პროგრამირების ამოცანების ამოხსნის პოვნისას, ჩვენ ავირჩიეთ მნიშვნელობები ა ი , თვითნებურად, რამაც გამოიწვია მნიშვნელოვანი რყევები განსაზღვრული წერტილების დისტანციურობაში შესაძლებელი გადაწყვეტილებების რეგიონიდან. ეს მინუსი აღმოიფხვრება პრობლემის Arrow-Hurwitz მეთოდით გადაჭრით, რომლის მიხედვითაც რიცხვის მომდევნო საფეხურზე a i (k) გამოითვლება ფორმულის მიხედვით
როგორც საწყისი მნიშვნელობები a i (0) მიიღეთ თვითნებური არაუარყოფითი რიცხვები.
გადაწყვეტის მაგალითი
მაგალითი 1.
იპოვეთ ფუნქციის ადგილობრივი მინიმუმი
წერტილის განსაზღვრა x k
1 კომპლექტი .
2. დააყენე k = 0 .
ოცდაათი . გამოთვლა
40 . გამოთვლა 
. მოდით გადავიდეთ მე-5 საფეხურზე.
ორმოცდაათი . მოდით შევამოწმოთ მდგომარეობა 
. გადავიდეთ მე-6 საფეხურზე.
60 . დავაყენოთ t 0 \u003d 0.5 .
70. გამოთვლა
80. მოდით შევადაროთ 
. Ჩვენ გვაქვს 
. დასკვნა: პირობა k = 0
არ არის შესრულებული. დავაყენოთ t0 = 0.25
, ჩვენ ვაგრძელებთ 7, 8 ნაბიჯების გამეორებას.
701 . მოდით გამოვთვალოთ.
801 . მოდით შევადაროთ f (x 1) და f (x 0) . დასკვნა: f(x1)< f (x 0) . გადავიდეთ მე-9 საფეხურზე.
90. გამოთვლა
დასკვნა: ჩვენ გვჯერა k=1 და გადადით მე-3 საფეხურზე.
3 1 . გამოთვლა
4 1 . გამოთვლა 
. მოდით გადავიდეთ მე-5 საფეხურზე.
5 1 . მოდით შევამოწმოთ მდგომარეობა k ≥ M: k = 1< 10 = M . გადავიდეთ მე-6 საფეხურზე.
6 1 . დავაყენოთ t 1 \u003d 0.25.
7 1 . გამოთვლა
8 1 . მოდით შევადაროთ f (x 2) f (x 1) . დასკვნა: f (x 2)< f (х 1). გადავიდეთ მე-9 საფეხურზე.
9 1 . გამოთვლა
დასკვნა: ჩვენ გვჯერა k = 2 და გადადით მე-3 საფეხურზე.
3 2 . გამოთვლა
4 2 . მოდით გამოვთვალოთ. მოდით გადავიდეთ მე-5 საფეხურზე.
5 2 . მოდით შევამოწმოთ მდგომარეობა k ≥ M : k = 2< 10 = М , გადადით მე-6 საფეხურზე.
6 2 . დავაყენოთ t2 =0,25 .
7 2 . გამოთვლა
8 2 . მოდით შევადაროთ f (x 3) და f (x 2) . დასკვნა: f (x 3)< f (х 2) .გადადით მე-9 საფეხურზე.
9 2 . გამოთვლა 
დასკვნა: ჩვენ გვჯერა k = 3 და გადადით მე-3 საფეხურზე.
3 3 . გამოთვლა
4 3 . მოდით გამოვთვალოთ. მოდით გადავიდეთ მე-5 საფეხურზე.
5 3 . მოდით შევამოწმოთ მდგომარეობა k ≥ M : k = 3<10 = М , გადადით მე-6 საფეხურზე.
6 3 . დავაყენოთ t 3 \u003d 0.25.
7 3 . გამოთვლა
8 3 . მოდით შევადაროთ f (x 4) და f (x 3) : f (x 4)< f (х 3) .
9 3 . გამოთვლა 
პირობები შესრულებულია ქ k = 2.3 . Გაანგარიშება
დასრულდა. წერტილი ნაპოვნია
ნახ. 3 მიღებული წერტილი ერთმანეთთან არის დაკავშირებული წერტილოვანი ხაზით.
II. წერტილის ანალიზი x 4 .
ფუნქცია 
არის ორჯერ დიფერენცირებადი, ამიტომ ვამოწმებთ საკმარის პირობებს მინიმუმისთვის წერტილში x 4
. ამისათვის ჩვენ ვაანალიზებთ ჰესიან მატრიცას.
მატრიცა მუდმივია და არის დადებითი განსაზღვრული (ე.ი. . H > 0
), რადგან მისი ორივე კუთხოვანი მცირე და დადებითია. აქედან გამომდინარეობს წერტილი 
არის ლოკალური მინიმალური წერტილისა და მნიშვნელობის ნაპოვნი მიახლოება 
არის მნიშვნელობის ნაპოვნი მიახლოება f(x*)=0
. გაითვალისწინეთ, რომ პირობა H > 0
, ერთდროულად არის ფუნქციის მკაცრი ამობურცულობის პირობა 
. აქედან გამომდინარე, ნაპოვნია გლობალური მინიმალური წერტილის მიახლოებები f(x)
და მისი ყველაზე მცირე მნიშვნელობა R2
. ■
მაგალითი 2
იპოვეთ ფუნქციის ადგილობრივი მინიმუმი
I. წერტილის განსაზღვრა x k, რომელშიც შეწყვეტის ერთ-ერთი კრიტერიუმი მაინც დაკმაყოფილებულია.
1 კომპლექტი .
იპოვეთ ფუნქციის გრადიენტი თვითნებურ წერტილში
2. დააყენე k = 0 .
ოცდაათი . გამოთვლა
40 . გამოთვლა . მოდით გადავიდეთ მე-5 საფეხურზე.
ორმოცდაათი . მოდით შევამოწმოთ მდგომარეობა 
. გადავიდეთ მე-6 საფეხურზე.
6°. შემდეგი წერტილი ნაპოვნია ფორმულით
მიღებული გამონათქვამები ჩავანაცვლოთ კოორდინატებით
იპოვეთ ფუნქციის მინიმუმი f(t0) on t0 უპირობო ექსტრემისთვის აუცილებელი პირობების გამოყენება:
აქედან t0 =0.24
. როგორც 
ნაპოვნი ნაბიჯის მნიშვნელობა უზრუნველყოფს ფუნქციის მინიმუმს f(t0)
on t0
.
განვსაზღვროთ 
70. მოდი ვიპოვოთ
8°. გამოთვლა
დასკვნა: ჩვენ გვჯერა k = 1 და გადადით მე-3 საფეხურზე.
3 1 . გამოთვლა
4 1 . გამოთვლა 
5 1 . მოდით შევამოწმოთ მდგომარეობა k ≥ 1: k = 1< 10 = М.
6 1 . განვსაზღვროთ
7 1 . მოდი ვიპოვოთ 
:
8 1 . გამოთვლა
Ჩვენ გვჯერა k = 2 და გადადით მე-3 საფეხურზე.
3 2 . გამოთვლა
4 2 . გამოთვლა
5 2 . მოდით შევამოწმოთ მდგომარეობა k ≥ M: k = 2< 10 = M .
6 2 . განვსაზღვროთ
7 2 . მოდი ვიპოვოთ 
8 2 . გამოთვლა
Ჩვენ გვჯერა k=3 და გადადით მე-3 საფეხურზე.
3 3 . გამოთვლა
4 3 . მოდით გამოვთვალოთ.
გაანგარიშება დასრულდა. წერტილი ნაპოვნია
II. წერტილის ანალიზი x 3 .
მაგალითში 1.1 (თავი 2 §1) ნაჩვენები იყო, რომ ფუნქცია f(x) არის მკაცრად ამოზნექილი და, შესაბამისად, 3 წერტილებში არის ნაპოვნი გლობალური მინიმალური წერტილის მიახლოება X* .
მაგალითი 3
იპოვეთ ფუნქციის ადგილობრივი მინიმუმი
I. წერტილის განსაზღვრა x jk , რომელშიც შეწყვეტის ერთ-ერთი კრიტერიუმი მაინც დაკმაყოფილებულია.
1 კომპლექტი
იპოვეთ ფუნქციის გრადიენტი თვითნებურ წერტილში 
2. კომპლექტი j = 0.
ოცდაათი . შევამოწმოთ პირობის შესრულება
40 . დავაყენოთ k = 0.
ორმოცდაათი . შევამოწმოთ პირობის შესრულება
60 . გამოთვლა
70. მოდით შევამოწმოთ მდგომარეობა 
80. დავაყენოთ
90. გამოთვლა 
, სად
100 . მოდით შევამოწმოთ მდგომარეობა
დასკვნა: ჩვენ ვივარაუდებთ და მივდივართ მე-9 საფეხურზე.
9 01 . გამოთვლა x 01 ნაბიჯ - ნაბიჯ
1001 . მოდით შევამოწმოთ მდგომარეობა 
110 . მოდით შევამოწმოთ პირობები
Ჩვენ გვჯერა k=1 და გადადით მე-5 საფეხურზე.
5 1 . მოდით შევამოწმოთ მდგომარეობა
6 1 . გამოთვლა
7 1 . მოდით შევამოწმოთ მდგომარეობა
8 1 . დავაყენოთ
9 1 . გამოთვლა
10 1 . მოდით შევამოწმოთ მდგომარეობა 
:
11 1 . მოდით შევამოწმოთ პირობები
Ჩვენ გვჯერა k = 2 , გადადით მე-5 საფეხურზე.
5 2 . მოდით შევამოწმოთ მდგომარეობა. დააყენეთ, გადადით მე-3 საფეხურზე.
3 1 . მოდით შევამოწმოთ მდგომარეობა
4 1 . დავაყენოთ k = 0.
5 2 . მოდით შევამოწმოთ მდგომარეობა
6 2 . გამოთვლა
7 2 . მოდით შევამოწმოთ მდგომარეობა
8 2 . დავაყენოთ
9 2 . გამოთვლა
10 2 . მოდით შევამოწმოთ მდგომარეობა 
11 2 . მოდით შევამოწმოთ პირობები
Ჩვენ გვჯერა k=1 და გადადით მე-5 საფეხურზე.
5 3 . მოდით შევამოწმოთ მდგომარეობა
6 3 . გამოთვლა
7 3 . მოდით შევამოწმოთ პირობები
8 3 . დავაყენოთ
9 3 . გამოთვლა
10 3 . მოდით შევამოწმოთ მდგომარეობა 
11 3 . მოდით შევამოწმოთ პირობები
დავაყენოთ k = 2 და გადადით მე-5 საფეხურზე.
5 4 . მოდით შევამოწმოთ მდგომარეობა 
Ჩვენ გვჯერა j \u003d 2, x 20 \u003d x 12 და გადადით მე-3 საფეხურზე.
3 2 . მოდით შევამოწმოთ მდგომარეობა
4 2 . დავაყენოთ k=0 .
5 4 . მოდით შევამოწმოთ მდგომარეობა
6 4 . გამოთვლა
7 4 . მოდით შევამოწმოთ მდგომარეობა
8 4 . დავაყენოთ
9 4 . გამოთვლა
10 4 . მოდით შევამოწმოთ მდგომარეობა, გადადით მე-11 საფეხურზე.
11 4 . მოდით შევამოწმოთ პირობები
პირობები დაკმაყოფილებულია ნომრებით ზედიზედ ორ ციკლში j = 2 და j -1= 1 . გაანგარიშება დასრულებულია, წერტილი ნაპოვნია
ნახ. 6, მიღებული წერტილები დაკავშირებულია წერტილოვანი ხაზით.
კოორდინატთა დაღმართის მეთოდით, ჩვენ დავეშვით გატეხილი ხაზის გასწვრივ, რომელიც შედგება კოორდინატთა ღერძების პარალელურად ხაზოვანი სეგმენტებისგან.
II. წერტილის ანალიზი x21.
მაგალითმა 1.1 აჩვენა, რომ ფუნქცია f(x)
არის მკაცრად ამოზნექილი, აქვს ერთი მინიმალური და აქედან გამომდინარე წერტილი 
არის გლობალური მინიმალური წერტილის ნაპოვნი მიახლოება.
ყველა ზემოთ ჩამოთვლილ გრადიენტულ მეთოდში, წერტილების თანმიმდევრობა ( x k ) კონვერგირდება ფუნქციის სტაციონარულ წერტილში f(x) ამ ფუნქციის თვისებების შესახებ საკმაოდ ზოგადი წინადადებების ქვეშ. კერძოდ, თეორემა მართალია:
თეორემა. თუ ფუნქცია f (x) შემოსაზღვრულია ქვემოდან, მისი გრადიენტი აკმაყოფილებს ლიპშიცის პირობას () და მნიშვნელობის არჩევანს. t n წარმოებულია ზემოთ აღწერილი ერთ-ერთი მეთოდით, მაშინ როგორიც არ უნდა იყოს საწყისი წერტილი x 0 :
ზე.
სქემის პრაქტიკულ განხორციელებაში
k=1, 2, …n.
გამეორებები ჩერდება თუ ყველასთვის i , i = 1, 2, ..., n , ტიპის პირობები
,
სად არის გარკვეული მოცემული რიცხვი, რომელიც ახასიათებს მინიმალურის პოვნის სიზუსტეს.
თეორემის პირობებში, გრადიენტური მეთოდი უზრუნველყოფს ფუნქციაში კონვერგენციას ან უმცირეს ქვედა ზღვარს (თუ ფუნქცია f(x) არ აქვს მინიმუმი; ბრინჯი. 7), ან ფუნქციის მნიშვნელობას რომელიმე სტაციონარულ წერტილში, რომელიც არის მიმდევრობის ზღვარი (x-მდე). მარტივია მაგალითების მოფიქრება, როცა უნაგირს რეალიზდება ამ ეტაპზე და არა მინიმუმი. პრაქტიკაში, გრადიენტული დაღმართის მეთოდები დამაჯერებლად გვერდის ავლით უნაგირის წერტილებს და პოულობენ ობიექტური ფუნქციის მინიმუმებს (ზოგად შემთხვევაში, ლოკალურ მინიმუმებს).
დასკვნა
ზემოთ განხილული იყო შეუზღუდავი ოპტიმიზაციის გრადიენტული მეთოდების მაგალითები. შესრულებული სამუშაოს შედეგად შეიძლება გამოვიდეს შემდეგი დასკვნები:
1. შეზღუდვების არსებობისას ექსტრემის პოვნის მეტ-ნაკლებად რთული პრობლემები განსაკუთრებულ მიდგომებსა და მეთოდებს მოითხოვს.
2. შეზღუდვებით პრობლემების გადაჭრის მრავალი ალგორითმი მოიცავს მინიმიზაციას შეზღუდვების გარეშე, როგორც გარკვეულ ეტაპს.
3. დაღმართის სხვადასხვა მეთოდი ერთმანეთისგან განსხვავდება დაშვების მიმართულების არჩევით და ამ მიმართულებით ნაბიჯის სიგრძით.
4. ჯერჯერობით არ არსებობს ისეთი თეორია, რომელიც მხედველობაში მიიღებდა ფუნქციების რაიმე მახასიათებელს, რომელიც აღწერს პრობლემის ფორმულირებას. უპირატესობა უნდა მიენიჭოს იმ მეთოდებს, რომლებიც უფრო ადვილად მართულია პრობლემის გადაჭრის პროცესში.
გამოყენებითი ოპტიმიზაციის რეალური პრობლემები ძალიან რთულია. ოპტიმიზაციის თანამედროვე მეთოდები ყოველთვის არ უმკლავდება რეალური პრობლემების გადაჭრას ადამიანის დახმარების გარეშე.
ბიბლიოგრაფია
1. კოსორუკოვი ო.ა. ოპერაციების კვლევა: სახელმძღვანელო. 2003 წ
2. პანტლეევი ა.ვ. ოპტიმიზაციის მეთოდები მაგალითებში და ამოცანებში: სახელმძღვანელო. სარგებელი. 2005 წ
3. შიშკინი ე.ვ. ოპერაციების კვლევა: სახელმძღვანელო. 2006 წ
4. აკულიჩ ი.ლ. მათემატიკური პროგრამირება მაგალითებში და ამოცანებში. 1986წ
5. ვენცელი ე.ს. ოპერაციების კვლევა. 1980 წ
6. Venttsel E.S., Ovcharov L.A. ალბათობის თეორია და მისი საინჟინრო აპლიკაციები. 1988 წ
©2015-2019 საიტი
ყველა უფლება ეკუთვნის მათ ავტორებს. ეს საიტი არ აცხადებს ავტორობას, მაგრამ უზრუნველყოფს უფასო გამოყენებას.
გვერდის შექმნის თარიღი: 2017-07-02
ნახ.3. ყველაზე ციცაბო დაღმართის მეთოდის გეომეტრიული ინტერპრეტაცია. ყოველ საფეხურზე ის არჩეულია ისე, რომ შემდეგი გამეორება იყოს ფუნქციის მინიმალური წერტილი L სხივზე.
გრადიენტური მეთოდის ეს ვარიანტი ეფუძნება საფეხურის არჩევას შემდეგი მოსაზრებებიდან. იმ წერტილიდან ჩვენ ვიძაბებით ანტიგრადიენტის მიმართულებით, სანამ არ მივაღწევთ f ფუნქციის მინიმუმს ამ მიმართულებით, ანუ სხივზე:
სხვა სიტყვებით რომ ვთქვათ, არჩეულია ისე, რომ შემდეგი გამეორება იყოს f ფუნქციის მინიმალური წერტილი L სხივზე (იხ. სურ. 3). გრადიენტური მეთოდის ამ ვარიანტს უწოდებენ ყველაზე ციცაბო დაღმართის მეთოდს. სხვათა შორის, გაითვალისწინეთ, რომ ამ მეთოდში მიმდებარე საფეხურების მიმართულებები ორთოგონალურია.
ყველაზე ციცაბო დაღმართის მეთოდი მოითხოვს ერთგანზომილებიანი ოპტიმიზაციის პრობლემის გადაჭრას ყოველ საფეხურზე. პრაქტიკა გვიჩვენებს, რომ ეს მეთოდი ხშირად მოითხოვს ნაკლებ ოპერაციებს, ვიდრე გრადიენტური მეთოდი მუდმივი ნაბიჯით.
თუმცა, ზოგად სიტუაციაში, ყველაზე ციცაბო დაღმართის მეთოდის დაახლოების თეორიული სიჩქარე არ არის უფრო მაღალი ვიდრე გრადიენტური მეთოდის კონვერგენციის სიჩქარე მუდმივი (ოპტიმალური) საფეხურით.
რიცხვითი მაგალითები
მუდმივი საფეხურის გრადიენტური დაღმართის მეთოდი
გრადიენტული დაღმართის მეთოდის კონვერგენციის შესასწავლად მუდმივი ნაბიჯით, არჩეული იყო ფუნქცია:
მიღებული შედეგებიდან შეგვიძლია დავასკვნათ, რომ მეთოდი შორდება, თუ სიხშირე ძალიან დიდია, და ნელა კონვერგირდება, თუ სიხშირე ძალიან მცირეა, ხოლო სიზუსტე უარესია. აუცილებელია აირჩიოს საფეხური, რომელიც ყველაზე დიდია იმ საფეხურთაგან, რომელთათვისაც მეთოდი თანხვედრაშია.
გრადიენტური მეთოდი საფეხურების გაყოფით
გრადიენტული დაღმართის მეთოდის კონვერგენციის შესასწავლად საფეხურების გაყოფით (2), აირჩიეს შემდეგი ფუნქცია:
საწყისი მიახლოება არის წერტილი (10,10).
გამოყენებული შეჩერების კრიტერიუმი:
ექსპერიმენტის შედეგები ნაჩვენებია ცხრილში:
|
მნიშვნელობა პარამეტრი |
პარამეტრის მნიშვნელობა |
პარამეტრის მნიშვნელობა |
მიღწეული სიზუსტე |
გამეორებების რაოდენობა |
მიღებული შედეგებიდან შეგვიძლია დავასკვნათ, რომ პარამეტრების ოპტიმალური არჩევანია: , თუმცა მეთოდი არ არის ძალიან მგრძნობიარე პარამეტრების არჩევის მიმართ.
ყველაზე ციცაბო დაღმართის მეთოდი
ყველაზე ციცაბო დაღმართის მეთოდის კონვერგენციის შესასწავლად აირჩიეს შემდეგი ფუნქცია:
საწყისი მიახლოება არის წერტილი (10,10). გამოყენებული შეჩერების კრიტერიუმი:
ოქროს მონაკვეთის მეთოდი გამოიყენებოდა ერთგანზომილებიანი ოპტიმიზაციის ამოცანების გადასაჭრელად.
მეთოდმა მიიღო 6e-8 სიზუსტე 9 გამეორებაში.
აქედან შეგვიძლია დავასკვნათ, რომ ყველაზე ციცაბო დაღმართის მეთოდი უფრო სწრაფად იყრის თავს, ვიდრე საფეხურების გაყოფის გრადიენტური მეთოდი და მუდმივი საფეხურის გრადიენტური დაღმართის მეთოდი.
ყველაზე ციცაბო დაღმართის მეთოდის მინუსი არის ერთგანზომილებიანი ოპტიმიზაციის პრობლემის გადაჭრის აუცილებლობა.
გრადიენტური წარმოშობის მეთოდების დაპროგრამებისას, ფრთხილად უნდა იყოთ პარამეტრების არჩევისას, კერძოდ
- · გრადიენტური დაღმართის მეთოდი მუდმივი საფეხურით: საფეხური არჩეული უნდა იყოს 0,01-ზე ნაკლები, წინააღმდეგ შემთხვევაში მეთოდი განსხვავდება (მეთოდი შეიძლება განსხვავდებოდეს ასეთ საფეხურზეც, შესასწავლი ფუნქციის მიხედვით).
- · გრადიენტური მეთოდი ნაბიჯების გაყოფით არ არის ძალიან მგრძნობიარე პარამეტრების არჩევის მიმართ. არჩევანის ერთ-ერთი ვარიანტი:
- · ყველაზე ციცაბო დაღმართის მეთოდი: როგორც ერთგანზომილებიანი ოპტიმიზაციის მეთოდი, შეიძლება გამოყენებულ იქნას ოქროს მონაკვეთის მეთოდი (როდესაც ეს შესაძლებელია).
კონიუგირებული გრადიენტის მეთოდი არის მრავალგანზომილებიანი სივრცეში შეუზღუდავი ოპტიმიზაციის განმეორებითი მეთოდი. მეთოდის მთავარი უპირატესობა ის არის, რომ ის წყვეტს კვადრატული ოპტიმიზაციის პრობლემას სასრული რაოდენობის ნაბიჯებით. აქედან გამომდინარე, პირველად აღწერილია კვადრატული ფუნქციის ოპტიმიზაციის კონიუგირებული გრადიენტის მეთოდი, მიღებულია განმეორებითი ფორმულები და მოცემულია კონვერგენციის სიჩქარის შეფასებები. ამის შემდეგ ნაჩვენებია, თუ როგორ განზოგადებულია კონიუგირებული მეთოდი თვითნებური ფუნქციის ოპტიმიზაციისთვის, განიხილება მეთოდის სხვადასხვა ვერსია და განიხილება კონვერგენცია.
განცხადება ოპტიმიზაციის პრობლემის შესახებ
მოდით იყოს მოცემული სიმრავლე და განისაზღვროს ობიექტური ფუნქცია (ობიექტური ფუნქცია). ოპტიმიზაციის პრობლემა არის ობიექტური ფუნქციის ზუსტი ზედა ან ქვედა ზღვრის პოვნა ნაკრებზე. აღინიშნება წერტილების სიმრავლე, რომლებზეც მიღწეულია ობიექტური ფუნქციის ქვედა ზღვარი.
თუ, მაშინ ოპტიმიზაციის პრობლემას ეწოდება შეუზღუდავი. თუ, მაშინ ოპტიმიზაციის პრობლემას უწოდებენ შეზღუდულს.
კონიუგირებული გრადიენტის მეთოდი კვადრატული ფუნქციისთვის
მეთოდის განცხადება
განვიხილოთ ოპტიმიზაციის შემდეგი პრობლემა:
აქ არის სიმეტრიული დადებით-განსაზღვრული ზომის მატრიცა. ოპტიმიზაციის ასეთ პრობლემას კვადრატული ეწოდება. გაითვალისწინეთ, რომ. ფუნქციის უკიდურესი მდგომარეობა სისტემის ექვივალენტურია. ფუნქცია აღწევს ქვედა ზღვარს განტოლებით განსაზღვრულ ერთ წერტილში. ამრიგად, ოპტიმიზაციის ეს პრობლემა მცირდება წრფივი განტოლებათა სისტემის ამოხსნით. კონიუგირებული გრადიენტის მეთოდის იდეა ასეთია: დაე, იყოს c-ის საფუძველი. შემდეგ, ნებისმიერი წერტილისთვის, ვექტორი გაფართოვდება საფუძვლის თვალსაზრისით. ამრიგად, ის შეიძლება წარმოდგენილი იყოს როგორც
ყოველი შემდეგი მიახლოება გამოითვლება ფორმულით:
განმარტება. ორი ვექტორი და ეწოდება კონიუგატი B სიმეტრიული მატრიცის მიმართ თუ
აღვწეროთ ბაზის აგების მეთოდი კონიუგატური გრადიენტის მეთოდში.საწყისი მიახლოების სახით ვირჩევთ თვითნებურ ვექტორს. ყოველი გამეორებისას არჩეულია შემდეგი წესები:
ძირითადი ვექტორები გამოითვლება ფორმულებით:
კოეფიციენტები არჩეულია ისე, რომ ვექტორები და არიან კონიუგატები A-სთან მიმართებაში.
თუ აღვნიშნავთ, მაშინ რამდენიმე გამარტივების შემდეგ ვიღებთ საბოლოო ფორმულებს, რომლებიც გამოიყენება კონიუგირებული გრადიენტის მეთოდის პრაქტიკაში გამოყენებისას:
კონიუგატური გრადიენტის მეთოდისთვის მართებულია შემდეგი თეორემა: თეორემა Let, სადაც არის ზომის სიმეტრიული დადებითი განსაზღვრული მატრიცა. შემდეგ კონიუგირებული გრადიენტის მეთოდი იყრის თავს არაუმეტეს ნაბიჯებით და მოქმედებს შემდეგი მიმართებები:
მეთოდის კონვერგენცია
თუ ყველა გამოთვლა ზუსტია, ხოლო საწყისი მონაცემები ზუსტი, მაშინ მეთოდი გადადის სისტემის ამოხსნასთან არაუმეტეს გამეორებით, სადაც არის სისტემის განზომილება. უფრო დახვეწილი ანალიზი აჩვენებს, რომ გამეორებების რაოდენობა არ აღემატება, სადაც არის A მატრიცის სხვადასხვა საკუთრივ მნიშვნელობების რაოდენობა. კონვერგენციის სიჩქარის შესაფასებლად სწორია შემდეგი (საკმაოდ უხეში) შეფასება:
ის საშუალებას იძლევა შეფასდეს კონვერგენციის სიჩქარე, თუ ცნობილია მატრიცის მაქსიმალური და მინიმალური საკუთარი მნიშვნელობების შეფასებები. პრაქტიკაში ყველაზე ხშირად გამოიყენება შემდეგი შეჩერების კრიტერიუმი:
გამოთვლითი სირთულე
ოპერაციები ტარდება მეთოდის ყოველი გამეორებისას. ოპერაციების ეს რაოდენობა საჭიროა პროდუქტის გამოსათვლელად - ეს არის ყველაზე შრომატევადი პროცედურა ყოველი გამეორებისას. დანარჩენი გამოთვლები მოითხოვს O(n) ოპერაციებს. მეთოდის საერთო გამოთვლითი სირთულე არ აღემატება - რადგან გამეორებების რაოდენობა მაქსიმუმ n-ია.
რიცხვითი მაგალითი
სისტემის ამოსახსნელად ვიყენებთ კონიუგატური გრადიენტის მეთოდს, სადაც C კონიუგატური გრადიენტის მეთოდის გამოყენებით, ამ სისტემის ამონახსნი მიიღება ორ გამეორებაში. მატრიცის საკუთრივ მნიშვნელობები - 5, 5, -5 - ორი მათგანი განსხვავებულია, ამიტომ, თეორიული შეფასებით, გამეორებების რაოდენობა არ შეიძლება აღემატებოდეს ორს.
კონიუგირებული გრადიენტის მეთოდი არის ერთ-ერთი ყველაზე ეფექტური მეთოდი SLAE-ს გადაჭრისთვის დადებითი განსაზღვრული მატრიცით. მეთოდი უზრუნველყოფს კონვერგენციას სასრული რაოდენობის საფეხურებში და საჭირო სიზუსტის მიღწევა შესაძლებელია ბევრად ადრე. მთავარი პრობლემა ის არის, რომ შეცდომების დაგროვების გამო შეიძლება დაირღვეს ფუძის ქარის ორთოგონალურობა, რაც აუარესებს კონვერგენციას.
კონიუგატური გრადიენტის მეთოდი ზოგადად
ახლა განვიხილოთ კონიუგირებული გრადიენტის მეთოდის მოდიფიკაცია იმ შემთხვევისთვის, როდესაც მინიმალირებული ფუნქცია არ არის კვადრატული: ჩვენ მოვაგვარებთ პრობლემას:
მუდმივად დიფერენცირებადი ფუნქცია. ამ პრობლემის გადასაჭრელად კონიუგირებული გრადიენტის მეთოდის შესაცვლელად, საჭიროა მივიღოთ ფორმულები, რომლებიც არ შეიცავს მატრიცას A:
შეიძლება გამოითვალოს სამი ფორმულიდან ერთის გამოყენებით:
1. - ფლეტჩერ-რივზის მეთოდი
- 2. - Polak-Ribi`ere მეთოდი
თუ ფუნქცია არის კვადრატული და მკაცრად ამოზნექილი, მაშინ სამივე ფორმულა იძლევა ერთსა და იმავე შედეგს. თუ ეს არის თვითნებური ფუნქცია, მაშინ თითოეული ფორმულა შეესაბამება კონიუგირებული გრადიენტის მეთოდის საკუთარ მოდიფიკაციას. მესამე ფორმულა იშვიათად გამოიყენება, რადგან ის მოითხოვს ფუნქციას და ფუნქციის ჰესიანულის გამოთვლას მეთოდის ყოველ საფეხურზე.
თუ ფუნქცია არ არის კვადრატული, კონიუგირებული გრადიენტის მეთოდი შეიძლება არ გადაიზარდოს საფეხურების სასრულ რაოდენობაში. გარდა ამისა, ზუსტი გაანგარიშება თითოეულ ეტაპზე შესაძლებელია მხოლოდ იშვიათ შემთხვევებში. ამრიგად, შეცდომების დაგროვება იწვევს იმ ფაქტს, რომ ვექტორები აღარ მიუთითებენ ფუნქციის კლების მიმართულებაზე. შემდეგ რაღაც ეტაპზე ისინი ვარაუდობენ. ყველა რიცხვის ნაკრები, რომლებისთვისაც იგი მიღებულია, აღინიშნა როგორც. ციფრებს ეწოდება მეთოდის განახლების დრო. პრაქტიკაში, ადამიანი ხშირად ირჩევს სად არის სივრცის განზომილება.
მეთოდის კონვერგენცია
ფლეტჩერ-რივზის მეთოდისთვის არსებობს კონვერგენციის თეორემა, რომელიც აწესებს არც თუ ისე მკაცრ პირობებს მინიმიზაციის ფუნქციაზე: თეორემა. მოდით დაკმაყოფილდეს შემდეგი პირობები:
კომპლექტი შეზღუდულია
წარმოებული აკმაყოფილებს Lipschitz-ის მდგომარეობას მუდმივით ზოგიერთ სამეზობლოში
კომპლექტი M: .
კონვერგენცია დადასტურებულია პოლაკ-რაიბერის მეთოდისთვის იმ ვარაუდით, რომ ეს არის მკაცრად ამოზნექილი ფუნქცია. ზოგად შემთხვევაში შეუძლებელია პოლაკ-რეიბერის მეთოდის კონვერგენციის დადასტურება. პირიქით, მართალია შემდეგი თეორემა: თეორემა. დავუშვათ, რომ Polak-Reiber მეთოდით, მნიშვნელობები თითოეულ საფეხურზე ზუსტად გამოითვლება. შემდეგ არის ფუნქცია და საწყისი მიახლოება, ისეთი, რომ.
თუმცა პოლაქ-რეიბერის მეთოდი პრაქტიკაში უკეთ მუშაობს. შეჩერების ყველაზე გავრცელებული კრიტერიუმები პრაქტიკაში: გრადიენტის ნორმა ხდება გარკვეულ ზღურბლზე ნაკლები ფუნქციის მნიშვნელობა m თანმიმდევრული გამეორებების დროს თითქმის არ შეცვლილა.
გამოთვლითი სირთულე
Polack-Reiber ან Fletcher-Reeves მეთოდების ყოველი გამეორებისას ფუნქცია და მისი გრადიენტი გამოითვლება ერთხელ და წყდება ერთგანზომილებიანი ოპტიმიზაციის პრობლემა. ამრიგად, კონიუგირებული გრადიენტის მეთოდის ერთი საფეხურის სირთულე ისეთივე რიგია, როგორც ყველაზე ციცაბო დაღმართის მეთოდის საფეხურის სირთულე. პრაქტიკაში, კონიუგირებული გრადიენტის მეთოდი აჩვენებს საუკეთესო კონვერგენციის მაჩვენებელს.
ფუნქციის მინიმუმს მოვიძიებთ კონიუგირებული გრადიენტების მეთოდით
ამ ფუნქციის მინიმუმი უდრის 1-ს და მიიღწევა წერტილში (5, 4). ამ ფუნქციის მაგალითზე შევადაროთ პოლაქ-რაიბერისა და ფლეტჩერ-რივზის მეთოდები. ორივე მეთოდში გამეორებები ჩერდება, როდესაც გრადიენტის ნორმის კვადრატი მცირდება მიმდინარე საფეხურზე. შერჩევისთვის გამოიყენება ოქროს მონაკვეთის მეთოდი.
|
ფლეტჩერ-რივზის მეთოდი |
პოლაკ-რაიბერის მეთოდი |
|||||
|
გამეორებების რაოდენობა |
იპოვეს გამოსავალი |
ფუნქციის ღირებულება |
გამეორებების რაოდენობა |
იპოვეს გამოსავალი |
ფუნქციის ღირებულება |
|
|
(5.01382198,3.9697932) |
(5.03942877,4.00003512) |
|||||
|
(5.01056482,3.99018026) |
(4.9915894,3.99999044) |
|||||
|
(4.9979991,4.00186173) |
(5.00336181,4.0000018) |
|||||
|
(4.99898277,4.00094645) |
(4.99846808,3.99999918) |
|||||
|
(4.99974658,4.0002358) |
(4.99955034,3.99999976) |
დანერგილია კონიუგირებული გრადიენტის მეთოდის ორი ვერსია: კვადრატული ფუნქციის მინიმიზაციისთვის და თვითნებური ფუნქციის მინიმიზაციისთვის. პირველ შემთხვევაში, მეთოდი ხორციელდება ვექტორული ფუნქციით
გრადიენტური დაღმართის მეთოდები საკმაოდ ძლიერი ინსტრუმენტია ოპტიმიზაციის პრობლემების გადასაჭრელად. მეთოდების მთავარი მინუსი არის გამოყენების შეზღუდული არეალი. კონიუგირებული გრადიენტის მეთოდი იყენებს ინფორმაციას მხოლოდ მონაკვეთის წრფივი ნაწილის შესახებ, როგორც გრადიენტული დაღმართის მეთოდებში. ამავდროულად, კონიუგირებული გრადიენტის მეთოდი საშუალებას იძლევა გადაჭრას კვადრატული ამოცანები სასრული რაოდენობის ნაბიჯებით. ბევრ სხვა პრობლემასთან დაკავშირებით, კონიუგირებული გრადიენტის მეთოდი ასევე აღემატება გრადიენტული დაღმართის მეთოდს. გრადიენტური მეთოდის კონვერგენცია არსებითად დამოკიდებულია იმაზე, თუ რამდენად ზუსტად არის მოგვარებული ერთგანზომილებიანი ოპტიმიზაციის პრობლემა. შესაძლო მეთოდების მარყუჟები ფიქსირდება განახლებებით. თუმცა, თუ მეთოდი მიაღწევს ფუნქციის ლოკალურ მინიმუმს, ის დიდი ალბათობით ვერ შეძლებს მისგან თავის დაღწევას.
Ანოტაცია: ამ ლექციაში ფართოდ არის გაშუქებული მრავალპარამეტრული ოპტიმიზაციის ისეთი მეთოდები, როგორიცაა ყველაზე ციცაბო დაღმართის მეთოდი და დევიდონ-ფლეტჩერ-პაუელის მეთოდი. გარდა ამისა, ტარდება ზემოაღნიშნული მეთოდების შედარებითი ანალიზი, რათა დადგინდეს ყველაზე ეფექტური, გამოიკვეთოს მათი დადებითი და უარყოფითი მხარეები; და ასევე განიხილავს მრავალვარიანტული ოპტიმიზაციის პრობლემებს, როგორიცაა ხევების მეთოდი და მრავალექსტრემალური მეთოდი.
1. ყველაზე ციცაბო დაღმართის მეთოდი
ამ მეთოდის არსი ის არის, რომ ზემოთ აღნიშნულის დახმარებით კოორდინატული წარმოშობის მეთოდიძიება ხორციელდება მოცემული წერტილიდან ერთ-ერთი ღერძის პარალელურად, ამ მიმართულებით მინიმალურ წერტილამდე. შემდეგ ძიება ხორციელდება სხვა ღერძის პარალელურად და ა.შ. მიმართულებები, რა თქმა უნდა, დაფიქსირებულია. მიზანშეწონილია ამ მეთოდის მოდიფიცირების მცდელობა ისე, რომ ყოველ ეტაპზე მინიმალური წერტილის ძიება განხორციელდეს "საუკეთესო" მიმართულებით. უცნობია რომელი მიმართულებაა „საუკეთესო“, მაგრამ ცნობილია, რომ გრადიენტური მიმართულებაარის ფუნქციის ყველაზე სწრაფი ზრდის მიმართულება. ამიტომ, საპირისპირო მიმართულება არის ფუნქციის ყველაზე სწრაფი შემცირების მიმართულება. ეს ქონება შეიძლება გამართლდეს შემდეგნაირად.
დავუშვათ, რომ ჩვენ გადავდივართ x წერტილიდან შემდეგ წერტილში x + hd , სადაც d არის გარკვეული მიმართულება და h არის გარკვეული სიგრძის ნაბიჯი. ამიტომ მოძრაობა ხდება წერტილიდან (x 1, x 2, ..., x n) წერტილამდე (x 1 + zx 1, x 2 + zx 2, ..., x n + zx n), სად
ფუნქციის მნიშვნელობების ცვლილება განისაზღვრება ურთიერთობებით
| (1.3) |
პირველი რიგის zx i-მდე, ხოლო ნაწილობრივი წარმოებულები გამოითვლება x წერტილში. როგორ უნდა ავირჩიოთ d i მიმართულებები, რომლებიც აკმაყოფილებენ (1.2) განტოლებას, რათა მივიღოთ df ფუნქციის უდიდესი ცვლილება? სწორედ აქ ჩნდება შეზღუდვით მაქსიმიზაციის პრობლემა. ვიყენებთ ლაგრანჟის მამრავლების მეთოდს, რომლის დახმარებითაც განვსაზღვრავთ ფუნქციას
df-ის მნიშვნელობა, რომელიც აკმაყოფილებს შეზღუდვას (1.2) აღწევს მაქსიმუმს, როდესაც ფუნქცია
მაქსიმუმს აღწევს. მისი წარმოებული
აქედან გამომდინარე,
 |
(1.6) |
მაშინ di ~ df/dx i და მიმართულება d პარალელურია V/(x) მიმართულების x წერტილში.
ამრიგად, ყველაზე დიდი ადგილობრივი ზრდაფუნქცია მოცემული მცირე ნაბიჯისთვის h ხდება მაშინ, როდესაც d არის მიმართულება Vf(x) ან g(x). ამიტომ, ყველაზე ციცაბო დაღმართის მიმართულება არის მიმართულება
უფრო მარტივი ფორმით, განტოლება (1.3) შეიძლება ჩაიწეროს შემდეგნაირად:
სად არის კუთხე Vf(x) და dx ვექტორებს შორის. dx-ის მოცემული მნიშვნელობისთვის, ჩვენ ვამცირებთ df-ს არჩევით, ისე რომ dx-ის მიმართულება იგივეა, რაც -Vf(x)-ის მიმართულება.
კომენტარი. გრადიენტური მიმართულებამუდმივი დონის ხაზის ნებისმიერ წერტილზე პერპენდიკულარული, რადგან ფუნქცია მუდმივია ამ ხაზის გასწვრივ. ამრიგად, თუ (d 1 , d 2 , ..., d n) არის პატარა ნაბიჯი დონის ხაზის გასწვრივ, მაშინ
Და, შესაბამისად
 |
(1.8) |
მაგალითი 6.8.3-1. იპოვეთ Q(x, y) ფუნქციის მინიმუმი GDS მეთოდით.
მოდით Q(x,y) = x 2 +2y 2; x 0 = 2; y 0 = 1.
მოდით შევამოწმოთ საკმარისი პირობები მინიმუმის არსებობისთვის:
მოდით გავაკეთოთ ერთი გამეორება ალგორითმის მიხედვით.
1. Q(x0,y0) = 6.
2.
როდესაც x \u003d x 0 და y \u003d y 0, 
3. ნაბიჯი l k \u003d l 0 \u003d 0.5
ასე რომ 4< 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.
მეთოდის არსი შემდეგია. შერჩეული წერტილიდან (x 0 ,y 0) დაღმართი ტარდება ანტიგრადიენტის მიმართულებით სხივის გასწვრივ ობიექტური ფუნქციის Q(x, y) მინიმალური მნიშვნელობის მიღწევამდე (სურ. 6.8.4-). 1). აღმოჩენილ წერტილში სხივი ეხება დონის ხაზს. შემდეგ ამ წერტილიდან დაღმართი ტარდება ანტიგრადიენტის (დონის ხაზის პერპენდიკულარული) მიმართულებით, სანამ შესაბამისი სხივი არ შეეხება მასში გამავალ დონის ხაზს ახალ წერტილში და ა.შ.
ობიექტური ფუნქცია Q(x, y) გამოვხატოთ l საფეხურის მიხედვით. ამავდროულად, ჩვენ წარმოვადგენთ ობიექტურ ფუნქციას გარკვეულ საფეხურზე, როგორც ერთი ცვლადის ფუნქცია, ე.ი. ნაბიჯის ზომა
ნაბიჯის ზომა თითოეულ გამეორებაზე განისაზღვრება მინიმალური პირობით:
Min((l)) l k = l*(x k, y k), l >0.
ამრიგად, ყოველი გამეორებისას l k საფეხურის არჩევა გულისხმობს ერთგანზომილებიანი ოპტიმიზაციის პრობლემის გადაწყვეტას. ამ პრობლემის მოგვარების მეთოდის მიხედვით, არსებობს:
· ანალიტიკური მეთოდი (NSA);
· რიცხვითი მეთოდი (NCh).
NSA მეთოდში ნაბიჯის მნიშვნელობა მიიღება მდგომარეობიდან, ხოლო NSS მეთოდში მნიშვნელობა l k გვხვდება მოცემული სიზუსტით სეგმენტზე ერთგანზომილებიანი ოპტიმიზაციის მეთოდის გამოყენებით.
მაგალითი 6.8.4-1. იპოვეთ Q(x,y)=x 2 + 2y 2 ფუნქციის მინიმუმი e=0.1 სიზუსტით, საწყის პირობებში: x 0 =2; y 0 =1.
მოდით გავაკეთოთ ერთი გამეორება მეთოდით NSA.
=(x-2lx) 2 +2 (y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 .
პირობიდან ¢(l)=0 ვპოულობთ მნიშვნელობას l*: 
შედეგად მიღებული ფუნქცია l=l(x,y) გაძლევთ საშუალებას იპოვოთ l-ის მნიშვნელობა. x=2 და y=1 გვაქვს l=0.3333.
გამოთვალეთ შემდეგი წერტილის კოორდინატების მნიშვნელობები:
შევამოწმოთ განმეორების შეწყვეტის კრიტერიუმის შესრულება k=1-ისთვის:
ვინაიდან |2*0.6666|>0.1 და |-0.3333*4|>0.1 , გამეორების პროცესის შეწყვეტის პირობები არ არის დაცული, ე.ი. მინიმალური არ მოიძებნა. ამიტომ, თქვენ უნდა გამოთვალოთ l-ის ახალი მნიშვნელობა x=x 1-ზე და y=y 1-ზე და მიიღოთ შემდეგი დაღმართის წერტილის კოორდინატები. გამოთვლები გრძელდება მანამ, სანამ დაღმართის საბოლოო პირობები არ დაკმაყოფილდება.
განსხვავება რიცხვითი NN მეთოდსა და ანალიტიკურს შორის არის ის, რომ l-ის მნიშვნელობის ძიება ყოველ გამეორებაზე ხორციელდება ერთგანზომილებიანი ოპტიმიზაციის ერთ-ერთი რიცხვითი მეთოდით (მაგალითად, დიქოტომიის მეთოდით ან ოქროს მონაკვეთის მეთოდით). ამ შემთხვევაში, l-ის დასაშვები მნიშვნელობების დიაპაზონი ემსახურება გაურკვევლობის ინტერვალს.
