A tolerant algorithm for linearly constrained optimization calculations View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-08

AUTHORS

M. J. D. Powell

ABSTRACT

Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with “small” residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the “small” residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua. More... »

PAGES

547-566

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01589118

DOI

http://dx.doi.org/10.1007/bf01589118

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Cambridge", 
          "id": "https://www.grid.ac/institutes/grid.5335.0", 
          "name": [
            "Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Powell", 
        "givenName": "M. J. D.", 
        "id": "sg:person.07731545105.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02591962", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034228875", 
          "https://doi.org/10.1007/bf02591962"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02591962", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034228875", 
          "https://doi.org/10.1007/bf02591962"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02591850", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039185361", 
          "https://doi.org/10.1007/bf02591850"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02591850", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039185361", 
          "https://doi.org/10.1007/bf02591850"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1011036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062860143"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989-08", 
    "datePublishedReg": "1989-08-01", 
    "description": "Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with \u201csmall\u201d residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the \u201csmall\u201d residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01589118", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "45"
      }
    ], 
    "name": "A tolerant algorithm for linearly constrained optimization calculations", 
    "pagination": "547-566", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ae36da270864ee00636fd19f327807f44f56eb9f92c21ecd0cd723eb652b8988"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01589118"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036571828"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01589118", 
      "https://app.dimensions.ai/details/publication/pub.1036571828"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T15:56", 
    "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_8664_00000533.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF01589118"
  }
]
 

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.1007/bf01589118'

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.1007/bf01589118'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01589118'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01589118'


 

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

72 TRIPLES      21 PREDICATES      30 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01589118 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N80edd79721d348269bed6bb63453b6e4
4 schema:citation sg:pub.10.1007/bf02591850
5 sg:pub.10.1007/bf02591962
6 https://doi.org/10.1137/1011036
7 schema:datePublished 1989-08
8 schema:datePublishedReg 1989-08-01
9 schema:description Two extreme techniques when choosing a search direction in a linearly constrained optimization calculation are to take account of all the constraints or to use an active set method that satisfies selected constraints as equations, the remaining constraints being ignored. We prefer an intermediate method that treats all inequality constraints with “small” residuals as inequalities with zero right hand sides and that disregards the other inequality conditions. Thus the step along the search direction is not restricted by any constraints with small residuals, which can help efficiency greatly, particularly when some constraints are nearly degenerate. We study the implementation, convergence properties and performance of an algorithm that employs this idea. The implementation considerations include the choice and automatic adjustment of the tolerance that defines the “small” residuals, the calculation of the search directions, and the updating of second derivative approximations. The main convergence theorem imposes no conditions on the constraints except for boundedness of the feasible region. The numerical results indicate that a Fortran implementation of our algorithm is much more reliable than the software that was tested by Hock and Schittkowski (1981). Therefore the algorithm seems to be very suitable for general use, and it is particularly appropriate for semi-infinite programming calculations that have many linear constraints that come from discretizations of continua.
10 schema:genre research_article
11 schema:inLanguage en
12 schema:isAccessibleForFree false
13 schema:isPartOf N66fd287d125640f38c23648a4c4481d5
14 N77df0c7d2f774f3b90365c62cd2140f4
15 sg:journal.1047630
16 schema:name A tolerant algorithm for linearly constrained optimization calculations
17 schema:pagination 547-566
18 schema:productId N2b0c206bd45d44ea936b820ec24fdff6
19 N397b3b159f8542319b56d645ed01864b
20 N3c40fdf37df4453a94ae785a9200fdec
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036571828
22 https://doi.org/10.1007/bf01589118
23 schema:sdDatePublished 2019-04-10T15:56
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher Nc4096ef12ebc4b2e8bc1c6c50214b9e1
26 schema:url http://link.springer.com/10.1007%2FBF01589118
27 sgo:license sg:explorer/license/
28 sgo:sdDataset articles
29 rdf:type schema:ScholarlyArticle
30 N2b0c206bd45d44ea936b820ec24fdff6 schema:name doi
31 schema:value 10.1007/bf01589118
32 rdf:type schema:PropertyValue
33 N397b3b159f8542319b56d645ed01864b schema:name readcube_id
34 schema:value ae36da270864ee00636fd19f327807f44f56eb9f92c21ecd0cd723eb652b8988
35 rdf:type schema:PropertyValue
36 N3c40fdf37df4453a94ae785a9200fdec schema:name dimensions_id
37 schema:value pub.1036571828
38 rdf:type schema:PropertyValue
39 N66fd287d125640f38c23648a4c4481d5 schema:volumeNumber 45
40 rdf:type schema:PublicationVolume
41 N77df0c7d2f774f3b90365c62cd2140f4 schema:issueNumber 1-3
42 rdf:type schema:PublicationIssue
43 N80edd79721d348269bed6bb63453b6e4 rdf:first sg:person.07731545105.07
44 rdf:rest rdf:nil
45 Nc4096ef12ebc4b2e8bc1c6c50214b9e1 schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
48 schema:name Mathematical Sciences
49 rdf:type schema:DefinedTerm
50 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
51 schema:name Numerical and Computational Mathematics
52 rdf:type schema:DefinedTerm
53 sg:journal.1047630 schema:issn 0025-5610
54 1436-4646
55 schema:name Mathematical Programming
56 rdf:type schema:Periodical
57 sg:person.07731545105.07 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
58 schema:familyName Powell
59 schema:givenName M. J. D.
60 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07
61 rdf:type schema:Person
62 sg:pub.10.1007/bf02591850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039185361
63 https://doi.org/10.1007/bf02591850
64 rdf:type schema:CreativeWork
65 sg:pub.10.1007/bf02591962 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034228875
66 https://doi.org/10.1007/bf02591962
67 rdf:type schema:CreativeWork
68 https://doi.org/10.1137/1011036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062860143
69 rdf:type schema:CreativeWork
70 https://www.grid.ac/institutes/grid.5335.0 schema:alternateName University of Cambridge
71 schema:name Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England
72 rdf:type schema:Organization
 




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


...