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

CONVEX PROGRAMMING PROBLEMS

Sirunyan Lolita Yuryevna

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

Russia, Ulyanovsk

АННОТАЦИЯ

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

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

ABSTRACT

This work discusses the theoretical foundations and practical applications of convex programming, a branch of optimization that studies problems where the objective function and the feasible region are convex. The first part introduces key concepts in detail: convex sets (with examples of a circle, a square, and a half-plane), convex functions and their geometric interpretation as a "bowl," as well as the classical form of a convex programming problem with inequality constraints (convex) and equality constraints (affine). The importance of convexity is justified to ensure the existence and uniqueness of a global minimum, the absence of false local optima, and the applicability of efficient numerical methods (gradient descent, Newton's method).

The second part demonstrates the full course of the solution on two specific examples: for a convex quadratic function with a minimum inside the admissible domain (circle, linear constraints, first quadrant) and for a concave function where the maximum is reached on the boundary. The construction of the admissible solution domain, the finding of the vertices, the analysis of the optimality point belonging, and, if necessary, the study on the boundaries (including the parametrization of a segment and a parabola arc) are performed in detail. The work clearly illustrates why convexity turns a difficult global optimization problem into a well-posed problem, and also shows the difference in approaches when solving minimum and maximum problems with a concave objective function.

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

Keywords: convex programming, convex set, convex function, global minimum, local optimum, domain of admissible solutions, objective function, problem constraints.

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

Определение выпуклого множества основывается на том, что для произвольных двух точек внутри этого множества весь отрезок, соединяющий их, также принадлежит ему. Формально это выражается так: если точки A и B принадлежат множеству, а параметр λ принимает значения от 0 до 1, то точка C, вычисляемая по формуле C = λA + (1−λ)B, находится внутри того же множества. Отсутствие внутренних пустот или впадин в выпуклой области обеспечивает возможность перемещения по прямой линии между любыми двумя допустимыми точками, не покидая границ множества. В качестве примеров таких объектов можно привести круг, квадрат, полуплоскость, всю плоскость и аффинные пространства.

Функция f(x) считается выпуклой, если для любых точек x и y из области определения и для каждого λ в диапазоне от 0 до 1 выполняется неравенство f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y). С геометрической точки зрения это означает, что график функции располагается не выше хорды, соединяющей две точки на графике, либо совпадает с ней. В противоположность этому, для вогнутых функций характерно расположение графика выше соответствующей хорды. Визуально выпуклая функция напоминает U-образную кривую, подобную чаше, где вся кривая находится под прямой, соединяющей две крайние точки. Вогнутая функция, похожая на перевернутую чашу или холм, характеризуется тем, что хорда проходит ниже максимума, расположенному выше всех таких линий. К классическим примерам выпуклых функций относятся f(x) = x², f(x) = eˣ и f(x) = |x|, графики которых представляют собой параболу с ветвями вверх, экспоненту с ускоряющимся ростом и V-образную форму соответственно. Линейные функции вида f(x) = ax + b образуют частный случай, поскольку их график совпадает с любой своей хордой и поэтому считается одновременно выпуклым и вогнутым.

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

Классическая задача выпуклого программирования формулируется как минимизация функции f(х) при ограничениях g_i(х) ≤ 0 для i=1,...,m и h_j(х) = 0 для j=1,...,p. Для сохранения выпуклости требуется, чтобы функция f(х) и все неравенства g_i(х) были выпуклыми, а равенства h_j(х) представляли собой аффинные зависимости вида аᵀх + b = 0 с фиксированными коэффициентами а и b. В таких условиях множество допустимых решений, определяемое системой g_i(х) ≤ 0 и h_j(х) = 0, остается выпуклым. Нелинейные равенства, например х² + у² = 1, приводят к невыпуклому множеству решений и поэтому не допускаются, в отличие от неравенств, которые могут быть нелинейными при условии сохранения выпуклости.

Рассмотрим на практике. Пример: Найти минимум функции:

F = (х-3)^2 + (у-2)^2 →min 

при условиях:

 Решение: Шаг 1. Анализ целевой функции

 F = (х-3)^2 + (у-2)^2 ) - это квадрат расстояния от точки (x;y) до точки А(3;2). 

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

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

Шаг 2. Допустимая область

 х^2 + у^2≤ 25 — круг радиуса 5 с центром в (0;0)

 х≥ 0, у≥ 0 — первый квадрант

 у ≥х — область выше прямой y = x (включая границу)

В пределах первого квадранта расположен сектор круга, который охватывается углом, простирающимся от 45∘ (луч у=х) до 90∘ (ось у).

Шаг 3. Где находится точка A(3;2)?

3^2 + 2^2 = 9 + 4 = 13≤ 25 - внутри круга

 х ≥ 0, у≥ 0 - выполняется

у≥х: 2≥3 — ложно

Положение точки A находится под линией у = х, что означает ее расположение за пределами разрешенной зоны.

Шаг 4. Ближайшая точка на границе

Так как точка А располагается за пределами заданной области, то точка, расположенная ближе всего к ней, окажется на границе, заданной уравнением у = х, которая является ближайшей «верхней» границей.

Подставляем y = x в целевую функцию: F = (х-3)^2 + (х-2)^2

Раскрываем: F = (х^2 - 6х + 9) + (х^2 - 4х + 4) = 2х^2 - 10х + 13

Шаг 5. Находим минимум

Производная: F' = 4х - 10 = 0 ⇒  х = 2,5

Тогда у = х = 2,5

Шаг 6. Проверяем другие ограничения

х^2 + у^2 = 6,25 + 6,25 = 12,5≤ 25 - выполняется 

х ≥ 0, у≥ 0 - выполняется

у ≥ х (равенство) - выполняется

Точка (2,5; 2,5) принадлежит допустимой области.

Шаг 7. Значение функции

F = (2,5-3)^2 + (2,5-2)^2 = (-0,5)^2 + (0,5)^2 = 0,25 + 0,25 = 0,5

Ответ х^* = 2,5, у^* = 2,5, F_min = 0,5

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

1. Гольштейн Е.Г. Выпуклое программирование. Элементы теории. – М.: Наука, 1970. – 68 с.
2. Магарил-Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ. Теория и приложения. – М.: Издательство Московского университета, 2024. – 223 с. – ISBN 978-5-19-012110-0
3. Дмитрук А.В. Выпуклый анализ. Элементарный курс. – М.: МАКС Пресс, 2023. – 300 с. – DOI:10.29003/m3571.978-5-89407-634-8
4. Kılınç-Karzan F., Nemirovski A. Essential Mathematics for Convex Optimization. – Cambridge: Cambridge University Press, 2025. – 444 p. – ISBN 9781009510523
5. Basu A. Convexity and its applications in discrete and continuous optimization. – Cambridge: Cambridge University Press, 2025. – 310 p. – ISBN 9781108837590