2 Расчётная часть

2.1 Аналитический метод решения

Найти минимум функции аналитическим методом, используя необходимые и достаточные условия.

Рассмотрим функцию f(x1,x2)=2 с ограничением и начальную точку x₀(4,3). Найдем минимум f(x₁, x₂).

Найдем частные производные первого порядка функции f(x):

Решим систему уравнений:

Получили критическую точку М(-3,4). Найдём роизводные 2-го порядка:

Составим матрицу Гессе и классифицируем ее, используя критерий Сильвестра:

Так как главные миноры матрицы Гессе положительны, то матрица является положительно определенной. Используя критерии проверки достаточных условий экстремума, можно сделать вывод: точка М( , ) является точкой локального минимума:

f_min( , )= .

2.2 Алгоритм метода градиентного спуска

Алгоритм метода градиентного спуска с дроблением шага для квадратичной функции.

Требуется найти минимум данной функции методом градиентного спуска с дроблением шага. Разобьем все действия на шаги:

Шаг 1. Для квадратичной функции f(x) = + + с, ввести матрицу A =(a_ij), вектор b = (b₁, b₂, … , b_n)^T и коэффициент c,

i = 1, … , n; j = 1, … , n.

Выбрать произвольную начальную точку x = (x₁, x₂, … , x_n)^T, например,

x = (0, 0, … , 0)^T, начальный шаг a и e > 0. Вычислить f(x).

Шаг 2. Вычислить g = f '(x) = Ax + b, или покоординатно

g = (g₁, g₂, … , g_n)^T,

g_i = + b_i, i = 1, …, n.

Шаг 3. Проверить выполнение критерия окончания вычислений:

||f '(x)|| < e.

Если это условие выполнено, вычисления закончить и за приближенное значение точки минимума принять точку

x* = x = (x₁, x₂, … , x_n)^T.

В противном случае перейти к шагу 4.

Шаг 4. Вычислить

y = (y₁, y₂, … , y_n), y_i= x_i– a g_i, i = 1, …, n.

Шаг 5. Вычислить f(y).

Шаг 6. Если f(y) < f(x), то положить x = y, f(x) = f(y) и перейти к шагу 2, иначе – перейти к шагу 7.

Шаг 7. Положить и перейти к шагу 4.

Заключение

В курсовой работе был рассмотрен градиентный метод оптимизации с переменным шагом, без ограничений. Составлена программа в Mathcad, реализующая этот метод. Была найдена точка оптимума, являющаяся минимумом. В ней выполняются необходимые и достаточные условия. Было выяснено, что градиентный метод обладает высокой эффективностью.

Реальные прикладные задачи дискретной оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи.

Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации.

В данной работе были реализованы все поставленные цели, решены и рассмотрены все основные задачи, также были проанализированы результаты и сделаны соответствующие выводы.