Метод золотого сечения

Рассматриваемая в данном методе функция должна быть унимодальной. Функция f (x) является унимодальной на отрезке [a, b], если она на этом отрезке имеет единственную точку глобального минимума и слева от этой точки является строго убывающей, а справа строго возрастающей.

Суть метода золотого сечения заключается в том, чтобы определить точку глобального минимума на отрезке [a, b] за минимальное количество шагов, т. е. за минимальное количество вычислений целевой функции.

В соответствии с данным методом в каждый текущий момент времени рассматривается всегда две точки, например, в начальный момент точки х₁ и х₂ так, чтобы а < х₁ < х₂ < b. При этом возможен один из двух случаев (рис. 3.7). Согласно свойству унимодальной функции в первом случае искомая точка х_min не может находиться на отрезке [x₂, b], во втором случае на отрезке [a, x₁] (показаны штриховкой). Значит, область поиска сужается, и следующую точку х₃ необходимо брать на одном из укороченных отрезков: [a, x₂] – случай 1 или [x₁, b] – случай 2.

Далее следует определиться, где на исходном отрезке [a, b] необходимо выбирать точки х₁ и х₂. Первоначально о положении точки х_min ничего не известно, поэтому любой из приведенных выше случаев возможен с одинаковой вероятностью. Это означает, что лишним может оказаться любой из отрезков: [x₂, b] или [a, x₁]. Отсюда следует, что точки х₁ и х₂ необходимо выбирать симметрично относительно середины отрезка [a, b].

Рис. 3.7. Варианты выбора области поиска минимума целевой функции

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

Таким образом, с одной стороны, точки следует брать рядом с серединой отрезка, а, с другой стороны, слишком близко друг от друга их брать нельзя. То есть необходимо найти некую «золотую середину».

Рассмотрим для простоты вместо отрезка [a, b] отрезок единичной длины [0, 1] (рис. 3.8).

Рис. 3.8.

На рис. 3.8 ÷АВê=÷CDê= х, ÷АCê=÷ВDê= 1 – х, ÷ВСê= 1 – 2х.

Для того, чтобы точка B была «выгодной» как на данном, так и на следующем этапе (шаге), она должна делить отрезок AD в таком же отношении, как и AC: AB/AD = BC/AC. При этом в силу симметрии аналогичным свойством будет обладать и точка C: CD/AD = BC/BD. В обозначениях координаты x эти пропорции принимают вид: x/1 = (1 – 2x)/(1 – x). Решим эту пропорцию:

х(1 – х) = 1 – 2х Þ х – х² = 1 – 2х Þ х – х² – 1 + 2х = 0 Þ – х² + 3х – 1 = 0 Þ х² – 3х + 1 = 0; Д = b² – 4ac = 9 – 4 = 5.

Корни этого уравнения равны:

.

Корень x₂ > 1 не приемлем, т. е. уравнение имеет один корень.

О точке, которая расположена на расстоянии длины от одного из концов отрезка, говорят, что она осуществляет «золотое сечение» данного отрезка. Очевидно, что каждый отрезок имеет две такие точки, расположенные симметрично относительно его середины.

Таким образом, алгоритм метода «золотого сечения» заключается в следующем (рис. 3.9). На исходном отрезке [a, b] выбираются две точки x₁ и x_{2 ,} так, чтобы выполнялось приведенное выше соотношение «золотого сечения» этого отрезка. Вычисляются значения целевой функции в этих точках f (x₁) и f (x₂). Они сравниваются, и из дальнейшего рассмотрения исключается отрезок, прилегающий к точке, дающей большее значение целевой функции (здесь отрезок [x₂, b]). Т. е. исходный отрезок [a, b] «стягивается» до отрезка [a, b₁].

Рис. 3.9. Иллюстрация алгоритма метода «золотого сечения»

Для этого нового отрезка находится его середина, и по отношению к ней симметрично оставшейся точке x₁ ставится точка x₃. Для нее рассчитывается значение целевой функции f (x₃) и сравнивается с f (x₁). Из дальнейшего рассмотрения опять исключается отрезок, прилегающий к точке с большим значением целевой функции, здесь это отрезок [a, x₃]. Текущий отрезок «стягивается» до нового отрезка, здесь это [a₁, b₁] и т. д.

Метод «золотого сечения» прост, эффективен и широко применяется в практической оптимизации.

Метод линеаризации

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

Пример № 1. Рассмотрим суть данного метода на примере № 2 многопараметрической однокритериальной задачи оптимизации, который решался ранее. Напомним формулировку задачи: найти х_1опт и х_2опт. Целевая функция у = х₂ / х₁ ® max, ограничения:

1 £ х₁ £ 8, 2 £ х₂ £ 12, х₁ × х₂ ³ 10.

В первую очередь приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:

lg 1 £ lg х₁ £ lg 8; lg 2 £ lg х₂ £ lg 12; lg х₁ + lg х₂ ³ lg 10.

После вычислений получим:

0 £ lg х₁ £ 0,903; 0,301 £ lg х₂ £ 1,079; lg х₁ + lg х₂ ³ 1.

После логарифмирования целевой функции:

lg y = lg х₂ – lg х ® max.

Далее задача решается с применением симплекс-метода или графо-аналитически.

Пример № 2. Необходимо определить область рациональных режимов резания (например, токарной обработки) исходя из условия максимума производительности.

Целевой функцией в данном случае является величина Q производительности обработки:

Q = B× n× S ® max,

где B – постоянный множитель; n – число оборотов шпинделя; S – подача.

При решении задачи оптимизации абсолютное значение целевой функции не играет никакой роли. Таким образом, от исходной формулировки целевой функции можно перейти к формулировке упрощённой:

Q = n× S ® max.

Полученная зависимость нелинейна, т. е. задача относится к классу задач нелинейного программирования. Приводим данную задачу к задаче линейного программирования. Для этого проводим логарифмирование ограничений и целевой функции:

ln Q = ln n + ln S. Тогда Z = ln Q;

x₁ = ln n; x₂ = ln S; Z = x₁ + x₂ ® max.

Ограничения, накладываемые на область допустимых решений задачи S_min, S_max, n_min, n_max, определяются паспортом станка, заданными параметрами шероховатости обработанной поверхности, стойкостью инструмента и др. Пример графо-аналитического решения задачи приведен на рис. 3.10.

Рис. 3.10. Область допустимых значений режимов резания