Численные методы безусловной оптимизации

 
 
 
 
 
 
 
 
Г. И. Каныгин, О. В. Колесникова 
 
 
 
 
ЧИСЛЕННЫЕ МЕТОДЫ  
БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва    Вологда 
«Инфра-Инженерия» 
2024 
1 
 

 
УДК 004.45:517 
ББК 32.973 
 
К19 
 
 
Рецензент: 
доктор технических наук, профессор О. А. Полушкин 
 
 
Научный редактор: 
кандидат технических наук, доцент Е. Н. Остроух 
 
 
 
 
 
 
 
 
 
 
Каныгин, Г. И. 
К19  
Численные методы безусловной оптимизации : учебное пособие / 
Г. И. Каныгин, О. В. Колесникова. - Москва ; Вологда : ИнфраИнженерия, 2024. - 148 с. : ил., табл. 
ISBN 978-5-9729-1761-7 
 
 
Рассмотрены численные методы поиска безусловного экстремума функций. 
Приведены алгоритмы и тексты программ на алгоритмических языках С  
и Python, реализующие данные алгоритмы с помощью вычислительных средств. 
Уделено внимание поиску оптимальных решений с использованием электронных 
таблиц MS Excel, включая надстройку MS Excel «Поиск решения». Все методы 
проиллюстрированы примерами оптимизации функций. По каждой теме даны задания для самостоятельного решения. 
 
Для студентов бакалавриата по направлению подготовки 09.03.02 «Информационные системы и технологии». Может быть полезно магистрантам, занимающимся оптимизацией математических моделей, вопросами их анализа и принятия 
решений. 
 
УДК 004.45:517 
ББК 32.973 
 
 
 
 
ISBN 978-5-9729-1761-7 
” Каныгин Г. И., Колесникова О. В., 2024 
 
” Издательство «Инфра-Инженерия», 2024 
 
” Оформление. Издательство «Инфра-Инженерия», 2024 
2 
 

 
 
ОГЛАВЛЕНИЕ 
 
1. Методы минимизации функций одной переменной ............................................................ 
4 
1.1. Метод дихотомии .......................................................................................................... 
10 
1.2. Метод деления интервала пополам ............................................................................. 
12 
1.3. Метод золотого сечения................................................................................................ 
15 
1.4. Метод Фибоначчи.......................................................................................................... 
18 
1.5. Метод Пауэлла квадратичной интерполяции ............................................................. 
25 
1.6. Решение одномерных задач оптимизации с помощью надстройки MS Excel  
«Поиск решения» 
............................................................................................................ 
31 
1.7. Задания для лабораторных работ 
................................................................................. 
36 
2. Методы безусловной минимизации функций многих переменных ................................. 
42 
2.1. Методы нулевого порядка ............................................................................................ 
42 
2.1.1. Метод Хука - Дживса ......................................................................................... 
43 
2.1.2. Симплексный метод ............................................................................................ 
53 
2.1.3. Метод Нелдера - Мида ....................................................................................... 
66 
2.2. Методы первого порядка .............................................................................................. 
82 
2.2.1. Метод градиентного спуска с постоянным шагом 
........................................... 
82 
2.2.2. Метод наискорейшего градиентного спуска .................................................... 
91 
2.2.3. Метод покоординатного спуска 
....................................................................... 
101 
2.2.4. Метод Флетчера - Ривса 
................................................................................... 
110 
2.3. Методы второго порядка ............................................................................................ 
121 
2.3.1. Метод Ньютона ................................................................................................. 
121 
2.3.2. Метод Ньютона - Рафсона ............................................................................... 
132 
2.4. Задания для лабораторных работ 
............................................................................... 
143 
Рекомендуемая литература  
...................................................................................................... 
145 
 
 
 
 
 
 
3 
 

 
 
1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ  
ОДНОЙ ПЕРЕМЕННОЙ 
 
 
 
