The Potapov–Grishin Principal Hyperface Method, Completed and Machine-Checked

The principal hyperface method of G. G. Potapov and I. Yu. Grishin (2007) solves a linear program by a sequence of geometric decisions. It picks the constraint hyperplane whose normal is closest in direction to the objective vector, turns that inequality into an equality, eliminates one variable, and repeats, so that the dimension drops by one at each step. The method is short and easy to picture, but it was published as a heuristic, without a proof of when it is correct. This paper completes the method and verifies every result in the Lean 4 proof assistant. We prove that a run of the method returns an optimal point if and only if every hyperface it selects is principal, that is, active at some optimum. We prove that a principal hyperface always exists when the objective is non-zero. We prove that in two dimensions the projection rule of the method never errs on systems without redundant constraints, and we give a machine-checked counterexample in three dimensions. Finally, we turn the method into a certified algorithm: it follows the projection rule, checks a dual certificate after each step, and backtracks when the check fails. We prove that it always returns an optimal point when one exists, and every certified answer can be checked independently. Along the way we formalise Farkas' lemma over an arbitrary ordered field by Fourier-Motzkin elimination. The worked example of the 2008 paper is confirmed exactly. A Python implementation of the same algorithm in exact rational arithmetic accompanies the paper. Code, Lean formalisation and figures: https://github.com/albond/principal-hyperfaces

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24283336
Primary Topic
Advanced Optimization Algorithms Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Potapov–Grishin Principal Hyperface Method, Completed and Machine-Checked

Олександр Боднар
Zenodo (CERN European Organization for Nuclear Research)
Advanced Optimization Algorithms Research
preprint

The Potapov–Grishin Principal Hyperface Method, Completed and Machine-Checked

Олександр Боднар
preprint en

Abstract

The principal hyperface method of G. G. Potapov and I. Yu. Grishin (2007) solves a linear program by a sequence of geometric decisions. It picks the constraint hyperplane whose normal is closest in direction to the objective vector, turns that inequality into an equality, eliminates one variable, and repeats, so that the dimension drops by one at each step. The method is short and easy to picture, but it was published as a heuristic, without a proof of when it is correct. This paper completes the method and verifies every result in the Lean 4 proof assistant. We prove that a run of the method returns an optimal point if and only if every hyperface it selects is principal, that is, active at some optimum. We prove that a principal hyperface always exists when the objective is non-zero. We prove that in two dimensions the projection rule of the method never errs on systems without redundant constraints, and we give a machine-checked counterexample in three dimensions. Finally, we turn the method into a certified algorithm: it follows the projection rule, checks a dual certificate after each step, and backtracks when the check fails. We prove that it always returns an optimal point when one exists, and every certified answer can be checked independently. Along the way we formalise Farkas' lemma over an arbitrary ordered field by Fourier-Motzkin elimination. The worked example of the 2008 paper is confirmed exactly. A Python implementation of the same algorithm in exact rational arithmetic accompanies the paper. Code, Lean formalisation and figures: https://github.com/albond/principal-hyperfaces

Zenodo (CERN European Organization for Nuclear Research)
Advanced Optimization Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon