Курсовая работа: Минимизация функций нескольких переменных. Метод спуска
Изменение шага осуществляется по схеме
если ; если
Вычисление градиента происходит по методу с парными пробами, это улучшает поиск за счёт более точного вычисления градиента.
Метод наискорейшего спуска по сравнению с обычным градиентным методом дает некоторое ускорение , метод хорошо "работает" при минимизации гладких функций и если начальное приближение выбрано достаточно далеко от оптимума. Если же очередная точка окажется в окрестности оптимума, то уменьшение целевой функции будет очень медленным. Это происходит из-за того, что для получения оптимума с высокой точностью необходимо выполнить большое число мелких шагов.
Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях.
В связи с этим в программе был реализован более точный метод градиентного спуска.
В качестве условия окончания поиска задаётся требуемая малость модуля градиента функции, т.е. должно выполнятся условие
(В области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).
Так же в программе можно задавать номер итерации выхода из цикла,
Другими словами при достижении какого количества точек прерывать цикл, если он не прервется сам раньше.
Исследование функции
U=1*x1^3+2*x2^2-3*x1-4*x2
(изменением шага).
h=0,1; x1 =-0,5; x2=-1 ; x1нач=-2, x1кон=2, x2нач=-2, x2кон=2
№ | x1 | x2 | R |
0 | -0,5 | -1 | 7,375 |
1 | -0,2750 | -0,1999 | 1,6842 |
2 | 0,0023 | 0,2800 | -0,9701 |
3 | 0,3023 | 0,5680 | -2,5059 |
4 | 0,5749 | 0,7408 | -3,4002 |
5 | 0,7757 | 0,8445 | -3,8120 |
6 | 0,8952 | 0,9067 | -3,9508 |
7 | 0,9548 | 0,9440 | -3,9877 |
8 | 0,9813 | 0,9664 | -3,9967 |
9 | 0,9924 | 0,9798 | -3,9990 |
10 | 0,9969 | 0,9879 | -3,9997 |
11 | 0,9988 | 0,9927 | -3,9999 |
12 | 0,9995 | 0,9956 | -4,0000 |
13 | 0,9998 | 0,9974 | -4,0000 |
14 | 1,0000 | 0,9984 | -4,0000 |
h=0,2; x1 =-0,5; x2=-1 ; x1нач=-2, x1кон=2, x2нач=-2, x2кон=2
№ | x1 | x2 | R |
0 | -0,5 | -1 | 7,375 |
1 | 0,0500 | 0,6000 | -1,5301 |
2 | 0,5485 | 0,9200 | -3,4676 |
3 | 0,9680 | 0,9840 | -3,9964 |
4 | 1,0058 | 0,9968 | -3,9999 |
5 | 0,9988 | 0,9994 | -4,0000 |
h=0,3; x1 =-0,5; x2=-1 ; x1нач=-2, x1кон=2, x2нач=-2, x2кон=2
№ | x1 | x2 | R |
0 | -0,5 | -1 | 7,375 |
1 | 0,1750 | 1,4 | -2,1996 |
2 | 1,0473 | 0,9200 | -3,9804 |
3 | 0,9600 | 1,016 | -3,9948 |
4 | 1,0305 | 0,9968 | -3,9972 |
5 | 0,9747 | 0,0006 | -3,9981 |
6 | 1,0196 | 0,9999 | -3,9988 |
7 | 0,9839 | 1,0000 | -3,9992 |
8 | 1,0126 | 1,0000 | -3,9995 |
9 | 0,9898 | 1,0000 | -3,9997 |
10 | 1,0081 | 1,0000 | -39998 |
11 | 0,9935 | 1,0000 | -3,9999 |
12 | 1,0052 | 1,0000 | -3,9999 |
13 | 0,9958 | 1.0000 | -3,9999 |
14 | 1,0033 | 1,0000 | -4,0000 |
15 | 0,9973 | 1,0000 | -4,0000 |
16 | 1,0021 | 1,0000 | -4,0000 |
17 | 0,9983 | 1,0000 | -4,0000 |
18 | 1,0013 | 1,0000 | -4,0000 |
h=1; x1 =-0,5; x2=-1 ; x1нач=-2, x1кон=2, x2нач=-2, x2кон=2
№ | x1 | x2 | R |
0 | -0,5 | -1 | 7,375 |
1 | 0,6250 | 3 | 4,3692 |
2 | 1,5391 | -1,0000 | 5,0283 |
3 | 0,5125 | 1 | -3,4029 |
4 | 1,0655 | 1 | -3,9869 |
5 | 0,9640 | 1 | -3,9961 |
6 | 1,0170 | 1 | -3,9991 |
7 | 0,9913 | 1,0000 | -3,9998 |
8 | 1,0043 | 1 | -3,9999 |
9 | 0,9978 | 1 | -4,0000 |
10 | 1,0011 | 1 | -4,0000 |
Заключение
Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.
Список используемой литературы
1. Корнеенко В. П. Методы оптимизации: Учебник / В. П. Корнеенко. – М.: Высш. шк., 2007.
2. Пантелеев А. В. Методы оптимизации в примерах и задачах: Учеб. пособие / А. В. Пантелеев, Т. А. Летова. – М.: Высш. шк., 2005.
3. Батищев Д. И. Оптимизация в САПР: Учебник / Д. И. Батищев, Я. Е. Львович, В. Н. Фролов. – Воронеж: Изд-во ВГУ, 1997.
4. Банди Б. Методы оптимизации. Вводный курс / Б. Банди. – М.: Радио и связь, 1988.
5. Реклейтис Г. Оптимизация в технике: в 2 кн. / Г. Реклейтис, А. Рейвиндран. – М.: Мир, 1986.
Приложение
Листинг программы:
#include <vcl.h>
#pragma hdrstop
#include "Math.hpp"
#include "math.h"
#include "Unit1.h"