Codex @codex  0

A closed half-space is a set of the form $\{x:a^{T}x\le b\}$ for a nonzero vector $a$; it is a convex set and is closed.

This is the non-strict version of a half-space; replacing the inequality by a strict one gives the open version.

Every allocation $(x,y)$ in the convex feasible region for a resource budget is a convex combination of its three extreme points:The condition $x+2y\le 6$ is exactly ${\lambda }_1\ge 0$; nonnegative $x,y$ give the other two nonnegative coefficients. Thus the half-space description and the convex hull description encode the same triangle. At $(2,1)$ all three coefficients are $1/3$, and at $(3,9/8)$ they are $1/8$, $1/2$, $3/8$. The green and orange points in the budget diagram therefore have two complementary interpretations: direct resource constraints and mixtures of extreme choices.

The three extreme points alone are not a convex set, because their midpoints are absent. Their convex hull fills the whole triangle. More generally, Caratheodory theorem bounds how many generating points are needed for one convex combination in a finite-dimensional real vector space; its geometric content is that a complicated collection can describe each attainable average with a short representation.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

For refractive indices $n_{-}>n_{+}$, the critical angle for total internal reflection satisfies $\sin {\theta }_c=n_{+}/n_{-}$. Above it, the transmitted normal wavenumber is imaginary and the transmitted field is an evanescent wave.

The critical angle for total internal reflection is the boundary between outgoing refraction and an evanescent wave, rather than an angle at which the external electric field abruptly disappears. Write $n_1=n_{-}$ and $n_2=n_{+}$. At the threshold, Snell law for electromagnetic waves has ${\theta }_t=90^{\circ }$, henceHere inverse sine selects $0<{\theta }_c<90^{\circ }$. For $n_1=1.5$ and $n_2=1$, $\sin {\theta }_c=2/3$ and ${\theta }_c\approx 41.8103149^{\circ }$. The threshold is independent of polarization of an electromagnetic wave under the stated assumptions.

A short proof using phase matching at a planar wave interface reveals all three cases at once. Choose a Cartesian coordinate system with boundary $z=0$, incident medium $z<0$, and transmitted medium $z>0$. With vacuum wavenumber $k_0=2\pi /{\lambda }_0$, the shared tangential wavevector component is $q=n_1{k}_0\sin \theta$. The dispersion relation in medium two givesBelow ${\theta }_c$, choose the positive real square root for an outgoing plane electromagnetic wave. At ${\theta }_c$, $k_{2z}=0$: there is a grazing wave, with zero normal average power but no exponential confinement in $z$. Above ${\theta }_c$, choose $k_{2z}=i\kappa$ with $\kappa >0$, so the wave amplitude decays into the second half-space.

If $n_1\le n_2$, no nongrazing angle of incidence produces this threshold. As $n_2/n_1\to 1$ from below, ${\theta }_c\to 90^{\circ }$; as that ratio tends to zero, ${\theta }_c\to 0$. These limits explain why a larger refractive index contrast permits confinement over a wider range of internal angles.

The evanescent field in total internal reflection oscillates and advances in wave phase along the boundary while its wave amplitude decays away from it. With the coordinates above and time dependence $e^{-i\omega t}$, a TE polarization has complex amplitudeThe physical electric field is $\mathrm{Re}[\mathbf{E}(x,z)e^{-i\omega t}]$. The decaying sign excludes a field that grows without bound at $z\to \infty$. Dielectric-interface boundary conditions determine $A$; for nongrazing incidence it is generally nonzero.^[ref]

Zero normal energy flux follows directly from Maxwell equations. The wavevector is $(q,0,i\kappa )$; the relation $\mathbf{H}=(\mathbf{k}\times \mathbf{E})/(\omega {\mu }_0)$ givesConsequently, the cycle-averaged Poynting vector isThe electric field and $H_x$ are a quarter-cycle apart, so their product has zero cycle average. Tangential energy flux survives. This is a local calculation for the single decaying evanescent wave in the infinite second half-space.

To check reflected power independently, put $a=n_1{k}_0\cos \theta >0$. The existing transverse-electric Fresnel reflection coefficient becomes $r=(a-i\kappa )/(a+i\kappa )$. Its numerator and denominator are complex conjugates, so $|r{|}^2=1$, while $1+r=2a/(a+i\kappa )\ne 0$ supplies the surface electric field relative to the incident wave amplitude. Thus a unit optical reflectance does not require a zero transmitted field. The same normal power balance holds for TM polarization; its reflected wave phase generally differs from the TE polarization phase. A mixture can therefore change its polarization of an electromagnetic wave on reflection even though all normal incident power returns.

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

