Одномерная оптимизация
Общие положения.
Методы оптимизации позволяют найти экстремум функции в практических задачах. Все многообразии методов оптимизации можно классифицировать следующим образом:
1. По размерности решаемой задачи: одномерные и многомерные.
2. По способу формирования шага многомерные методы делятся на градиентные, безградиентные и случайные.
3. По наличию активных ограничений: безусловные и условные.
Рассмотрим задачу вида:
Решением задачи называется х*, при котором R(х*)≥R(x) для 
При практическом решении задач не будем различать два значения хi и хi+1, если 
где ε – заданная погрешность решения.
Если возникает задача нахождения минимума R, то всегда можно перейти к новому критерию R1=–R, который необходимо максимизировать.
Метод сканирования заключается в последовательном переборе всех значений х на [a,b] с шагом ε и вычислении критерияоптимальности R в каждой точке. Точка, в которой R принимает максимальное значение, принимается за решение задачи оптимизации.
На практике можно реализовать одну из основных модификаций метода – последовательное уточнение решения. На первом этапе сканирование осуществляют с крупным шагом. Затем отрезок, внутри которого получено наибольшое значение R, разбивается на более мелкие отрезки для нахождения уточненного значения экстремума.
Главный недостаток метода – возможность пропуска «острого» глобального максимума.
Метод дихотомии (половинного деления) заключается в делении заданного отрезка на две равные части с последующим выбором одной из них, в которой локализуется экстремум. Выбор отрезка осуществляется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε/2.
Пусть х – середина [a,b]. Если R(x+ ε/2)=R(x- ε/2), то максимум достигается в точке х. Если R(x+ ε/2)>R(x- ε/2), то максимум располагается на правой половине текущего отрезка и для дальнейшего поиска выбирается отрезок [x- ε/2, b], в противном случае –
[a, x+ ε/2].
Процесс поиска завершается при достижении отрезком, на котором находится экстремум, величины ε.
Метод золотого сечения основан на делении текущего отрезка [a,b]на неравные части, подчиняющиеся правилу золотого сечения, с последующим выбором отрезка, содержащего экстремум.
Золотое сечение определяется по правилу: отношение всего отрезка к большей части равно отношению большей части к меньшей. Этому правилу удовлетворяют две точки c и d , расположенные симметрично относительно середины отрезка: 
. Если R(c)>R(d), то для поиска максимума выбирается [a,d], в противном случае – [c,b]. Процесс поиска завершается при достижении отрезком, на котором находится экстремум, величины ε.
Найдем золотое сечение ξ на отрезке [0,1]: 
ξ2-3ξ+1=0 
На отрезке существуют две точки золотого сечения. Получим аналитические формулы для расчета точек золотого сечения отрезка [a,b]:
.
ЗАДАЧА 6.1. Найти максимум функции y=x3–x на [-1,0]:
РЕШЕНИЕ.
1) Метод сканирования
| x | -1 | -0,9 | -0,8 | -0,7 | -0,6 | -0,5 | -0,4 | -0,3 | -0,2 | -0,1 | |
| y | 0,171 | 0,288 | 0,357 | 0,384 | 0,375 | 0,336 | 0,273 | 0,192 | 0,099 |
Максимальное значение находится на отрезке [-0,7; 0,5]:
Уточним значение, уменьшив интервал сканирования до 0,01
| x | -0,7 | -0,69 | …… | -0,64 | -0,63 | -0,62 | -0,61 | -0,6 | -0,59 | -0,58 | -0,57 |
| y | 0,36 | 0,361 | 0,378 | 0,38 | 0,382 | 0,383 | 0,384 | 0,3846 | 0,38489 | 0,38481 |
С точностью 0,01 максимум у=0,3849 достигается в точке х=-0,58
2)Метод дихотомии
Выберем точность е=0,05
| a | b | x=(a+b)/2 | x-e/2 | x+e/2 | y(x-e/2) | y(x+e/2) |
| -1 | -0,5 | -0,55 | -0,45 | 0,38363 | 0,35888 | |
| -1 | -0,45 | -0,725 | -0,775 | -0,675 | 0,30952 | 0,36745 |
| -0,755 | -0,45 | -0,6025 | -0,653 | -0,553 | 0,37469 | 0,38385 |
| -0,653 | -0,45 | -0,5515 | -0,602 | -0,502 | 0,38388 | 0,37537 |
| … |
3) метод золотого сечения
| a | b | c | d | y© | y(d) |
| -1 | -0,618 | -0,382 | 0,382 | 0,3263 | |
| -1 | -0,382 | -0,764 | -0,618 | 0,318 | 0,382 |
| -0,764 | -0,382 | -0,618 | -0,528 | 0,382 | 0,3808 |
| … |
Задание 6.1.
Продолжить вычисления в задаче 6.1 по методам дихотомии и золотого сечения