Методы оптимизации для машинного обучения

 
 
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ  
РОССИЙСКОЙ ФЕДЕРАЦИИ 
РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ 
(РИНХ) 
 
 
 
 
 
Л.В. Сахарова, Г.В. Лукьянова 
 
 
 
 
 
МЕТОДЫ ОПТИМИЗАЦИИ 
ДЛЯ МАШИННОГО ОБУЧЕНИЯ 
 
 
 
 
УЧЕБНОЕ ПОСОБИЕ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ростов-на-Дону 
Издательско-полиграфический комплекс РГЭУ (РИНХ) 
2023 

 
 
УДК 517(075) 
ББК 22.161 
С 22 
 
Авторы: 
Сахарова Л.В., доктор физико-математических наук,  
профессор кафедры фундаментальной и прикладной математики (ФиПМ) РГЭУ (РИНХ); 
Лукьянова Г.В., кандидат технических наук, доцент кафедры фундаментальной  
и прикладной математики (ФиПМ) РГЭУ (РИНХ) 
 
Сахарова, Л.В. 
С 22  Методы оптимизации для машинного обучения : учебное пособие [Электронный 
ресурс] / Л.В. Сахарова, Г.В. Лукьянова. – Ростов-на-Дону : Издательско-полиграфический комплекс Ростовского государственного экономического университета (РИНХ), 2023. – Электрон. сетевое изд. – 87 с. – Режим доступа : 
http://library.rsue.ru. 
 
ISBN 978-5-7972-3139-4  
 
 Учебное пособие содержит теоретический и практический материал курса «Методы оптимизации для машинного обучения». Материал сгруппирован в главы по темам: «Математическое моделирование в оптимизации», «Численные методы решения 
задач одномерной оптимизации» и «Методы безусловной оптимизации функции многих переменных». 
 Пособие предназначено для проведения занятий по курсу дисциплины «Методы 
оптимизации для машинного обучения» для бакалавров и магистрантов дневного и заочного отделения подготовки направления «Прикладная математика и информатика». 
УДК 517(075) 
ББК 22.161 
 
Рецензенты: 
Боев Н.В., д.ф.-м.н., профессор кафедры «Дифференциальные  
и интегральные уравнения» ФГАОУ ВО «Южный федеральный университет»;  
Мисиченко Н.Ю., к.э.н., доцент кафедры  
«Общий и стратегический менеджмент» ФГБОУ ВО «РГЭУ (РИНХ)»  
 
Утверждено в качестве учебного пособия  
учебно-методическим советом РГЭУ (РИНХ) 
 
 
 
ISBN 978-5-7972-3139-4  
© Ростовский государственный  
экономический университет (РИНХ), 2023 
© Сахарова Л.В., Лукьянова Г.В., 2023 

ОГЛАВЛЕНИЕ 
Предисловие ............................................................................................................... 5 
Глава 1 
Математическое моделирование в оптимизации ............................................... 6 
1.1. Определение границ объекта оптимизации ................................................................ 6 
1.2. Выбор управляемых переменных ................................................................................. 7 
1.3. Определение ограничений на управляемые переменные ........................................ 8 
1.4. Выбор числового критерия оптимизации ................................................................... 8 
1.5. Формулировка математической задачи оптимизации .............................................. 9 
Глава 2 
Численные методы решения задач одномерной оптимизации ...................... 10 
2.1. Предварительные сведения.......................................................................................... 10 
2.1.1. Минимум функции одной переменной ................................................... 10 
2.1.2. Унимодальные функции ........................................................................... 12 
2.1.3. Выпуклые функции ................................................................................... 13 
2.1.4. Условие Липшица ...................................................................................... 16 
2.1.5. Классическая минимизация функции одной переменной ..................... 18 
2.2. Прямые методы .............................................................................................................. 19 
2.2.1. Метод перебора .......................................................................................... 20 
2.2.2. Методы исключения отрезков .................................................................. 21 
2.2.3. Метод парабол ........................................................................................... 30 
Глава 3 
Методы безусловной минимизации функций многих переменных .............. 34 
3.1. Предварительные сведения.......................................................................................... 34 
3.1.1. Основные понятия линейной алгебры..................................................... 34 
3.1.2. Минимум функции многих переменных ................................................ 38 
3.1.3. Дифференцируемые функции многих переменных ............................... 38 
3.1.4. Необходимые и достаточные условия минимума  
дифференцируемой функции ............................................................................. 40 
Упражнения ......................................................................................................................... 41 
3.2. Выпуклые множества и выпуклые функции ............................................................ 42 
3.2.1. Свойства выпуклых функций ................................................................... 42 
3.2.2. Выпуклые квадратичные функции .......................................................... 46 
Упражнения ......................................................................................................................... 48 
3.3. Общие принципы n-мерной минимизации ............................................................... 49 
Упражнения .............................................................................................................. 52 
 
 

