ЗАДАЧИ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

​CONVEX PROGRAMMING PROBLEMS

Bagautdinov Rafael Ilnurovich

Student, Faculty of Engineering and Economics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

Kireev Sergey Vladimirovich

Scientific supervisor, PhD in Physics. - Mat. of Sciences, Associate Professor of the Department of Higher Mathematics, Ulyanovsk State Technical University,

Russia, Ulyanovsk

АННОТАЦИЯ

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

ABSTRACT

The paper considers a class of mathematical programming problems with a convex objective function and a convex feasible region. Definitions of a convex set and a convex function are given, along with reasons why such problems admit efficient numerical solutions. Two examples illustrate the construction of the feasible region and the search for an optimum with boundary verification.

Ключевые слова: выпуклое программирование; выпуклое множество; выпуклая функция; целевая функция; область допустимых решений; глобальный минимум.

Keywords: convex programming; convex set; convex function; objective function; feasible region; global minimum.

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

Класс задач с выпуклой целевой функцией и выпуклой допустимой областью обладает редким для оптимизации свойством: любой найденный локальный минимум совпадает с глобальным. Именно поэтому существуют надёжные численные методы, такие как градиентный спуск, метод Ньютона и метод внутренних точек, которые гарантированно сходятся к решению за разумное время [1, с. 18]. Невыпуклые задачи такой гарантии не дают, и приходится прибегать к эвристикам или полному перебору. Ниже излагается необходимый минимум определений и разбираются две учебные задачи, на которых видна вся схема решения целиком.

1. Выпуклые множества и выпуклые функции

Множество называется выпуклым, если вместе с любыми двумя своими точками оно содержит и весь соединяющий их отрезок. Формально: для любых точек A и B из множества и любого числа λ ∈ [0; 1] точка

                      (1)

тоже принадлежит этому множеству [2, с. 92]. Геометрически здесь нет внутренних провалов или вырезов, через которые отрезок мог бы выйти наружу. Круг, шар, прямоугольник, куб, полуплоскость, вся плоскость, все эти объекты выпуклы. Пересечение нескольких выпуклых множеств снова даёт выпуклое множество, и это удобно: ограничения задачи, заданные линейными неравенствами, автоматически выкраивают выпуклый многогранник. А вот объединение двух непересекающихся кругов уже не выпукло, потому что отрезок между точками разных кругов пройдёт через пустоту.

Функция f(x) называется выпуклой на своей области определения, если для любых двух точек x и y и любого λ ∈ [0; 1] выполняется неравенство:

         (2)

По смыслу хорда, соединяющая две точки графика, проходит не ниже самого графика [3, с. 56]. Парабола y = x² ведёт себя именно так: при x = −2 и x = 2 значения функции равны 4, хорда лежит на высоте 4, а сам график между этими точками опускается до нуля. Экспонента, модуль и любая линейная функция тоже выпуклы. Линейная функция вырожденный случай, она одновременно и выпуклая, и вогнутая, потому что её график совпадает с собственной хордой. Если поменять знак, получится вогнутая функция в форме перевёрнутой чаши: хорда между точками на её склонах пойдёт под графиком, а вершина окажется выше любой такой хорды.

Ключевое свойство выпуклой функции состоит в том, что любая её точка локального минимума автоматически оказывается точкой глобального минимума. У чаши нет других углублений, кроме главного: куда бы шарик ни закатился, он попадёт на дно. Для вогнутой функции аналогичное свойство работает для максимума [2, с. 124].

2. Постановка задачи выпуклого программирования

Стандартная запись задачи имеет вид: минимизировать f(x) при ограничениях:

(3)

Чтобы задача была выпуклой, требуется одновременное выполнение трёх условий. Целевая функция f(x) выпукла. Каждая функция g_i(x) в ограничении-неравенстве тоже выпукла. Все ограничения-равенства h_j(x) аффинные, то есть имеют вид aᵀx + b = 0 [4, с. 47].

Последнее требование часто вызывает вопрос: почему равенство обязательно линейное. Причина в форме множества решений. Нелинейное равенство x² + y² = 1 задаёт окружность, а окружность не выпукла. Допусти такие равенства, и допустимая область перестанет быть выпуклой, теряется главное свойство, ради которого вся постановка и затевается.

Когда условия выпуклости соблюдены, задача становится «хорошо поставленной». При замкнутой и ограниченной допустимой области решение гарантированно существует, локальные ловушки отсутствуют, а численные методы дают сходимость с теоретическими оценками [3, с. 211]. Дальше разбираются две задачи, в которых эта схема разворачивается на конкретных функциях.

3. Задача а): минимизация смещённого параболоида

Целевая функция имеет вид:

          (4)

