Вектор оптимума: Градиентный метод для поиска лучших решений

Вектор оптимума: Градиентный метод для поиска лучших решений

Михаил Ночесвет

От практической задачи к задаче оптимизации: переменные, цель и ограничения

В шесть утра в пекарне пахнет дрожжами, кофе и лёгкой паникой. У дверей уже ждут первые покупатели. На полке, где должен лежать хлеб, — пустота. На соседнем подносе остались вчерашние булочки: к обеду они, скорее всего, станут ещё менее желанными. Хозяйка пекарни Марина смотрит на очередь и пытается вспомнить, сколько всего испекли в прошлый вторник. «Кажется, хлеба было мало. А круассанов, наоборот, многовато».

Вчера она планировала выпечку примерно так же. И позавчера. Каждый раз — на основе опыта, памяти и того самого «кажется». Опыт полезен, но память сглаживает детали: очередь в один день запоминается лучше, чем тихое утро в другой. Марине нужно не просто «работать лучше». Ей нужно каждое утро решить, сколько изготовить хлеба, булочек и круассанов, чтобы заработать, не остаться без популярных товаров и не выбросить остатки.

Это уже задача, которую можно разобрать. Но начинать следует не с градиента, формулы или программы. Начинать нужно с вопроса: какое именно решение мы выбираем?

1. Сначала — решение, потом математика

Марина управляет количеством выпечки на сегодня. Обозначим число произведённых буханок через \(qh\), булочек — через \(qb\), круассанов — через \(qc\). Буква \(q\) напоминает о количестве, а индексы помогают не путать продукты.

Но произведённое не всегда равно проданному. Если испечь 30 булочек, а купить готовы только 24, шесть останутся. Поэтому введём ещё три переменные: \(sh\), \(sb\), \(sc\) — сколько единиц каждого товара будет продано.

Так мы отделяем два разных решения и события: сколько изготовить и сколько продать. Это не педантизм ради букв. Именно в промежутке между ними возникают непроданные остатки.

Здесь важно отличать переменные решения от параметров модели. Переменные — то, что Марина выбирает. Параметры — данные, которые она пока считает известными: цена продукта, расход муки, доступное время. Например, цену хлеба Марина сегодня не выбирает в задаче о плане выпечки; она получает её из действующего прайс-листа. Поэтому цена — параметр, а количество буханок — переменная.

2. Что известно, а что нужно решить

Для первого приближения Марина собирает данные за утреннюю смену. Расход времени указан как среднее число минут производственной работы на одну единицу продукции. В реальной пекарне часть операций идёт параллельно; пока мы объединим их в один показатель, чтобы построить понятную начальную модель.

Продукт

Цена продажи, руб.

Переменные затраты, руб.

Время, мин.

Мука, кг

Масло, кг

Прогноз спроса, шт.

Хлеб

160

60

12

0,50

0,02

40

Булочка

70

25

4

0,10

0,02

80

Круассан

130

85

8

0,12

0,06

35

На смену у Марины есть не более 360 минут производственного времени, 24 килограммов муки и 3 килограммов масла. Это параметры ресурсов: в плане на сегодня они заданы. Если завтра поставка масла задержится, число изменится — и вместе с ним изменится задача.

Ещё один параметр — прогноз спроса. Он говорит, сколько товара, по оценке Марины, удастся продать. Это не точное пророчество и не обязательно жёсткий закон природы; на первом шаге мы просто не планируем продаж больше, чем ожидаемый спрос. Позже можно будет учесть неопределённость подробнее.

3. Цель должна измеряться

«Хочу, чтобы день прошёл лучше» — хорошее человеческое желание, но плохая математическая цель. Модель должна понимать, что именно считать успехом. Для Марины естественная первая цель — максимизировать прибыль от сегодняшней выпечки.

Если единица товара продана, пекарня получает выручку. Если она произведена, возникают затраты — даже когда продукт так и не купили. Поэтому выручка зависит от продаж \(s\), а производственные расходы — от количества изготовленного \(q\):

\[ \max \ \Pi = 160sh+70sb+130sc -60qh-25qb-85qc. \]

