Методы оптимизации и вычислительная геометрия

ВВЕДЕНИЕ 2
1. Цель, задачи и этапы выполнения курсовой работы 4
2. Метод ломаных 6
2.1 Описание метода ломаных 6
2.2 Описание программы, реализующей метод ломаных 8
3. Метод наискорейшего спуска 12
3.1 Общая схема методов спуска 12
3.2 Описание метода градиентного спуска 14
3.3 Описание метод наискорейшего спуска 17
3.4 Описание метода наискорейшего спуска для квадратичных функций 18
3.5 Описание программы, реализующей метод наискорейшего спуска 20
ЗАКЛЮЧЕНИЕ 25
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 26
ПРИЛОЖЕНИЕ А. Блок-схема к программе, реализующей метод ломаных 27
ПРИЛОЖЕНИЕ Б. Листинг программы, реализующей метод ломаных 30
ПРИЛОЖЕНИЕ В. Блок-схема программы, реализующей метод наискорейшего спуска 32
ПРИЛОЖЕНИЕ Г. Листинг программы, реализующей метод наискорейшего спуска 33

Метод наискорейшего спуска по сравнению с обычным градиентным методом дает некоторое ускорение, метод хорошо "работает" при минимизации гладких функций и если начальное приближение выбрано достаточно далеко от оптимума. Если же очередная точка окажется в окрестности оптимума, то уменьшение целевой функции будет очень медленным. Это происходит из-за того, что для получения оптимума с высокой точностью необходимо выполнить большое число мелких шагов.Метод наискорейшего спуска хотя не дает особенного ускорения сходимости он свободен от параметров и на практике может дать некоторый выигрыш, особенно на начальных итерациях.В связи с этим в программе был реализован более точный метод градиентного спуска.В качестве условия окончания поиска задаётся требуемая малость модуля градиента функции, т.е. должно выполнятся условие(в области оптимума градиент равен 0, но достичь этого значения практически не возможно, поэтому задаётся требуемая малость близкая к 0).Программа написана на языке программирования VBA в среде MicrosoftOfficeExcel.Программа имеет понятный интуитивный графический интерфейс (рисунок3.1).Рисунок 3.1 Главное окно программыПосле запуска необходимо ввести требуемую точность вычислений (рисунок3.2).Рисунок 3.2 Ввод входных значенийЗатем программа рассчитывает точки приближения и находит для данных ограничений точку минимума (рисунок3.3).Рисунок 3.3 Вывод результатов расчетаТаблица расчетов приведена в таблице 3.1.Таблица 3.1 Расчет поиска минимума по методу наискорейшего спуска0,013868-0,298630,6609110,072739-0,308160,6116090,116095-0,313540,5851910,147855-0,316320,5711460,170995-0,317580,5637370,187777-0,317970,5598530,199903-0,317920,5578290,208643-0,317680,5567770,214929-0,317380,5562320,219445-0,317080,5559510,222686-0,316820,5558050,225011-0,316610,555730,226678-0,316430,5556920,227873-0,31630,5556720,22873-0,31620,5556620,229344-0,316120,5556560,229784-0,316060,5556540,230099-0,316020,5556520,230326-0,315990,5556520,230488-0,315970,5556510,230604-0,315950,5556510,230687-0,315940,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