gradOL – Gradient Approach to Chebyshev Center Problems

Abstract

A New Frontier in Optimal Function Learning

We introduce gradOL, the first gradient-based optimization framework for solving Chebyshev center problems, a fundamental challenge in optimal function learning and geometric optimization. gradOL hinges on reformulating the semi-infinite problem as a finitary max-min optimization, making it amenable to gradient-based techniques.

By leveraging automatic differentiation for precise numerical gradient computation, gradOL ensures numerical stability and scalability, making it suitable for large-scale settings. Under strong convexity of the ambient norm, gradOL provably recovers optimal Chebyshev centers while directly computing the associated radius. This addresses a key bottleneck in constructing stable optimal interpolants.

Empirically, gradOL achieves significant improvements in accuracy and efficiency on 34 benchmark Chebyshev center problems from a benchmark CSIP library. Moreover, we extend gradOL to general convex semi-infinite programming (CSIP), attaining up to 4000× speedups over the state-of-the-art SIPAMPL solver tested on the indicated CSIP library containing 67 benchmark problems. gradOL thus offers a unified solution framework for Chebyshev centers and broader CSIPs.

4000×

Max Speedup vs SIPAMPL

67

Benchmark Problems Solved

638ms

Avg. Runtime (Cheby. Center)

34/34

Chebyshev Instances Solved

Contributions

What gradOL Brings to the Table

01

Efficient Chebyshev Center Solver

A robust, gradient-based Julia implementation using automatic differentiation libraries for high accuracy and scalability. The optimal value corresponds directly to the Chebyshev radius.

02

Theoretical Foundation

We establish that the map u ↦ G(u) is locally Lipschitz, justifying gradient-based learning and proving convergence to a generalized Goldstein stationary point.

03

Benchmark Superiority

Tested on 34 Chebyshev center and 33 additional CSIP benchmark instances, gradOL consistently outperforms all existing solvers — including SIPAMPL and simulated annealing methods.

04

General CSIP Extension

The gradient-based framework extends naturally to general convex semi-infinite programming, achieving several orders-of-magnitude improvement in speed with solution quality matching or exceeding state-of-the-art.

Presentation

Paper Walkthrough

A short presentation covering the key ideas, formulation, and results of gradOL.

Results

Performance Comparison

gradOL is benchmarked against the industry-standard SIPAMPL, MSA–Simulated Annealing, and Iterative Sampling on all benchmark instances. Runtime measured in milliseconds on an AWS t2.large instance (Intel Xeon, 8 GiB RAM).

Method	Chebyshev Center (34 instances)		CSIP (33 instances)
Method	Solved	Avg. Runtime (ms)	Solved	Avg. Runtime (ms)
Iterative Sampling	9	3,880.95	20	1,695.37
MSA–Simulated Annealing	19	23,768.12	20	16,417.43
SIPAMPL	32	50,906.00	28	72,336.00
gradOL OURS	34	638.79	33	303.77

Table 1: gradOL solves all benchmark instances while being up to ~80× faster than SIPAMPL on Chebyshev center problems and up to ~238× faster on general CSIPs.

Detailed Benchmark Comparison

Per-problem breakdown of gradOL against best-known values from the literature. Problems marked † are Chebyshev center instances. Values marked * were not in original literature but obtained via SIPAMPL.

Problem	Source	Reported Value	gradOL Value	Reported Time (ms)	gradOL Time (ms)
coopeL	Price & Coope (1996)	3.4310 × 10⁻¹	3.3631 × 10⁻¹	—	4.067
coopeM	Price & Coope (1996)	1.0000 × 10⁰	1.0000 × 10⁰	—	3.052
coopeN	Price & Coope (1996)	0.0000 × 10⁰	−6.9580 × 10⁻³	1.19 × 10³	3.209
fang1	Fang & Wu (1994)	4.7927 × 10⁻¹	4.7939 × 10⁻¹	2.173 × 10⁴	28.737
fang2	Fang & Wu (1994)	6.9315 × 10⁻¹	6.7982 × 10⁻¹	2.307 × 10⁴	65.094
fang3	Fang & Wu (1994)	1.7185 × 10⁰	1.7183 × 10⁰	2.128 × 10⁴	33.526
ferris1 †	Ferris & Philpott (1989)	4.8800 × 10⁻³	4.9828 × 10⁻⁴	5.99 × 10³	2.296 × 10²
ferris2	Ferris & Philpott (1989)	−1.7869 × 10⁰	−1.7865 × 10⁰	7.46 × 10³	8.177
goerner4 †	Goerner (1997)	5.3324 × 10⁻²	2.6209 × 10⁻²	8.25 × 10³	2.658 × 10²
goerner5 †	Goerner (1997)	2.7275 × 10⁻²	2.5906 × 10⁻²	2.2 × 10⁴	1.665 × 10²
goerner6 †	Goerner (1997)	1.0770 × 10⁻³	5.9995 × 10⁻⁵	4.658 × 10⁴	47.247
honstedel	Honstede (1979)	1.2124 × 10⁰	1.0424 × 10⁰	—	3.984
kortanek1	Kortanek & No (1993)	3.2212 × 10⁰	3.2184 × 10⁰	4.802 × 10⁴	6.018
kortanek2	Kortanek & No (1993)	6.8629 × 10⁻¹	6.8628 × 10⁻¹	1.11 × 10³	9.324 × 10²
kortanek3 †	Kortanek & No (1993)	1.4708 × 10⁻²	2.2281 × 10⁻⁴	1.5 × 10³	95.012
kortanek4 †	Kortanek & No (1993)	5.2083 × 10⁻³	3.7413 × 10⁻⁵	2.666 × 10⁴	1.443
leon1 †	Leon et al. (2000)	4.5050 × 10⁻³	2.4607 × 10⁻⁴	1.29 × 10³	7.283
leon2 †	Leon et al. (2000)	4.1880 × 10⁻⁵	1.0002 × 10⁻⁷	1.111 × 10⁴	12.273
leon3 †	Leon et al. (2000)	5.2190 × 10⁻⁴	1.0002 × 10⁻⁵	5.12 × 10³	4.778 × 10²
leon4 †	Leon et al. (2000)	2.6028 × 10⁻³	1.3479 × 10⁻⁴	1.381 × 10⁴	6.175 × 10³
leon5 †	Leon et al. (2000)	1.4257 × 10⁻²	4.8963 × 10⁻⁴	4.722 × 10⁴	14.99
leon6 †	Leon et al. (2000)	1.5540 × 10⁻⁴	1.1692 × 10⁻⁵	4.12 × 10³	7.378
leon7 †	Leon et al. (2000)	2.0997 × 10⁻³	2.5904 × 10⁻⁴	4.37 × 10³	21.41
leon8 †	Leon et al. (2000)	5.4222 × 10⁻²	1.0002 × 10⁻⁷	2.139 × 10⁴	5.146 × 10³
leon9 †	Leon et al. (2000)	1.6338 × 10⁻¹	1.6338 × 10⁻¹	1.696 × 10⁴	8.694
leon10 †	Leon et al. (2000)	5.3825 × 10⁻¹	5.3776 × 10⁻¹	2.65 × 10³	19.612
leon11 †	Leon et al. (2000)	4.8414 × 10⁻²	2.3620 × 10⁻³	1.28 × 10³	15.384
leon13 †	Leon et al. (2000)	2.3607 × 10⁻¹	2.3531 × 10⁻¹	1.26 × 10³	3.972
leon14	Leon et al. (2000)	6.6667 × 10⁻¹	6.6640 × 10⁻¹	1.4 × 10³	5.151
leon15	Leon et al. (2000)	−6.6667 × 10⁻¹	−6.6657 × 10⁻¹	9.5 × 10²	4.234
leon16	Leon et al. (2000)	1.7263 × 10⁰	1.7187 × 10⁰	2.2 × 10²	3.04
leon17	Leon et al. (2000)	−2.0000 × 10⁰	−1.9998 × 10⁰	1.9 × 10²	3.4
leon18 *	Leon et al. (2000)	−1.7500 × 10⁰	−1.7000 × 10⁰	3.63 × 10³	3.303
leon19 *	Leon et al. (2000)	7.8584 × 10⁻¹	7.7543 × 10⁻¹	2.12 × 10³	4.003
leon20	Leon et al. (2000)	3.2380 × 10⁻¹	3.2316 × 10⁻¹	1.68 × 10³	11.713
leon21	Leon et al. (2000)	−9.9661 × 10¹	−9.9670 × 10¹	3.73 × 10³	4.399 × 10³
leon22	Leon et al. (2000)	−1.0472 × 10¹	−1.0472 × 10¹	5.9 × 10²	4.211 × 10³
leon23	Leon et al. (2000)	−3.0857 × 10¹	−3.0857 × 10¹	5.1 × 10²	16.434
leon24 *	Leon et al. (2000)	−1.1998 × 10¹	−1.0370 × 10¹	1.54 × 10³	7.526
lin1 *	Lin et al. (1998)	−1.8244 × 10⁰	−1.8300 × 10⁰	2.98 × 10⁴	3.785
reemtsen1 †	Reemtsen (1991)	1.5249 × 10⁻¹	1.5231 × 10⁻¹	1.2689 × 10⁵	4.974 × 10²
reemtsen2 †	Reemtsen (1991)	5.8359 × 10⁻²	5.6952 × 10⁻²	1.0145 × 10⁵	17.249
reemtsen3 †	Reemtsen (1991)	7.3547 × 10⁻¹	7.3548 × 10⁻¹	1.6633 × 10⁵	15.484
reemtsen4 †	Reemtsen (1991)	1.1401 × 10⁻²	1.0001 × 10⁻⁵	4.5109 × 10⁵	64.185
reemtsen5 †	Reemtsen (1991)	8.8932 × 10⁻²	2.8761 × 10⁻²	1.4513 × 10⁵	1.950
potchinkov3 †	Potchinkov (1997)	—	3.4226 × 10⁻³	—	5.788
potchinkovPL †	Potchinkov (1997)	—	9.2940 × 10⁻⁷	—	2.595
powell1	Todd (1994)	−1.0000 × 10⁰	−1.0000 × 10⁰	9.2 × 10²	3.096
hettich2 †	Hettich (1979)	5.3800 × 10⁻¹	5.3742 × 10⁻¹	2.68 × 10³	3.98
hettich4 †	Hettich (1979)	1.0000 × 10⁰	1.0001 × 10⁰	3.6 × 10²	8.137
hettich5 †	Hettich (1979)	5.3800 × 10⁻¹	5.3505 × 10⁻¹	1.1995 × 10⁵	10.909
hettich6 †	Hettich (1979)	2.8100 × 10⁻²	2.8163 × 10⁻²	5.504 × 10⁴	1.735
hettich7 †	Hettich (1979)	1.7800 × 10⁻¹	1.7776 × 10⁻¹	4.976 × 10⁴	7.776
hettich8 †	Hettich (1979)	—	2.996 × 10⁻²	2.290 × 10³	1.139 × 10²
hettich9 †	Hettich (1979)	3.4700 × 10⁻³	3.4791 × 10⁻³	8.465 × 10⁴	3.837
hettich12 †	Hettich (1979)	—	1.0252 × 10⁻³	7.844 × 10⁴	8.695 × 10³
priceK	Price (1992)	−3.0000 × 10⁰	−3.0000 × 10⁰	5.1 × 10²	3.191
still1	Still (2001)	1.0000 × 10⁰	9.9771 × 10⁻¹	3.9 × 10²	4.888
userman	—	—	1.2802 × 10⁻⁷	—	4.028
watson4a	Watson (1983)	6.4904 × 10⁻¹	6.5012 × 10⁻¹	1.78 × 10³	10.116
watson4b	Watson (1983)	6.1688 × 10⁻¹	6.1610 × 10⁻¹	2.22 × 10³	37.654
watson4c	Watson (1983)	6.1661 × 10⁻¹	6.1564 × 10⁻¹	2.82 × 10³	10.029
watson5	Watson (1983)	4.3012 × 10⁰	4.2966 × 10⁰	8.4 × 10²	17.097
watson7	Watson (1983)	1.0000 × 10⁰	9.9777 × 10⁻¹	1.23 × 10³	7.534
watson8	Watson (1983)	2.4356 × 10⁰	2.4356 × 10⁰	2.189 × 10⁴	1.627 × 10²
watson10	Watson (1983)	2.7527 × 10⁻¹	−7.0000 × 10⁻⁵	—	6.952
zhou1 †	Zhou & Tits (1996)	2.3605 × 10⁻¹	2.3505 × 10⁻¹	3.09 × 10³	42.561

Table 2: Per-problem comparison. Teal rows (†) indicate Chebyshev center problems. * denotes values not in original literature, obtained via SIPAMPL. For 65 of 67 problems, gradOL deviates by less than 10⁻² from previously reported results.

Authors

Meet the Team

This work was conducted at the Indian Institute of Technology, Bombay

AR

Abhinav Raghuvanshi

Indian Institute of Technology, Bombay

abhinavr11.github.io →

MB

Mayank Baranwal

TCS Research, Mumbai &
Indian Institute of Technology, Bombay

sc.iitb.ac.in/~mayank →

DC

Debasish Chatterjee

Indian Institute of Technology, Bombay

sc.iitb.ac.in/~chatterjee →

Citation

BibTeX

@article{raghuvanshi2025gradol,
  title={On a Gradient Approach to {Chebyshev} Center Problems with
         Applications to Function Learning},
  author={Raghuvanshi, Abhinav and Baranwal, Mayank and Chatterjee, Debasish},
  journal={Transactions on Machine Learning Research},
  year={2025},
  url={https://openreview.net/forum?id=lPZVsDhyj3}
}