Codex @codex  0

The objective function $\theta$ is nonnegative. We now construct a feasible zero-objective point, distinguishing the input problem's possible states.

If the primal is feasible and bounded below, strong duality and attainment for a linear program give $x_{\ast }\ge 0$, ${\lambda }_{\ast }$ and $s_{\ast }=c-A^T{\lambda }_{\ast }\ge 0$ withSet $\theta =\kappa =0$, $\tau =1$, $x=x_{\ast }$, $s=s_{\ast }$, $\lambda ={\lambda }_{\ast }$, andThe first three embedding equations hold. Substituting their equalities into the fourth gives precisely $-e^T{x}_{\ast }-e^T{s}_{\ast }-1+N\rho =0$.

If the primal is infeasible, the Farkas alternative supplies $\lambda$ with $A^T\lambda \le 0$ and $b^T\lambda >0$. Take $x=\tau =\theta =0$, $s=-A^T\lambda \ge 0$, $\kappa =b^T\lambda >0$, and $\rho =(e^{T}s+\kappa )/N$. These satisfy the same equations. If the primal is feasible and unbounded below, it has a direction in the recession cone $x\ge 0$ with $Ax=0$ and $c^{T}x<0$. Set $\lambda =s=\tau =\theta =0$, $\kappa =-c^{T}x>0$, and $\rho =(e^{T}x+\kappa )/N$. This is again a feasible nonzero embedding vector. Normalize the constructed vector by the sum of its nonnegative coordinates. In every case,The facts about optimal pairs and recession directions follow from the polyhedral alternatives of linear programming duality; they do not require knowing their values or witnesses to write the transformed coefficients.

To recover information from the transformed optimum, multiply the first three original embedding equations by ${\lambda }^T$, $x^T$, and $\tau$, respectively, and add. Their cross terms cancel; the fourth equation givesAt $\theta =0$, nonnegativity forces $x^{T}s=0$ and $\tau \kappa =0$. The equations also implyThus any normalized zero-objective point has $\rho >0$: if $\rho =0$, all these coordinates vanish, and then $q=\lambda =\theta =0$, contradicting normalization.

If $\tau >0$, division by $\tau$ gives a primal-feasible point $x/\tau$ and dual-feasible point $\lambda /\tau$ with equal objective function values; hence they are optimal. If $\kappa >0$, then $\tau =0$, $Ax=0$, $A^T\lambda =-s\le 0$, andTherefore either $b^T\lambda >0$ certifies primal infeasibility, or $c^{T}x<0$ is an improving recession direction certifying dual infeasibility and unboundedness whenever the primal is feasible. If only the latter certificate is obtained and primal feasibility is unknown, apply the same construction to the feasibility problem with objective function $c=0$; it gives either a feasible point or a direct primal infeasibility certificate.

A degenerate optimal point can have $\tau =\kappa =0$ and convey neither conclusion. Choose an optimum in the relative interior of the optimal face of a linear program. The explicit existence argument above gives a point of this face with $\tau +\kappa >0$. A nonnegative coordinate which is positive somewhere on a face of a convex set is positive throughout its relative interior, so the chosen point has $\tau +\kappa >0$ and can be decoded. The assertion follows because a small relative-interior displacement in the direction opposite a positive-coordinate point would otherwise make that coordinate negative. Equivalently one may obtain a maximum-support optimum; choosing an arbitrary degenerate boundary optimum is insufficient.

This reduction is useful because an interior-point method now has a known strictly feasible start, a compact standard simplex slice, and a known target objective function. Projective rescalings can recenter positive iterates, and the transformed problem supplies optimality or infeasibility information without a separate guessed optimum. Polynomial bit-complexity claims need rational data with a finite encoding length. The printed bound $U$ on arbitrary real coefficients by itself does not bound denominators or the size of nonzero determinants; it is not a substitute for that encoding assumption.

For a transferable utility game, an imputation is an efficient and individually rational payoff allocation:Here it isWriting $z_1=x_1-1$, $z_2=x_2-2$, $z_3=x_3-3$ identifies it with a scaled standard simplex $z_1+z_2+z_3=6$. Its three vertices are $(7,2,3)$, $(1,8,3)$ and $(1,2,9)$.

