Execution of one rounded ellipsoid step
ProvedLax109476Proofs.RamEllipsoidStep.ellipsoidStep_specalgorithmscomputational-complexitylinear-programming
Let , let be a rational matrix, and let , with . Let bound the heights of their entries, and let bound the intermediate form, dimension and precision quantities. Set and at iteration . Under the routine's explicit word-range bounds for modulus , the ellipsoid-step command maps the encoded state and its allocated workspace to the rounded next center and shape:
It preserves the old shape and center and the dimension field, records the grid , and runs within the explicit bound defined by the implementation. The hypotheses include all rational-height, array-extent and intermediate overflow conditions. This operational interface is reusable both in the feasibility solver and in the native MWIS rounding program.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeOperationalInterfaces
Formal statement
theorem Lax109476Proofs.RamEllipsoidStep.ellipsoidStep_spec : ∀ (B n H M k : ℕ) (A : Matrix (Fin n) (Fin n) ℚ) (a c : Fin n → ℚ),
2 ≤ n →
1 ≤ H →
(∀ (i j : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (A i j) H) →
(∀ (i : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (a i) H) →
(∀ (i : Fin n), Lax109476Proofs.RationalArithmeticBounds.Height (c i) H) →
0 < a ⬝ᵥ A.mulVec a →
n * n ≤ M →
Lax109476Proofs.RamEllipsoidForm.formHeight n H ≤ M →
2 ^ (2 * k + 3 * n + 9) ≤ M →
2 ^ (2 * n + 4) ≤ M →
2 *
Lax109476Proofs.RamShapeCoordinate.shapeCap
(Lax109476Proofs.RamEllipsoidCoefficients.coefficientCap M) ^
2 +
3 <
B →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.shape"
(Lax109476Proofs.RamMatrixStorage.flatten A) σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.normal" (List.ofFn a) σ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.center" (List.ofFn c) σ ∧
Lax109476Proofs.RamEllipsoidStep.Workspace n σ ∧
σ.vars "vec.n" = n ∧ σ.vars "iter.k" = k)
Lax109476Proofs.RamEllipsoidStep.ellipsoidStep
(fun (x τ : Lax808846Proofs.Imp.Env) =>
Lax109476Proofs.RamRationalArrays.Represents "ell.nextcenter"
(List.ofFn
(Lax109476Proofs.EllipsoidCenter.roundedCenter n A a c (2 ^ (2 * k + 3 * n + 9))))
τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.nextshape"
(Lax109476Proofs.RamMatrixStorage.flatten
(Lax109476Proofs.EllipsoidCenter.roundedStepShape n A a (2 ^ (2 * k + 3 * n + 9))
(Lax109476Proofs.EllipsoidIteration.stepAccuracy n)))
τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.shape"
(Lax109476Proofs.RamMatrixStorage.flatten A) τ ∧
Lax109476Proofs.RamRationalArrays.Represents "ell.center" (List.ofFn c) τ ∧
τ.vars "vec.n" = n ∧ τ.vars "grid.D" = 2 ^ (2 * k + 3 * n + 9))
(Lax109476Proofs.RamEllipsoidStep.stepCost n H M) := by sorrySource