The Polarity Process for the Maximum-Volume Inscribed Ellipsoid Problem
Abstract
We study the maximum-volume inscribed ellipsoid (MaxIE) problem for a polytope through a geometric iteration based on polarity. Given an interior point, the method forms the shifted polar polytope, computes its minimum-volume covering ellipsoid (MinCE), and then polarizes this covering ellipsoid back to obtain a new inscribed ellipsoid. This procedure was suggested by Khachiyan and Todd in 1993. Prior work studied basic polarity identities and gave an asymptotic-convergence argument for the exact process, but did not furnish a volume-ratio rate. Independently of that asymptotic argument, we develop a new analysis based on the log-volume of the polar MinCE as a potential function. We prove its convexity with an explicit gradient formula and establish global linear contraction of the potential gap along each trajectory. The contraction factor is existential and instance-dependent. This gives both a separate convergence proof and a finite volume-ratio iteration bound. We further analyze an inexact polarity process in which each MinCE subproblem is solved only approximately, and derive sufficient oracle tolerances for producing a prescribed volume approximation. Combining this outer analysis with existing algorithms for MinCE gives conditional arithmetic estimates based on the path-following Newton method, the barycentric coordinate descent, and the away-step Frank-Wolfe method. Numerical experiments compare these oracle choices with two MaxIE baselines and illustrate that performance depends on matching the MinCE solver to the instance geometry.
Related
- Reading Multiple Regression from an Ellipsoid Inscribed in the Unit Hypercube
- A Stochastic Maximum Principle for Partially Observed Jump-Diffusion Systems with State-Dependent Counting-Process Observations
- Maximum likelihood estimation in the ergodic Volterra Ornstein-Uhlenbeck process
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem
BibTeX
@misc{sun2026polarity,
title = {{The Polarity Process for the Maximum-Volume Inscribed Ellipsoid Problem}},
author = {Kaizhao Sun},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10888},
eprint = {2609.10888},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10888},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Polarity Process for the Maximum-Volume Inscribed Ellipsoid Problem
AU - Kaizhao Sun
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10888
UR - https://arxiv.org/abs/2609.10888
AB - We study the maximum-volume inscribed ellipsoid (MaxIE) problem for a polytope through a geometric iteration based on polarity. Given an interior point, the method forms the shifted polar polytope, computes its minimum-volume covering ellipsoid (MinCE), and then polarizes this covering ellipsoid back to obtain a new inscribed ellipsoid. This procedure was suggested by Khachiyan and Todd in 1993. Prior work studied basic polarity identities and gave an asymptotic-convergence argument for the exact process, but did not furnish a volume-ratio rate. Independently of that asymptotic argument, we develop a new analysis based on the log-volume of the polar MinCE as a potential function. We prove its convexity with an explicit gradient formula and establish global linear contraction of the potential gap along each trajectory. The contraction factor is existential and instance-dependent. This gives both a separate convergence proof and a finite volume-ratio iteration bound. We further analyze an inexact polarity process in which each MinCE subproblem is solved only approximately, and derive sufficient oracle tolerances for producing a prescribed volume approximation. Combining this outer analysis with existing algorithms for MinCE gives conditional arithmetic estimates based on the path-following Newton method, the barycentric coordinate descent, and the away-step Frank-Wolfe method. Numerical experiments compare these oracle choices with two MaxIE baselines and illustrate that performance depends on matching the MinCE solver to the instance geometry.
ER -