4 - Linear, Quadratic & Conic Optimization

Before we touch a solver, clear a small corner of the desk and keep one blank sheet of paper beside you. Today that sheet matters more than any software: every important model in this blog will first have to survive a hand calculation.

Optimization often arrives wearing intimidating notation: vectors, cones, multipliers, matrix inequalities, solver logs. The central question, however, is wonderfully ordinary: among all decisions that obey the rules, which one best serves our purpose? In this blog we will learn three increasingly expressive languages for answering that question—linear programming (LP), quadratic programming (QP), and second-order cone programming (SOCP). We will not begin with software. We will begin with a decision, derive every mathematical object, solve small instances by hand, and only then discuss algorithms and code.

The running competition case is the 2024 CUMCM Problem C on crop-planning. A publicly displayed national excellent paper formulates a seven-year planting strategy over heterogeneous plots, seasons, crops, rotation rules, uncertain yield, price, cost, and demand. That case is useful because it reveals both the power and the danger of optimization: writing “maximize profit” is easy; encoding what can actually be planted, sold, rotated, and managed is the real work. We will reconstruct the core model independently rather than copying the paper’s equations or numerical answer. The original paper remains the source of record in the CUMCM excellent-paper archive .

The optimization contract

Every optimization model must expose five things: decision variables, objective, constraints, data, and validation. If one is missing, the solver may still return a number, but you do not yet have a defensible decision.

1. From a Decision to a Mathematical Program

Suppose a small campus kitchen must choose how many trays of rice bowls and salad bowls to prepare for lunch. A rice tray earns 30, uses no rice, and needs 3 staff-minutes. Today the kitchen has 80 kg of rice and 72 staff-minutes. Demand limits sales to 18 rice trays and 16 salad trays.

Pause before calculating. What is under our control? Not profit, rice stock, or demand. We control the numbers of trays. Let

Profit becomes , and the rules become

This is a linear program because the objective and every constraint are affine. “Linear” does not mean easy or one-dimensional. It means each expression is a weighted sum of decisions plus a constant; there are no products such as , powers such as , or nonlinear functions such as .

In matrix form an LP can be written

Here is the vector of decisions, gives their objective coefficients, rows of and encode rules, and are data. The notation is compact, but the model must retain units. A row that adds kilograms to staff-minutes is not sophisticated; it is wrong.

Natural language usually hides the algebra in three verbs. “At most,” “capacity,” and “cannot exceed” produce constraints. “At least,” “coverage,” and “must satisfy” produce constraints. “Balance,” “conservation,” and “exactly” produce equalities.

Logical phrases require more care. “Plant crop only if plot is activated” needs a binary variable and a link . The continuous amount says how much; the binary variable says whether. Once binary or integer decisions appear, the model becomes a mixed-integer linear program (MILP), even if every expression is linear.

Stop and model

A clinic schedules nurses for four shifts. Each nurse can work at most two consecutive shifts; each shift needs a minimum number of nurses. What should the decision variable mean? Which rule is a coverage constraint, and which rule needs binary logic? Write the meanings before writing any equation.

2. Geometry, Vertices, and Why LP Works

Each kitchen inequality describes a half-plane. Their intersection is the feasible region. Because intersections of half-spaces are convex, a line segment joining any two feasible points stays feasible.

The objective describes parallel lines. Increasing slides the line toward higher profit until it last touches the feasible polygon. Unless the objective is parallel to an entire edge, the last contact is a vertex. This is the geometric reason an LP has an optimal extreme point whenever a finite optimum exists.

For two variables, list candidate vertices. The labor and salad-demand boundaries intersect at , so and profit is . The rice-demand and labor boundaries give , hence and profit is . Checking the remaining vertices confirms is optimal.

This hand calculation also supplies a unit test. If a solver returns , it ignored the demand bound. If it returns a profit of 1008 at a different point, inspect whether the optimum is non-unique or output was rounded incorrectly.

A set is convex if, for any and , . For a linear objective,

An interior convex combination cannot be strictly better than both endpoints. Repeatedly moving toward an extreme point preserves or improves the objective. This is the mathematical idea behind vertex-search methods such as simplex.

