Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Objectives, Decision Variables, Constraints, and Feasibility › Visualizing the Feasible Set and the Optimality Gap

Michael BrenndoerferOctober 29, 20268 min read

Machine Learning from ScratchAll chapters

Part 14 of 15Constrained Optimization

Chapter 84Objectives, Decision Variables, Constraints, and Feasibility › Visualizing the Feasible Set and the Optimality Gap

Reading section 5 of 10 · Visualizing the Feasible Set and the Optimality Gap · 8 minSection 5 of 10 · 8 min

Section 5 of 10 · 8 min read

Objectives, Decision Variables, Constraints, and Feasibility › Visualizing the Feasible Set and the Optimality GapSection view · Sections in this chapter5 / 10 ↓

Sections in this chapter10

Reading tools Definitions, links & notes

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Notes & comments

Notes & commentsLeave notes and join the discussionSelection toolbarShow comment actions when selecting text. Turn off for the browser menu only.Comment indicatorsShow small counts beside annotated passagesPassage highlightsGently shade annotated text selections

With two decision variables we can draw the entire problem, and the picture is a useful antidote to abstract notation. Each inequality $a_i^\top x \leq b_i$ defines a half-plane, its boundary line is where the constraint is tight, and the feasible set is the intersection of these half-planes with the non-negative quadrant. The objective $c^\top x$ is constant along lines perpendicular to $c$ , so we can draw several iso-profit lines and watch which one is the last to touch the region.

PythonIn [3]
CollapseExpandA_demo = np.array([[2.0, 1.0], [1.0, 2.0]])
b_demo = np.array([8.0, 8.0])
c_demo = np.array([40.0, 30.0])

x1_grid = np.linspace(0.0, 4.0, 400)
machine_line = 8.0 - 2.0 * x1_grid
labour_line = (8.0 - x1_grid) / 2.0
ceiling = np.minimum(machine_line, labour_line)
x_opt = np.linalg.solve(A_demo, b_demo)

PythonIn [4]
CollapseExpandfrom book_plot_style import PALETTE, label_bars, polish_axes, use_book_style

use_book_style()
C = [PALETTE[key] for key in ("primary", "teal", "amber", "purple")]

fig = plt.figure(figsize=(6.0, 4.8))
ax = fig.add_subplot(111)
ax.fill_between(
    x1_grid, 0.0, ceiling, color=C[0], alpha=0.15, label="feasible set"
)
ax.plot(
    x1_grid,
    machine_line,
    color=C[0],
    lw=1.1,
    label=r"$2x_1 + x_2 = 8$ (machine)",
)
ax.plot(
    x1_grid, labour_line, color=C[1], lw=1.1, label=r"$x_1 + 2x_2 = 8$ (labour)"
)

for level in (60.0, 120.0, 180.0, 240.0):
    ax.plot(
        x1_grid,
        (level - c_demo[0] * x1_grid) / c_demo[1],
        color=C[3],
        lw=1.0,
        ls=":",
        label="iso-profit lines" if level == 60.0 else None,
    )

ax.scatter(*x_opt, s=110, color=C[2], zorder=5, label=r"optimum $(8/3,\,8/3)$")

ax.set_xlim(0, 5)
ax.set_ylim(0, 5)
ax.set_xlabel(r"$x_1$ (pallets of product 1)")
ax.set_ylabel(r"$x_2$ (pallets of product 2)")
ax.set_title("Feasible set and iso-profit contours")
ax.legend(loc="upper center", bbox_to_anchor=(0.5, -0.20), ncol=2)
polish_axes(ax)
plt.show()

VisualizationOut [4]
CollapseExpand

A polygon in the first quadrant bounded by the lines 2 x1 plus x2 equals 8 and x1 plus 2 x2 equals 8, shaded, with four parallel dotted iso-profit lines sweeping toward the upper right and a marked optimum at x1 equals x2 equals 2.67. — Feasible set of the two-product allocation problem, bounded by the two resource constraints and the two axes, with dotted iso-profit contours. Raising the profit level slides the contours northeast until the last one touches the polygon exactly at the corner where both resources are exhausted, so that vertex is the optimum at x1 = x2 = 8/3 with profit 186.67. This illustrates why a linear objective reaches its maximum at a corner of the feasible polygon.