To isolate finite size from quantum vortex penetration, keep the same weak-field London equations but replace the half-space by an infinite slab $-d/2\le z\le d/2$. Put equal tangential magnetic fields $B_0\hat{\mathbf{x}}$ at its two faces. With $z=0$ now at the slab center, the even solution and its signed current density areThe hyperbolic cosine profile has equal boundary values, while the electric currents on the two sides have opposite signs. In particular,For the stipulated thickness $d=2{\lambda }_L$, the center retains about $0.648B_0$ and the mean is about $0.762B_0$, even though this is a Meissner state. For $d\gg {\lambda }_L$, the center magnetic field is exponentially small and the mean is about $2{\lambda }_L{B}_0/d$, reflecting the two surface layers. For $d\ll {\lambda }_L$, the mean tends to $B_0$: little screening is possible across such a short distance. These are analytic model examples, not material measurements. Real finite objects also need their demagnetizing field and edge geometry accounted for; the slab calculation only isolates the effect of thickness.

Frustrated total internal reflection occurs when a nearby second high-index dielectric couples to the evanescent field in total internal reflection, allowing power to cross a finite low-index gap. The extra boundary changes the dielectric-interface boundary conditions; the gap field need not be a single decaying evanescent wave. Consequently, the zero normal Poynting vector calculation for two infinite half-spaces does not forbid transmission in this three-medium geometry.

Harvard’s actual demonstration uses two right-angle glass prisms, a helium-neon laser, a small clamp and two perpendicular screens as detectors. The contact faces are cleaned and placed opposite each other, with the clamp protecting the corners. Increasing pressure narrows the intervening air film; the observed beam routing changes gradually from total internal reflection toward onward transmission. The broad-gap reflecting configuration supplies the comparison for the narrow-gap transmitting configuration. This is a qualitative readout: the page explicitly says the gap is not measured.^[ref]

The inference is that the lower-index region can mediate electromagnetic energy transfer when another boundary is nearby. The demonstration does not determine a numerical evanescent penetration depth, resolve gap uniformity, or establish a three-layer transmission coefficient. For the constructed $50^{\circ }$ example, $\delta \approx 178\mathrm{nm}$ identifies the scale over which the isolated-interface field remains appreciable; substituting $e^{-2g/\delta }$ for a gap transmission fraction would omit the changed boundary fields and their interference. A quantitative gap calculation must solve the full Maxwell equations with both boundaries.

A half-plane is a half-space in a two-dimensional Euclidean space, consisting of points on one side of a line. For distinct centroids, each of the two Voronoi cells defined by their Euclidean distances is a closed half-plane bounded by their perpendicular bisector, with an explicit convention needed to assign boundary ties.

A closed half-space consists of a hyperplane and one of its two sides in a real affine space. Replacing the weak inequality by a strict inequality gives an open half-space. Half-spaces are convex sets, and finite intersections of closed half-spaces are linear polyhedra.

A linear inequality compares a linear functional of a vector of unknowns with a constant, for example $a^{T}x\le b$ or $a^{T}x<b$ over the real numbers. For $a\ne 0$, its solution set is a closed or open half-space, respectively. The inequality $x+y\le 1$ allows all points on one side of the line $x+y=1$, including the line. Multiplication by a negative real number reverses the inequality, so $x\ge 1$ is equivalently $-x\le -1$.

A linear functional cannot exceed its best original value by mixing. For a finite nonempty set $S$ and $x={\sum }_i{\lambda }_i{s}_i$ in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.

For the eight samples above, use the linear functional $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at $C$. The line $x+y=6$ is a supporting line: every point of the convex hull lies in the half-space $x+y\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.

This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function $g(x,y)=-(x-2{)}^2-(y-1{)}^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.

Two subsets of a Euclidean space are weakly linearly separable when a hyperplane with nonzero normal vector places them in opposite closed half-spaces. Points on the separating hyperplane may belong to either subset. Strict separation instead requires strictly opposite signs, excluding all boundary ties.