An optimization run has more outcomes than “success” and “error”: it may be optimal, infeasible, unbounded, or numerically difficult. Never make an infeasible model feasible by quietly deleting constraints. Introduce explicit slack, price the violation, and explain which promise must be relaxed.

3. Duality: The Price of a Scarce Resource

Consider

Assign a nonnegative price to each resource. If , then for any feasible ,

Thus is an upper bound on profit. Seeking the tightest bound gives the dual

This is weak duality. Under standard feasibility conditions, LP strong duality says the best primal value equals the best dual value. The dual variable is a shadow price: for a small increase in , optimal value changes approximately by .

At the kitchen optimum , rice stock is slack—only 72 of 80 kg are used—so its shadow price is zero. Labor and rice-bowl demand bind. Solving the corresponding dual equalities gives a labor price of per minute and an additional rice-tray-demand value of per tray. These values are local: buying one extra minute is useful only until another constraint becomes active.

Complementary slackness makes the relationship precise:

A resource can carry positive price only when its constraint binds; a positive activity must have zero reduced cost. This converts a solver result into an explanation: which rule limits the decision, and what is the marginal value of relaxing it?

4. Quadratic Objectives: Risk, Tracking, and Diminishing Returns

Linear objectives assume marginal value is constant. Often it is not. A schedule may be penalized for deviating from a target; a portfolio may trade return against variance; a control input may be penalized for changing too sharply. These lead to

When is symmetric, and . If , the problem is convex and every local minimizer is global. If , the objective is strictly convex and the minimizer is unique over a convex feasible set.

Ordinary least squares is a QP:

So and . Setting the gradient to zero gives . In practice use QR or SVD rather than explicitly forming normal equations, because the latter squares the condition number.

For another example, two generators provide to meet demand , with , . The dispatch problem minimizes subject to and bounds. Ignoring active bounds, the Lagrangian gives : unconstrained generators have equal marginal cost. A generator at its upper bound may have lower marginal cost because it would like to produce more but cannot.

5. KKT Conditions: A Common Language

For subject to and , define

The Karush–Kuhn–Tucker conditions are

$$
\begin{aligned}
\nabla_xL(x^*,\lambda^*,\nu^*)&=0 &&\text{stationarity},\
g_i(x^*)&\le0,quad h_j(x^*)=0 &&\text{primal feasibility},\
\lambda_i^*&\ge0 &&\text{dual feasibility},\
\lambda_i^g_i(x^)&=0 &&\text{complementary slackness}.
\end{aligned}
$$

For convex problems satisfying a qualification such as Slater’s condition, these conditions are sufficient as well as necessary. For nonconvex problems they may describe only a local stationary point.

Take subject to . If is feasible, . Otherwise the boundary binds. Stationarity gives and , hence

The correction occurs only along the constraint normal and has exactly the magnitude needed to reach the boundary.

6. Norms, Uncertainty, and Second-Order Cones

The canonical second-order cone is . An SOCP has affine equalities and constraints

This language includes LPs, many convex quadratic constraints, robust linear constraints under ellipsoidal uncertainty, portfolio risk limits, and geometric location problems.

Suppose resource usage is uncertain:

The worst perturbation is . By Cauchy–Schwarz,

with equality when aligns with . The infinitely many uncertain inequalities are therefore equivalent to

an SOCP constraint. Uncertainty does not automatically require simulation; the right uncertainty geometry can yield a tractable deterministic model.

If , then , , is equivalent to $|Lx|2\le t\sqrt{x^T\Sigma x}\le\sigma{\max}\Sigma$.

7. Algorithms and Numerical Evidence

Simplex walks between adjacent vertices and provides useful basis sensitivity information. Interior-point methods move through the interior and solve Newton systems associated with barrier-regularized KKT equations. First-order methods use gradients and projections; they scale farther but may need more iterations for high accuracy.

For an inequality , a logarithmic barrier solves

As approaches a boundary, the barrier grows. As , minimizers follow the central path toward the constrained optimum. Newton’s method uses

and a line search that remains feasible.