3.4. Прямые методы безусловной минимизации................................................ 53 
3.4.1. Минимизация по правильному симплексу ............................................. 53 
3.4.2. Поиск точки минимума по деформируемому симплексу ..................... 56 
3.4.3. Метод циклического покоординатного спуска ...................................... 58 
3.4.4. Алгоритм Хука – Дживса .......................................................................... 60 
3.4.5. Методы случайного поиска ...................................................................... 62 
3.4.6. Метод сопряженных направлений ........................................................... 64 
Упражнения ......................................................................................................................... 69 
3.5. Методы безусловной минимизации, использующие производные функции .... 70 
3.5.1. Метод градиентного спуска ...................................................................... 70 
3.5.2. Метод наискорейшего спуска .................................................................. 74 
3.5.3. Метод сопряженных градиентов .............................................................. 75 
3.5.4. Метод Ньютона .......................................................................................... 79 
3.5.5. Квазиньютоновские методы ..................................................................... 81 
Упражнения ......................................................................................................................... 84 
Заключение ............................................................................................................... 85 
Литература ................................................................................................................ 86 
 
 
 
 

Предисловие 
 
 Настоящее пособие соответствует рабочей программе дисциплины «Методы оптимизации для машинного обучения» для бакалавров и магистрантов 
дневного и заочного отделения подготовки направления «Прикладная математика и информатика». 
Оно содержит обзор теории, а также задачи для решения по разделам «Математическое моделирование в оптимизации», «Численные методы решения задач одномерной оптимизации» и «Методы безусловной оптимизации функции 
многих переменных». 
Раздел «Математическое моделирование в оптимизации» является кратким обзором основных понятий теории оптимизации, а также основных этапов 
построения соответствующих математических моделей. 
Раздел «Численные методы решения задач одномерной оптимизации» содержит описание основных понятий теории оптимизации функции одной переменной, а также простейших численных методов поиска минимума функции 
(т.н. прямых методов): метода перебора, метода исключения отрезков, метода 
парабол. 
Раздел «Методы безусловной оптимизации функции многих переменных» 
содержит основные понятия теории функций многих переменных, необходимых 
для понимания принципов n-мерной оптимизации; формулировку этих принципов; описание алгоритмов прямых методов безусловной оптимизации: минимизации по правильному симплексу, поиска точки минимума по деформируемому 
симплексу, метода циклического покоординатного спуска, алгоритма Хука –
Дживса, методов случайного поиска, метода сопряженных направлений; методов безусловной оптимизации, использующих производные функций: метода 
градиентного спуска, метода наискорейшего спуска, метода сопряженных градиентов, метода Ньютона, квазиньютоновских методов. 
 Нумерация задач самостоятельна к каждой главе. Символика и терминология соответствуют учебным пособиям, рекомендуемым программой курса дисциплины «Методы оптимизации для машинного обучения». 
 
 

Глава 1 
 
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В ОПТИМИЗАЦИИ 
 