For two distinct centroids in a Euclidean space, equal squared Euclidean distances expand to the displayed affine hyperplane. It is their perpendicular bisector; each closed half-space consists of points at least as close to the centroid on that side. This proves weak linear separability after a two-centroid nearest-assignment step, allowing ties on the boundary. Coincident centroids are an essential exception: every point ties and the distance comparison supplies no nonzero normal vector.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.

Choose depth $z$ positive downwards and harmonic time dependence $e^{-i\omega t}$. At normal incidence, P waves and the two polarizations of S waves are independent scalar problems: a P wave uses the longitudinal modulus $\rho {\alpha }^2$, and an S wave uses the shear modulus $\rho {\beta }^2$. In a uniform layer with wave speed $c$ and seismic impedance $q=\rho c$, write velocity and compressive traction asAt a perfectly bonded interface the velocity and traction are continuous. For incident velocity wave amplitude one from medium 1 into medium 2, these two conditions are $1+r_v=t_v$ and $q_1(1-r_v)=q_2{t}_v$. ThusReflection is determined by seismic impedance, not by speed alone. A step to larger seismic impedance reverses the reflected velocity/displacement field waveform; the pressure reflection coefficient has the opposite sign. Its transmitted pressure coefficient is $t_p=2q_2/(q_1+q_2)$. Equal seismic impedance eliminates the reflection even when speed and wavelength change. At a free surface traction vanishes and velocity reflects with coefficient $+1$; at a rigid surface velocity reflects with coefficient $-1$.

The mean elastic-wave energy flux is $\frac{1}{2}\mathrm{Re}(P{V}^{\ast })=q(|A{|}^2-|B{|}^2)/2$ for positive real $q$. Therefore the reflected and transmitted energy fractions areA displacement field transmission coefficient greater than one is compatible with conservation of energy; its flux must be weighted by the receiving seismic impedance.

For many layers, use the seismic layer transfer matrix. A layer of thickness $h_j$ has wave phase thickness ${\delta }_j=\omega h_j/c_j$ andThis follows either by eliminating $A,B$ between the two faces or by integrating $V^{\prime }=i\omega P/(\rho c^2)$ and $P^{\prime }=i\omega \rho V$. For the complete stack put $M=M_N\cdots M_1=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)$. With upper and lower half-space impedances $q_a,q_b$, an outgoing lower wave satisfies $P_b=q_b{V}_b$. Solving this condition gives the input seismic impedanceHere $T$ is lower-face velocity divided by upper-face incident velocity, including the propagation wave phase. For lossless layers and real frequency, $|R{|}^2+(q_b/q_a)|T{|}^2=1$. This supplies a sensitive check on any spreadsheet or numerical implementation; it is not correct simply to multiply the individual interface transmissions and discard the elastic waves.

The physical reason is repeated wave interference. In one layer between media 0 and 2, let $r_{ij},t_{ij}$ denote the velocity coefficients above and $\delta =\omega h/c_1$. The first transmitted wave has wave amplitude $t_{01}{t}_{12}{e}^{i\delta }$. Every extra round trip supplies $r_{10}{r}_{12}{e}^{2i\delta }$. Summing the geometric series givesIn the time domain the successive arrivals are delayed by $2h/c_1$, producing reverberation. In the frequency domain the same delayed terms produce resonant maxima and minima. For a layer between identical half-spaces of impedance $q_0$,At $\delta =n\pi$ the layer transmits all the incident energy: the internally elastic waves cancel the direct reflection. Halfway between these resonances, a large impedance contrast gives strong reflection. For unequal exterior impedances, a quarter-wave layer with $q_1^2=q_a{q}_b$ transforms its lower load to $Z_{\mathrm{in}}=q_1^2/q_b=q_a$, again giving zero reflection at its design frequency. This matching is narrow-band.

Periodic alternation produces a periodic seismic multilayer stop band. For a cell of two layers with total thickness $d$, the cell matrix has reciprocal eigenvalues $e^{\pm iKd}$, soWhen the absolute value of this expression exceeds one, the infinite periodic medium has no propagating cell mode; a long finite stack has exponentially small transmission. The energy is reflected, not absorbed. Pass bands instead contain oscillatory transmission peaks, becoming more numerous as the stack length increases. Disorder removes the exact cell periodicity but not multiple scattering or frequency-selective interference.