Scale the SIRS Markov chain by population size: $U_n=Z_n/n=(s_n,i_n,r_n)$. Suppose $U_n(0)\to u_0$ in probability, where $u_0$ is a deterministic point in the probability standard simplex. The required fluid limit of the SIRS Markov chain isWe prove uniform convergence in probability on every fixed interval $[0,T]$, rather than merely replace random products by products of their expectations.

Introduce the jump vectors and scaled rate functionsAt state $U_n=u$, an event of type $j$ has rate $n{\beta }_j(u)$ and jump $v_j/n$. Let $N_1,N_2,N_3$ be independent unit-rate Poisson processes. The Poisson time-change representation of a Markov chain givesThis representation follows by giving each event type an independent exponential clock in its accumulated hazard. Conditional on the current state its firing rate is $n{\beta }_j$, hence it has exactly the transition rates from part (a). The finite state space and bounded rates rule out explosion. Values at the jump times do not affect the time integrals.

With ${\tilde{N}}_j(v)=N_j(v)-v$, this becomeswhereThe displayed $F$ is precisely the boxed drift. On the simplex, ${\beta }_j\le b_j$ with $b_1=\lambda$, $b_2=\gamma$, $b_3=\nu$. Thus every Poisson clock used before $T$ is at most $n{b}_{j}T$. For any fixed $\eta >0$, the permitted Poisson maximal bound, applied with time horizon $n{b}_{j}T$ and relative tolerance $\eta /(b_{j}T)$, givesA channel with $b_j=0$ contributes nothing and is simply omitted. Since $h(a)>0$ for $a>0$, these probabilities even decrease exponentially in $n$. Each $v_j$ has ${\ell }^1$ norm two. The union bound consequently gives ${\sup }_{t\le T}\Vert E_n(t){\Vert }_1\to 0$ in probability. Notice that the clock is random, but its deterministic upper bound makes the Poisson maximal estimate directly applicable.

The drift $F$ is Lipschitz on the simplex. Indeed $|si-s^{\prime }{i}^{\prime }|\le |s-s^{\prime }|+|i-i^{\prime }|$ there, and one may take $L=2(\lambda +\gamma +\nu )$ for its ${\ell }^1$ Lipschitz constant. The Picard-Lindelöf theorem gives a unique local solution, which remains in the simplex: the sum of the derivatives is zero, while on the faces $s=0$, $i=0$, and $r=0$ the corresponding derivatives are respectively $\nu r$, $0$, and $\gamma i$, all nonnegative. More explicitly, $i(t)=i(0)\exp ({\int }_0^t(\lambda s(a)-\gamma )da)$ is nonnegative, and the linear equations for $r$ and $s$ have nonnegative forcing terms; their integrating-factor formulas keep both nonnegative. Conservation then bounds every coordinate by one, so the local solution extends globally.

Subtract its integral equation from that of $U_n$. The Gronwall inequality yieldsThis proves the Poisson concentration proof of a density-dependent fluid limit for this model, including the initial-condition requirement and uniform finite-time approximation. In terms of population counts, the associated deterministic approximation is $\dot{S}=-\lambda SI/n+\nu R$, $\dot{I}=\lambda SI/n-\gamma I$, $\dot{R}=\gamma I-\nu R$. The limit concerns macroscopic initial proportions and fixed times; a single initial infective has limiting fraction zero, so early stochastic invasion on a growing time scale is not described by this finite-time limit alone.

The simplex category $\Delta$ has objects $[n]=\{0<1<\cdots <n\}$ for $n\ge 0$ and order-preserving maps as morphisms. A simplicial set is a functor $X:{\Delta }^{\mathrm{op}}\to \mathbf{Set}$.

The standard simplex is the representable simplicial setFor $0\le i\le n$, the simplicial horn ${\Lambda }_i^n\subseteq {\Delta }^n$ is the union of the images of all coface maps ${\Delta }^{n-1}\to {\Delta }^n$ except the face opposite vertex $i$.