Процедура решения задачи

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ.......................................................................................... 2

ВВЕДЕНИЕ............................................................................................... 3

Способы РЕШЕНИЯ............................................................................... 5

Способ градиентного спуска с неизменным шагом................................ 5

Способ наискорейшего градиентного спуска......................................... 7

Способ покоординатного спуска............................................................ 9

Способ Франка—Вулфа........................................................................ 11

Способ штрафных функций.................................................................. 14

Способ Эрроу — Гурвица.................................................................... 16

ПРИМЕР РЕШЕНИЯ.............................................................................. 17

Пример 1............................................................................................... 17

Пример 2............................................................................................... 21

Пример 3............................................................................................... 23

ЗАКЛЮЧЕНИЕ....................................................................................... 30

Перечень ЛИТЕРАТУРЫ....................................................................... 31

ВВЕДЕНИЕ

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

Градиентные способы — численные способы решения при помощи градиента задач, сводящихся к нахождению экстремумов Процедура решения задачи функции.

Используя градиентные способы, можно отыскать решение хоть какой задачки нелинейного программирования. Но в общем случае применение этих способов позволяет отыскать точку локального экстремума. Потому оптимально использовать градиентные способы для нахождения решения задач выпуклого программирования, в каких всякий локальный экстремум является сразу и глобальным. Процесс нахождения решения задачки при помощи Процедура решения задачи градиентных способов заключается в том, что начиная с некой точки Xk осуществляется поочередный переход к неким другим точкам до того времени, пока не выявляется применимое решение начальной задачки. При всем этом градиентные способы могут быть подразделены на две группы.
К первой группе относятся способы, при использовании Процедура решения задачи которых исследуемые точки не выходят за границы области допустимых решений задачки.
Ко 2-ой группе относятся способы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Но в итоге реализации итерационного процесса находится точка области допустимых решений, определяющая применимое решение.
При нахождении решения задач градиентными Процедура решения задачи способами, в том числе и нареченными, итерационный процесс осуществляется до того момента, пока градиент функции f (x1, х2, ..., xn) в очередной точке X(k+1) не станет равным нулю либо же пока |f(X(k+1)-f(X(k))|< є , где є — довольно маленькое положительное число, характеризующее точность приобретенного решения.

Способы РЕШЕНИЯ

1. Способ Процедура решения задачи градиентного спуска с неизменным шагом.

Постановка задачки

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

Требуется отыскать локальный минимум функции f (х) на огромном количестве допустимых решений X = Rn , т.е. отыскать такую точку , что

Стратегия поиска

Стратегия решения задачки состоит в построении Процедура решения задачи последовательности точек {x k } , k = 0,1,..., таких, что , k = 0,1,... . Точки последовательности {x k } рассчитываются по правилу

(1)

где точка х0 задается юзером; - градиент функции f (х) , вычисленный в точке x k ; величина шага tk задается юзером и остается неизменной до того времени, пока функция убывает в точках последовательности, что контролируется методом проверки выполнения

условия либо

Построение последовательности Процедура решения задачи { x k} завершается в точке x k , для которой , где ε - данное маленькое положительное число, либо k ≥ M, где М - предельное число итераций, либо при двукратном одновременном выполнении 2-ух неравенств , где ε2 - маленькое положительное число. Вопрос о том, может ли точка x k рассматриваться как отысканное приближение разыскиваемой точки минимума, решается методом проведения дополнительного Процедура решения задачи исследования, которое описано ниже.

Геометрическая интерпретация способа для n =2 приведенана рис. 2.

Рис. 2

Процедура решения задачки

1.Используя метод градиентного спуска с неизменным шагом, отыскать точку x k в какой выполнен по последней мере один из критериев окончания расчетов.

2.Провести анализ точки x k с целью установить, является ли точка x k отысканным приближением Процедура решения задачи решения задачки. Процедура анализа определяется на­личием у функции f (х) непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных критерий минимума: матрица Гессе Если , то точка x k есть отысканное приближение разыскиваемой точки x * . Если f (х)=C1,то следует провести проверку функции f (х) на Процедура решения задачи выпук­лость в Q -окрестности точки x k , используя аспект неровности для функций f (х)=C1 : функция f (х)выпукла (строго выпукла) в том и исключительно в том случае, если Если функция f (х)выпукла (строго вы­пукла), то x k есть отысканное приближение точки x * .


process-razrabotki-programmi-marketingovih-kommunikacij.html
process-razuchivaniya-pesen.html
process-realizacii-geneticheskoj-informacii-ego-osnovnie-etapi.html