Back to the on-screen lesson ·
Local implies global under convexity, the proof, and what a method may claim when it does not hold.
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 state and prove that a local minimum of a convex function over a convex set is a global minimum, and to say where each of the two hypotheses is used in the proof. You will also be able to say exactly what a method that has converged is entitled to claim in each case — the optimum when both hypotheses hold, and a statement about one neighbourhood when they do not — and why restarting a non-convex search raises the chance of a good answer without ever producing a certificate.
Convex sets, from lesson 7: every mixture of two feasible points is feasible. Convex functions, from lesson 8: the function at a mixture is at most the mixture of the values. This lesson is the theorem those two were for, and it is the only theorem in the course that changes what a method is allowed to say.
Local minimum: a feasible point no worse than every feasible point near it. A statement about a neighbourhood.
Global minimum: a feasible point no worse than every feasible point at all. A statement about the problem.
Neighbourhood: the feasible points within some small distance — what nearby means, made precise.
Stopping condition: the test a method applies before reporting. It is almost always local.
Certificate: evidence that an answer is optimal, as opposed to evidence that a method has stopped.
Multistart: running a method from many starting points and keeping the best result. It raises the chance of a good answer and produces no certificate.
Hypothesis: a condition a theorem requires. Here there are two — the set is convex and the function is convex — and each does a separate job.
Theorem. Let $f$ be convex on a convex set $C$, and let $x^\star \in C$ be a local minimum of $f$ on $C$. Then $x^\star$ is a global minimum.
Both hypotheses are used, and they are used in different places:
Drop either and the theorem fails. An integer program is a convex objective over a non-convex set, and its local minima are not global — which is the entire reason unit 4 is a separate unit.
Why this is the dividing line. Convexity is what makes a local answer the answer. Without it, a method that has stopped has only told you that nothing nearby is better — which is a true statement about a neighbourhood and no statement at all about the problem.
A numerical method can only ever test a neighbourhood. It computes a gradient, takes a step, and stops when no small step improves. That stopping condition is local by construction, and no amount of computation makes it global. What makes the answer global is a theorem proved before the method ran.
| Convex | Non-convex | |
|---|---|---|
| A method stops at $x$ | $x$ is optimal | nothing nearby is better |
| Certificate available | yes (duality, lesson 13) | in general, no |
| More computation | finds it faster | finds more local answers |
| Restarting | pointless | helps, and proves nothing |
Another way: picture
Two landscapes. The first is a single bowl: a ball released anywhere rolls to the same floor. The second is a range of hills and hollows: where the ball stops depends entirely on where it was dropped, and the ball has no way of knowing whether a deeper hollow lies over the ridge.
Another way: steps
Before running any method:
Suppose $x^\star$ is a local minimum and, for contradiction, that some feasible $y$ has $f(y) < f(x^\star)$.
For $\lambda \in (0, 1]$ let $z_\lambda = (1-\lambda)x^\star + \lambda y$. Because $C$ is convex, $z_\lambda \in C$: it is a point the problem permits.
Because $f$ is convex, $$f(z_\lambda) \le (1-\lambda) f(x^\star) + \lambda f(y) < (1-\lambda) f(x^\star) + \lambda f(x^\star) = f(x^\star),$$ the strict step using $f(y) < f(x^\star)$ and $\lambda > 0$.
Now take $\lambda$ as small as you like. The point $z_\lambda$ is then as close to $x^\star$ as you like, and it is still strictly better. So every neighbourhood of $x^\star$ contains a better point — which is precisely the denial of $x^\star$ being a local minimum. Contradiction, so no such $y$ exists.
The shape is worth keeping: a local claim is upgraded to a global one by showing that any counterexample, however far away, can be dragged arbitrarily close along a segment that stays legal.
Reading convergence as optimality. A method converges when it stops moving. On a non-convex problem that is a statement about one hollow.
Checking convexity at the answer. $f''(x^\star) > 0$ classifies the point. Convexity is about the whole domain and has to be established before, not after.
Assuming the solver would have said. Most solvers do not check convexity of a general nonlinear model, and cannot. The claim they return is whatever their class of method supports, and the burden of knowing which is on the modeller.
Believing a good answer proves a good method. On a non-convex problem, an answer that happens to be optimal is still an answer with no certificate, and there is no way to tell the two cases apart from inside.
Convergence is a fact about the method: the iterates stopped moving, the gradient got small, the improvement fell below a threshold. Optimality is a fact about the problem. On a convex problem they coincide, and it is easy to come away thinking they are the same word — most people's experience of optimization is convex, because the tractable examples are. They come apart the first time a model has an integer variable or a non-convex objective, and they come apart silently: the run looks identical, the report looks identical, and only the theorem you did or did not prove beforehand distinguishes them.
$\min\ (x-3)^2 + (y+1)^2$ over $x + y \le 4$, $x, y \ge 0$. Objective convex (a sum of squares); set convex (linear constraints).
Both hypotheses checked, before running anything.
A method stops at some $x^\star$. By the theorem it is the global minimum, and "this is the optimal plan" is an accurate sentence.
The claim is permitted.
Now require $x, y$ integer. The objective is unchanged and still convex; the set is now a scatter of dots and is not. The same method's answer is now "the best we found", and turning that back into a certificate needs a bound — unit 4.
One hypothesis gone, one sentence lost.
$f(x) = x^4 - 8x^2 + 2x$ has $f'' = 12x^2 - 16$, negative for small $|x|$: not convex.
The test fails, so the theorem does not apply.
It has two hollows, near $x \approx -2.1$ and $x \approx 1.9$, with different depths. A descent method started at $x = -3$ reaches the first; started at $x = 3$ it reaches the second.
Two stopping points, both correct as local claims.
Both runs report convergence and neither is wrong about what it tested. What is missing is any way, from inside either run, to learn that the other hollow exists. That absence — not slowness, not inaccuracy — is what non-convexity costs.
The missing thing is information, not effort.
Minimise a sum of squared errors subject to linear constraints. Sum of squares: convex. Linear constraints: convex set. Both hold, so yes.
Check the two hypotheses separately.
Minimise the same objective, but at most three of the variables may be non-zero. The objective is unchanged and still convex. "At most three non-zero" is a union over which three — not convex. So no.
Maximise a concave revenue subject to linear constraints. Maximising concave is the mirror of minimising convex, so the theorem applies in its mirrored form: yes. The habit worth forming is to state which of the four combinations you are in before choosing a method, because it decides what the method may be asked to promise.
Match each piece of evidence to the strongest claim it supports.
| A local minimum only | A global minimum | A promising candidate, not a proof | |
|---|---|---|---|
| Descent stopped; convexity was not established | |||
| A local minimum in a convex model | |||
| The best result from ten random restarts |
Build the proof that a local minimum of a convex function over a convex set is a global minimum.
This task has no paper form; do it on a device.
A one-variable objective has $2$ separate dips, each with a valley floor. From how many of these can a descent method fail to reach the best one?
Answer:
A non-convex problem is solved from $29$ random starting points and the best answer kept. What has been established?
A model mixes 5 feasible plans along a segment. In the proof that a local minimum is global, where is the convexity of the *feasible set* used, as distinct from the convexity of the function?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A model mixes 6 feasible plans along a segment. In the proof that a local minimum is global, where is the convexity of the *feasible set* used, as distinct from the convexity of the function?
You can prove local-implies-global, name where each hypothesis enters, and say what a converged method may claim with and without convexity. Next: finding that minimum when there are no constraints at all.
10. Your turn: which of these may claim a global answer?, step 3