Skip to content

Lesson 45: Quadratic Programming and Course Capstone

45.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the standard form of a quadratic programme and recognise where QPs arise.
  2. Write the KKT system of a QP and see that it is linear except for complementary slackness.
  3. Apply Wolfe's method — modified simplex with a restricted-entry rule.
  4. Outline Beale's method and say when it is preferred.
  5. Assemble the whole course into one decision framework.

45.2 The Quadratic Programme

Standard form. $\(\begin{aligned} \text{maximise}\quad & f(\mathbf{x})=\mathbf{c}^{T}\mathbf{x}+\tfrac12\mathbf{x}^{T}Q\mathbf{x}\\ \text{subject to}\quad & A\mathbf{x}\le\mathbf{b},\qquad \mathbf{x}\ge\mathbf{0} \end{aligned}\)$ with \(Q\) symmetric. The objective is quadratic; all constraints are linear.

If \(Q\) is negative semi-definite the maximisation is concave (equivalently, minimising a convex function), the feasible region is a polyhedron, and by Lesson 44 any KKT point is the global optimum. Indefinite \(Q\) makes the problem NP-hard, so this lesson assumes the definite case.

Why QP matters

Application Quadratic term
Portfolio selection (Markowitz, Nobel 1990) risk \(=\mathbf{x}^{T}\Sigma\mathbf{x}\)
Least squares with constraints \(\lVert A\mathbf{x}-\mathbf{b}\rVert^{2}\)
Support vector machines the margin objective
Model-predictive control tracking error plus control effort
Production with price effects revenue \(=p(x)x\)

QP is also the inner problem of sequential quadratic programming (SQP), the leading general non-linear method: at each iteration a general NLP is approximated by a QP and solved.

45.3 The KKT System of a QP

Apply Lesson 44 to the standard form (with \(\mathbf{y}\) for the \(A\mathbf{x}\le\mathbf{b}\) multipliers and \(\mathbf{s}\) for \(\mathbf{x}\ge0\)):

\[\mathbf{c}+Q\mathbf{x}-A^{T}\mathbf{y}+\mathbf{s}=\mathbf{0} \tag{2.1a}\]
\[A\mathbf{x}+\mathbf{v}=\mathbf{b} \tag{2.1b}\]
\[\mathbf{x},\mathbf{y},\mathbf{s},\mathbf{v}\ge\mathbf{0} \tag{2.1c}\]
\[\boxed{\ s_jx_j=0\ \text{ and }\ y_iv_i=0\ \text{ for all }i,j\ }\tag{2.1d}\]

The crucial observation. Equations (2.1a)–(2.1c) are linear. Only the complementary slackness conditions (2.1d) are non-linear — and even they are combinatorial rather than truly non-linear: each says "at most one of this pair is positive."

This is why a QP can be solved by a modified simplex method: run the simplex algorithm on the linear system, and simply forbid any pivot that would make a complementary pair both positive.

45.4 Wolfe's Method

Algorithm (Wolfe, 1959).

  1. Write the problem in standard form; check \(Q\) is negative semi-definite (for a maximisation).
  2. Form the KKT system (2.1a)–(2.1c), adding slacks \(\mathbf{v}\) and surpluses \(\mathbf{s}\).
  3. Add artificial variables to (2.1a) and set up a Phase I problem: minimise the sum of the artificials.
  4. Run the simplex method with one extra rule — the restricted-entry rule: $\(\textbf{never let } x_j \textbf{ and } s_j \textbf{ (or } y_i \textbf{ and } v_i) \textbf{ be basic at the same time.}\)$
  5. When all artificials reach zero, the current basic solution satisfies every KKT condition and is therefore optimal.

Properties. Finite termination when \(Q\) is definite; each iteration costs the same as an ordinary simplex pivot; and the method is genuinely simple to implement given a simplex code. Its drawback is that Phase I roughly doubles the tableau.

45.5 Beale's Method

Beale's method works directly on the objective rather than on the KKT system.