Two features of the figure carry most of the intuition. The feasible set is a polygon with four corners: the origin, the two axis intercepts at (4, 0) and (0, 4), and the intersection of the two resource lines. And the iso-profit lines all have the same slope, so pushing the profit level up slides the line northeast until it either exits the polygon through a corner or runs along an edge. Here it exits through the corner where both resources are exhausted, so this bounded polygon has an optimal vertex. A whole edge can tie in another linear example.

The next figure restricts production to whole pallets. The feasible decisions become the integer lattice points inside the continuous polygon. The best integer profit is 180, while the LP relaxation reaches $560/3\approx186.67$ . Their difference $20/3\approx6.67$ is this instance's additive integrality gap. It differs from a MILP solver's final search gap: after proving the integer optimum, the solver can report a zero search gap even though the initial LP relaxation remains fractional.

PythonIn [5]
CollapseExpandlattice = np.array(list(itertools.product(range(5), repeat=2)), dtype=float)
inside = np.all(lattice @ A_demo.T <= b_demo + 1e-12, axis=1)
lattice_profit = lattice @ c_demo
best_point = lattice[inside][np.argmax(lattice_profit[inside])]
best_integer_profit = float(lattice_profit[inside].max())

PythonIn [6]
CollapseExpandfrom book_plot_style import PALETTE, label_bars, polish_axes, use_book_style

use_book_style()
C = [PALETTE[key] for key in ("primary", "teal", "amber", "purple")]

fig = plt.figure(figsize=(6.0, 4.8))
ax = fig.add_subplot(111)
ax.fill_between(
    x1_grid, 0.0, ceiling, color=C[0], alpha=0.15, label="LP relaxation"
)
ax.plot(x1_grid, machine_line, color=C[0], lw=1.1)
ax.plot(x1_grid, labour_line, color=C[1], lw=1.1)
ax.scatter(
    lattice[inside, 0],
    lattice[inside, 1],
    s=55,
    color=C[1],
    label="feasible integer plans",
    zorder=4,
)
ax.scatter(
    lattice[~inside, 0],
    lattice[~inside, 1],
    s=45,
    marker="x",
    color=C[3],
    label="infeasible lattice points",
)
ax.scatter(
    *best_point,
    s=150,
    facecolors="none",
    edgecolors=C[2],
    lw=1.1,
    label=f"best integer {tuple(map(int, best_point))}, profit {best_integer_profit:.0f}",
)
ax.scatter(
    *x_opt,
    s=110,
    marker="x",
    color=C[2],
    zorder=6,
    label="LP optimum (fractional)",
)

ax.set_xlim(0, 5)
ax.set_ylim(0, 5)
ax.set_xlabel(r"$x_1$ (pallets of product 1)")
ax.set_ylabel(r"$x_2$ (pallets of product 2)")
ax.set_title("Integer decisions versus the LP relaxation")
ax.legend(loc="upper center", bbox_to_anchor=(0.5, -0.20), ncol=2)
polish_axes(ax)
plt.show()

VisualizationOut [6]
CollapseExpand

The same shaded feasible polygon with dots at integer coordinates inside it and crosses at infeasible lattice points just outside; a marked cross at 2.67, 2.67 shows the fractional relaxation optimum and a ringed dot at 3, 2 shows the best integer plan. — Integer decisions versus the LP relaxation of the two-product allocation problem. Restricting both quantities to whole pallets shrinks the decision set from the polygon to the integer lattice points it contains, including its boundary, so the best integer plan is (3, 2), worth 180, while the fractional relaxation optimum (8/3, 8/3), worth 186.67, cannot be produced. The 6.67 difference between the two profit levels is the integrality gap, the price exact integrality pays on this instance.

