ВУЗ:
Составители:
точке определяется только градиентом ЦФ. Если же указанная точка не
принадлежит области допустимых решений, то за счет данного
слагаемого на последующих итерациях достигается возвращение в
область допустимых решений. При этом, чем меньше α, тем быстрее
находится приемлемое решение, однако точность его снижается.
Поэтому итерационный процесс обычно начинают при сравнительно
малых значениях
α и постепенно увеличивают.
Применение градиентных методов для решения САУ.
Нельзя полагать, что методы оптимизации можно использовать
только для конкретно сформулированных задач поиска наилучшего
решения.
На третьем курсе при изучении дисциплины "Мат. задачи в
электроэнергетике" мы рассматривали установившиеся режимы
Поиск решений с помощью оптимизационных методов
(продолжение темы)
Применение оптимизационных методов для решения задач
расчета установившегося режима.
Динамическое программирование представляет собой
математический аппарат для решения нелинейных оптимизационных
задач. Этим методом решаются задачи оптимального управления
многошаговыми процессами путем сведения многомерной задачи к
последовательности простых одномерных оптимизационных задач.
Целевая функция оптимизации может быть как гладкой, так и
негладкой, что затрудняет использование классических методов
оптимизации.
Методы минимизации функции ошибки.
Для СЛАУ вида Ах=b точность приближения итерационного
процесса к решению можно оценить по следующим показателям:
1)
вектор ошибки xxY −= * , где х – вектор, полученный на
некоторой итерации, х* – решение СЛАУ;
2)
вектор невязки Axbr −
=
.
В точке решения как вектор невязки, так и вектор ошибки нулевые.
Если А – положительно определенная матрица, то удобной мерой
точности является скалярная функция ошибки, определяемая как
положительно-определенная квадратичная форма
AYYxF
t
=
)( . (1)
Очевидно, что F(x)>0 при любых
xxY
−
=
* ≠0 и F(x)=0 при х=х*.
Следовательно, функция ошибки имеет нулевой минимум в точке
решения, т.е. можно построить алгоритм поиска минимума функции и с
его помощью найти решение СЛАУ.
Однако, определить F(x), не зная точного решения, невозможно,
поэтому приведем выражение (1) к удобному виду
(
)
()
AxxAxxAxxAxxxxAxxxF
tttttt
+−−=−⋅⋅−= ***)(
***
.
Учтем, что Ax*=b, тогда и
ttt
bAx =
*
, поскольку
t
AA = для
положительно определенной матрицы, то
tt
bAx =
*
. Проведя замены,
получим
bxbxxbAxxxF
t
t
tt
*
)( +−−= . (2)
Последний член в сумме – постоянный, поэтому минимум функции
F(x) и минимум функции
bxxbAxxxf
t
tt
−−=)( (3)
будут при х=х*, хотя и будут отличаться по величине, что для нас
неважно. Поэтому задачу решения СЛАУ с положительно определенной
матрицей А можно свести к задаче определения минимума функции f(x).
Для проведения преобразований удобнее функцию (3) представить в
виде скалярного произведения. Скалярное произведение векторов
α
β
=
α
β
=
βα=
β
α
tt
),(),(. Тогда
),(2),()( bxAxxxf
−
=
(4)
Непосредственное определение минимума через производную
приводит к исходной задаче. Поэтому организуем итерационный
процесс минимизации, который сочетал бы простоту расчета на каждом
шаге с быстротой сходимости. Итерационный процесс построим
следующим образом:
)()()()1( kkkk
chxx +=
+
, (5)
точке определяется только градиентом ЦФ. Если же указанная точка не В точке решения как вектор невязки, так и вектор ошибки нулевые.
принадлежит области допустимых решений, то за счет данного Если А – положительно определенная матрица, то удобной мерой
слагаемого на последующих итерациях достигается возвращение в точности является скалярная функция ошибки, определяемая как
область допустимых решений. При этом, чем меньше α, тем быстрее положительно-определенная квадратичная форма
находится приемлемое решение, однако точность его снижается. F ( x) = Yt AY . (1)
Поэтому итерационный процесс обычно начинают при сравнительно Очевидно, что F(x)>0 при любых Y = x * − x ≠0 и F(x)=0 при х=х*.
малых значениях α и постепенно увеличивают. Следовательно, функция ошибки имеет нулевой минимум в точке
Применение градиентных методов для решения САУ. решения, т.е. можно построить алгоритм поиска минимума функции и с
его помощью найти решение СЛАУ.
Нельзя полагать, что методы оптимизации можно использовать
Однако, определить F(x), не зная точного решения, невозможно,
только для конкретно сформулированных задач поиска наилучшего
поэтому приведем выражение (1) к удобному виду
решения.
На третьем курсе при изучении дисциплины "Мат. задачи в ( )
F ( x) = xt* − xt ⋅ A ⋅ (x * − x ) = xt* Ax * − xt* Ax − xt Ax * + xt Ax .
электроэнергетике" мы рассматривали установившиеся режимы Учтем, что Ax*=b, тогда и xt* At = bt , поскольку A = At для
Поиск решений с помощью оптимизационных методов положительно определенной матрицы, то xt* A = bt . Проведя замены,
получим
(продолжение темы)
F ( x) = xt Ax − bt x − xt b + xt*b . (2)
Применение оптимизационных методов для решения задач
расчета установившегося режима. Последний член в сумме – постоянный, поэтому минимум функции
F(x) и минимум функции
Динамическое программирование представляет собой
математический аппарат для решения нелинейных оптимизационных f ( x) = xt Ax − bt x − xt b (3)
задач. Этим методом решаются задачи оптимального управления будут при х=х*, хотя и будут отличаться по величине, что для нас
многошаговыми процессами путем сведения многомерной задачи к неважно. Поэтому задачу решения СЛАУ с положительно определенной
последовательности простых одномерных оптимизационных задач. матрицей А можно свести к задаче определения минимума функции f(x).
Целевая функция оптимизации может быть как гладкой, так и Для проведения преобразований удобнее функцию (3) представить в
негладкой, что затрудняет использование классических методов виде скалярного произведения. Скалярное произведение векторов
оптимизации. α t β = (α, β) = (β, α) = β t α . Тогда
f ( x) = ( x, Ax) − 2( x, b) (4)
Методы минимизации функции ошибки. Непосредственное определение минимума через производную
Для СЛАУ вида Ах=b точность приближения итерационного приводит к исходной задаче. Поэтому организуем итерационный
процесса к решению можно оценить по следующим показателям: процесс минимизации, который сочетал бы простоту расчета на каждом
1) вектор ошибки Y = x * − x , где х – вектор, полученный на шаге с быстротой сходимости. Итерационный процесс построим
некоторой итерации, х* – решение СЛАУ; следующим образом:
2) вектор невязки r = b − Ax . x ( k +1) = x ( k ) + h ( k ) c ( k ) , (5)