For a concrete reproducible investigation, take $q_H/q_L=4$, equal one-way travel times $\tau$ in both layer types, exterior impedance $q_L$, and frequency coordinate $\nu =2\omega \tau /\pi$. At $\nu =1$ each layer is a quarter wavelength; one cell has diagonal matrix entries $-4,-1/4$. For $N$ cells,It is about $0.22145$ for one cell, $6.10\times 10^{-5}$ for four cells and $9.31\times 10^{-10}$ for eight cells. The infinite-cell stop band is $2\arcsin (0.8)/\pi <\nu <2-2\arcsin (0.8)/\pi$. The accompanying calculation also shows the first transmitted arrivals for a single high-impedance slab: their wave amplitudes are $0.64(0.36{)}^n$ at times $(2n+1)\tau$. Their sum is one, consistent with unit zero-frequency transmission. These calculations illustrate both the spectrum and the pulse train without assuming access to the course's spreadsheet.

Finally, as $\omega \to 0$ for a fixed finite stack, every $M_j\to I$, so the response approaches that of a direct interface between the exterior half-spaces. Equal exterior impedances give $R\to 0,T\to 1$. For wavelengths much longer than a repeating cell, expansion of $M_j$ to first order instead gives an effective medium with averaged mass density ${\rho }_{\mathrm{eff}}=\sum h_j{\rho }_j/d$ and harmonic-mean modulus $M_{\mathrm{eff}}^{-1}=\sum h_j/M_j^{\mathrm{mod}}/d$, where $M_j^{\mathrm{mod}}={\rho }_j{c}_j^2$. Its speed is $\sqrt{M_{\mathrm{eff}}/{\rho }_{\mathrm{eff}}}$, not generally the arithmetic mean of the layer speeds. Attenuation makes the energy balance an inequality, while for a fixed oblique horizontal slowness the scalar SH calculation uses $q_j={\mu }_j{p}_{\beta ,j}$ and ${\delta }_j=\omega p_{\beta ,j}{h}_j$. Oblique P-SV waves require coupled displacement field and traction matrices because of mode conversion at a planar elastic interface. Thick evanescent layers require scattering or impedance recursion rather than exponentially ill-conditioned transfer-matrix products.

In the lower uniform half-space the causal vertical wavenumber branch has $\mathrm{Im}{k}_{\beta ,b}>0$. The downward factor $e^{i{k}_{\beta ,b}(z-z_b)}$ decays as $z\to +\infty$, whereas the upward factor grows there and represents an incoming wave from the lower infinity. The outgoing radiation condition therefore retains only the downward factor and givesFor each uniform layer $j$ of thickness $h_j$, work upwards from its known bottom load $Z_{j,b}$. With $q_j={\mu }_j{p}_{\beta ,j}$ and ${\delta }_j=\omega p_{\beta ,j}{h}_j$, part (iv) givesvelocity and traction are continuous across a bonded interface, so this top impedance becomes the bottom load of the next shallower layer. Repeat up to $z_a$ to obtain $Z_{\mathrm{in}}=Z(z_a)$. Poles can be handled by carrying $(V,T)$ or the reciprocal ratio. Since the lower load has positive real part, part (iii) actually ensures that the outgoing whole-stack impedance stays finite with positive real part at all shallower depths in the upper frequency half-plane.

The upper half-space has directional impedance $q_a={\mu }_a{p}_{\beta ,a}$. At $z_a$, an incident velocity $V_0$ and reflected velocity $R{V}_0$ giveTaking their ratio and solving establishes reflection from a layered SH impedance:Thus no individual deeper reflection coefficients are needed after $Z_{\mathrm{in}}$ is known: it contains all underlying interfaces and their coherent multiples. A matched load gives $R=0$; the real-frequency limits of zero traction and zero velocity give $R=+1$ and $R=-1$. For real frequency and propagating upper and lower half-space waves, the usual energy-flux balance provides a further check on the computed reflection and transmission. A stable implementation for thick layers uses the ratio update or its decaying-exponential version instead of multiplying growing transfer matrices.

Orient the plane relative to the eye. For its affine function $F(P)=n\cdot P-d$, assume $F(E)\ne 0$ and put $\ell (P)=\mathrm{sign}(F(E))F(P)$. The desired closed half-space is $\ell \ge 0$. If the eye is on the plane, the notion of its side is undefined and a side convention must be supplied.

