Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 5 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Put . The image penalty is discrete isotropic total variation ; the fidelity term is the L1 norm . Introduce scalars and minimize the linear objectivesubject to the following affine residuals being cone-feasible:where is the Lorentz cone. Every component displayed is affine in , so stacking them gives exactly the requested form, withThe first two inequalities imply , so separate nonnegativity constraints for are unnecessary. The cone constraints imply . Every lifted feasible objective bounds the original objective from above; choosing and gives equality. Since both objective weights are positive, an optimum uses these tight values. Thus the lift is an exact second-order cone program for box-constrained TV-L1 denoising.
The product cone is proper, closed, convex and self-dual. The stacked has full column rank: the box rows recover , the fidelity rows then recover , and the first coordinates of the Lorentz blocks recover . Strict feasibility is also explicit: choose , then take and .
For generic cone slack , a canonical barrier ison and . The positive sheet condition matters: positivity of the quadratic expression alone would also include the wrong Lorentz nappe.
Composing the barrier with the affine residual map givesIts domain includes the strict inequalities above. Each orthant coordinate contributes one to the self-concordant barrier parameter and each Lorentz block contributes two. Therefore the product-cone logarithmically homogeneous barrier hasThe affine composition is the barrier used in the primal variables; it need not itself be logarithmically homogeneous in because the image data and box offsets are affine constants.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 5 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the nonnegative-pairing dual cone . The Lagrangian is for . Its infimum over unrestricted is finite exactly when . Therefore the conic dual problem isThe final equality uses the self-dual cone assumption.
For the canonical self-concordant barrier, use its logarithmically homogeneous barrier normalizationAt parameter , the primal barrier problem isWrite , the Legendre dual cone barrier. The matching dual barrier problem isDefining the dual barrier this way is valid generally; self-duality of the cone alone does not assert that an arbitrarily selected barrier equals its Legendre dual.
The joint central path characterization isThe primal stationarity equation is , exactly the dual feasibility equation after defining . For the dual relation, logarithmic homogeneity gives , so . Thus dual stationarity is , giving the same primal equation. At these points,
Newton step. At a chosen target parameter , defineLinearizing the three equality conditions gives the central-path Newton systemEliminating the slack and dual directions yieldsThe barrier Hessian is positive definite. Full column rank of therefore makes positive definite and the reduced solve unique. Use a damped step with and remaining interior; a full Newton step need not do so.
At an exact point with parameter , choosing gives and , the usual predictor towards the next path point. Infinitesimally,
The path definition presupposes interior feasibility and attainment of the barrier problems; strict primal-dual feasibility is a standard sufficient setting. The printed full-rank condition by itself is insufficient. For example , , and give the sole primal feasible point , with no interior slack at all, despite full column rank. Rank guarantees the Newton solve at an interior point, not existence of the central path.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
LetThe proximal operator optimality condition saysBy subgradient inversion under convex conjugacy, which uses Fenchel–Young inequality and from the Fenchel-Moreau theorem,Consequently , meaning . Uniqueness of the backward subgradient step identifies the result:This is the scaled Moreau decomposition. It requires one backward step on , with reciprocal parameter and scaled input , followed by a scalar multiplication and subtraction. No separate proximal computation of the convex conjugate is needed.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The forward subgradient step and backward subgradient step are the set-valued mapsThus means . They are respectively the explicit and implicit time discretizations of subgradient flow . At a differentiable point the forward update is , while the backward update evaluates the gradient at the new point. For proper closed convex data the latter is the proximal operator
To prove at most one output, suppose . Then and . The two subgradient inequalities imply monotonicity of a convex subdifferential, givingSince , . Convexity supplies this monotonicity; lower semicontinuity is not needed for this at-most-one argument.
Under the full printed assumptions the output actually exists at every . Properness ensures a finite point and excludes . Proper lower-semicontinuous convex has an affine minorant, so the quadratic proximal objective is coercive. Lower semicontinuity makes its minimum attained on a compact sublevel set. Convexity and the positive quadratic curvature make it strongly convex, hence its minimizer is unique. The subgradient optimality condition, with the differentiable quadratic term, is exactly . ThusThis also identifies precisely which assumptions provide existence, uniqueness and the update's optimality interpretation.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Use the standard form with unrestricted :The nonnegative multipliersatisfies and . This is a Farkas certificate for linear inequalities, so the system is infeasible by Farkas' lemma. In scalar form, adding twice the first inequality to the other two produceswhich directly exhibits the contradiction.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
One form of Farkas' lemma states that exactly one of the following holds:Their mutual exclusion is immediate: if both held, .
For existence of the alternative certificate, let , the finitely generated cone of the columns of . It is convex. It is also closed, a fact that must be justified rather than assumed for arbitrary linear images of closed cones. In a representation with dependent active generators, choose a nonzero dependence with at least one . Subtractfrom the nonnegative coefficient vector. The represented point is unchanged, all coefficients remain nonnegative, and at least one active coefficient disappears. Iteration produces a representation with independent active columns. For a convergent sequence in , pass to a subsequence using the same independent set, possible because there are finitely many sets. Its coefficients converge through a fixed left inverse, and their limits remain nonnegative. This proves closedness of finitely generated cones.
The indicator functional is therefore proper, lower semicontinuous and convex. Its Legendre-Fenchel transform isIndeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The Fenchel-Moreau theorem now givesIf , the left side is infinite, so some feasible has . Taking gives and . If , the first alternative holds. The biconjugation theorem applied to a closed finitely generated cone proves the alternative.
For inequalities with unrestricted , split and add nonnegative slack:The equivalent Farkas certificate for linear inequalities is
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Compute the convex conjugate of at a general pair . With , the independent variables become and , soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is , and the continuous convex equals its biconjugate.
For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve . For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For each fixed , choose the convex perturbation functionIt is jointly convex and has marginalBecause and are nonnegative and finite everywhere,for every . The inf-convolution is convex: for approximate decompositions of , take their convex combination and use convexity of both costs; then let their approximation errors tend to zero. Thus is a finite convex function on all of , hence continuous everywhere. In particular is proper and finite near zero, so the qualification in the previous solution applies at every :This is strong duality for a finite-valued infimal convolution.
No primal attainment was used. For example and meet all the stated assumptions, but is approached only as . This illustrates why a proof based on an assumed minimizing decomposition would be incomplete. The printed functions are real-valued everywhere, not merely extended-real; that distinction supplies continuity and the strong-duality qualification.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Use the maximizing-dual convention. For the perturbation function , defineThe primal problem is ; the Lagrangian dual problem is . The sign convention makes the dual marginal concave for jointly convex data; some formulations negate to express a minimization problem.
The central convex perturbation duality calculation isThe last inequality is weak duality. A sufficient finite-dimensional condition for strong duality with dual attainment is: is jointly proper and convex, is proper with finite, and is finite on a neighborhood of zero. More generally suffices.
Indeed continuity of a convex function on the interior of its domain gives a supporting subgradient , soTherefore and the dual maximum is attained. This qualification establishes equality and dual attainment; it does not by itself establish a primal minimizer.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Let . Maximizing a linear functional over this line segment occurs at an endpoint, soThis identifies as a support function. Its convex conjugate is the indicator functional : if , then for every , with equality at zero; if , strict separation and positive scaling of the separating vector make the supremum infinite.
For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. HenceThis is support-function subgradients as exposed faces. In particular a maximizing really is a subgradient, since for every .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The Legendre-Fenchel transform and biconjugate areThe Fenchel-Moreau theorem says that every proper convex function which is lower semicontinuous equals its biconjugate. More generally, if a proper extended-real has an affine minorant, thenwhere the right side is the greatest lower semicontinuous convex minorant. This is biconjugation as closed convexification. The affine-minorant hypothesis ensures that the closed convexification is proper; an unqualified statement including arbitrary improper functions would need separate conventions.
Here are the essential proof steps. The Fenchel–Young inequality gives . Every term in the supremum defining is an affine minorant of , and conversely any affine minorant has . Thus is exactly the supremum of all affine minorants, hence is convex and lower semicontinuous.
Put . Its epigraph is the closed convex hull of the epigraph of . Applying the half-space representation of a closed convex set in recovers that epigraph from its containing half-spaces. A containing half-space writtenhas , since epigraphs extend upwards. If , it is precisely the epigraph inequality of an affine minorant, .
Vertical half-spaces with must also be accounted for. Choose one affine minorant of , which exists because is proper and closed: strictly separate from its epigraph for a finite domain point ; the separating coefficient of cannot be zero, since that would not distinguish points with the same . If a vertical containing inequality is , thenis still an affine minorant on the domain of . At a point violating the vertical inequality, these minorants tend to infinity as . Thus vertical domain restrictions are also recovered by the supremum of affine minorants.
Consequently equals that supremum. Every affine minorant of is below , while the epigraph of any affine minorant of contains its closed convex epigraph hull. Therefore and have the same affine minorants, completing . The theorem in the previous solution supplies the geometric separation step behind biconjugation.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 62 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Let be the family of closed half-spaces containing . Certainly . To prove the reverse inclusion, exclude an arbitrary .
Suppose first that is nonempty. Its Euclidean projection onto a convex set exists: minimizing the continuous squared distance may be restricted to a sufficiently large closed ball, whose intersection with the closed set is compact. Put . For every , convexity puts in for . Minimality of givesThus the closed half-spacecontains , while excludes . Since every point outside is excluded by some member of ,This is the half-space representation of a closed convex set. If , every point can again be excluded by a containing half-space, so the intersection is empty. If , no proper half-space contains it and the empty intersection is, by convention, .
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 6 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
An explicit construction gives Bernstein's lethargy theorem in the requested inequality form. SetStrict decrease makes every coefficient positive. Telescoping and the limit assumption giveThusdefines a continuous function by the Weierstrass M-test and the uniform limit theorem. Apply the positive lacunary Chebyshev series calculation. At ,For , choose so that . Its error isTherefore the function satisfiesThis explicit Chebyshev construction for Bernstein lethargy also has . It shows that continuity imposes no universal speed of convergence of best polynomial approximation, even though convergence itself follows from the Weierstrass approximation theorem.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 6 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The original PDF has indices ; the exponent is lost in the TeX transcription. This lacunary indexing is essential to the positive lacunary Chebyshev series argument below.
Let be the least nonnegative integer with , so for . DefineFor the sum is empty and means the zero polynomial. Each included Chebyshev polynomial has degree at most . Also on the interval, so summability of the positive coefficients gives uniform convergence by the Weierstrass M-test, andChoose and the points , . For every omitted index , the integer is odd. Consequently,Every term of the tail has the same sign at a given point, and thereforeThis shows both that the error norm is exactly and that it alternates at distinct points. The points are in decreasing order; reversing their order still gives alternation. The Chebyshev alternation theorem proves that this partial sum is the unique best uniform approximation. HenceIn particular, and . The equal signs of all tail terms at the same extrema are the reason positivity and the odd integer frequency ratios are useful.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 6 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
We work in the usual real-valued setting of the Chebyshev alternation theorem. For and an algebraic polynomial of degree at most , the theorem says that is a best uniform approximation if and only if its error has ordered points with alternating maximal values:If , the zero-error case is included directly.
Existence follows, for example, by taking a minimizing sequence: its supremum norms are bounded, all norms on the finite-dimensional polynomial space are equivalent, and a convergent coefficient subsequence attains the infimum. To prove uniqueness of best uniform polynomial approximation, let both attain the minimum error . Their average has error at most by the triangle inequality and therefore exactly by minimality.
If , both polynomials equal and are equal. Otherwise apply the Chebyshev alternation theorem to . At every alternating extremal point, is either or . But it is the average of and , each lying in . An average attains an endpoint of this interval only when both entries equal that endpoint. Hence at all points. The difference is a degree-at-most- polynomial with more than distinct zeros, so it is identically zero. The best approximating polynomial is unique.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 5 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For the uniform spline knots, translation reduces every degree-two basis function to a quadratic cardinal B-spline. From the Cox-de Boor recurrence, an order-three function takes the valuesAt the prescribed site , only and, when , have nonzero values. Hence the B-spline collocation matrix isThe shift satisfies . A finite geometric expansion gives the exact inverseIts th absolute row sum is , so . Use the preceding bounds and the supplied stability constant :Thus the linear growth of shifted quadratic spline interpolation is , which in particular is . The lower bound, rather than the upper bound alone, proves that these spline interpolation operators are not uniformly bounded.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 5 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
Write , and let . We use the standard interpolation convention of distinct ordered sites . Together with , the Schoenberg–Whitney theorem makes the B-spline collocation matrix invertible. Equivalently, its invertibility is implicit in the existence of the interpolation operator for every data vector.
If distinctness is not understood, the printed positivity condition alone is insufficient. For the order-two basis on spline knots , take . Both diagonal B-spline values are , but the two rows of coincide. Arbitrary data cannot then be interpolated uniquely. The norm statement below concerns the intended well-defined interpolation operator.
Spline interpolation determines the coefficient vector by , and henceNonnegativity and the subpartition of unity for B-splines giveFor completeness, extend the finite spline knot sequence beyond both ends. For the full sequence the order-one interval indicators sum to one. Summing the Cox-de Boor recurrence and shifting the index in its second term combines the two coefficients of each lower-order B-spline to one, so induction gives partition of unity at every order. Our finite collection is a subset of that nonnegative collection, and thus has sum at most one. Repeated spline knots are handled by the standard zero-term convention or a knot limit. This argument controls the entire interval, not only the basic knot interval.
Since , the operator norm upper bound isHere the matrix operator norm is the maximum absolute row sum. For the lower bound, choose a row of with maximum absolute row sum and a data vector whose components are the signs of that row's entries. Then andA continuous piecewise-linear function taking these values at the distinct ordered sites, and constant outside their range, has supremum norm one. Apply the given uniform-norm stability of a B-spline basis to its coefficient vector:ThereforeThe construction of the bounded continuous data extension is what permits the matrix norm to give a lower bound for a function-space operator norm.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 4 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For the indicated function the cosine substitution givesThe absolute-value function is Lipschitz continuous with constant one, and so is sine. Their composition therefore satisfiesUse the sharper intermediate estimate from the preceding part, rather than the ordinary interval modulus of continuity:
The usual inverse theorem for trigonometric approximation cannot hold verbatim with the ordinary interval modulus of continuity. It would implyBut comparison with the endpoint giveswhich is of order and contradicts that bound as . This is an endpoint obstruction to an algebraic inverse approximation theorem. The algebraic approximation rate measures smoothness after cosine substitution; cosine compresses distances quadratically near the endpoints. A valid algebraic inverse theorem must account for that endpoint geometry rather than using the unchanged periodic formulation.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
The first Jackson theorem for periodic approximation asserts that a universal constant satisfiesfor every continuous -periodic function , where the infimum is over degree-at-most- trigonometric polynomials.
Apply it to the even function . If is a trigonometric polynomial approximating , its even parthas no larger error, because and the triangle inequality bounds each averaged error by . Every even trigonometric polynomial has the formHere the Chebyshev polynomials have algebraic degree , so has degree at most . Surjectivity of cosine givesConversely, every algebraic polynomial of degree at most yields such an even trigonometric polynomial. Taking infima therefore proves the exact identity , not merely an inequality. Combine this with the periodic theorem and the preceding modulus of continuity estimate:Symmetrization, the degree correspondence and the equality of norms justify every step in transferring the Jackson-type estimate.
Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 61 4 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-07
For a periodic function use the modulus of continuityOn the interval, take the supremum over pairs of points whose distance is at most . The mean value theorem applied to cosine, whose derivative has absolute value at most one, givesBoth cosine values lie in , so for ,Taking the supremum provesThe cosine substitution for polynomial approximation is also a linear isometry in the supremum norm, since cosine maps a full period onto ; its image consists of even continuous periodic functions.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





