The Chebyshev Hyperplane Optimization Problem

G. Still, M. Streng

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)


We consider the following problem. Given a finite set of pointsyj inR n we want to determine a hyperplane H such that the maximum Euclidean distance betweenH and the pointsyj is minimized. This problem(CHOP) is a non-convex optimization problem with a special structure. Forexample, all local minima can be shown to be strongly unique. We present agenericity analysis of the problem. Two different global optimizationapproaches are considered for solving (CHOP). The first is a Lipschitzoptimization method; the other a cutting plane method for concaveoptimization. The local structure of the problem is elucidated by analysingthe relation between (CHOP) and certain associated linear optimizationproblems. We report on numerical experiments.
Original languageEnglish
Pages (from-to)361-376
Number of pages16
JournalJournal of global optimization
Issue number11
Publication statusPublished - 1997


  • curve fitting
  • Global Optimization
  • Chebyshev approximation

Cite this