Здесь \(\Pi\) — прибыль за смену, измеряемая в рублях. Слово «максимизировать» означает: среди допустимых планов выбрать тот, у которого значение \(\Pi\) наибольшее.

Почему нельзя просто максимизировать выручку? Потому что высокая цена ещё не означает высокую прибыль. Один круассан приносит 130 рублей выручки, а одна булочка — 70. Но переменные затраты на круассан составляют 85 рублей, на булочку — 25. После вычета затрат в обоих случаях остаётся по 45 рублей. При этом круассан требует вдвое больше времени и втрое больше масла. Если поставить целью одну только выручку, модель будет считать круассан гораздо привлекательнее, чем он выглядит с точки зрения заработка и ресурсов.

Это типичная ловушка: оптимизировать измеримый показатель, который лишь похож на настоящее желание. Иногда компании максимизируют число заказов, хотя важна прибыль; люди сокращают время поездки, не замечая стоимости дороги; пекарня печёт больше, полагая, что «больше продаж» автоматически означает «лучший день».

У цели должен быть ясный смысл. Если Марина хочет прежде всего увеличить прибыль — мы записываем прибыль. Если для неё критично, чтобы к обеду на полке был хлеб, это тоже важно, но такую заботу нельзя незаметно растворить в слове «успех». Её нужно выразить отдельно.

4. Ограничения очерчивают допустимое

Целевая функция отвечает на вопрос: какой результат предпочитаем? Ограничения отвечают на другой вопрос: какие планы вообще возможны?

Например, на производство нельзя потратить больше имеющегося времени:

\[ 12qh+4qb+8qc \leq 360. \]

Каждый коэффициент показывает, сколько минут требуется на одну единицу продукта. Если Марина планирует 10 буханок, это 120 минут; 20 булочек — ещё 80; 5 круассанов — ещё 40. Левая часть суммирует время всех изделий. Знак \(\leq\) означает: можно потратить меньше доступного, но нельзя больше.

По той же логике записываются запасы ингредиентов:

\[ 0{,}50qh+0{,}10qb+0{,}12qc \leq 24 \]

для муки и

\[ 0{,}02qh+0{,}02qb+0{,}06qc \leq 3 \]

для масла.

Продать больше, чем изготовлено, нельзя:

\[ sh\leq qh,\qquad sb\leq qb,\qquad sc\leq qc. \]

А прогноз спроса ограничивает возможные продажи:

\[ sh\leq40,\qquad sb\leq80,\qquad sc\leq35. \]

Наконец, количества не могут быть отрицательными. И в обычной пекарне нельзя выпустить 3,7 буханки, поэтому для точной модели количества целые:

\[ qh,qb,qc,sh,sb,sc\in\mathbb{Z}{\geq0}. \]

Все эти условия вместе и есть ограничения модели.

Обратите внимание: ограничение не обязательно выражает нехватку. Оно может отражать обязательство. Если Марина решила, что хлеб должен оставаться в ассортименте и каждый день нужно произвести не менее 20 буханок, можно добавить условие \(qh\geq20\). Но это уже осознанный выбор: такой минимум защищает ассортимент, зато может увеличить остатки. Математика не решает, важен ли хлеб покупателям. Она помогает точно показать, что произойдёт, если Марина внесёт это требование в план.

5. Собираем модель целиком

Полная начальная постановка выглядит так:

\[ \begin{aligned} \max \quad &160sh+70sb+130sc -60qh-25qb-85qc,\\ \text{при условиях}\quad &12qh+4qb+8qc\leq360,\\ &0{,}50qh+0{,}10qb+0{,}12qc\leq24,\\ &0{,}02qh+0{,}02qb+0{,}06qc\leq3,\\ &0\leq si\leq qi,\qquad i\in\{h,b,c\},\\ &sh\leq40,\quad sb\leq80,\quad sc\leq35,\\ &qi,si\in\mathbb{Z}{\geq0}. \end{aligned} \]

У этой записи есть простое прочтение: выбери целые объёмы производства и продаж так, чтобы не превысить время и запасы, не продавать несуществующий товар и не рассчитывать на спрос выше прогноза; среди всех таких планов найди тот, который даёт наибольшую прибыль.

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

6. Карточка модели: проверка перед расчётом

