Chapter 4 Optimization
4.1 Epigraph Form
In optimization, we often solve problems of the form
\[\begin{equation} \begin{aligned} \min_x \quad & J(x). \end{aligned} \end{equation}\]
Here, \(x\) is the decision variable and \(J(x)\) is the objective function. The goal is to find the value of \(x\) that makes \(J(x)\) as small as possible.
The epigraph form rewrites this problem by introducing a new scalar variable \(z\). Instead of minimizing \(J(x)\) directly, we minimize \(z\), while forcing \(z\) to be an upper bound on \(J(x)\).
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & J(x) \leq z. \end{aligned} \end{equation}\]
So the original problem
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \end{aligned} \end{equation}\]
is rewritten as
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & J(x) \leq z. \end{aligned} \end{equation}\]
The new variable \(z\) is not a penalty weight. It is not multiplied by the objective. It is simply an upper bound on the objective value.
4.2 Example 1: Basic Epigraph Form
Consider the optimization problem
\[\begin{equation} \begin{aligned} \min_x \quad & x^2. \end{aligned} \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & x^2 \leq z. \end{aligned} \end{equation}\]
This says: choose \(x\) and \(z\), make \(z\) as small as possible, but require that \(z\) stays above \(x^2\).
The optimal solution is
\[\begin{equation} x^\star = 0, \qquad z^\star = 0. \end{equation}\]
So the epigraph form gives the same answer as the original problem.
4.3 Why does this work?
The constraint
\[\begin{equation} J(x) \leq z \end{equation}\]
forces \(z\) to be at least as large as the objective value.
For any fixed \(x\), the smallest valid value of \(z\) is
\[\begin{equation} z = J(x). \end{equation}\]
So when we minimize \(z\), the optimizer naturally pushes \(z\) down until it touches \(J(x)\).
At the optimum,
\[\begin{equation} z^\star = J(x^\star). \end{equation}\]
Therefore, minimizing \(z\) subject to \(J(x) \leq z\) is equivalent to minimizing \(J(x)\).
4.4 Geometric meaning of the epigraph
The epigraph of a function \(J(x)\) is the set of all points lying on or above the graph of \(J(x)\).
Formally,
\[\begin{equation} \mathrm{epi}(J) = \left\{ (x,z) \;|\; J(x) \leq z \right\}. \end{equation}\]
The variable \(z\) represents height. The constraint \(J(x)\leq z\) says that the point \((x,z)\) must lie above the function. Minimizing \(z\) pushes this point as low as possible.
So the epigraph problem can be understood as:
\[\begin{equation} \text{Find the lowest point in the epigraph of } J. \end{equation}\]
4.5 Example 2: Absolute Value Objective
Consider
\[\begin{equation} \begin{aligned} \min_x \quad & |x|. \end{aligned} \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & |x| \leq z. \end{aligned} \end{equation}\]
The constraint
\[\begin{equation} |x| \leq z \end{equation}\]
is equivalent to
\[\begin{equation} -z \leq x \leq z. \end{equation}\]
Equivalently, this can be written as two inequalities:
\[\begin{equation} x \leq z, \qquad -x \leq z. \end{equation}\]
Therefore, the epigraph form can be written as
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & x \leq z, \\ & -x \leq z. \end{aligned} \end{equation}\]
This is useful because the nonsmooth objective \(|x|\) becomes a linear objective with linear constraints.
4.6 Epigraph form for constrained optimization
Now consider a constrained optimization problem:
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \\ \text{s.t.}\quad & h(x) \leq 0. \end{aligned} \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & h(x) \leq 0, \\ & J(x) \leq z. \end{aligned} \end{equation}\]
The original constraint \(h(x)\leq 0\) stays exactly the same.
The only change is that the objective \(J(x)\) becomes an upper-bound constraint \(J(x)\leq z\), and the new objective is to minimize \(z\).
4.7 Example 3: Constrained Epigraph Form
Consider
\[\begin{equation} \begin{aligned} \min_x \quad & x^2 \\ \text{s.t.}\quad & x \geq 1. \end{aligned} \end{equation}\]
We can rewrite the constraint as
\[\begin{equation} 1-x \leq 0. \end{equation}\]
Therefore, the original problem is
\[\begin{equation} \begin{aligned} \min_x \quad & x^2 \\ \text{s.t.}\quad & 1-x \leq 0. \end{aligned} \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & 1-x \leq 0, \\ & x^2 \leq z. \end{aligned} \end{equation}\]
The optimal solution is
\[\begin{equation} x^\star = 1, \qquad z^\star = 1. \end{equation}\]
Again, \(z^\star\) equals the optimal objective value.
4.8 Combining constraints using a maximum
The epigraph form
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & h(x) \leq 0, \\ & J(x) \leq z \end{aligned} \end{equation}\]
can also be written using one maximum constraint:
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & \max\{h(x),J(x)-z\} \leq 0. \end{aligned} \end{equation}\]
This works because
\[\begin{equation} \max\{h(x),J(x)-z\} \leq 0 \end{equation}\]
means that both terms inside the maximum must be less than or equal to zero. Therefore,
\[\begin{equation} h(x) \leq 0, \end{equation}\]
and
\[\begin{equation} J(x)-z \leq 0. \end{equation}\]
The second inequality is equivalent to
\[\begin{equation} J(x) \leq z. \end{equation}\]
So
\[\begin{equation} h(x)\leq 0, \qquad J(x)\leq z \end{equation}\]
is equivalent to
\[\begin{equation} \max\{h(x),J(x)-z\}\leq 0. \end{equation}\]
4.9 Inner and outer problem view
The epigraph form can also be viewed as an outer problem over \(z\) and an inner problem over \(x\).
Start with
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & \max\{h(x),J(x)-z\} \leq 0. \end{aligned} \end{equation}\]
For a fixed value of \(z\), define
\[\begin{equation} \phi(z) = \min_x \max\{h(x),J(x)-z\}. \end{equation}\]
Then the epigraph problem can be written as
\[\begin{equation} \begin{aligned} \min_z\quad & z \\ \text{s.t.}\quad & \phi(z) \leq 0. \end{aligned} \end{equation}\]
This gives two subproblems.
The inner problem is
\[\begin{equation} \phi(z) = \min_x \max\{h(x),J(x)-z\}. \end{equation}\]
For a fixed proposed upper bound \(z\), the inner problem asks whether there exists an \(x\) that can satisfy both the original constraint and the objective upper-bound constraint.
The outer problem is
\[\begin{equation} \begin{aligned} \min_z\quad & z \\ \text{s.t.}\quad & \phi(z) \leq 0. \end{aligned} \end{equation}\]
The outer problem asks for the smallest value of \(z\) for which the inner problem can satisfy the constraints.
4.10 Example 4: Inner and Outer View
Consider
\[\begin{equation} \begin{aligned} \min_x \quad & x^2 \\ \text{s.t.}\quad & x \geq 1. \end{aligned} \end{equation}\]
Write the constraint as
\[\begin{equation} h(x)=1-x, \end{equation}\]
and the objective as
\[\begin{equation} J(x)=x^2. \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & 1-x \leq 0, \\ & x^2 \leq z. \end{aligned} \end{equation}\]
Equivalently, using the maximum form,
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & \max\{1-x,x^2-z\} \leq 0. \end{aligned} \end{equation}\]
For a fixed \(z\), the inner problem is
\[\begin{equation} \phi(z) = \min_x \max\{1-x,x^2-z\}. \end{equation}\]
If \(z<1\), then no feasible \(x\) can satisfy both
\[\begin{equation} x\geq 1 \end{equation}\]
and
\[\begin{equation} x^2\leq z. \end{equation}\]
So \(z<1\) is infeasible.
If \(z=1\), choosing \(x=1\) gives
\[\begin{equation} 1-x=0, \end{equation}\]
and
\[\begin{equation} x^2-z=0. \end{equation}\]
Therefore,
\[\begin{equation} \max\{1-x,x^2-z\}=0. \end{equation}\]
So \(z=1\) is feasible.
The outer problem chooses the smallest feasible \(z\), so
\[\begin{equation} z^\star=1, \qquad x^\star=1. \end{equation}\]
4.11 Why \(z\) is subtracted, not multiplied
A common confusion is why we write
\[\begin{equation} J(x)-z \end{equation}\]
inside the max instead of multiplying the objective by \(z\).
The reason is that \(z\) is an upper bound, not a weight.
The constraint
\[\begin{equation} J(x)\leq z \end{equation}\]
is equivalent to
\[\begin{equation} J(x)-z\leq 0. \end{equation}\]
That is why \(z\) appears by subtraction.
It is not trying to scale the objective. It is representing the statement
\[\begin{equation} \text{objective value} \leq \text{upper bound}. \end{equation}\]
So the correct expression is
\[\begin{equation} J(x)-z. \end{equation}\]
not
\[\begin{equation} zJ(x). \end{equation}\]
If we multiplied \(J(x)\) by \(z\), then \(z\) would become a weighting or scaling variable. That would be a different optimization problem.
4.12 Feasibility interpretation
For each value of \(z\), the question is:
\[\begin{equation} \text{Does there exist an }x\text{ such that }h(x)\leq 0\text{ and }J(x)\leq z? \end{equation}\]
If yes, then \(z\) is feasible.
If no, then \(z\) is infeasible.
The optimal value \(z^\star\) is the smallest feasible upper bound.
This gives the interpretation
\[\begin{equation} z^\star = \text{best achievable objective value under the constraints}. \end{equation}\]
4.13 Monotonicity property
The feasible set in \(z\) is monotonic.
If a value \(z\) is feasible, then any larger value \(\bar{z}\geq z\) is also feasible.
To see this, suppose there exists an \(x\) such that
\[\begin{equation} h(x)\leq 0, \qquad J(x)\leq z. \end{equation}\]
If \(\bar{z}\geq z\), then
\[\begin{equation} J(x)\leq z \leq \bar{z}. \end{equation}\]
Therefore, the same \(x\) also satisfies
\[\begin{equation} h(x)\leq 0, \qquad J(x)\leq \bar{z}. \end{equation}\]
So if \(z\) is feasible, any larger \(\bar{z}\) is also feasible.
This means the outer problem often has a threshold structure:
\[\begin{equation} z < z^\star \quad \Rightarrow \quad \text{infeasible}, \end{equation}\]
\[\begin{equation} z \geq z^\star \quad \Rightarrow \quad \text{feasible}. \end{equation}\]
This is why epigraph forms are often convenient for one-dimensional search over \(z\).
4.14 Convexity property
Epigraph form is especially important in convex optimization.
A function \(J(x)\) is convex if and only if its epigraph is a convex set:
\[\begin{equation} J(x) \text{ is convex} \quad \Longleftrightarrow \quad \mathrm{epi}(J) = \{(x,z):J(x)\leq z\} \text{ is convex}. \end{equation}\]
This means a convex objective can be converted into a linear objective with a convex constraint.
The original problem
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \end{aligned} \end{equation}\]
becomes
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & J(x)\leq z. \end{aligned} \end{equation}\]
The objective \(z\) is linear, and the complexity of \(J(x)\) is moved into the constraint.
4.15 Example 5: Maximum Objective
Suppose we want to minimize the maximum of several functions:
\[\begin{equation} \begin{aligned} \min_x \quad & \max\{f_1(x),f_2(x),f_3(x)\}. \end{aligned} \end{equation}\]
Introduce \(z\) as an upper bound on all three functions.
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & f_1(x)\leq z, \\ & f_2(x)\leq z, \\ & f_3(x)\leq z. \end{aligned} \end{equation}\]
This works because
\[\begin{equation} \max\{f_1(x),f_2(x),f_3(x)\}\leq z \end{equation}\]
is equivalent to
\[\begin{equation} f_1(x)\leq z, \qquad f_2(x)\leq z, \qquad f_3(x)\leq z. \end{equation}\]
So the max objective becomes multiple inequality constraints.
4.16 Relation to minimax problems
Epigraph form is often used when the objective contains a maximum:
\[\begin{equation} \begin{aligned} \min_x \quad & \max_i f_i(x). \end{aligned} \end{equation}\]
The epigraph form is
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & f_i(x)\leq z, \qquad \forall i. \end{aligned} \end{equation}\]
Instead of minimizing the worst-case value directly, we minimize an upper bound on all possible values.
This is why epigraph form appears often in robust optimization, safety-constrained optimization, and multi-agent optimization.
4.17 Relation to Lagrangian methods
For a constrained problem
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \\ \text{s.t.}\quad & h(x)\leq 0, \end{aligned} \end{equation}\]
a Lagrangian method forms
\[\begin{equation} L(x,\lambda) = J(x)+\lambda h(x), \end{equation}\]
where \(\lambda\geq 0\) is a multiplier.
Here, the constraint is added to the objective through a multiplier.
By contrast, the epigraph form writes
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & h(x)\leq 0, \\ & J(x)\leq z. \end{aligned} \end{equation}\]
The key difference is:
\[\begin{equation} \text{Lagrangian method: constraints affect the objective through multipliers.} \end{equation}\]
\[\begin{equation} \text{Epigraph form: the objective becomes an upper-bound constraint.} \end{equation}\]
The epigraph variable \(z\) does not multiply the objective or the constraint. It is a candidate upper bound on the objective value.
4.18 Important properties
4.18.1 Property 1: Same optimizer
The epigraph form has the same optimal \(x^\star\) as the original problem.
Original problem:
\[\begin{equation} \begin{aligned} \min_x \quad & J(x). \end{aligned} \end{equation}\]
Epigraph form:
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & J(x)\leq z. \end{aligned} \end{equation}\]
At the optimum,
\[\begin{equation} z^\star = J(x^\star). \end{equation}\]
4.18.2 Property 2: Converts objective into a constraint
The objective \(J(x)\) becomes the constraint
\[\begin{equation} J(x)\leq z. \end{equation}\]
The new objective is simply
\[\begin{equation} \min z. \end{equation}\]
4.18.3 Property 3: Useful for maximum objectives
A problem like
\[\begin{equation} \begin{aligned} \min_x \quad & \max_i f_i(x) \end{aligned} \end{equation}\]
becomes
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & f_i(x)\leq z, \qquad \forall i. \end{aligned} \end{equation}\]
4.19 Common mistake
A common mistake is to think that epigraph form changes the objective by weighting it.
That is not correct.
The epigraph form does not write
\[\begin{equation} zJ(x). \end{equation}\]
It writes
\[\begin{equation} J(x)\leq z. \end{equation}\]
or equivalently,
\[\begin{equation} J(x)-z\leq 0. \end{equation}\]
So \(z\) is not a weight. It is an upper bound.
4.20 Summary
The epigraph form rewrites
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \end{aligned} \end{equation}\]
as
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & J(x)\leq z. \end{aligned} \end{equation}\]
For constrained problems,
\[\begin{equation} \begin{aligned} \min_x \quad & J(x) \\ \text{s.t.}\quad & h(x)\leq 0 \end{aligned} \end{equation}\]
becomes
\[\begin{equation} \begin{aligned} \min_{x,z}\quad & z \\ \text{s.t.}\quad & h(x)\leq 0, \\ & J(x)\leq z. \end{aligned} \end{equation}\]
The constraint \(J(x)\leq z\) says that \(z\) is an upper bound on the objective.
At the optimum,
\[\begin{equation} z^\star = J(x^\star). \end{equation}\]
So the epigraph form does not change the original optimization problem. It rewrites it in a form that is often easier to analyze, easier to decompose, and useful for max objectives, constrained optimization, and convex optimization.