Outline. 1. Split the variables into basic and non-basic using the constraints. 2. Express the objective in terms of the non-basic variables only by substitution. 3. Compute \(\partial f/\partial(\text{non-basic})\) at the current point. If all partials indicate no improvement, stop. 4. Otherwise choose an entering variable and increase it until either a basic variable hits zero (an ordinary simplex ratio test) or the relevant partial derivative reaches zero (an unconstrained minimum along that edge) — whichever happens first. 5. In the second case introduce a free variable to record the interior point reached; repeat.

Wolfe Beale
Works on the KKT system the objective directly
Extra variables artificials (Phase I) free variables
Tableau size roughly doubles grows slowly
Interior optima reached via KKT reached naturally by step 4
Best when constraints dominate the optimum is interior or near it

Both are exact for definite \(Q\); the choice is a matter of convenience.

45.6 Solved Problems

Problem 1 — A QP with one active constraint

\[\text{maximise } f=4x_1+6x_2-2x_1^{2}-2x_1x_2-2x_2^{2} \quad\text{s.t.}\quad x_1+2x_2\le2,\ x_1,x_2\ge0.\]

Solution.

Step 0 — check concavity.

\[Q=\nabla^{2}f=\begin{pmatrix}-4&-2\\-2&-4\end{pmatrix},\qquad D_1=-4<0,\quad \det=16-4=12>0\]

Signs alternate from negative \(\Rightarrow\) negative definite \(\Rightarrow\) \(f\) is strictly concave, so any KKT point is the global maximum.

Step 1 — try the unconstrained optimum.

\[\frac{\partial f}{\partial x_1}=4-4x_1-2x_2=0,\qquad \frac{\partial f}{\partial x_2}=6-2x_1-4x_2=0\]

Solving: \(x_1=\tfrac13\), \(x_2=\tfrac43\). Then \(x_1+2x_2=\tfrac13+\tfrac83=3>2\): infeasible.

Step 2 — assume the constraint active. With multiplier \(u\) on \(x_1+2x_2-2\le0\):

\[4-4x_1-2x_2-u=0 \tag{i}\]
\[6-2x_1-4x_2-2u=0 \tag{ii}\]
\[x_1+2x_2=2 \tag{iii}\]

From (iii), \(x_1=2-2x_2\). Substituting into (i): \(4-4(2-2x_2)-2x_2-u=0\), i.e. \(-4+6x_2-u=0\), so \(u=6x_2-4\). Substituting into (ii): \(6-2(2-2x_2)-4x_2-2u=0\), i.e. \(2-2u=0\), giving

\[u=1\ \Rightarrow\ 6x_2-4=1\ \Rightarrow\ x_2=\frac56,\qquad x_1=2-\frac53=\frac13\]
\[\boxed{x_1^{*}=\tfrac13,\quad x_2^{*}=\tfrac56,\quad u=1,\quad f^{*}=\tfrac{25}{6}=4.1\overline{6}}\]

Step 3 — verify all KKT conditions.

Condition Check
Stationarity (i) \(4-\tfrac43-\tfrac53-1=4-3-1=0\) ✓
Stationarity (ii) \(6-\tfrac23-\tfrac{10}{3}-2=6-4-2=0\) ✓
Primal feasibility \(\tfrac13+\tfrac53=2\le2\) ✓; \(x_1,x_2>0\) ✓
Dual feasibility \(u=1\ge0\) ✓
Complementary slackness \(u(x_1+2x_2-2)=1(0)=0\) ✓; \(x_1,x_2>0\) so their multipliers are \(0\) ✓

Objective check.

\[f=4\left(\tfrac13\right)+6\left(\tfrac56\right)-2\left(\tfrac19\right)-2\left(\tfrac13\right)\left(\tfrac56\right)-2\left(\tfrac{25}{36}\right) =\tfrac43+5-\tfrac29-\tfrac59-\tfrac{25}{18}=\tfrac{25}{6}\ \checkmark\]