Прежде чем искать лучший план, Марина сводит постановку в короткую карточку.

Поле карточки

Модель пекарни

Что выбираем

Сколько произвести и сколько продать каждого продукта

Что улучшаем

Прибыль за утреннюю смену, рубли

Что нельзя нарушать

Запасы времени, муки и масла; продажи не выше производства и прогноза спроса

Единицы измерения

Штуки, минуты, килограммы, рубли

Основные допущения

Цены и затраты постоянны в течение смены; время на единицу усреднено; спрос ограничен прогнозом; остатки не имеют ценности

Какие данные неизвестны или неточны

Фактический спрос, изменение времени работы, возможные скидки, стоимость утилизации остатков

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

У прогноза спроса есть и менее заметная ловушка. Если хлеб закончился к десяти утра, данные о продажах покажут, сколько хлеба успели продать, а не сколько покупатели хотели бы купить за весь день. Пустая полка скрывает неудовлетворённый спрос. Поэтому Марине полезно отдельно записывать случаи, когда товар закончился до конца смены. Иначе модель может сделать аккуратный вывод из неполных данных: «сорока буханок не нужно», потому что в журнале продаж их никогда и не было.

7. Проверка здравого смысла

До сложных расчётов стоит проверить, не противоречит ли модель сама себе. Например, план из 80 булочек и 3 буханок требует:

• 356 минут: \(80\cdot4+3\cdot12\);

• 9,5 килограмма муки: \(80\cdot0{,}10+3\cdot0{,}50\);

• 1,66 килограмма масла: \(80\cdot0{,}02+3\cdot0{,}02\).

Он укладывается в заданные запасы и не превышает прогноз спроса. Если считать, что всё произведённое продаётся, прибыль такого плана составит \(80\cdot45+3\cdot100=3900\) рублей. Это не доказательство, что план лучший. Это лишь проверка, что числа и ограничения прочитаны правильно.

Полезны и другие короткие тесты.

1. Проверить размерности. В уравнении времени число минут на штуку умножается на количество штук, а результат измеряется минутами. Если в одной части ограничения внезапно сложились рубли и килограммы, ошибка видна ещё до запуска алгоритма.

2. Проверить знаки. Дополнительные продажи обычно увеличивают прибыль, а дополнительные производственные расходы — уменьшают. Если затраты в целевой функции стоят со знаком «плюс», стоит остановиться и выяснить почему.

3. Проверить крайний случай. Нулевое производство должно быть допустимым, если в модели нет обязательного минимума. Если оно запрещено, должна быть понятная причина.

4. Сравнить модель с реальностью. Может ли пекарь действительно изготовить рассчитанное количество за указанное время? Есть ли в таблице упаковка, уборка, прогрев печи? Не учтено ли одно и то же время дважды?

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

8. Где заканчиваются данные и начинаются решения

Числа в таблице не одинаково надёжны. Цена продажи известна точно. Средний расход муки, вероятно, довольно стабилен. А спрос на завтра — оценка. Полезно не складывать их в одну кучу, будто все они — одинаково твёрдые факты.

Если спрос на круассаны колеблется от 15 до 35 штук, можно использовать осторожный прогноз, сравнить несколько сценариев или задать запас на случай высокого спроса. Если время на изготовление зависит от загрузки печи, одного ограничения по минутам может быть недостаточно: понадобится отдельная мощность оборудования. Если товар быстро теряет привлекательность, для разных изделий могут потребоваться разные ограничения на запас или срок продажи.

Это не означает, что первая модель обязана описать каждую крошку и минуту. Слишком подробная модель бывает так же неудобна, как карта, на которой нарисован каждый камешек. Хорошее начало — достаточная точность для важного решения и явное перечисление того, что пока упрощено.

Есть ещё одно существенное упрощение: количества в пекарне целые, а базовый градиентный метод работает с непрерывными переменными и предполагает, что функцию можно гладко менять. Нельзя бездумно выдать результат «21,6 буханки», округлить его до 22 и считать задачу решённой: после округления можно нарушить ограничение по времени или ингредиентам. Для целочисленных решений нужны специальные приёмы, допустимое приближение или метод, подходящий для целых переменных. Но выбирать способ решения имеет смысл только после того, как сама задача сформулирована честно.

