Relaxation (approximation) (original) (raw)
En mathématiques, une technique de relaxation est une méthode d'optimisation qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont largement utilisées dans les méthodes de séparation et évaluation. Il ne faut pas confondre les techniques de relaxation avec les méthodes itératives de relaxation, comme la méthode de surrelaxation successive, qui servent notamment à résoudre des systèmes d'équations linéaires.
| Property | Value |
|---|---|
| dbo:abstract | In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem. For example, a linear programming relaxation of an integer programming problem removes the integrality constraint and so allows non-integer rational solutions. A Lagrangian relaxation of a complicated problem in combinatorial optimization penalizes violations of some constraints, allowing an easier relaxed problem to be solved. Relaxation techniques complement or supplement branch and bound algorithms of combinatorial optimization; linear programming and Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming. The modeling strategy of relaxation should not be confused with iterative methods of relaxation, such as successive over-relaxation (SOR); iterative methods of relaxation are used in solving problems in differential equations, linear least-squares, and linear programming. However, iterative methods of relaxation have been used to solve Lagrangian relaxations. (en) En mathématiques, une technique de relaxation est une méthode d'optimisation qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont largement utilisées dans les méthodes de séparation et évaluation. Il ne faut pas confondre les techniques de relaxation avec les méthodes itératives de relaxation, comme la méthode de surrelaxation successive, qui servent notamment à résoudre des systèmes d'équations linéaires. (fr) Relaxation är en term inom optimeringslära som betyder att man lättar på eller helt tar bort vissa av villkoren som finns på ett optimeringsproblem. Det kan exempelvis innebära att man istället för ett problem där en variabel är heltalig, låter anta alla reella värden. Relaxeringar brukar göras för att det nya problemet man får är enklare att hantera, mer lättlösligt, gärna ett . Eftersom man vid en relaxering tillåter fler värden än tidigare (man utökar mängden ) utan att ta bort några tillåtna lösningar ur ursprungsproblemet, så kommer det relaxerade problemet alltid att ge ett minst lika bra resultat som ursprungsproblemet. Man säger att en relaxation ger en av optimalvärdet. Om optimallösningen i relaxationen är en tillåten lösning i ursprungsproblemet så är den även optimallösningen till det problemet. Oftast är optimallösningen till det relaxerade problemet en otillåten lösning till ursprungsproblemet. Man kan då behöva göra kapningar/snitt/beskärningar eller förgreningar av det tillåtna området för att bli av med punkten som var optimum och leta upp en ny optimal lösning. Detta kan upprepas tills den funna optimallösningen är en tillåten lösning i ursprungsproblemet. (sv) |
| dbo:wikiPageID | 6347835 (xsd:integer) |
| dbo:wikiPageLength | 6509 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1065520936 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Branch_and_bound dbc:Approximations dbr:Integer_programming dbr:Mathematical_optimization dbc:Relaxation_(approximation) dbr:Lagrangian_relaxation dbr:Approximation dbr:Linear_least_squares_(mathematics) dbr:Linear_programming dbr:Linear_programming_relaxation dbr:Partial_differential_equation dbr:Iterative_method dbc:Mathematical_optimization dbr:Claude_Lemaréchal dbr:Mathematical_model dbr:Successive_over-relaxation dbr:Relaxation_method dbr:W._R._Pulleyblank dbr:Semidefinite_relaxation dbr:Surrogate_duality dbr:Surrogate_relaxation |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Efn dbt:Notelist dbt:Reflist dbt:Sfnp |
| dct:subject | dbc:Approximations dbc:Relaxation_(approximation) dbc:Mathematical_optimization |
| gold:hypernym | dbr:Strategy |
| rdf:type | yago:WikicatApproximations yago:Abstraction100002137 yago:Calculation105802185 yago:Cognition100023271 yago:Estimate105803379 yago:HigherCognitiveProcess105770664 yago:ProblemSolving105796750 yago:Process105701363 yago:PsychologicalFeature100023100 dbo:VideoGame yago:Thinking105770926 |
| rdfs:comment | En mathématiques, une technique de relaxation est une méthode d'optimisation qui consiste à remplacer une contrainte stricte en contrainte moins stricte, voire à la supprimer. Les techniques de relaxation sont largement utilisées dans les méthodes de séparation et évaluation. Il ne faut pas confondre les techniques de relaxation avec les méthodes itératives de relaxation, comme la méthode de surrelaxation successive, qui servent notamment à résoudre des systèmes d'équations linéaires. (fr) In mathematical optimization and related fields, relaxation is a modeling strategy. A relaxation is an approximation of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem. (en) Relaxation är en term inom optimeringslära som betyder att man lättar på eller helt tar bort vissa av villkoren som finns på ett optimeringsproblem. Det kan exempelvis innebära att man istället för ett problem där en variabel är heltalig, låter anta alla reella värden. Relaxeringar brukar göras för att det nya problemet man får är enklare att hantera, mer lättlösligt, gärna ett . Om optimallösningen i relaxationen är en tillåten lösning i ursprungsproblemet så är den även optimallösningen till det problemet. (sv) |
| rdfs:label | Relaxation (approximation) (en) Technique de relaxation (mathématiques) (fr) Relaxation (sv) |
| owl:sameAs | freebase:Relaxation (approximation) yago-res:Relaxation (approximation) wikidata:Relaxation (approximation) dbpedia-fr:Relaxation (approximation) dbpedia-sv:Relaxation (approximation) https://global.dbpedia.org/id/4pqpd |
| prov:wasDerivedFrom | wikipedia-en:Relaxation_(approximation)?oldid=1065520936&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Relaxation_(approximation) |
| is dbo:wikiPageDisambiguates of | dbr:Relaxation |
| is dbo:wikiPageRedirects of | dbr:Mathematical_relaxation dbr:Relaxation_technique_(mathematics) |
| is dbo:wikiPageWikiLink of | dbr:Bellman–Ford_algorithm dbr:List_of_numerical_analysis_topics dbr:Nullspace_property dbr:ΑΒΒ dbr:Mathematical_optimization dbr:Lagrangian_relaxation dbr:MRF_optimization_via_dual_decomposition dbr:Matching_polytope dbr:Mutilated_chessboard_problem dbr:Admissible_heuristic dbr:Duality_(optimization) dbr:Fairness_(machine_learning) dbr:Partial_sorting dbr:Relaxation dbr:Relaxation_(iterative_method) dbr:Bilevel_optimization dbr:Autoencoder dbr:Weapon_target_assignment_problem dbr:Sparse_approximation dbr:Mathematical_relaxation dbr:Relaxation_technique_(mathematics) |
| is foaf:primaryTopic of | wikipedia-en:Relaxation_(approximation) |