Interpretation. The unconstrained maximum was \(f=\tfrac{14}{3}=4.667\) at \((\tfrac13,\tfrac43)\), so the constraint costs \(4.667-4.167=0.500\). The multiplier \(u=1\) predicts that relaxing the constraint to \(x_1+2x_2\le3\) would gain about \(1\). But \(3\) is exactly where the unconstrained optimum becomes feasible (\(\tfrac13+\tfrac83=3\)), so beyond that the constraint stops binding and the true gain is only \(0.500\). Once again the shadow price is a tangent and over-predicts across a change of active set (compare Lesson 44, Problem 1).

Problem 2 — Wolfe's method, set up in full

Set up Problem 1 for Wolfe's method and state the tableau.

Solution.

The KKT system. With slack \(v\) on the constraint and surpluses \(s_1,s_2\) on \(x_1,x_2\ge0\):

\[4-4x_1-2x_2-u+s_1=0\ \Longrightarrow\ 4x_1+2x_2+u-s_1=4\]
\[6-2x_1-4x_2-2u+s_2=0\ \Longrightarrow\ 2x_1+4x_2+2u-s_2=6\]
\[x_1+2x_2+v=2\]

Phase I. Add artificials \(A_1,A_2\) to the first two rows and minimise \(A_1+A_2\):

Basis \(x_1\) \(x_2\) \(u\) \(s_1\) \(s_2\) \(v\) \(A_1\) \(A_2\) RHS
\(A_1\) 4 2 1 \(-1\) 0 0 1 0 4
\(A_2\) 2 4 2 0 \(-1\) 0 0 1 6
\(v\) 1 2 0 0 0 1 0 0 2
\(-w\) 6 6 3 \(-1\) \(-1\) 0 0 0 10

The restricted-entry rule. At every pivot, \(x_1\) may not enter while \(s_1\) is basic, \(x_2\) may not enter while \(s_2\) is basic, and \(u\) may not enter while \(v\) is basic (and vice versa in each pair). Subject to that restriction, pivot as usual.

The outcome. Phase I terminates with \(A_1=A_2=0\) and the basis \(\{x_1,\ x_2,\ u\}\) — note that \(s_1,s_2,v\) are all non-basic, so every complementary pair is respected. Reading the values gives \(x_1=\tfrac13\), \(x_2=\tfrac56\), \(u=1\), matching Problem 1.

Interpretation. Wolfe's method is ordinary simplex plus one prohibition. No new machinery is needed — which is precisely its appeal, and why quadratic programming was practicable long before modern interior-point codes. The prohibition is what enforces the only non-linear part of the KKT system.

Note also what the method does not need: no line search, no gradient iteration, no convergence tolerance. Like the simplex method, it terminates exactly in finitely many pivots.

Problem 3 — Portfolio selection

An investor allocates fractions \(x_1,x_2\) of a portfolio to two assets with expected returns \(12\,\%\) and \(8\,\%\), variances \(0.04\) and \(0.01\), and covariance \(0.005\). Minimise risk subject to a required return of at least \(10\,\%\) and \(x_1+x_2=1\), \(x_i\ge0\).

Solution.

Formulate.

\[\text{minimise } \sigma^{2}=0.04x_1^{2}+0.01x_2^{2}+2(0.005)x_1x_2\]
\[\text{s.t. } 0.12x_1+0.08x_2\ge0.10,\qquad x_1+x_2=1,\qquad x_i\ge0\]

Simplify. Substituting \(x_2=1-x_1\) into the return constraint:

\[0.12x_1+0.08-0.08x_1\ge0.10\ \Rightarrow\ 0.04x_1\ge0.02\ \Rightarrow\ x_1\ge0.5\]

The risk becomes a function of \(x_1\) alone:

\[\sigma^{2}(x_1)=0.04x_1^{2}+0.01(1-x_1)^{2}+0.01x_1(1-x_1) =0.04x_1^{2}+0.01-0.02x_1+0.01x_1^{2}+0.01x_1-0.01x_1^{2}\]
\[=0.04x_1^{2}-0.01x_1+0.01\]

Unconstrained minimum. \(\dfrac{d\sigma^{2}}{dx_1}=0.08x_1-0.01=0\) gives \(x_1=0.125\), which violates \(x_1\ge0.5\). Since \(\sigma^{2}\) is convex and increasing for \(x_1>0.125\), the constrained minimum is at the boundary:

\[\boxed{x_1^{*}=0.5,\quad x_2^{*}=0.5,\quad \sigma^{2}=0.04(0.25)-0.005+0.01=0.015}\]
\[\sigma=\sqrt{0.015}=12.25\,\%,\qquad \text{return}=0.5(12)+0.5(8)=10\,\%\]

Interpretation.

  • The minimum-variance portfolio would hold only \(12.5\,\%\) of the risky asset, with \(\sigma^{2}=0.01-0.000625=0.009375\), i.e. \(\sigma=9.68\,\%\) — but it returns only \(0.125(12)+0.875(8)=8.5\,\%\).
  • Demanding \(10\,\%\) instead of \(8.5\,\%\) raises risk from \(9.68\,\%\) to \(12.25\,\%\). That is the efficient frontier: every extra unit of return is bought with risk, and the QP traces the trade-off exactly.
  • Markowitz's insight, and the reason this is a QP rather than an LP, is that risk is quadratic because assets covary. Note that the two-asset portfolio at \((0.5,0.5)\) has variance \(0.015\), less than the \(0.025\) average of the individual variances — diversification is precisely the cross-term \(2\rho\sigma_1\sigma_2x_1x_2\) doing its work.

Problem 4 — Recognising the right method

Classify each problem and name the method from this course.

Problem Class Method Lesson
Maximise \(3x_1+5x_2\) s.t. linear constraints LP Simplex 5
As above, \(x_j\) integer ILP Gomory / branch and bound 16, 18
Ship from 3 plants to 4 depots at least cost Transportation VAM + MODI 8, 9
Assign 5 workers to 5 jobs Assignment Hungarian 10
Two firms choose prices simultaneously Game Saddle point / LP 11, 13
Schedule 6 jobs on 2 machines Sequencing Johnson's rule 14
Project of 20 activities, uncertain durations Network PERT 20
Staff a call centre Queueing \(M/M/c\) + cost model 27, 29
Order quantity with price breaks Inventory Discount algorithm 35
Minimise \(x^{2}+54/x\) on \([1,5]\), no derivatives 1-D NLP Golden section 40
Fit 50 parameters, gradients available Unconstrained NLP Conjugate gradient / BFGS 42
Minimise cost s.t. a fixed volume Equality-constrained Lagrange multipliers 43
Minimise risk s.t. return \(\ge r\) and \(\sum x_i=1\) QP Wolfe / Beale 45

The three questions that select a method.

  1. Is the objective linear? If yes and the constraints are linear, use LP (and check whether integrality is required). If no, go to 2.
  2. Are there constraints? If none, use Lessons 38–42. If they are equalities only, use Lagrange (L43). If inequalities, use KKT (L44).
  3. Is the objective quadratic and the constraints linear? Then it is a QP and Wolfe's method applies directly (L45).

Problem 5 — The capstone: one framework for the whole course

State the common structure of every model in the course.

Solution. Every technique in this course is an instance of

\[\text{optimise } f(\mathbf{x})\quad\text{subject to}\quad \mathbf{x}\in S,\]

and differs only in the form of \(f\) and \(S\), which in turn dictates the algorithm.

Unit \(f\) \(S\) Structural insight
I — LP linear polyhedron Optimum at a vertex; duality gives shadow prices
II — IP, games, networks linear + integrality / combinatorial discrete Relax, then branch or cut to restore integrality
III — queues, inventory convex non-linear usually a box Balance a falling cost against a rising one
IV — NLP general defined by \(g,h\) Convexity decides whether local means global