Под минимизацией целевой функции 
)
(x
f
 на интервале 
]
,
[
b
a
 будем понимать решение следующей задачи: найти такую точку 


x , которая минимизирует функцию 
)
(x
f
 


x
f
x
f
b
a
x
 
.     
(1.1) 
 
)
(
 
min
)
(
]
;
[
 
Интервал [ , ]
a b , содержащий точку минимума 


x , будем называть интервалом неопределенности.  
 
Задача нахождения точки максимума 


x и максимального значения функции 
)
(


x
f
 
эквивалентна задаче 


x
f
x
f
x
f
b
a
x
b
a
x



 
 
. 
 (1.2) 
 
)]
(
[ 
min
)
(
 
max
)
(
]
;
[
]
;
[
 
Практически все одномерные численные методы поиска минимума целевой функции 
)
(x
f
 основаны на предположении, что функция внутри интервала неопределенности 
[ , ]
a b  обладает свойством унимодальности.  
 
Определение.  Функция 
)
(x
f
 называется унимодальной на интервале 
]
,
[
b
a
, если 
она достигает минимального значения в единственной точке 


x , причем слева от точки 


x  
функция строго убывает, а справа от точки 


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


x ;  
x вычисление значения 


x с заданной точностью 
0
!
H
. 
Точность вычисления  


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


b
a
x 
. Возьмем две произвольные точки 
1
x  и 
2
x , расположенные на интерва4 
 

ле 
]
,
[
b
a
 таким образом, что 
2
1
x
x 
. Сравнивая значения функции 
),
( 1
x
f
 
)
( 2
x
f
в этих 
точках, можно сузить интервал неопределенности следующим образом: 
x если 
)
(
)
(
2
1
x
f
x
f

, то точка минимума 


x лежит на интервале 
]
,
[
2
x
a
 (рис. 1.1, а); 
x если 
)
(
)
(
2
1
x
f
x
f
!
, то точка минимума 


x лежит на интервале 
]
,
[ 1 b
x
 (рис. 1.1, б); 
x если 
)
(
)
(
2
1
x
f
x
f
 
, то точка минимума 


x лежит на интервале 
]
,
[
2
1 x
x
 (рис. 1.1, в) 
 
               а) если 
)
(
)
(
2
1
x
f
x
f

                                   б) если 
)
(
)
(
2
1
x
f
x
f
!
 
                                      
 
                                                    в) если 
)
(
)
(
2
1
x
f
x
f
 
 
Рис. 1.1. Иллюстрация уменьшения интервала неопределенности 
 
Для выбора начального интервала неопределенности, содержащего точку миниму- 
ма 


x , можно применить эвристический алгоритм Свенна. 
1. Задать исходные данные: 
0
x - начальная точка, h - шаг поиска 
)
0
( !
h
. 
2. Вычислить значения функций 
)
(
  
),
(
  
),
(
0
0
0
h
x
f
x
f
h
x
f


. 
3. Если 
)
(
)
(
 
)
(
0
0
0
h
x
f
x
f
h
x
f

t
d

, то функция не является унимодальной. Необходимо перейти к шагу 1 и задать другую начальную точку  
0
x . 
4. Если 
)
(
)
(
  
)
(
0
0
0
h
x
f
x
f
h
x
f

d
t

, то интервал неопределенности 
]
,
[
b
a
 найден: 
h
x
a

 
0
, 
h
x
b

 
0
. Конец вычислений. 
5. Если 
)
(
)
(
  
)
(
0
0
0
h
x
f
x
f
h
x
f

t
t

, то согласно предположению об унимодальности, точка минимума должна располагаться правее точки 
0
x : 
;
h
t  
 
;
0
x
a  
 
;
0
1
h
x
x

 
 
1
 
k
. Перейти к шагу 7. 
6. Если 
)
(
)
(
  
)
(
0
0
0
h
x
f
x
f
h
x
f

d
d

, то точка минимума должна располагаться левее точки 
0
x : 
;
h
t

 
 
;
0
x
b  
 
;
0
1
h
x
x

 
 
1
 
k
. Перейти к шагу 7. 
5 
 

7. Найти следующую точку 
t
x
x
k
k
k
2
1

 

 и вычислить значение функции 
)
(
1

k
x
f
. 
8. Если 
)
(
)
(
1
k
k
x
f
x
f


, то положить 
1

 k
k
 и перейти к шагу 7. 
9. Если 
0
!
h
, то 
;
k
x
a  
1

 
k
x
b
. В противном случае  
;
1

 
k
x
a
k
x
b  
. Конец вычислений. 
В результате использования алгоритма Свенна получим исходный интервал неопределенности 
]
,
[
b
a
. 
На листингах 1.1, 1.2 приведены программы на языках С и Python для реализации 
алгоритма Свенна. 
Тексты программ включают функцию пользователя 
)
("
f
, в тело которой записывается код исследуемой целевой функции. В приведенных текстах программ этот код записан для целевой функции примера 1.1 (на листинге он выделен фоном). При выполнении 
лабораторной работы этот код заменяется кодом заданной целевой функции. 
Исходные данные вводятся в диалоговом режиме в следующем порядке: 
0
x  – начальная точка; 
h - величина шага. 
В результате выполнения программы на экран выводится искомый начальный интервал неопределенности. 
 
Листинг 1.1.Программа на языке С++, реализующая алгоритм Свенна
//********************************************** 
//   Эвристический алгоритм Свенна для выбора 
//    начального интервала неопределенности  
//********************************************** 
#include <iostream> 
#include <cmath> 
using namespace std; 
double f(double x){ 
  return -(3-x*x)*x; 
} 
//********************************************** 
double xk1(double xk,double t,int k){ 
  return xk+pow(2,k)*t; 
} 
//********************************************** 
int main(){ 
  double a,b; 
  double x0,x1,x2,y1,y2; 
  double y0,yL,yR; 
  double h,t; 
  int k; 
  for(;;){ 
   cout<<"Исходные данные:\n"; 
   cout<<"Введи начальную точку:x0="; 
   cin>>x0; 
6 
 

cout<<"Введи шаг: h=";cin>>h; 
yL=f(x0-h);yR=f(x0+h);y0=f(x0); 
if(!((y0>=yL)&& (y0>=yR))) break; 
cout<<"Функция не унимодальная\n"; 
   cout<<"Рекомендуется задать \n"; 
   cout<<"другую начальную точку x0\n"; 
  } 
  if((yL>=y0)&&(y0>=yR)){ 
    t=h;a=x0;x1=x0+h; 
  } 
  if((yL<=y0)&&(y0<=yR)){ 
    t=-h;b=x0;x1=x0-h; 
  } 
  if((yL>=y0)&&(yR>=y0)){ 
    a=x0-h;b=x0+h; 
  } 
  else{ 
    k=0;x2=x1; 
    do{ 
      k++; 
      x1=x2; y1=f(x1); 
      x2=xk1(x1,t,k); y2=f(x2); 
    } while(y2<y1); 
    if(t>0){ 
      a=xk1(x1,-t,k-1);b=x2; 
    } 
    else{ 
      a=x2;b=xk1(x1,-t,k-1); 
    } 
  } 
  cout<<"Результат поиска начального\n"; 
  cout<<"интервала неопределенности\n"; 
  cout<<"a="<<a<<"b="<<b; 
 
} 
 
    Листинг 1.2.  Программа на языке Python, реализующая алгоритм Свенна 
# ********************************************** 
#   Эвристический алгоритм Свенна для выбора 
#    начального интервала неопределенности 
# ********************************************** 
from math import * 
def f(x): 
  return -(3-x*x)*x 
# ********************************************** 
def xk1(xk, t, k): 
    return xk + pow(2, k) * t 
# ********************************************** 
while True: 
  print('Исходные данные:\n') 
  x0=float(input('Введи начальную точку:x0=')) 
  h=float(input('Введи шаг: h = ')) 
  yL=f(x0 - h) 
  yR=f(x0 + h) 
  y0=f(x0) 
  if not((y0 >= yL) and (y0 >= yR)): 
    break 
  print('Функция не унимодальная\n') 
7 
 

  print('Рекомендуется задать другую ’) 
  print('начальную точку x0\n') 
  if yL >= y0 >= yR: 
    t = h 
    a = x0 
    x1 = x0 + h 
  if yL <= y0 <= yR: 
    t = -h 
    b = x0 
    x1 = x0 - h 
  if yL >= y0 and yR >= y0: 
    a = x0 - h 
    b = x0 + h 
  else: 
    k = 0 
    x2 = x1 
    while True: 
      k += 1 
      x1 = x2 
      y1 = f(x1) 
      x2 = xk1(x1, t, k) 
      y2 = f(x2) 
      if y2 > y1: 
        break 
      if t > 0: 
        a = xk1(x1, -t, k-1) 
        b = x2 
      else: 
        a = x2 
        b = xk1(x1, -t, k-1) 
  print('Результат поиска начального\n') 
  print('интервала неопределенности\n') 
  print('a = ', a, 'b = ', b) 
 
 
Пример 1.1. Используя алгоритм Свенна, найти начальный интервал неопределенности для поиска максимума функции 
x
x
x
f
)
3
(
)
(
2

 
.  
 
Решение. Запускаем программы на выполнение. В диалоговом режиме вводим исходные данные и получаем исходный начальный интервал неопределенности. Работа программ на языках С и Python приведена на рис. 1.2. 
 
 
 
         на языке C 
   на языке Python 
Рис. 1.2. Результаты расчетов по алгоритму Свенна  
8 
 

В результате работы программы был найден искомый начальный интервал неопределенности [0; 1,5]. Здесь следует отметить, что точный максимум функции 
)
(x
f
 достигается в точке 
1

  
x
. 
В программе знак функции 
)
(x
f
 был заменен на противоположный, так как производится поиск интервала, содержащего точку максимума.  
 
Вычислительный процесс в алгоритме Свенна непосредственно зависит от величины 
шага h . Если h  взять большим, то получим грубые оценки координат граничных точек,  
и построенный интервал может оказаться весьма широким. С другой стороны, если h  мало, то для определения граничных точек может потребоваться большое количество итераций. 
 После того как найден интервал неопределенности, содержащий точку минимума, 
применяют численные методы, позволяющие вычислить ее с заданной точностью.   
Ниже рассмотрим наиболее распространенные на практике прямые методы минимизации, использующие только значения функции.  
Иллюстрация методов минимизации функции проводится на коротком примере 1.2  
с использованием возможностей MS Excel, включая надстройку «Поиск решения» и программ MS Excel VBA, С и Python. 
 
Пример 1.2.  Спроектировать из трёх одинаковых полос железа шириной 
м
 
1
 
a
. 
желоб (рис. 1.3) с максимальной пропускной способностью, имеющий в поперечном сечении вид трапеции. 
Решение. 
 
Рис. 1.3 
Найдем целевую функцию - площадь трапеции. 
h
x
h
x
a
a
h
x
S
)
1
(
2
)
2
(
)
,
(

 


 
. 
Выберем за независимую переменную угол D  между боковой стороной и высотой трапеции 
 
sin
sin
D
D  
 a
x
 
 
cos
cos
 
D
D  
 a
h
. Тогда 
D
D
D
cos
)
sin
1
(
)
(

 
S
, где по смыслу 
задачи 
»
¼
º
«
¬
ª

2
;
0 S
D
. 
9 
 

Таким образом, задача принимает следующий вид: максимизировать функцию 
D
D
D
cos
)
sin
1
(
)
(

 
S
 в интервале 
0; 2
S
D
ª
º
«
»
¬
¼
. Эта задача будет решена численными методами, рассмотренными ниже. 
Учитывая, что в данном примере целью является максимизация значения целевой 
функции, то в представленных ниже алгоритмах ее знак изменен на противоположный. 
Решение данной задачи с помощью необходимых и достаточных условий, дает результат: 


S
D
 
 
;
523599
,
0
6


S
 
D
 
.
299038
,
1
)
(
 
1.1. Метод дихотомии 
 
Метод дихотомии заключается в следующем. Интервал поиска 
]
,
[
b
a
 делится пополам, 
2
b
a
x

 
 и вычисляются две абсциссы симметрично расположенные относительно 
G

 x
x
; 
2
2
G

 x
x
, где G  - величина различимости точек 
)
(
H
G 
. Вычисляточки x : 
2
1
ются функции 
)
( 1
x
f
 и 
)
( 2
x
f
. Сравниваются полученные значения и находится новый 
суженный интервал неопределенности: 
1) если 
)
(
)
(
2
1
x
f
x
f

, то полагают 
2
x
b  
; 
2) если 
)
(
)
(
2
1
x
f
x
f
!
, то 
1
x
a  
; 
3) если 
)
(
)
(
2
1
x
f
x
f
 
, то 
1
x
a  
,  
2
x
b  
. 
Затем снова вычисляются координаты 
1
x , 
2
x  и продолжается поиск. За оценку пре
b
a
x

 
. 
кращения поиска принимают 
H
d
 a
b
, а за минимальное значение 
2
Подробное описание алгоритма представлено в блок-схеме (рис. 1.4). 
 
10