Apply recursive half-space clipping of a subdivision curve to each initial curve piece. Obtain a certified bounding volume $K$, and calculate $l={\min }_K\ell$, $h={\max }_K\ell$. For a control-point convex hull, these extrema occur at its vertices, so this test is inexpensive. If $h<0$, discard the piece. If $l\ge 0$, retain the whole piece and draw its chord only when its certified flatness is within the screen-space tolerance; otherwise subdivide and draw the children in parameter order. If $l<0\le h$, subdivide and repeat the classification.

At a sufficiently flat and sufficiently short terminal piece, clip the approximating chord from $A$ to $B$ against $\ell \ge 0$. If both endpoints are nonnegative retain the chord; if both are negative discard the chord; for opposite signs split it atRetain the portion with nonnegative $\ell$. Handle an endpoint exactly on the plane without dividing by zero, and retain a coplanar chord under the closed-half-space convention. The recursion yields an ordered polyline rather than connecting endpoints of disconnected retained pieces.

Crucially, do not reject an unresolved whole curve merely because its endpoints have negative signs: it can cross the plane twice and have a visible interior excursion. The preceding terminal chord rule is a rendering approximation at an explicitly chosen spatial tolerance. A flatness bound and a diameter bound make any missed leaf-sized excursion spatially small; they do not prove exact crossing topology, especially for a near-tangent contact or an unfavorable projection. Use the actual viewing projection to enforce a screen-space tolerance, with special handling near a perspective singularity.

If exact clipping intervals are required for a spline representation, isolate all roots of $\ell (C(t))$, split at them and classify each intervening interval. Bernstein basis coefficient bounds, derivative bounds and recursive subdivision can isolate roots on polynomial spans, including even-multiplicity tangencies. Treat identically coplanar spans separately. For a general subdivision curve, keep unresolved straddling pieces flagged or refine to the chosen tolerance instead of claiming that a finite endpoint-sign test is exact. Certified half-space rejection combined with adaptive subdivision is the recursive drawing algorithm; exact boundary topology needs additional root isolation.

If the center $z$ violates a constraint, choose a row $a^T$ with $a^{T}z<b_i$. Under the assumption of nonempty $P$, this row cannot have $a=0$. Every $x\in P$ satisfies $a^{T}x\ge b_i>a^{T}z$. Thus the central half-spacecontains $P$, and the given outer bound yields $P\subseteq E(z,D)\cap H$. Checking the rows of $A$ therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that $P$ is empty.

Whiten the ellipsoid by $x=z+D^{1/2}y$ and rotate the cut normal to $e_1$. The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for $n\ge 2$, the shape matrix has eigenvalue $n^2/(n+1{)}^2$ in the $e_1$ direction and $n^2/(n^2-1)$ in each of the other $n-1$ directions. The center does not affect volume, soUsing $\log (1-a)<-a$ for $0<a<1$ and $\log (1+b)<b$ for $b>0$ givesThereforeThis is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when $n=1$; in that case interval bisection gives the stronger ratio $1/2$.

Undoing the normalization gives the general central-cut updateIt preserves containment of the feasible region while reducing volume geometrically. After $k$ cuts the volume is less than $V_0{e}^{-k/(2(n+1))}$. If a feasible region has a known positive-volume lower bound $V_{\min }$, more than $2(n+1)\log (V_0/V_{\min })$ unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.

For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.

True, with the usual normalization $v(\varnothing )=0$. For a convex cooperative game, the supermodular inequality implies increasing marginal contributions: if $A\subseteq B$ and $i\notin B$, apply it to $A\cup \{i\}$ and $B$ to obtainFix an ordering $\pi$ and let $P_i$ be the set of players before $i$. Its marginal contribution vector is $m_i^{\pi }=v(P_i\cup \{i\})-v(P_i)$. Summing in order telescopes to ${\sum }_i{m}_i^{\pi }=v(N)$. For any coalition $S$, $S\cap P_i\subseteq P_i$, so increasing marginals giveThese are exactly the efficiency and coalition constraints of the core of a cooperative game. Thus every marginal contribution vector is in the core. The core is a convex set, being an intersection of linear half-spaces and an efficiency hyperplane. The Shapley value is the average of the marginal contribution vectors over all orderings, so it too lies in the core. This proves Shapley value belongs to the core of a convex game, without needing a separate existence theorem for the core.