9. Переносим способ на домашнюю задачу

Тот же подход годится не только для пекарни. Представьте, что вы планируете меню на рабочую неделю. Не начинайте с вопроса «как питаться идеально?». Сформулируйте решение конкретнее.

1. Что выбираем? Количество порций каждого блюда.

2. Что измеряем? Общую стоимость покупок или время готовки — это возможные цели.

3. Что нельзя нарушать? Бюджет, доступное время, необходимые ограничения рациона.

4. Какие данные известны не точно? Цена в магазине, срок хранения, вероятность того, что в пятницу вы действительно захотите приготовить запланированное.

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

Попробуйте прямо сейчас выбрать небольшую бытовую задачу — например, собрать план поездки, распределить время подготовки к экзамену или решить, сколько продуктов купить. Запишите одной строкой: что вы выбираете, что считаете успехом, какие условия нельзя нарушить и какие данные лишь предполагаете. Если для ответа приходится использовать слова «удобно», «много» или «достаточно», спросите себя: как я узнаю, что именно это произошло?

От догадки — к ясному вопросу

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

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

А когда вопрос сформулирован, появляется следующий: как устроен ландшафт этой цели — какие значения лучше, где лежат допустимые решения и насколько легко двигаться к улучшению? Именно с этого начинается разговор о рельефе целевой функции.

Рельеф целевой функции: уровни, выпуклость и обусловленность

В 23:40 команда инженеров в третий раз запускает настройку модели. На экране — две ручки. Первая почти не меняет ошибку: её можно крутить долго, и показатель плавно ползёт вниз. Вторая будто связана с пружиной: чуть сдвинешь — ошибка резко меняется, а иногда и подскакивает. «Значит, второй параметр важнее», — говорит кто-то. Но инженер, который смотрит на график, качает головой: возможно, параметр не важнее. Возможно, поверхность задачи просто устроена так, что в одном направлении она пологая, а в другом — крутая.

Представьте, что целевая функция — это рельеф, а каждая настройка модели задаёт координату на карте. Высота в точке — значение ошибки. Наша задача — найти низину. Но карта не видна напрямую: мы можем лишь менять параметры и измерять результат. Линии уровня помогают восстановить её форму. Именно форма рельефа объясняет, почему градиентный метод в одной задаче скользит к минимуму уверенно, а в другой мечется, словно пытается пройти по узкой тропе в тумане.

Контуры на невидимой карте

Линия уровня соединяет все точки, где целевая функция имеет одно и то же значение:

\[ f(x,y)=c. \]

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

Для простейшей круглой чаши

\[ f(x,y)=\frac12(x^2+y^2) \]

линии уровня — окружности:

\[ x^2+y^2=2c. \]

Чем ближе к центру, тем ниже значение функции. Со всех сторон к центру ведёт одинаковый склон. Это симметричная, удобная для поиска местность: ни одному направлению не отдано предпочтение.

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

Есть важная оговорка: линия уровня — не сама долина, а лишь её горизонтальный контур. Ещё полезнее смотреть на область под уровнем,

\[ \{(x,y): f(x,y)\le c\}, \]

то есть на все точки, где значение не выше \(c\). Для выпуклой функции такие области выпуклы. А вот отдельная линия \(f=c\) не обязана быть выпуклой или даже выглядеть как одна простая замкнутая петля.

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

Что даёт выпуклость

Слово «выпуклость» описывает не просто красивую чашу на картинке, а точное свойство функции. Функция выпукла на некоторой области, если для любых двух точек \(a\) и \(b\) и любого числа \(0\le\lambda\le1\) выполняется условие

\[ f(\lambda a+(1-\lambda)b) \le \lambda f(a)+(1-\lambda)f(b). \]

Если соединить значения функции в точках \(a\) и \(b\) прямой, график выпуклой функции между ними не поднимется выше этой прямой. В одном измерении это похоже на чашу. В нескольких измерениях такой проверки нужно придерживаться вдоль каждого возможного отрезка внутри рассматриваемой области.

Зачем это оптимизатору? У выпуклой функции нет ложных локальных минимумов: всякий локальный минимум является глобальным. Иными словами, если мы нашли точку, из которой ни в одном достаточно близком направлении нельзя спуститься ниже, то ниже неё нигде на выпуклой области уже не будет. Это очень сильная гарантия.

