The Surgical Separation of Sets View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-12

AUTHORS

James E. Falk, Emma Lopez-Cardona

ABSTRACT

Given a pair of finite disjoint setsA andB inRn, a fundamental problem with many important applications isto efficiently determine a hyperplaneH(w,λ) which separates these sets when they are separable, or ‘nearly’ separates themwhen they are not. We seek a hyperplane which minimizes a natural errormeasure in the latter case, and so will ‘surgically’ separate the sets. Whenthe sets are separable in a strong sense, we show that the problem is aconvex program with a unique solution, which has been investigated byothers. Using the KKT conditions, we improve on an existing algorithm. Whenthe sets are not separable, the problem is nonconvex, generally with properlocal solutions, and we solve an equivalent problem by Branch and Bound.Numerical results are presented. More... »

PAGES

433-462

References to SciGraph publications

  • 1976-06. Infinitely constrained optimization problems in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1008284015704

    DOI

    http://dx.doi.org/10.1023/a:1008284015704

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1013421507


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "George Washington University", 
              "id": "https://www.grid.ac/institutes/grid.253615.6", 
              "name": [
                "Department of Operations Research, The George Washington University, 20052, Washington, DC, U.S.A"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Falk", 
            "givenName": "James E.", 
            "id": "sg:person.012617405611.31", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012617405611.31"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Office of Environmental Management", 
              "id": "https://www.grid.ac/institutes/grid.457407.5", 
              "name": [
                "Department of Energy, Office of Environmental Management, 20585, Washington, DC, U.S.A"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lopez-Cardona", 
            "givenName": "Emma", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1982.tb00139.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000480519"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10556789208805504", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006237986"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-247x(65)90150-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006271376"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(89)90007-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009298105"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(89)90007-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009298105"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1988.tb00266.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021859590"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1986.tb00244.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027393137"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1986.tb00218.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032229269"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00934096", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036679122", 
              "https://doi.org/10.1007/bf00934096"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00934096", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036679122", 
              "https://doi.org/10.1007/bf00934096"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0305-0548(94)00042-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041474171"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1981.tb00061.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045404190"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1989.tb01423.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045917864"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1990.tb01249.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052497566"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1111/j.1540-5915.1989.tb01875.x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053469999"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1968.229395", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061531342"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.15.9.550", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064716537"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.13.3.444", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064726865"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1997-12", 
        "datePublishedReg": "1997-12-01", 
        "description": "Given a pair of finite disjoint setsA andB inRn, a fundamental problem with many important applications isto efficiently determine a hyperplaneH(w,\u03bb) which separates these sets when they are separable, or \u2018nearly\u2019 separates themwhen they are not. We seek a hyperplane which minimizes a natural errormeasure in the latter case, and so will \u2018surgically\u2019 separate the sets. Whenthe sets are separable in a strong sense, we show that the problem is aconvex program with a unique solution, which has been investigated byothers. Using the KKT conditions, we improve on an existing algorithm. Whenthe sets are not separable, the problem is nonconvex, generally with properlocal solutions, and we solve an equivalent problem by Branch and Bound.Numerical results are presented.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1008284015704", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050312", 
            "issn": [
              "0925-5001", 
              "1573-2916"
            ], 
            "name": "Journal of Global Optimization", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "11"
          }
        ], 
        "name": "The Surgical Separation of Sets", 
        "pagination": "433-462", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "3feffdcd46c631bcb80199aa7549e546466cf7da7652f74639a94e803ba6c7ba"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1008284015704"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1013421507"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1008284015704", 
          "https://app.dimensions.ai/details/publication/pub.1013421507"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:54", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8681_00000499.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023/A:1008284015704"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1008284015704'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1008284015704'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008284015704'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008284015704'


     

    This table displays all metadata directly associated to this object as RDF triples.

    119 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1008284015704 schema:about anzsrc-for:17
    2 anzsrc-for:1701
    3 schema:author N53b75331124b471994c50f94d5a4e0d6
    4 schema:citation sg:pub.10.1007/bf00934096
    5 https://doi.org/10.1016/0022-247x(65)90150-2
    6 https://doi.org/10.1016/0305-0548(89)90007-5
    7 https://doi.org/10.1016/0305-0548(94)00042-7
    8 https://doi.org/10.1080/10556789208805504
    9 https://doi.org/10.1109/tc.1968.229395
    10 https://doi.org/10.1111/j.1540-5915.1981.tb00061.x
    11 https://doi.org/10.1111/j.1540-5915.1982.tb00139.x
    12 https://doi.org/10.1111/j.1540-5915.1986.tb00218.x
    13 https://doi.org/10.1111/j.1540-5915.1986.tb00244.x
    14 https://doi.org/10.1111/j.1540-5915.1988.tb00266.x
    15 https://doi.org/10.1111/j.1540-5915.1989.tb01423.x
    16 https://doi.org/10.1111/j.1540-5915.1989.tb01875.x
    17 https://doi.org/10.1111/j.1540-5915.1990.tb01249.x
    18 https://doi.org/10.1287/mnsc.15.9.550
    19 https://doi.org/10.1287/opre.13.3.444
    20 schema:datePublished 1997-12
    21 schema:datePublishedReg 1997-12-01
    22 schema:description Given a pair of finite disjoint setsA andB inRn, a fundamental problem with many important applications isto efficiently determine a hyperplaneH(w,λ) which separates these sets when they are separable, or ‘nearly’ separates themwhen they are not. We seek a hyperplane which minimizes a natural errormeasure in the latter case, and so will ‘surgically’ separate the sets. Whenthe sets are separable in a strong sense, we show that the problem is aconvex program with a unique solution, which has been investigated byothers. Using the KKT conditions, we improve on an existing algorithm. Whenthe sets are not separable, the problem is nonconvex, generally with properlocal solutions, and we solve an equivalent problem by Branch and Bound.Numerical results are presented.
    23 schema:genre research_article
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf Nbe5162f063f445b0bcb91706420731d9
    27 Ne024951f0b964eb3818696e26b2bb899
    28 sg:journal.1050312
    29 schema:name The Surgical Separation of Sets
    30 schema:pagination 433-462
    31 schema:productId N3c100f8c200a4198ade474639b066467
    32 N756d81c0f33246fdbd91f1159d9ba82e
    33 Nb7436556a40e44bc8d4eb8b9339cf9f4
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013421507
    35 https://doi.org/10.1023/a:1008284015704
    36 schema:sdDatePublished 2019-04-10T19:54
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher N96564bd8c36c4be8abe0156f747f4ef9
    39 schema:url http://link.springer.com/10.1023/A:1008284015704
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset articles
    42 rdf:type schema:ScholarlyArticle
    43 N3c100f8c200a4198ade474639b066467 schema:name readcube_id
    44 schema:value 3feffdcd46c631bcb80199aa7549e546466cf7da7652f74639a94e803ba6c7ba
    45 rdf:type schema:PropertyValue
    46 N3e7749298a5b4700b8f02347fb4732c2 schema:affiliation https://www.grid.ac/institutes/grid.457407.5
    47 schema:familyName Lopez-Cardona
    48 schema:givenName Emma
    49 rdf:type schema:Person
    50 N53b75331124b471994c50f94d5a4e0d6 rdf:first sg:person.012617405611.31
    51 rdf:rest Nb8fc417d07a84f87abc7b18b169fed48
    52 N756d81c0f33246fdbd91f1159d9ba82e schema:name dimensions_id
    53 schema:value pub.1013421507
    54 rdf:type schema:PropertyValue
    55 N96564bd8c36c4be8abe0156f747f4ef9 schema:name Springer Nature - SN SciGraph project
    56 rdf:type schema:Organization
    57 Nb7436556a40e44bc8d4eb8b9339cf9f4 schema:name doi
    58 schema:value 10.1023/a:1008284015704
    59 rdf:type schema:PropertyValue
    60 Nb8fc417d07a84f87abc7b18b169fed48 rdf:first N3e7749298a5b4700b8f02347fb4732c2
    61 rdf:rest rdf:nil
    62 Nbe5162f063f445b0bcb91706420731d9 schema:issueNumber 4
    63 rdf:type schema:PublicationIssue
    64 Ne024951f0b964eb3818696e26b2bb899 schema:volumeNumber 11
    65 rdf:type schema:PublicationVolume
    66 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Psychology and Cognitive Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Psychology
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1050312 schema:issn 0925-5001
    73 1573-2916
    74 schema:name Journal of Global Optimization
    75 rdf:type schema:Periodical
    76 sg:person.012617405611.31 schema:affiliation https://www.grid.ac/institutes/grid.253615.6
    77 schema:familyName Falk
    78 schema:givenName James E.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012617405611.31
    80 rdf:type schema:Person
    81 sg:pub.10.1007/bf00934096 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036679122
    82 https://doi.org/10.1007/bf00934096
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/0022-247x(65)90150-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006271376
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0305-0548(89)90007-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009298105
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0305-0548(94)00042-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041474171
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1080/10556789208805504 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006237986
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1109/tc.1968.229395 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061531342
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1111/j.1540-5915.1981.tb00061.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1045404190
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1111/j.1540-5915.1982.tb00139.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1000480519
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1111/j.1540-5915.1986.tb00218.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1032229269
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1111/j.1540-5915.1986.tb00244.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027393137
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1111/j.1540-5915.1988.tb00266.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1021859590
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1111/j.1540-5915.1989.tb01423.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1045917864
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1111/j.1540-5915.1989.tb01875.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1053469999
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1111/j.1540-5915.1990.tb01249.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1052497566
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1287/mnsc.15.9.550 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064716537
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1287/opre.13.3.444 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064726865
    113 rdf:type schema:CreativeWork
    114 https://www.grid.ac/institutes/grid.253615.6 schema:alternateName George Washington University
    115 schema:name Department of Operations Research, The George Washington University, 20052, Washington, DC, U.S.A
    116 rdf:type schema:Organization
    117 https://www.grid.ac/institutes/grid.457407.5 schema:alternateName Office of Environmental Management
    118 schema:name Department of Energy, Office of Environmental Management, 20585, Washington, DC, U.S.A
    119 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...