Use LP/MILP solvers for linear relationships and discrete decisions, convex QP when the Hessian is positive semidefinite, and SOCP when norms or ellipsoidal robustness appear. Do not send a convex model to a genetic algorithm merely because the heuristic is easier to describe. Do not claim a global optimum for a nonconvex heuristic without a valid bound or proof.

Scale variables when coefficients differ by many orders of magnitude. After solving, report primal residuals, constraint violation, dual residuals, and duality gap—not only a status string.

8. Winning-Paper Case: 2024 CUMCM Crop Planning

The real case asks for crop decisions across years, seasons, plots, and crops. Let

and indicate whether that combination is used. Let be plot area, yield, cost, price, and expected demand. Production is

To avoid the nonlinear expression , introduce full-price sales and surplus :

If surplus is wasted, its price is zero. If it sells at half price, revenue is . The seven-year objective is

Core rules are:

and, for legumes ,

Incompatible plot-crop-season combinations are fixed to zero. The resulting model is a MILP. The excellent paper uses a differential-evolution genetic algorithm and later incorporates CVaR and correlation. A strong audit first asks which parts are already linear and whether an exact MILP solver can provide a benchmark. Even if the full instance is large, solve a reduced exact model.

For a hand test, take two 10-mu plots, two years, and crops wheat , beans , vegetables . Plot 1 accepts ; plot 2 accepts . Each plot must grow beans once and cannot repeat a crop. With profits RMB/mu, the best rotation is on plot 1 and on plot 2, yielding

This tests compatibility, rotation, legume coverage, and accounting. Only after it passes should we trust a seven-year workbook.

The lesson is not that one algorithm name is superior. It is that a plausible heatmap can violate rotation, a high profit can come from selling more than demand, and an unlinked binary variable can be meaningless. Recompute the objective from exported decisions and check every rule independently.

9. Implementation and Verification

import cvxpy as cp
import numpy as np

profit = np.array([36.0, 30.0])
x = cp.Variable(2, nonneg=True)
constraints = [4*x[0] <= 80,
               2*x[0] + 3*x[1] <= 72,
               x[0] <= 18, x[1] <= 16]
problem = cp.Problem(cp.Maximize(profit @ x), constraints)
problem.solve()
print(x.value, problem.value)
print([c.dual_value for c in constraints])

Audit primal feasibility with

$$r_p=\max{|Ex-d|\infty,\ |(Ax-b)+|_\infty},$$

recompute the objective, check units and integrality, and inspect business rules independently. Perturb important inputs. If a 1% demand change replaces the whole schedule, the recommendation needs a stability warning even if profit barely changes.

For integer models, report best feasible value , best bound , and

“Timed out” is not “failed.” A 0.4% gap may support a decision; an unreported gap does not.

10. A Defensible Optimization Report

A reader should be able to reconstruct the chain:

1. define every decision with indices and units;
2. write the objective as an accounting identity;
3. group constraints by physical, temporal, logical, and policy meaning;
4. classify the model and justify the classification;
5. explain solver choice and termination criteria;
6. verify a hand-sized instance;
7. report residuals, bounds, and active constraints;
8. translate dual values into operational language;
9. stress-test uncertain coefficients;
10. state what the model omits.

LP teaches disciplined translation. QP teaches curvature and compromise. SOCP teaches that useful nonlinear structure can remain globally tractable. The shared habit is more important than the labels: model the decision faithfully, exploit structure honestly, and treat verification as part of the mathematics.

One small easter egg before you leave: return to the kitchen model and increase available labor from 72 to 73. The best profit rises by exactly the labor shadow price predicted by the dual. Keep increasing it one minute at a time and watch for the first moment when that prediction fails. That breakpoint is where sensitivity analysis stops being a slogan and becomes something you can see.

Sources and further reading

• CUMCM official site and excellent-paper display for the 2024 crop-planning case.
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Chapters 4–6.
• CVXPY documentation for disciplined convex programming.

The next blog goes deeper into convexity proofs, conjugates, duality, proximal operators, first-order rates, and algorithms for models too large to hand directly to a generic solver.