Но выпуклость не означает, что минимум обязательно один. Например, функция \(f(x,y)=x^2\) выпукла, но её минимум достигается во всех точках прямой \(x=0\). Для единственного минимума нужны дополнительные условия. Строгая выпуклость гарантирует, что минимум, если он существует, не может быть более чем в одной точке. Сильная выпуклость добавляет ещё более полезное свойство: у функции есть минимальная кривизна, то есть она не становится совершенно плоской ни в одном направлении.

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

Гарантии выпуклости относятся к области, которую мы рассматриваем. Если задача ограничена, значение имеют не только функция, но и множество допустимых решений: для стандартных глобальных гарантий оно тоже должно иметь подходящую выпуклую структуру. А если функция невыпукла, градиентный метод всё ещё может быть полезен, однако обещать, что найденная впадина окажется самой глубокой во всей местности, уже нельзя. Он может остановиться в локальном минимуме; также его способны задержать плоский участок или седловая область.

Круглая чаша и узкая долина

Вернёмся к команде инженеров. Чтобы увидеть разницу между удобной и неудобной геометрией, сравним круглую чашу с вытянутой долиной. В круглой чаше линии уровня похожи на окружности, а склон во всех направлениях меняется сходным образом. В долине контуры растянуты: в одном направлении функция меняется резко, в другом — очень медленно.

Покажем это на двумерном квадратичном примере, который можно проследить вручную. Введём две взаимно перпендикулярные координаты:

\[ u=\frac{x+y}{\sqrt2}, \qquad v=\frac{x-y}{\sqrt2}, \]

и зададим функцию

\[ f(x,y)=\frac12(u^2+100v^2). \]

Координата \(u\) идёт вдоль долины, а \(v\) — поперёк неё. Вдоль долины кривизна равна \(1\), поперёк — \(100\). Поэтому для одного и того же уровня линии образуют эллипсы: длинная ось направлена вдоль \(u\), короткая — вдоль \(v\). Отношение их полуосей равно \(10:1\). Долина проходит по диагонали \(x=y\) и сужается к минимуму в начале координат.

Теперь запустим градиентный спуск. В координатах \(u,v\) его шаги особенно наглядны:

\[ u{k+1}=(1-\alpha)uk, \qquad v{k+1}=(1-100\alpha)vk, \]

где \(\alpha\) — размер шага. Начнём из точки \((x,y)=(1,0)\). Тогда \(u0=v0=1/\sqrt2\). Возьмём \(\alpha=0{,}018\). Множитель вдоль долины будет \(0{,}982\): продвижение медленное. Поперёк долины множитель равен \(-0{,}8\): знак меняется, и точка перескакивает через линию \(x=y\).

После первого шага координаты примерно равны \((0{,}09;\,0{,}89)\), после второго — \((0{,}80;\,0{,}16)\). Точка ходит то на одну, то на другую сторону узкой долины. При этом значение функции уменьшается — алгоритм не заблудился, но движение выглядит зигзагообразным. Поперечное колебание постепенно затухает, а продвижение к минимуму вдоль долины остаётся неторопливым.

Почему не взять гораздо меньший шаг, чтобы не перескакивать через стенки долины? Можно. Но тогда каждый шаг будет безопаснее поперёк, а продвижение вдоль длинного направления станет ещё медленнее. Если, напротив, выбрать шаг, подходящий для пологого направления, можно сделать скачок слишком большим в направлении крутой стенки. При чрезмерном шаге алгоритм способен не просто перескакивать через долину, а расходиться.

В этом и состоит практическая неприятность вытянутых контуров: одному размеру шага приходится обслуживать направления с очень разной кривизной. Круглая чаша прощает больше. Узкая долина требует осторожности и часто выигрывает от изменения масштаба переменных, подбора шага или более совершенной схемы поиска.

Обусловленность: насколько сильно вытянута задача

Для квадратичной функции кривизну описывает матрица вторых производных — матрица Гессе. У нашей долины её собственные значения равны \(1\) и \(100\): это кривизны вдоль главных направлений. Их отношение