Оптимизация – это выбор наилучшего решения. Математическая теория 
оптимизации включает в себя фундаментальные результаты и численные методы, позволяющие находить наилучший вариант из множества возможных альтернатив без их полного перебора и сравнения. 
Для того чтобы использовать результаты и вычислительные процедуры 
теории оптимизации на практике, необходимо, прежде всего, сформулировать 
рассматриваемую задачу на математическом языке, т.е. построить математическую модель объекта оптимизации. Математическая модель – это более или менее полное математическое описание исследуемого процесса или явления. 
В большинстве реальных ситуаций дать исчерпывающее математическое 
представление оптимизируемой системы с учетом всех взаимосвязей ее частей, 
взаимодействий с внешним миром, всех целей ее функционирования бывает затруднительно или невозможно. Поэтому при построении математической модели необходимо, как правило, выделять и учитывать в дальнейшем только 
наиболее важные, существенные стороны исследуемого объекта с тем, чтобы 
было возможным его математическое описание, а также последующее решение 
поставленной математической задачи. При этом неучтенные в математической 
модели факторы не должны существенно влиять на окончательный результат оптимизации. Таким образом, математическое моделирование является сложной и 
ответственной творческой задачей, требующей от исследователя глубоких знаний в соответствующей области, практического опыта, интуиции и критического 
анализа получаемых результатов. 
Несмотря на то, что общего рецепта построения математических моделей 
оптимизации не существует, можно условно разбить процесс математического 
моделирования на следующие основные этапы. 
 
 
 
1.1. ОПРЕДЕЛЕНИЕ ГРАНИЦ ОБЪЕКТА ОПТИМИЗАЦИИ 
 
Необходимость этого этапа диктуется невозможностью учета и исчерпывающего описания всех сторон большинства реальных систем. Выделив главные 
переменные, параметры и ограничения, следует приближенно представить систему как некоторую изолированную часть реального мира и упростить ее внутреннюю структуру. 

Например, при оптимизации работы одного из цехов предприятия в некоторых случаях можно пренебречь влиянием особенностей функционирования других цехов, систем снабжения и сбыта всего предприятия, его взаимодействием с 
другими организациями, конъюнктурой рынка и многими другими факторами. 
Тогда цех будет рассматриваться как изолированная система, а его связи с внешним миром либо считаются зафиксированными, либо вовсе не учитываются. 
Может оказаться, что первоначальные границы объекта оптимизации выбраны неудачно. Это становится ясным при дальнейшем анализе системы и ее 
математической модели, при интерпретации результатов поиска оптимального 
решения, сопоставлении их с практикой и т.д. 
Тогда в одних случаях границы системы следует расширить, а в других – 
сузить. Например, если выясняется, что влияние на работу исследуемого цеха 
других подразделений предприятия нельзя игнорировать при ее оптимизации, то 
необходимо включить в систему и эти подразделения. С другой стороны, может 
оказаться, что сам цех состоит из нескольких, в большой степени независимо работающих участков, которые без значительного упрощения реальной ситуации 
можно рассматривать изолированно. Тогда, для облегчения поиска оптимального решения разумно исследовать каждый участок, как отдельную систему. 
В инженерной практике следует, насколько возможно, стремиться упрощать системы, подлежащие оптимизации, разбивать сложные системы на более 
простые подсистемы, если есть уверенность, что это повлияет на окончательный 
результат в допустимых пределах. 
 
 
 
1.2.  ВЫБОР УПРАВЛЯЕМЫХ ПЕРЕМЕННЫХ 
 
На этом этапе математического моделирования необходимо провести различие между теми величинами, значения которых можно варьировать и выбирать с целью достижения наилучшего результата (управляемыми переменными), 
и величинами, которые фиксированы или определяются внешними факторами. 
Определение тех значений управляемых переменных, которым соответствует 
наилучшая (оптимальная) ситуация, и представляет собой задачу оптимизации. 
Одни и те же величины, в зависимости от выбранных границ оптимизируемой системы и уровня детализации её описания, могут оказаться либо управляемыми переменными, либо нет. Например, в упомянутой ситуации с оптимизацией работы цеха объем поставок какого-либо сырья из другого цеха в одних 
случаях следует считать фиксированным или не зависящим от нашего выбора, а 
в других случаях – регулируемым, т.е. управляемой переменной. 

