Is a convex optimization problem an algorithm?

No. It is the mathematical task supplied to an algorithm.

Can adding a variable preserve the answer?

Yes. The epigraph construction does so when its inequalities are represented correctly.

Must a convex problem have one solution?

No. It can have several optimal solutions, no feasible solution, or an infimum that is not attained.

AI Glossary / Mathematics and optimization / Advanced

Convex optimization problem

Definition

A convex optimization problem is a mathematical specification that asks for the minimum of a convex objective over a convex set of allowed decisions. It consists of variables, an objective and a feasible region. The Aalto glossary links this term to convex optimization; this entry emphasizes precise problem formulation.

What it means

The problem describes what should be solved; an optimization method describes how to solve it. The same problem may be handled by different algorithms, and equivalent formulations may use different numbers of variables while preserving the relevant solutions.
This distinction matters when a practical request contains words such as “worst,” “closest” or “balanced.” Those words need precise mathematical interpretation. Minimizing the largest deviation is different from minimizing the sum of deviations. Both can lead to convex formulations, but they can recommend different decisions and require different explanations.

How it works

Specify the decision domain and objective, then establish convexity of the allowed region and objective. A standard representation uses convex inequality functions bounded above by zero and affine equality constraints. Additional variables can expose useful structure without changing the original decision problem.
For example, minimizing f(x) can be written as minimizing a new variable t subject to f(x) ≤ t and the original restrictions on x. This is an epigraph formulation. It is an exact reformulation when represented correctly: for each allowed x, the smallest feasible t equals f(x). Introducing extra variables is therefore not necessarily an approximation or a change in the business objective.

Three practical examples

A service team chooses one target response setting to limit the worst deviation from several requested values. An auxiliary variable can represent the largest deviation and turn the comparison into explicit inequalities.
A model developer fits coefficients while bounding the maximum absolute residual. Separate positive and negative residual inequalities can express that bound without requiring a differentiable absolute-value formula.
A planner chooses a continuous allocation subject to nonnegativity and a fixed total. The mathematical specification should state whether fractional allocations are meaningful before a solver is selected; adding integer requirements can change the convex structure.

Think of it this way

Think of translating a written brief into a form with no hidden interpretation. Every variable needs a meaning, every restriction needs a direction, and the quantity being minimized needs a unit. An elegant solution to the wrong translation still fails the original brief.

Worked example

Consider an original one-dimensional setting problem. Two requested target positions are one and five. Choose x between zero and six to minimize the worst absolute deviation: f(x) = max(|x − 1|, |x − 5|).
Introduce t for the maximum deviation. Minimize t subject to x − 1 ≤ t, 1 − x ≤ t, x − 5 ≤ t, 5 − x ≤ t, and 0 ≤ x ≤ 6. Each restriction is affine and the objective is linear, so this representation is a linear program and hence a convex optimization problem.
At x = 3, both absolute deviations equal two, so t = 2 is feasible. To prove that no smaller value works, the constraints imply |x − 1| ≤ t and |x − 5| ≤ t. The triangle inequality gives 4 ≤ |x − 1| + |x − 5| ≤ 2t, hence t ≥ 2. The proposed point attains the bound.
Uniqueness of x here follows directly: at t = 2, the first target requires x between −1 and three, while the second requires x between three and seven. Their intersection is just x = 3. This uniqueness is established for this example, not assumed from convexity alone.

Illustrative case study

In a fictional configuration workshop, the team initially accepts x = 3 from the preceding formulation. A technical restriction then limits the setting to x ≤ 2. For any allowed x, the deviation from target five is at least three. Choosing x = 2 gives deviations one and three, so the new optimum is t = 3.
During review, an analyst proposes replacing the maximum deviation with the sum. Without the added cap, |x − 1| + |x − 5| equals four for every x from one to five. That alternative objective would treat all those settings as equally good, including values with a worse largest deviation than x = 3.
The workshop retains the maximum-deviation requirement and records why. The issue is a choice of objective, not a numerical error or disagreement between solvers. These target positions and restrictions are fictional teaching inputs.

Common misconceptions and mistakes

A problem does not become convex merely because it uses a convex objective. Its feasible set matters too. Nor must every displayed formula look linear: convex problems can have nonlinear objectives and restrictions.
An inequality t ≥ |r| requires both r ≤ t and −r ≤ t. Keeping only one side changes the model. Also, t is an upper bound at every feasible point, but it need not equal the actual maximum deviation unless minimization has made that bound tight. Finally, feasibility, existence of an optimum and uniqueness are separate questions.

Business use

A written problem specification makes assumptions reviewable before implementation effort. Record the variables, units, data, restrictions and objective in terms that decision owners can check. When using a reformulation, explain how its additional variables map back to the original request. Recheck that mapping after changes. A low reported objective value is useful only if the result satisfies the original interpretation and the operational limits.

Check your understanding

What does t represent in the worked problem?

Answer: An upper bound on both absolute deviations, minimized to the smallest achievable bound.

Why cannot t be below two in the original problem?

Answer: The targets are four units apart, and their combined deviations cannot be smaller than that separation.

What happens after imposing x ≤ 2?

Answer: The best setting is two and the worst deviation is three.

Related terms

Convex optimization
Objective function
Epigraph
Linear programming
feasible region
minimax approximation
auxiliary variable
equivalent formulation

Learn next

Practice converting absolute values and maxima into auxiliary-variable inequalities. Then examine how to distinguish exact reformulations from relaxations that enlarge the allowed set and may provide bounds instead of directly usable decisions.

Sources

Aalto Dictionary of Machine Learning, convex optimization problem and convex optimization: objective-plus-feasible-set formulation and epigraph representation. https://aaltodictionaryofml.github.io/ADictML_Main.pdf Stephen Boyd and Lieven Vandenberghe, Convex Optimization slides, chapter 4: standard convex formulations and epigraph form. https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf The target-position formulation, optimality proof and fictional workshop case are original teaching illustrations.

Previous: Convex optimization Next: Convex set