Novel approaches to the discrimination problem
Mathematical Methods of Operations ResearchPublished 1 November 1992
Patrice Marcotte, Gilles Savard
Citations21
SJR quartileQ2
SJR score0.38
SNIP0.93
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Two criteria for judging the quality of a candidate hyperplane are analyzed and the maximal distance of a misclassified point to the hyperplane and the number of misclassified points are analyzed.
Abstract
We consider the problem of determining a hyperplane that separates, as "well" as possible, two finite sets of points inR n . We analyze two criteria for judging the quality of a candidate hyperplane (i) the maximal distance of a misclassified point to the hyperplane (ii) the number of misclassified points. In each case, we investigate the computational complexity of the corresponding mathematical programs, give equivalent formulations, suggest solution algorithms and present preliminary numerical results.
Keywords
Decision SciencesMathematicsEngineering
Annals of EugenicsTHE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
14,727 Citations1936Ronald Aylmer Fisher
Global Optimization: Deterministic Approaches
1,644 Citations1992Reiner Horst, Tuy Hoang
This study develops a unifying approach to constrained global optimization that provides insight into the underlying concepts and properties of diverse techniques recently proposed to solve a wide variety of problems encountered in the decision sciences, engineering, operations research and other disciplines.
Mathematical ProgrammingA polynomial-time algorithm for a class of linear complementarity problems
340 Citations1989Masakazu Kojima, Shinji Mizuno +1 more
An algorithm is presented that solves the problem of finding n-dimensional vectors in O(n3L) arithmetic operations by tracing the path of centers by identifying the centers of centers of the feasible region.
European Journal of Operational ResearchSimple but powerful goal programming models for discriminant problems
330 Citations1981N. Freed, Fred Glover
It is demonstrated via simple illustration the potential of alternative assignment procedures to play a significant part in addressing the discriminant problem, and fundamental ideas that lay the foundation for other more sophisticated approaches are indicated.
Mathematical ProgrammingFinding the nearest point in A polytope
310 Citations1976Philip Wolfe
A terminating algorithm is developed for the problem of finding the point of smallest Euclidean norm in the convex hull of a given finite point set in Euclideann-space, or equivalently for finding an “optimal” hyperplane separating a given point from a given infinite point set.
Decision SciencesImproved Linear Programming Models for Discriminant Analysis*
236 Citations1990Fred Glover
It is shown how to eliminate a previously undetected distortion and thereby increase the scope and flexibility of the LP discriminant analysis models, including the use of a successive goal method for establishing a series of conditional objectives to achieve improved discrimination.
Decision SciencesApplications and Implementation
195 Citations1981N. Freed, Fred Glover
This work proposes an alternative solution to the discriminant problem that requires little more than a minimum familiarity with linear programming and shows promise for eliminating the complexities of conventional statistical approaches without sacrificing the essential power of existing methods.
Decision SciencesAN EXPERIMENTAL COMPARISON OF STATISTICAL AND LINEAR PROGRAMMING APPROACHES TO THE DISCRIMINANT PROBLEM
185 Citations1982Steve M. Bajgier, Arthur V. Hill
Theoretical Computer ScienceThe densest hemisphere problem
159 Citations1978David Johnson, F. P. Preparata
A discretized version of the original problem, restated as a feasibility question, is NP-complete when both n and d are arbitrary and there exists a polynomial time algorithm which solves the problem in time O( n d −1 log n ) on a random access machine with unit cost arithmetic operations.
Decision SciencesMinimizing Misclassifications in Linear Discriminant Analysis*
140 Citations1990Gary J. Kœhler, Ş. Selçuk Erengüç
SIAM Journal on Control and OptimizationIterative Methods for Large Convex Quadratic Programs: A Survey
125 Citations1987Y. Lin, Jong‐Shi Pang
A state-of-the-art review of many iterative methods for solving large convex quadratic programs is given, within which a unified iterative scheme will be introduced and its convergence analyzed.
Mathematical ProgrammingOn the complexity of four polyhedral set containment problems
95 Citations1985Robert M. Freund, James B. Orlin
The problems of determining if X is anH-cell andY is a closed solid ball, or whether there exists an integer point in aW-cell is shown to be NP-complete, demonstrating that regardless of the representation ofX as an H-cell or W-cell, this integer containment problem is NP- complete.
Mathematical ProgrammingMaximization of A convex quadratic function under linear constraints
88 Citations1976Hiroshi Konno
This paper develops an iterative procedure to improve a given cut by exploiting the symmetric structure of the bilinear program and generates a cut which is deeper (usually much deeper) than Tui's cut.
European Journal of Operational ResearchA comparison of a robust mixed-integer approach to existing methods for establishing classification rules for the discriminant problem
75 Citations1990Antonie Stam, Erich A. Joachimsthaler
This study suggests that under certain conditions the mixed-integer approach is an attractive alternative to establish classification methods.
COMBINATORICAComputational complexity of norm-maximization
72 Citations1990Hans L. Bodlaender, Peter Gritzmann +2 more
The present reexamination of the problem of maximizing a quasiconvex functionφ over a convex polytopeP inn-space that is presented as the intersection of a finite number of halfspaces proves theNP-hardness of maximization overn-dimensionalparallelotopes that are centered at the origin or have a vertex there.
Computers & Operations ResearchDiscriminant analysis via mathematical programming: Certain problems and their causes
61 Citations1989Tom M. Cavalier, James P. Ignizio +1 more
This work represents an ongoing effort on the part of the authors in the development of an efficient revised approach to discriminant analysis via mathematical programming.
Decision SciencesCharacterization of Unacceptable Solutions in LP Discriminant Analysis*
54 Citations1989Gary J. Kœhler
This paper characterized conditions leading to unacceptable solutions for all two-group models for linear programming models for discriminant analysis.
European Journal of Operational ResearchAn experimental comparison of several approaches to the discriminant problem with both qualitative and quantitative variables
47 Citations1987Carol A. Markowski, Edward P. Markowski
The results indicate that both methods are enhanced by the inclusion of the qualitative variables, but that the Fisher approach seems preferable.
Decision SciencesON USING LINEAR PROGRAMMING IN DISCRIMINANT PROBLEMS
34 Citations1982Louis W. Glorfeld, Norman Gaither
European Journal of Operational ResearchEvaluating the maximize minimum distance formulation of the linear discriminant problem
21 Citations1989Paul A. Rubin