Это параболоид вращения с минимумом в точке (1; 1) и значением F(1; 1) = 2. Линии уровня F = const представляют собой концентрические окружности с центром в (1; 1), радиус которых равен √(C − 2). При F = 2 окружность вырождается в точку, при F = 3 имеет радиус 1, при F = 4 радиус √2 ≈ 1,41.

Ограничения задают пересечение четырёх множеств: круг x² + y² ≤ 4 радиуса 2 с центром в начале координат, полуплоскость x ≤ 2y, полуплоскость y ≤ 2x, первый квадрант x ≥ 0, y ≥ 0. Прямая x = 2y проходит через начало координат и точку (2; 1), прямая y = 2x через начало и точку (1; 2). Вместе они вырезают узкий сектор между двумя лучами, а окружность срезает его сверху и справа.

Поиск вершин области сводится к пересечению пар границ. Подстановка x = 2y в уравнение окружности даёт 5y² = 4, откуда y = 2/√5 ≈ 0,89 и x ≈ 1,79. Аналогично для y = 2x: 5x² = 4, x ≈ 0,89, y ≈ 1,79. Прямые x = 2y и y = 2x пересекаются только в начале координат. Из точек пересечения с осями (2; 0) и (0; 2) лишь первая удовлетворяет всем ограничениям, вторая нарушает условие y ≤ 2x. Итог: криволинейный четырёхугольник с вершинами (0; 0), (2; 0), (1,79; 0,89), (0,89; 1,79). Соответствующее построение приведено на рисунке 1.

Рисунок 1. Область допустимых решений и линия уровня F = 3 в задаче а)

Точка минимума целевой функции (1; 1) проверяется на принадлежность области: 1² + 1² = 2 ≤ 4 выполняется, 1 ≤ 2 · 1 верно в обе стороны, неотрицательность тоже соблюдена. Значит, минимум лежит внутри допустимой области, ближайшая к (1; 1) линия уровня само вырожденное «окружность нулевого радиуса». Оптимальное решение:

              (5)

4. Задача б): максимизация вогнутой функции

Целевая функция:

                           (6)

вогнута: коэффициенты при квадратах отрицательны, и график представляет собой перевёрнутый параболоид с максимумом в точке (0; 0), где F(0; 0) = 2. Линии уровня окружности x² + y² = 2 − C с центром в начале координат, и чем меньше радиус, тем больше значение функции.

Ограничения: y ≤ 4 − x² (область под параболой с вершиной в (0; 4)), x + y ≥ 1 (полуплоскость над прямой y = 1 − x), x ≥ 0, y ≥ 0. Парабола пересекает оси в точках (0; 4) и (2; 0), прямая x + y = 1 в точках (0; 1) и (1; 0). Внутри первого квадранта парабола и прямая не пересекаются: уравнение 4 − x² = 1 − x приводит к x² − x − 3 = 0, корни ≈ 2,30 и ≈ −1,30, оба вне нужной области. Вершины допустимой области образуют четырёхугольник (0; 1), (0; 4), (2; 0), (1; 0), что видно на рисунке 2.

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

Точка глобального максимума (0; 0) ограничению x + y ≥ 1 не удовлетворяет, поэтому максимум приходится искать на границе. В угловых точках значения функции таковы: F(0; 1) = 1, F(0; 4) = −14, F(2; 0) = −2, F(1; 0) = 1. Два равных максимума в (0; 1) и (1; 0) подсказывают, что между ними по отрезку x + y = 1 может быть значение ещё больше. Подстановка y = 1 − x даёт

      (7)

производная 2 − 4x обнуляется в x = 0,5. Точка (0,5; 0,5) принадлежит области, в ней F = 1,5.

Остаётся проверить параболическую часть границы y = 4 − x². Подстановка даёт F = −x⁴ + 7x² − 14, производная −4x³ + 14x обнуляется в x = 0 и x ≈ 1,87. При x ≈ 1,87 получается F ≈ −1,8, что меньше уже найденного значения. Окончательный ответ:

(8)

Заключение

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

Список литературы:

1. Бойд С., Ванденберг Л. Выпуклая оптимизация. – М.: Книжный дом «ЛИБРОКОМ», 2017. – 596 с.
2. Поляк Б. Т. Введение в оптимизацию. – 2-е изд., испр. и доп. – М.: ЛЕНАНД, 2014. – 384 с.
3. Васильев Ф. П. Методы оптимизации: в 2 кн. – М.: МЦНМО, 2011. – Кн. 1. – 620 с.
4. Сухарев А. Г., Тимохов А. В., Фёдоров В. В. Курс методов оптимизации: учеб. пособие. – 2-е изд. – М.: ФИЗМАТЛИТ, 2005. – 368 с.