1.3. ОПРЕДЕЛЕНИЕ ОГРАНИЧЕНИЙ  
НА УПРАВЛЯЕМЫЕ ПЕРЕМЕННЫЕ 
 
В реальных условиях на выбор значений управляемых переменных, как 
правило, наложены ограничения, связанные с ограниченностью имеющихся ресурсов, мощностей и других возможностей. При построении математической модели эти ограничения обычно записывают в виде равенств и неравенств или указывают множества, которым должны принадлежать значения управляемых переменных. Совокупность всех ограничений на управляемые переменные определяет так называемое допустимое множество задачи оптимизации. 
Например, если годовой объем выпускаемой цехом продукции данного 
вида является управляемой переменной, то ее значения, во-первых, не могут 
быть отрицательными, во-вторых, ограничены сверху максимальной производительностью оборудования цеха. 
 
 
 
1.4. ВЫБОР ЧИСЛОВОГО КРИТЕРИЯ ОПТИМИЗАЦИИ 
 
Обязательной составной частью математической модели объекта оптимизации является числовой критерий, минимальному или максимальному значению которого (в зависимости от конкретной задачи) соответствует наилучший 
вариант поведения исследуемого объекта. Величина этого критерия полностью 
определяется выбранными значениями управляемых переменных, т.е. он является функцией этих переменных и называется целевой функцией. 
В инженерной практике используется широкий спектр критериев оптимизации. 
Это могут быть критерии экономического характера, например, себестоимость, прибыль, капитальные затраты и т.д., технические или физические параметры системы – 
продолжительность технологического процесса, потребляемая энергия, максимальная 
механическая нагрузка, достигнутая скорость движения и другие. 
Следует отметить, что во многих случаях выбор критерия оптимизации не является очевидным и однозначным. Часто бывает трудно поставить в соответствие 
всей совокупности целей функционирования системы какой-либо один критерий. 
Это объясняется различными причинами, такими, как сложность целевой функции, 
описывающей большую совокупность разнородных целей, неопределенность формулировок некоторых целей, препятствующая описанию их с помощью количественных характеристик, наличие противоречивых целей, важность каждой из кото

рых зависит от точки зрения и т.д. Например, невозможно найти решение, обеспечивающее одновременно минимальные затраты, максимальную надежность, минимальное энергопотребление и максимальное быстродействие. 
Выход из этого положения определяется в каждом конкретном случае. 
Например, из многих критериев, характеризующих различные цели оптимизации, выбирают один, считая его основным, а остальные – второстепенными. Далее второстепенные критерии либо не учитываются, либо учитываются частично 
с помощью дополнительных ограничений на управляемые переменные. Эти 
ограничения обеспечивают изменение второстепенных критериев в заданных 
диапазонах приемлемых значений. 
Другой путь состоит в формулировке комплексного критерия, т.е. целевой 
функции, включающей с разумно выбранными весовыми коэффициентами целевые функции, соответствующие различным целям. 
 
 
 
1.5. ФОРМУЛИРОВКА  
МАТЕМАТИЧЕСКОЙ ЗАДАЧИ ОПТИМИЗАЦИИ 
 
Объединяя результаты предыдущих этапов построения математической 
модели, ее записывают в виде математической задачи оптимизации, включающей построенную целевую функцию и найденные ограничения на управляемые 
переменные. В достаточно общем виде математическую задачу оптимизации 
можно сформулировать следующим образом: минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные. 
Под минимизацией (максимизацией) функции п переменных f (x) = (x1 ,.., xn) 
на заданном множестве U n-мерного векторного пространства Еn понимается 
определение хотя бы одной из точек минимума (максимума) этой функции на 
множестве U, а также, если это необходимо, и минимального (максимального) 
на множестве U значения f (x). При записи математических задач оптимизации в 
общем виде обычно используется следующая символика: 
 
f(x) min (max), 
х U 
где f (x) – целевая функция, а U – допустимое множество, заданное ограничениями на управляемые переменные.