Метод наискорейшего спуска по сравнению с обычным градиентным методом дает некоторое ускорение, метод хорошо «работает» при минимизации гладких функций и если начальное приближение выбрано достаточно далеко от оптимума. Если же очередная точка окажется в окрестности оптимума, то уменьшение целевой функции будет очень медленным. Это происходит из-за того, что для получения оптимума с высокой точностью необходимо выполнить большое число мелких шагов. Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях. В связи с этим в программе был реализован более точный метод градиентного спуска. В качестве условия окончания поиска задаётся требуемая малость модуля градиента функции, т. е. должно выполнятся условие (в области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).Программа написана на языке программирования VBA в среде MicrosoftOfficeExcel. Программа имеет понятный интуитивный графический интерфейс (рисунок3.
1).Рисунок 3.1 Главное окно программы
После запуска необходимо ввести требуемую точность вычислений (рисунок3.
2).Рисунок 3.2 Ввод входных значений
Затем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рисунок3.
3).Рисунок 3.3 Вывод результатов расчета
Таблица расчетов приведена в таблице 3.
1.Таблица 3.1 Расчет поиска минимума по методу наискорейшего спуска0,13 868−0,298 630,6609110,72 739−0,308 160,6116090,116 095−0,313 540,5851910,147 855−0,316 320,5711460,170 995−0,317 580,5637370,187 777−0,317 970,5598530,199 903−0,317 920,5578290,208 643−0,317 680,5567770,214 929−0,317 380,5562320,219 445−0,317 080,5559510,222 686−0,316 820,5558050,225 011−0,316 610,555730,226 678−0,316 430,5556920,227 873−0,31 630,5556720,22 873−0,31 620,5556620,229 344−0,316 120,5556560,229 784−0,316 060,5556540,230 099−0,316 020,5556520,230 326−0,315 990,5556520,230 488−0,315 970,5556510,230 604−0,315 950,5556510,230 687−0,315 940,555651
График поверхности представлен на рисунке 3.
4.Рисунок 3.4 График поверхности Таким образом в результате применения метода наискорейшего спуска и реализации этого метода программным образом был найден минимум функции с заданной точностью ЗАКЛЮЧЕНИЕВ результате выполнения данной курсовой работы:
Проанализированы теоретические основы методов оптимизации и вычислительной геометрии. Освоены основные этапы процесса постановки задачи оптимизации. Произведено построение и анализ математической модели, осуществлен выбор адекватного метода ее исследования. Применены на практике теоретические знания из разделов данного курса.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Пиявский С. А. Один алгоритм отыскания абсолютного экстремума функций // Журнал вычислительной математики и математической физики, т.12, № 4 (1972), стр. 885—896.Норкин В. И. О методе Пиявского для решения общей задачи глобальной оптимизации // Журнал вычислительной математики и математической физики, т.32, № 7 (1992), стр. 992—1006
Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986. — С. 298−311.Гилл Ф., Мюррей У., Райт М.
Практическая оптимизация. Пер. с англ. — М.: Мир, 1985
Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980. ПРИЛОЖЕНИЕ А. Блок-схема к программе, реализующей метод ломаных
ПРИЛОЖЕНИЕ Б. Листинг программы, реализующей метод ломаныхPrivate Sub CommandButton1_Click ()Dim a, b, e, L, x1, x2, fx1, fx2a = Val (TextBox1.Value)b = Val (TextBox2.Value)e = Val (TextBox3.Value)L = Abs ((a * Sin (a) + 2 * Cos (a)) / (a * a * a))For i = a To b Step 0.01 If Abs ((i * Sin (i) + 2 * Cos (i)) / (i * i * i)) > L Then L = Abs ((i * Sin (i) + 2 * Cos (i)) / (i * i * i)) End IfNext iCells (5, 11) = Lx0 = (a + b) / 2 + (Cos (a) / (a * a) — Cos (b) / (b * b)) / (2 * L) Cells (2, 11) = x0k = 0For i = 0 To 100 Cells (2 + i, 12) = «» Cells (2 + i, 13) = «» Cells (2 + i, 14) = «» Cells (2 + i, 15) = «» Next iDo While Abs (a — b) >= e x1 = (a + x0) / 2 + (Cos (a) / (a * a) — Cos (x0) / (x0 * x0)) / (2 * L) x2 = (x0 + b) / 2 + (Cos (x0) / (x0 * x0) — Cos (b) / (b * b)) / (2 * L) fx1 = Cos (x1) / (x1 * x1) fx2 = Cos (x2) / (x2 * x2) Cells (2 + k, 12) = x1 Cells (2 + k, 13) = x2 Cells (2 + k, 14) = fx1 Cells (2 + k, 15) = fx2 If fx1 < fx2 Then a = x1 x0 = x2 Else b = x2 x0 = x1 End If k = k + 1LoopIf (Cos (x1) / (x1 * x1)) < (Cos (x2) / (x2 * x2)) Then TextBox5. Value = Round (x1, 4) TextBox4. Value = Round (Cos (x1) / (x1 * x1), 5) Else TextBox5. Value = Round (x2, 4) TextBox4. Value = Round (Cos (x2) / (x2 * x2), 5) End IfCells (18, 7) = TextBox5. ValueCells (18, 8) = TextBox4. ValueEnd SubПРИЛОЖЕНИЕ В. Блок-схема программы, реализующей метод наискорейшего спуска
ПРИЛОЖЕНИЕГ. Листинг программы, реализующей метод наискорейшего спускаPrivate Sub CommandButton1_Click ()Dim e, L, x (1000), y (1000), f (1000) As Double, modgrade = Val (TextBox3.Value)x (0) = 1y (0) = 1h = 1f (0) = x (0) ^ 2 + 2 * y (0) ^ 2 + Exp (x (0) ^ 2 + y (0) ^ 2) — x (0) + 2 * y (0)For i = 0 To 100 Cells (2 + i, 12) = «» Cells (2 + i, 13) = «» Cells (2 + i, 14) = «» Next ii = 11: x (i) = x (i — 1) — h * (2 * x (i — 1) + 2 * x (i — 1) * Exp (x (i — 1) ^ 2 + y (i — 1) ^ 2) — 1) y (i) = y (i — 1) — h * (4 * y (i — 1) + 2 * y (i — 1) * Exp (x (i — 1) ^ 2 + y (i — 1) ^ 2) + 2) f (i) = x (i) ^ 2 + 2 * y (i) ^ 2 + Exp (x (i) ^ 2 + y (i) ^ 2) — x (i) + 2 * y (i) Cells (1 + i, 12) = x (i) Cells (1 + i, 13) = y (i) Cells (1 + i, 14) = f (i) R = f (i) — f (i — 1) If R > 0 Then h = h / 2 GoTo 1 End If modgrad = Sqr ((2 * x (i) + 2 * x (i) * Exp (x (i) ^ 2 + y (i) ^ 2) — 1) ^ 2 + (4 * y (i) + 2 * y (i) * Exp (x (i) ^ 2 + y (i) ^ 2) + 2) ^ 2) If modgrad > e Then i = i + 1 GoTo 1 End If TextBox5. Value = Round (x (i), 4) TextBox6. Value = Round (y (i), 4) TextBox4. Value = Round (f (i), 4) Cells (18, 7) = TextBox5. ValueCells (18, 8) = TextBox6. ValueCells (18, 9) = TextBox4. ValueEnd Sub
