Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Глава II. Численные методы нелинейного программирования



Общие положения

 

Постановка проблемы

Применение аналитических методов нахождения экстремумов (как условного, так и безусловного) практически применимо для ограниченного класса задач. Для большинства задач эти методы практически бесполезны по следующим причинам:

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

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

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

Общие принципы.

Подавляющее большинство численных методов оптимизации относится к итерационным. Суть итерационных методов заключается в том, что задаётся некоторая начальная точка X0 в Rn и строится последовательность {Xk} точек в Rn, причём очередная Xk+1 строится по предыдущим, как правило, по Xk.

Для определённости рассмотрим задачу безусловного локального минимума:

f(X*)= . (1.2.1)

Численное решение задачи (1.2.1) заключается в построении последовательности {Xk}, обладающей свойством

f(Xk+1)<f(Xk), k=0, 1, …, (1.2.2)

В общем виде итерационная последовательность по формулам

Xk+1=Xk+hkDk, (1.2.3)

где Dk - направление перехода из точки Xk в точку Xk+1, обеспечивающее выполнение условия (1.2.2). Оно называется направлением спуска, hk - величина шага.

Начальная точка X0 задаётся, исходя из некоторых соображений применительно к конкретному методу.

Направление спуска Dk должно удовлетворять условию

f(Xk), Dk)<0, k=0, 1, …, (1.2.4)

которое обеспечивает убывание функции. Например, в качестве Dk можно взять антиградиент -Ñf(Xk).

Величина шага hk>0 выбирается либо из условия (1.2.2), либо из условия

f(Xk+hkDk . (1.2.5)

обеспечивающего наискорейший спуск в направлении Dk.

Последовательность {Xk} называется минимизирующей, если = . Сходимость последовательности {Xk} при выборе приемлемого направления Dk и величины шага hk из условия (1.2.2) или (1.2.5) зависит от характера функции f(X) и от выбора начальной точки X0.



В зависимости от наивысшего порядка (частных) производных функции f(X), используемых для формирования Dk и hk, численные методы задачи безусловной оптимизации делятся на три группы:

1. Методы нулевого порядка, использующие только информацию о значении функции f(X).

2. Методы первого порядка, использующие информацию о первых производных функции f(X).

3. Методы второго порядка, использующие информацию о вторых производных функции f(X).

Наше рассмотрение мы и начнём с методов нулевого, первого и второго порядков безусловной оптимизации.

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!