2.3.4. Порядок выполнения лабораторной работы

1. Кратко описать изучаемые градиентные методы.

2. Дать геометрическую иллюстрацию полученного индивидуального задания и выполнить вручную две итерации по каждому алгоритму.

3. Выполнить с использованием компьютерного комплекса расчёты полученной задачи по каждому из рассмотренных методов при различных значениях параметров алгоритмов.

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

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

2.3.5. Задания для лабораторной работы

1. Минимизировать функцию f(X)=x₁²+4x₂²4x₁8x₂+5 из начальной точки X⁰=(1;2).

2. Минимизировать функцию f(X)=4x₁²+x₂²16x₁2x₂+17 из нач. точки X⁰=(0;0).

3. Минимизировать функцию f(X)=x₁²+4x₂²10x₁48x₂+169 из нач. точки X⁰=(0;0).

4. Минимизировать функцию f(X)=4x₁²+x₂²40x₁12x₂+136 из нач. точки X⁰=(0;0).

5. Минимизировать функцию f(X)=x₁²+4x₂²6x₁8x₂+13 из нач.точки X⁰=(0;0).

6. Минимизировать функцию f(X)=4x₁²+x₂²24x₁2x₂+37 из нач. точки X⁰=(2;0).

7. Минимизировать функцию f(X)=x₁²+9x₂²4x₁18x₂+13 из нач. точки X⁰=(1;0).

8. Минимизировать функцию f(X)=9x₁²+x₂²36x₁2x₂+37 из нач. точки X⁰=(2;0).

3. Методы оптимизации при наличии ограничений

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

Целевую функцию f(X)=f(x₁,x₂,...,x_n) и функции h_j(X)=h_j(x₁,x₂,...,x_n), j=1,...,m; g_s(X)=g_s(x₁,x₂,...,x_n), s=1,...,p, задающие ограничения, будем рассматривать как функции, заданные в точках n-мерного евклидова пространства Eⁿ.

Изучим наиболее употребительные методы решения рассматриваемых задач вида

min{f(X)| X R (3.1)

где R-допустимая область, задаваемая ограничениями типа равенств и неравенств

. (3.2)

В случае гладких выпуклых функций f(X),h_j(X),g_s(X) поставленная задача (3.1) может быть решена с применением необходимых и достаточных условий, устанавливаемых теоремами Куна-Таккера. Однако для решения большинства практических задач используются приближённые численные методы. Рассмотрим некоторые из них, представляющие две группы методов.

1. Методы, использующие преобразование задачи условной оптимизации в эквивалентную последовательность задач безусловной оптимизации путём введения в рассмотрение вспомогательных функций. Эти методы называют методами последовательной безусловной оптимизации.

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

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

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