Past exam of the continuous optimisation course of the University of Oxford 2011 3 iii Solution 2026-10-31
For and , define the optimization LagrangianThe Lagrangian primal isFor feasible , the supremum is : equality terms vanish and the nonpositive inequality term has maximum zero at . If , scale in the direction to make the supremum infinite. If the inequality fails, send . Thus the inner supremum is exactly the objective extended to off the feasible set. This proves equivalence with the original problem, including its infeasible case.
Past exam of the continuous optimisation course of the University of Oxford 2011 3 ii Solution 2026-10-31
The equality gradients are independent everywhere. At an interior point of the ellipsoid, there is no active inequality, so the Mangasarian–Fromovitz constraint qualification holds. At a boundary point , a qualifying direction must satisfy and .
If , choose . At a boundary point , andThus the qualification holds at every feasible point. If , the only feasible point is ; for every , , so no strict direction exists. This provesThe equivalence also identifies this case with strict feasibility of the inequality on the affine equality space.
Past exam of the continuous optimisation course of the University of Oxford 2011 3 i Solution 2026-10-31
Take the usual symmetric meaning of positive definite . To include all data allowed by the source, first check feasibility. PutFull row rank makes positive definite. Every satisfying is uniquely with , and . ThusIf , there is no feasible point. If , the only feasible point is , and is optimal for every . If , the Slater condition holds, and the following KKT conditions are necessary and sufficient:Necessity follows from the constraint qualification proved in (ii). Sufficiency follows from convexity: the stationary optimization Lagrangian is minimized at , while its feasible values never exceed the objective, and complementary slackness makes its value at equal the objective.
The singleton case cannot be silently covered by ordinary KKT necessity. For example, let , , , . The sole feasible point is optimal, but stationarity would require to lie in the span of , which is impossible. The feasibility split above supplies genuinely necessary and sufficient conditions without assuming an unprinted regularity hypothesis.
Past exam of the continuous optimisation course of the University of Oxford 2011 2 iv Solution 2026-10-31
A sequence is Q-linearly convergent to in a specified norm if for all sufficiently large , with some . Its asymptotic factor is the limsup of consecutive error ratios.
Put , and . For an error , an exact first-coordinate step sets , and an exact second-coordinate step sets . Once the first coordinate step has occurred, errors consequently alternate between the two linesThe next error has its free coordinate multiplied in magnitude by , and both lines have the same Euclidean norm factor . Therefore, until finite termination,This is a sharp bound, attained after the first step; the objective errors have factor per step. If , the problem separates and at most two exact steps suffice. When the condition number is large, the factor approaches one: the iterates zigzag slowly across a narrow tilted valley.
Past exam of the continuous optimisation course of the University of Oxford 2011 2 iii Solution 2026-10-31
Use the exact line searches from part (i). After minimizing along one coordinate, the corresponding gradient component is zero. Unless the optimum has been reached, the whole nonzero gradient therefore lies along the other coordinate, which is selected next. The chosen signed coordinate direction then has . A selected zero gradient component can be skipped; it already minimizes that coordinate.
The Zoutendijk theorem therefore gives . The unique point with zero gradient isSince and is invertible, gradient convergence implies . Positive definiteness makes this the unique global minimum.
Convergence also holds if “line search” is interpreted as any fixed-parameter Wolfe search. If coordinate is selected, its signed step satisfies , where and . Sufficient decrease gives . Summation shows that selected gradient components tend to zero and step lengths tend to zero. The other component was selected in the preceding step; Lipschitz continuity then makes it tend to zero as well. Thus the full gradient converges to zero. The simple one-step angle argument and sharp Q-linear factor below use exact coordinate minimization; arbitrary Wolfe choices need not have that same Euclidean one-step factor.
Past exam of the continuous optimisation course of the University of Oxford 2011 2 ii Solution 2026-10-31
A standard form of the Zoutendijk theorem assumes that is continuously differentiable and bounded below on the starting level set, that its gradient is Lipschitz on a neighborhood of that set, and that the steps satisfy fixed Wolfe conditions. For descent directions , defineThenIn particular, if , then . This last angle hypothesis is needed to turn the general descent theorem into gradient convergence.
For this quadratic, , the Hessian matrix is the constant positive-definite matrix , and the gradient is globally Lipschitz with constant . Its level sets are compact. Thus all objective-function hypotheses hold; Wolfe holds for the exact steps with the parameters above. The direction hypothesis will be verified for alternating exact coordinate minimization in the next part.
Past exam of the continuous optimisation course of the University of Oxford 2011 2 i Solution 2026-10-31
Assume the denominators are defined, so . For a descent direction , set . The Wolfe conditions areThe first is sufficient decrease and the second is the curvature condition. Hereis positive definite, with eigenvalues . The exact step isIt gives , so the curvature condition holds. Its decrease is , so sufficient decrease holds for the usual choice , . Hence exact searches satisfy Wolfe with an Armijo constant at most one half. If one allowed , even an exact quadratic minimizer would fail that condition; the parameter range matters.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 v Solution 2026-10-31
For the convention above, after approximately minimizing , updateThe exact shifted-residual identity isIf the constraint is violated, , its left side is , and replacing the new multiplier by its limiting value gives the printed local estimateFor arbitrary iterates, the precise unshifted statement includes the negative part:Thus the printed estimate describes approach from the violated side; it is not a universal signed equality on the feasible side. This qualification follows directly from the projection in the update.
Its numerical significance is that the constraint violation is controlled by times the multiplier error, rather than by alone. Once multipliers are accurate, high feasibility accuracy can be obtained with a moderate positive penalty parameter. This avoids forcing to become enormous and reduces the ill-conditioning of the inner minimization. Inactive constraints eventually have zero multiplier and zero violation.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 iv Solution 2026-10-31
Convert to minimization with and retain . A continuously differentiable inequality augmented Lagrangian method uses the merit functionFor its contribution is ; otherwise it is the constant . This shifted truncation permits multipliers to decrease as well as increase while remaining nonnegative.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 iii Solution 2026-10-31
Write , . The two inactive constraints are strict exactly for . Complementary slackness gives . The KKT conditions reduce toIf these give . Otherwise and , which gives a negative multiplier and is inadmissible. Thereforeis the only KKT point with this active set. Its active gradient is nonzero, so the linear independence constraint qualification, and hence the Mangasarian–Fromovitz constraint qualification, holds.
It is not a local maximizer: is feasible for small and has objective . The feasible boundary path for small negative has objective , so it is not a local minimizer either.
Past exam of the continuous optimisation course of the University of Oxford 2011 1 ii Solution 2026-10-31
All three active constraints force and , which also satisfy . For maximization use , . At ,Stationarity gives the complete familyIn particular is strictly positive. Three gradients in two dimensions cannot be linearly independent, so the linear independence constraint qualification fails. But gives , so the Mangasarian–Fromovitz constraint qualification holds.
For a nonzero linearized feasible direction , each , andThe inequality is strict because equality would require all three inner products to vanish, and the first and third gradients already span . This proves a strict local maximum: otherwise a sequence of nearby feasible points with no smaller objective would, after normalizing their differences from and taking a convergent subsequence, give a unit linearized feasible direction with nonnegative objective derivative, contradicting the displayed inequality. Thus
Past exam of the continuous optimisation course of the University of Oxford 2011 1 i Solution 2026-10-31
Use for the maximized objective function, and adopt optimization constraints withThe feasible set is nonempty, since it contains . It is closed as an intersection of inverse images of closed sets under continuous functions. It lies in the disk of radius , so is bounded and therefore compact by the Heine-Borel theorem. The objective function is a polynomial, hence continuous. The extreme value theorem now guarantees a global maximizer exists.
Retain
Data, AbstractData and StringData from part (c). The following are the additional software classes. Formatting denotes the supplied formatting facility with its two static format overloads; its implementation is expressly not required. These calls preserve the distinction between a minimum width and a maximum width: no stored value is truncated.abstract class NumericData extends AbstractData {
private int minDigits = 0;
protected NumericData(boolean leftj) { super(leftj); }
public final void setDigits(int n) { minDigits = Math.max(0, n); }
protected final int digits() { return minDigits; }
}
final class IntegerData extends NumericData {
private final int value;
public IntegerData(int n, boolean leftj) {
super(leftj);
value = n;
}
public String toString() {
return Formatting.format(value, digits());
}
}
final class RealData extends NumericData {
private final double value;
private int minPlaces = 0;
public RealData(double d, boolean leftj) {
super(leftj);
value = d;
}
public void setPlaces(int p) { minPlaces = Math.max(0, p); }
public String toString() {
return Formatting.format(value, digits(), minPlaces);
}
}Zero is the default minimum, and a nonpositive setting removes that minimum. Formatting a negative value, or a value already longer than the minimum, is delegated to the stated formatter contract. The inherited
length() calls the current toString(), so a change to either formatting setting immediately changes the measured column width. For example, after setDigits(3), an IntegerData containing 42 renders 042 and has length 3; after setPlaces(2), a RealData containing 2.7 renders 2.70 and has length at least 4.Unlike
StringData, these numeric software objects are mutable because their displayed state can change. Their numeric values and alignment remain fixed. The useful invariant isThe UML class diagram separates text shared by every displayable item from numeric formatting shared only by numeric items. A dashed hollow-triangle arrow denotes realization of a Java interface; solid hollow-triangle arrows denote class inheritance. Both kinds of arrow point towards the more general type.
AbstractData owns alignment and computes length from the current rendered text. NumericData adds the minimum digit width. IntegerData and RealData each own their numeric value, while RealData alone owns the minimum number of decimal places. The numeric formatting object methods do not belong on Data: ordinary text has no meaningful setPlaces operation. The design choice isThe problem is undecidable. Reduce the halting problem to it. Given a Turing machine and input word , construct a Turing machine over with the following behavior on input :
- If , reject.
- If , simulate on the fixed word . If that simulation ever halts, whether accepting or rejecting, accept ; otherwise continue the simulation forever.
This is an effective construction: are fixed data stored in the description of . Its recognized formal language isTherefore accepts exactly one input word if and only if halts on . A supposed decision procedure for the singleton-language problem for Turing machines, applied to the constructed , would decide the halting problem. The standard undecidability of the halting problem excludes that possibility.
The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.
First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of , test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.
Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word . If the initial automaton state is accepting, may be the empty word. Build a complete deterministic finite automaton for the singleton formal language : it tracks the matching prefix of , accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.
Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with , accepting exactly when the coordinate accepts and the other coordinate accepts. This product recognizesApply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that belongs to ; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.
The formal language is not a context-free language. Suppose otherwise, and let be a pumping length from the pumping lemma for context-free languages. ChooseThis word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would givewith in the formal language for every integer .
Let be the respective numbers of symbols in the two pumped pieces together. The window cannot contain both an and a : it would have to contain the entire middle block of length , plus at least those two outer symbols, exceeding . HencePump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, iswhere was used.
If , then , contradicting that equality. If , thenagain contradicting it. Thus every permissible decomposition fails at . This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.
The formal language is a context-free language. A context-free grammar with start nonterminal symbol isThe production rule for nests one on the left and one on the right on each recursive use, so generates exactly for . Similarly, generates exactly for . The start production rule concatenates these words, yieldingConversely, every choice of nonnegative integers is achieved by using the recursive production rules exactly times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.
The formal language is not a regular language. Let denote it and consider the infinitely many prefixesFor any , append the word . Then , whereas : the latter word has occurrences of and occurrences of , and every word of has equal numbers of those two symbols.
Thus and are not Myhill-Nerode equivalent. There are infinitely many Myhill-Nerode equivalence classes, so the Myhill-Nerode theorem rules out a finite-state automaton recognizing . Equivalently, if two such prefixes left a deterministic finite automaton in the same automaton state, appending could not distinguish their acceptance, giving the same contradiction.
The formal language is a regular language. A regular expression for it isThe first Kleene star independently chooses copies of the word , and the second independently chooses copies of . Their concatenation produces exactly the required words. Either count may be zero, including both counts zero, which gives the empty word. By Kleene theorem, the regular expression establishes regularity.
There are unlisted articles, also show them or only show them.