The Chebyshev Hyperplane Optimization Problem

Georg J. Still, Martin Streng, M. Streng

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

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 languageUndefined
Pages (from-to)361-376
Number of pages16
JournalJournal of global optimization
Volume11
Issue number11
DOIs
Publication statusPublished - 1997

Keywords

  • curve fitting
  • IR-85602
  • METIS-140403
  • Global Optimization
  • Chebyshev approximation

Cite this

Still, Georg J. ; Streng, Martin ; Streng, M. / The Chebyshev Hyperplane Optimization Problem. In: Journal of global optimization. 1997 ; Vol. 11, No. 11. pp. 361-376.
@article{22c12785b67b4b15b28b3efad5514d7b,
title = "The Chebyshev Hyperplane Optimization Problem",
abstract = "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.",
keywords = "curve fitting, IR-85602, METIS-140403, Global Optimization, Chebyshev approximation",
author = "Still, {Georg J.} and Martin Streng and M. Streng",
year = "1997",
doi = "10.1023/A:1008220431204",
language = "Undefined",
volume = "11",
pages = "361--376",
journal = "Journal of global optimization",
issn = "0925-5001",
publisher = "Springer",
number = "11",

}

The Chebyshev Hyperplane Optimization Problem. / Still, Georg J.; Streng, Martin; Streng, M.

In: Journal of global optimization, Vol. 11, No. 11, 1997, p. 361-376.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The Chebyshev Hyperplane Optimization Problem

AU - Still, Georg J.

AU - Streng, Martin

AU - Streng, M.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - curve fitting

KW - IR-85602

KW - METIS-140403

KW - Global Optimization

KW - Chebyshev approximation

U2 - 10.1023/A:1008220431204

DO - 10.1023/A:1008220431204

M3 - Article

VL - 11

SP - 361

EP - 376

JO - Journal of global optimization

JF - Journal of global optimization

SN - 0925-5001

IS - 11

ER -