Back to the on-screen lesson ·
A quadratic objective over linear constraints, the matrix that decides whether it is easy, and the bridge back to linear algebra.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write a quadratic program in standard form, form the matrix of its objective, and decide from that matrix alone whether the problem is convex and easy or indefinite and hard. You will also be able to recognise least squares as an unconstrained convex quadratic program whose gradient equation is the normal equations, solve a small constrained fit, and explain why two problems with identical linear constraints can sit on opposite sides of the tractability line.
Convex functions and the second-derivative test; the KKT conditions; least squares from linear algebra, where it was a projection. This lesson connects them: least squares is an unconstrained convex quadratic program, and adding constraints to it is what a great deal of applied optimization consists of.
A quadratic program is
$$\min\ \tfrac12 x^\top Q x + c^\top x \quad\text{subject to}\quad Ax \le b,\ \ Ex = d,$$
with $Q$ symmetric. The feasible set is a polyhedron, so it is convex whatever $Q$ is; the whole question is the objective.
$Q$ decides everything.
| $Q$ | Objective | Problem |
|---|---|---|
| positive definite | strictly convex | one solution, easy |
| positive semi-definite | convex | solvable, solution may not be unique |
| indefinite | neither | non-convex, in general NP-hard |
That is the sharpest statement of the course's organising idea available anywhere: two problems with identical constraints, differing only in the sign of one coefficient, sit on opposite sides of the tractability line. Linearity of the constraints has nothing to do with it.
Least squares is the unconstrained case. Minimising $\|Ax - b\|^2 = x^\top A^\top A x - 2 b^\top A x + b^\top b$ has $Q = 2A^\top A$, which is always positive semi-definite. So least squares is always convex, its gradient equation $A^\top A x = A^\top b$ is the normal equations, and fitting a line is one solve rather than a search.
Why the class matters. A great deal of applied work is least squares with something added: a non-negativity constraint, a budget, a bound. Each addition keeps the problem a convex quadratic program, and there are excellent methods — active set for small problems, interior point for large. Portfolio optimization, model predictive control, support vector machines and constrained curve fitting are all in this class.
Another way: picture
A bowl sitting over a polygon drawn on the floor. If the bowl's lowest point is over the polygon, that is the answer. If it is outside, the answer is on the polygon's edge — the lowest point of the bowl that is still above the shape, which is where the bowl's contours are tangent to an edge.
Another way: steps
To solve a quadratic program:
Fitting $y = mx + c$ to points $(x_i, y_i)$ means minimising $\sum_i (m x_i + c - y_i)^2$.
As calculus: a convex quadratic in $(m, c)$, so set both partial derivatives to zero and solve two linear equations.
As linear algebra: $\min \|Ax - b\|^2$, solved by the normal equations $A^\top A x = A^\top b$ — the projection of $b$ onto the column space of $A$.
As optimization: an unconstrained convex quadratic program, whose KKT conditions reduce to stationarity because there are no constraints.
All three are the same computation. The optimization view is the one that extends: require $m \ge 0$, or $|m| + |c| \le 1$, and the calculus view stops working while the problem stays a convex quadratic program and stays easy. That extensibility is the reason to learn the third view even though the first two already work.
Assuming linear constraints make it easy. They make the feasible set convex and settle nothing about $Q$.
Forming $A^\top A$ in practice. It squares the condition number. A QR or SVD factorisation solves least squares more accurately and is what any library does.
Reading an indefinite $Q$ as a modelling error. Sometimes it is the model. A risk model with negative correlations can produce one legitimately, and the right response is to say the answer is local, not to force $Q$ positive definite and pretend.
Forgetting the $\tfrac12$. The convention $\tfrac12 x^\top Q x$ makes $Q$ the Hessian exactly. Dropping it halves every multiplier and the error is invisible until the numbers are compared against something.
The name covers two things that share a form and share nothing else. A convex quadratic program — $Q$ positive semi-definite — is solved in polynomial time by mature software and is the backbone of applied optimization. A non-convex one, $Q$ indefinite, is NP-hard and needs unit 4's machinery or unit 26's honesty. They are written identically, and a solver will accept both without comment. Checking the definiteness of $Q$ is one eigenvalue computation, it decides which of the two you actually have, and it is the single cheapest thing in this course that changes what you are entitled to say about the answer.
Fit a constant $m$ to the numbers $3, 5, 10$: minimise $(m-3)^2 + (m-5)^2 + (m-10)^2$. Derivative zero gives $m = 6$, the mean.
Unconstrained: one solve.
Now require $m \le 4$ — a bound from outside the data. The unconstrained answer $6$ is infeasible.
The constraint bites.
The objective is convex and decreasing up to $6$, so on $m \le 4$ it is smallest at $m = 4$. The multiplier is $-2\sum(4 - x_i) = 2(3+5+10) - 24 = 12$: tightening the bound by one more unit would cost about $12$ in fit. The problem stayed easy and gained a price.
Constrained: still one small problem, plus a price.
$\min\ x^2 + y^2$ over $x + y \ge 2$, $x, y \ge 0$. $Q = 2I$, positive definite. KKT gives $x = y = 1$, and lesson 9 says it is global.
Convex: solved, with a certificate.
$\min\ -x^2 + y^2$ over the same constraints. $Q$ has eigenvalues $-2$ and $2$: indefinite.
One sign changed.
Now the objective falls without limit along the $x$ direction if the region is unbounded there, and even on a bounded region the minimum sits at a vertex that no local method can be trusted to find. Identical constraints, and the problem moved from a two-line solve to NP-hard.
The constraints never decided it.
The constraints are linear, so the feasible set is convex. The question is the objective, and the objective's matrix is $Q = \begin{pmatrix} 4 & 3 \\ 3 & 4\end{pmatrix}$ under the $\tfrac12$ convention.
Only the objective can fail.
Test definiteness: the leading entry $4 > 0$, and the determinant is $16 - 9 = 7 > 0$. Both leading minors positive, so $Q$ is positive definite.
So yes — convex, with a unique answer that KKT will find and lesson 9 will certify. Note how close it came: a cross coefficient of $5$ instead of $3$ would give determinant $16 - 25 < 0$, an indefinite $Q$, and a non-convex problem. The whole tractability of the model turns on one number nobody looks at twice.
Which single number $m$ minimises $(m - 2)^2 + (m - 10)^2 + (m - 13)^2$?
Answer:
A quadratic program minimises $2x^2 + -8x$ over linear constraints. Is it convex?
| Convex feasible polyhedron | Convex objective | Evidence of upward curvature | Convex optimization problem | |
|---|---|---|---|---|
| Linear constraints | ||||
| Positive quadratic coefficient | ||||
| Positive second derivative | ||||
| Resulting quadratic program |
The unconstrained minimiser of $(x - 17)^2$ is $x = 17$. With the constraint $x \le 6$, where is the constrained minimum?
Answer:
Write the matrix $Q$ for which $3x^2 + 3xy + 5y^2$ equals $\tfrac12 (x, y) Q (x, y)^\top$.
This task has no paper form; do it on a device.
Which single number $m$ minimises $(m - 3)^2 + (m - 5)^2 + (m - 7)^2$?
Answer:
A portfolio model minimises $-5x^2 + y^2$ over linear constraints. What has changed?
| A negative curvature direction | A positive curvature direction | Indefinite, hence non-convex | Proves only a local result | |
|---|---|---|---|---|
| Negative coefficient on $x^2$ | ||||
| Positive coefficient on $y^2$ | ||||
| Quadratic matrix | ||||
| A converged local method |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A quadratic program minimises $2x^2 + -8x$ over linear constraints. Is it convex?
| Convex feasible polyhedron | Convex objective | Evidence of upward curvature | Convex optimization problem | |
|---|---|---|---|---|
| Linear constraints | ||||
| Positive quadratic coefficient | ||||
| Positive second derivative | ||||
| Resulting quadratic program |
You can form a quadratic program, test it for convexity from its matrix, and connect it back to least squares. That closes unit 3. Next: what to do when the variables must be whole numbers.
9. Your turn: is $\min\ 2x^2 + 3xy + 2y^2$ over $x + y \le 5$ convex?, step 3