Методы нулевого порядка одномерной минимизации

Глава 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).

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

Способы нулевого порядка одномерной минимизации

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

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

Функция f(x) именуется унимодулярной на интервале [a, b], если она добивается глобального минимума на [a, b] в единственной точке x*, причём слева от x* функция строго убывает, а справа - строго увеличивается.

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

Для хоть какого способа одномерной оптимизации нужно задание исходного интервала L0=[a0, b0], в каком лежит точка Методы нулевого порядка одномерной минимизации минимума. Интервал L0 именуется исходным интервалом неопределённости.

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

Берутся равноотстоящие друг от друга на некий шаг h три точки x0-h, x0, x0+h и сравниваются значения f в этих точках. Если f(x0-hf(x0)£f(x0+h), то в качестве исходного интервала неопределённости берётся отрезок [x0-h, x0+h]. Если f(x0-hf(x0)≥f(x0+h), то Методы нулевого порядка одномерной минимизации функция на этом отрезке противоречит определению унимодулярности, и такой не является. Тогда берутся другие три точки и процедура повторяется. Если же на отрезке [x0-h, x0+h] функция однообразна, то наращиваем отрезок в сторону убывания с определённым шагом D до того времени, пока значение функции в следующем конце отрезка не превзойдет значения на прошлом. Это Методы нулевого порядка одномерной минимизации будет означать, что локальный минимум функции достигается на приобретенном отрезке. Более тщательно:

1. Задать произвольно последующие характеристики: x0 - некую точку, h>0 - величину шага. Положить k=0.

2. Вычислить значение функции в точках x0-h, x0, x0+h.

3. Проверить условие окончания:

а) если f(x0-hf(x0)£f(x0+h), то исходный интервал неопределённости определён: [a0, b0]=[x0-h, x0+h];

б) если f(x0-hf(x0)³f(x0+h), то функция не является унимодулярной, и требуемый Методы нулевого порядка одномерной минимизации интервал не может быть найден. Требуется задать другую x0.

в) если условие окончания не производится, то перейти к шагу 4.

4. Найти величину D:

а) если f(x0-hf(x0)³f(x0+h), то D=h, a0=x0, x1=x0+h;

б) если f(x0-hf(x0)£f(x0+h), то D=-h, b0=x0, x1=x0-h, k=1

5. Отыскать последующую точку xk+1=xk+2kD;

6. Проверить условие убывания функции:

а) если f(xk+1)<f(xk) и D=h, то a0=xk;

если f(xk+1)<f(xk) и D=-h, то b0=xk;

в обоих случаях Методы нулевого порядка одномерной минимизации положить k=k+1 и перейти к шагу 5);

б) если f(xk+1)³f(xk), то процедура заканчивается. При D=h положить b0=xk+1, а при D=-h положить a0=xk+1. В итоге имеем [a0, b0] - разыскиваемый интервал неопределённости.

Пример I. Отыскать способом Свенна исходный интервал неопределённости для решения задачки f(x)=x2-6x+14®min при x0=0, h=1.

Решение. 1. Положим k=0.

2.0. Вычислить значение функции в точках x0-h=-1, x0=0, x0+h=1:

f(-1)=21, f(0)=14, f(1)=9.

3.0. Потому что f(-1)>f(0)>f(1)=9, то условие окончания не Методы нулевого порядка одномерной минимизации производится.

4.0. Полагаем D=h=1, a0=x0=0, x1=x0+h=1, k=1.

5.1. Найдём последующую точку x2=x1+2D=3.

6.1. Проверим условие убывания функции. Потому что f(x2)=5<f(x1)=9 и D=h, то a0=x1=1. Положим k=2.

5.2. Найдём последующую точку x3=x2+22D=7;

6.2. Проверим условие убывания функции. Потому что f(x3)=21>5=f(x2) то поиск завершён: правая граница b0=7.

Ответ: [1; 7] - исходный интервал неопределённости.

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

1. Выбор исходного интервала неопределённости.

2. Уменьшение интервала неопределённости.

3. Проверка условия окончания. Поиск завершается Методы нулевого порядка одномерной минимизации, когда длина текущего интервала неопределённости [ak, bk] оказывается меньше данной величины e.

Ниже мы рассматриваем два способа нулевого порядка. Один относится к параллельным, другой - к поочередным стратегиям.


metodi-ocenki-kachestva-prognozirovaniya.html
metodi-ocenki-konkurentosposobnosti-turfirmi.html
metodi-ocenki-materialno-proizvodstvennih.html