Five ideas that recur in every unit.

  1. Trade-offs are the subject. Ordering against holding (L31), waiting against service (L29), utilisation against responsiveness (L24), risk against return (§5 Problem 3). Optimisation is the arithmetic of a trade-off, never the elimination of one.
  2. Shadow prices are the most useful output. LP duals (L7), MODI's \(u_i+v_j\) (L9), queueing marginal analysis (L29), Lagrange \(\lambda\) (L43), KKT \(\mu\) (L44) are the same object: the rate of change of the optimum with a constraint. Managers act on shadow prices more often than on the optimal solution itself.
  3. Convexity is the dividing line. It converts local into global, guarantees that the simplex method and KKT terminate at the answer, and is what makes EOQ and \(M/M/c\) formulas trustworthy.
  4. Systems behave badly near their limits. Queues explode as \(\rho\to1\) (L24); batch sizes explode as \(P\to D\) (L33); steepest descent crawls as \(\kappa\to\infty\) (L42). Never design a system to run at its capacity.
  5. Optima are flat, so answers are robust. The EOQ costs \(2\,\%\) extra for a \(20\,\%\) error (L31); the staffing optimum was within \(1\,\%\) over two values of \(c\) (L29). This is what makes these models usable with imperfect data — and it means that a model's value lies in the structure it reveals, not in the last decimal of its answer.

A final caution. Every result in this course is conditional on a model, and every model is wrong in some respect: demand is not really constant, service times are not really exponential, and costs are not really known. The professional skill is not solving the model — a computer does that — but choosing the model, stating its assumptions, and knowing which of its conclusions survive when the assumptions do not. That judgement is what the forty-five hours have been for.

45.7 Practice Problems

  1. Maximise \(f=2x_1+3x_2-x_1^{2}-x_2^{2}\) s.t. \(x_1+x_2\le1\), \(x_i\ge0\). (Answer: unconstrained \((1,1.5)\) infeasible; constraint active gives \(u=1.5\), \(\mathbf{x}^{*}=(0.25,\ 0.75)\), \(f^{*}=2.125\))
  2. Show that \(Q=\begin{pmatrix}-4&-2\\-2&-4\end{pmatrix}\) is negative definite, and state what would change if \(Q\) were indefinite.
  3. Write the KKT system for \(\min\ x_1^{2}+x_2^{2}\) s.t. \(x_1+x_2\ge2\), \(x_i\ge0\), and solve it. (Answer: \(\mathbf{x}^{*}=(1,1)\), \(\mu=2\), \(f^{*}=2\))
  4. In Problem 3 of §5, recompute the optimal portfolio for a required return of \(11\,\%\). (Answer: \(x_1\ge0.75\) binds; \(\mathbf{x}^{*}=(0.75,\ 0.25)\), \(\sigma^{2}=0.025\), \(\sigma=15.81\,\%\))
  5. Name the method you would use for: (a) blending fuel at least cost; (b) choosing which of \(20\) projects to fund with a fixed budget; (c) deciding how many ambulances to station. (Answers: LP; \(0\)–\(1\) integer programming via branch and bound; \(M/M/c\) with a cost model)

45.8 Summary

  • A quadratic programme has a quadratic objective and linear constraints. Negative semi-definite \(Q\) (for a maximisation) makes it convex, so any KKT point is global.
  • Its KKT system is linear except for complementary slackness, which is combinatorial rather than genuinely non-linear.
  • Wolfe's method = simplex on the KKT system, with artificials for Phase I and the restricted-entry rule forbidding a complementary pair from being basic together. It terminates exactly, in finitely many pivots.
  • Beale's method works on the objective directly using free variables, and handles interior optima more naturally.
  • QP is the model behind portfolio selection, constrained least squares, SVMs and MPC, and is the inner problem of SQP, the leading general NLP method.
  • The course in one sentence: optimisation is the arithmetic of trade-offs; shadow prices are its most useful output; convexity decides whether a local answer is a global one; systems misbehave near capacity; and optima are flat enough that the structure a model reveals matters more than its last decimal.

Course complete. The forty-five hours have run from formulating a linear programme to certifying a constrained non-linear optimum. Every technique met here is implemented in standard software; what this course provides is the ability to choose the model, defend the assumptions and interpret the multiplier — the parts no solver performs.

Practise now: unit4-nlp-search-lab.html → QP Solver: enter \(Q\), \(\mathbf{c}\) and the constraints, watch Wolfe's restricted-entry pivots, and see the optimum on a contour plot with the active constraints highlighted.