The third figure isolates the difference between a hard constraint and a soft penalty on a one-dimensional problem: minimize $(x - 1.5)^2$ subject to $x \leq 1$ . The unconstrained minimizer is $x = 1.5$ , which violates the rule by $0.5$ . Using the positive-part convention, the penalized objective is $(x - 1.5)^2 + \lambda\,(x - 1)_+^2$ , where $\lambda$ is the quadratic penalty weight on any violation of $x \leq 1$ , and $(x - 1)_+ = \max(0, x - 1)$ is the number of units by which $x$ exceeds the limit. For $x > 1$ this equals $(x - 1.5)^2 + \lambda (x - 1)^2$ , and for $x \leq 1$ it is just $(x - 1.5)^2$ . On the region $x > 1$ the first-order condition $2(x - 1.5) + 2\lambda (x - 1) = 0$ solves to

\begin{aligned} 2(x - 1.5) + 2\lambda (x - 1) &= 0 && \text{(first-order condition)} \\ x - 1.5 + \lambda x - \lambda &= 0 && \text{(divide by two)} \\ x(1 + \lambda) &= 1.5 + \lambda && \text{(collect } x \text{ terms)} \\ x^\star(\lambda) &= \frac{1.5 + \lambda}{1 + \lambda}. && \text{(solve for } x \text{)} \end{aligned}

where:

$x^\star(\lambda)$ : the penalized minimizer for penalty weight $\lambda$
$\lambda$ : the quadratic penalty weight on the violation of $x \leq 1$
$x$ : the scalar decision variable in the one-dimensional example
$1.5$ : the unconstrained minimizer of $(x-1.5)^2$
$1$ : the boundary of the hard constraint $x \leq 1$

The minimizer equals $1.333$ at $\lambda = 0.5$ , $1.167$ at $\lambda = 2$ , and $1.045$ at $\lambda = 10$ . The minimizer approaches the boundary from the wrong side and never crosses it.

PythonIn [7]
CollapseExpandtarget, limit = 1.5, 1.0
xs = np.linspace(0.3, 1.9, 500)
penalty_curves = []
for lam in (0.5, 2.0, 10.0):
    star = (target + lam * limit) / (1.0 + lam)
    star_val = (star - target) ** 2 + lam * max(0.0, star - limit) ** 2
    curve = (xs - target) ** 2 + lam * np.maximum(0.0, xs - limit) ** 2
    penalty_curves.append((lam, star, star_val, curve))

PythonIn [8]
CollapseExpandfrom book_plot_style import PALETTE, label_bars, polish_axes, use_book_style

use_book_style()
C = [PALETTE[key] for key in ("primary", "teal", "amber", "purple")]

fig = plt.figure(figsize=(6.0, 4.8))
ax = fig.add_subplot(111)
ax.plot(
    xs,
    (xs - target) ** 2,
    color=C[0],
    lw=1.1,
    label=r"unconstrained $(x-1.5)^2$",
)
for index, (lam, star, star_val, curve) in enumerate(penalty_curves):
    col = C[index + 1]
    ax.plot(
        xs, curve, color=col, lw=1.1, label=rf"penalised, $\lambda={lam:g}$"
    )
    ax.scatter(star, star_val, color=col, s=60, zorder=5)

ax.axvline(
    limit,
    color=PALETTE["muted"],
    ls="--",
    lw=1.2,
    label=r"constraint $x \leq 1$",
)
ax.set_xlim(0.3, 1.9)
ax.set_ylim(0, 2.0)
ax.set_xlabel(r"decision $x$")
ax.set_ylabel("objective value")
ax.set_title("Hard constraint versus quadratic penalty")
ax.legend(loc="upper center", bbox_to_anchor=(0.5, -0.20), ncol=2)
polish_axes(ax)

VisualizationOut [8]
CollapseExpand

A convex objective curve with three penalised curves whose minima, marked with dots, move leftward toward a dashed vertical line at x equals 1 as lambda increases. — Quadratic penalty versus a hard constraint on a one-dimensional problem. The plot shows the unconstrained objective and three penalized objectives, whose minima (dots) creep toward the constraint boundary x = 1 from the right as lambda grows but only reach it in the limit, whereas the hard constraint would place the answer exactly at x = 1.

A non-negotiable rule belongs in the feasible set. A preference that permits violations can instead use an explicit penalty with stated units and weight. In either case, check the returned decision. The one-dimensional example shows why a large finite quadratic penalty cannot simply be assumed to satisfy a hard rule.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Comments

Add to the conversation

Stay up to date