Minimax and ApplicationsDing-Zhu Du, Panos M. Pardalos Springer Science & Business Media, 2013. gada 1. dec. - 296 lappuses Techniques and principles of minimax theory play a key role in many areas of research, including game theory, optimization, and computational complexity. In general, a minimax problem can be formulated as min max f(x, y) (1) ",EX !lEY where f(x, y) is a function defined on the product of X and Y spaces. There are two basic issues regarding minimax problems: The first issue concerns the establishment of sufficient and necessary conditions for equality minmaxf(x,y) = maxminf(x,y). (2) "'EX !lEY !lEY "'EX The classical minimax theorem of von Neumann is a result of this type. Duality theory in linear and convex quadratic programming interprets minimax theory in a different way. The second issue concerns the establishment of sufficient and necessary conditions for values of the variables x and y that achieve the global minimax function value f(x*, y*) = minmaxf(x, y). (3) "'EX !lEY There are two developments in minimax theory that we would like to mention. |
No grāmatas satura
1.–5. rezultāts no 86.
2. lappuse
... proof of Theorem 1 , using the Theorem of the alternative for matrices . It is Ville's proof that von Neumann - Morgenstern expounded in [ 126 ] . Another elementary proof of Theorem 1 was given by Weyl [ 129 ] in 1950. Karlin gave an ...
... proof of Theorem 1 , using the Theorem of the alternative for matrices . It is Ville's proof that von Neumann - Morgenstern expounded in [ 126 ] . Another elementary proof of Theorem 1 was given by Weyl [ 129 ] in 1950. Karlin gave an ...
3. lappuse
... proof and , as a result , discovered the fixed - point theorem that bears his name . In 1952 , Fan [ 13 ] ... proof of the minimax theorem by elementary calculus . Likewise , Moreau [ 87 ] showed that it is possible to give a proof using ...
... proof and , as a result , discovered the fixed - point theorem that bears his name . In 1952 , Fan [ 13 ] ... proof of the minimax theorem by elementary calculus . Likewise , Moreau [ 87 ] showed that it is possible to give a proof using ...
4. lappuse
... proof of Theorem 3 was given in 1988 by Komiya [ 63 ] . Using the concept of a quarter continuous multifunction , Komiya [ 65 ] subsequently showed that , despite the fact that the semicontinuities in Sion's result and Ha's result are ...
... proof of Theorem 3 was given in 1988 by Komiya [ 63 ] . Using the concept of a quarter continuous multifunction , Komiya [ 65 ] subsequently showed that , despite the fact that the semicontinuities in Sion's result and Ha's result are ...
9. lappuse
... proof of Theorem 11 using the Eidelheit separation theorem . König in 1968 , and then Simons in 1971 , proved the ... proofs in [ 67 ] and [ 105 ] both used a version of the Hahn - Banach theorem due to Mazur - Orlicz . However , both ...
... proof of Theorem 11 using the Eidelheit separation theorem . König in 1968 , and then Simons in 1971 , proved the ... proofs in [ 67 ] and [ 105 ] both used a version of the Hahn - Banach theorem due to Mazur - Orlicz . However , both ...
14. lappuse
... proof that all finite subsets of X are good . It now follows from ( 19.1 ) and the finite intersection property for a third time that LE ( X , supy miny f ) ‡ Ø . This completes the proof of Theorem 19. Given the obvious topological ...
... proof that all finite subsets of X are good . It now follows from ( 19.1 ) and the finite intersection property for a third time that LE ( X , supy miny f ) ‡ Ø . This completes the proof of Theorem 19. Given the obvious topological ...
Saturs
Heilbronn Problem for Seven Points in a Planar Convex Body | 191 |
Propositions and Proofs for Easier Cases | 192 |
Configurations with Stability | 195 |
Computing the Smallest Triangle | 203 |
Open Problems | 217 |
References | 218 |
On the Complexity of MinMax Optimization Problems and Their Approximation | 219 |
Definition | 221 |
17 | |
19 | |
A Survey on Minimax Trees and Associated Algorithms | 25 |
Minimax Trees and the Theory Behind Them | 26 |
Sequential Minimax Game Tree Algorithms | 31 |
Parallel Minimax Tree Algorithms | 42 |
Open Problems and Conclusion | 51 |
References | 52 |
An Iterative Method for the Minimax Problem | 55 |
An ELQP Problem as a Subproblem | 56 |
A 2 | 58 |
Local and Superlinear Convergence | 60 |
References | 66 |
བྲསྤྱ | 73 |
Concepts and models | 110 |
Discussion | 120 |
References | 127 |
Mutually Repellant Sampling 129 | 128 |
MaxAverage Distance Sampling | 136 |
min max fx | 141 |
Problem Statement and Geometry | 142 |
Stationary Points and Local Minima | 148 |
Conclusions | 156 |
The Minmax Resource Allocation Problem | 162 |
Summary and Extensions | 169 |
Proof of the Main Theorem | 179 |
References | 188 |
IICompleteness Results | 223 |
Approximation Problems and Their Hardness | 231 |
Nonapproximability Results | 233 |
Conclusion and Open Questions | 238 |
References | 239 |
A Competitive Algorithm for the Counterfeit Coin Problem | 241 |
d | 242 |
A Competitive Algorithm | 244 |
Analysis of Competitiveness | 247 |
Conclusion | 249 |
References | 250 |
A Minimax aß Relaxation for Global Optimization | 251 |
Problem Model | 252 |
Relaxation Approach | 253 |
A General aß Relaxation Algorithm | 254 |
A Minimax aß Relaxation Algorithm for COP | 258 |
Experimental Results | 263 |
References | 268 |
Minimax Problems in Combinatorial Optimization | 269 |
Algorithmic Problems | 270 |
Geometric Problems | 274 |
Graph Problems | 281 |
Management Problems | 287 |
DingZhu Du and Panos M Pardalos | 288 |
Author Index | 293 |
Citi izdevumi - Skatīt visu
Bieži izmantoti vārdi un frāzes
3-partition problem a₁ alpha-beta algorithm approximation algorithms aß relaxation algorithm assume bilevel programming clause compact complexity compute constraints convex cones convex hull convex set counterfeit coin defined denote distance edges ELQP Euclidean exists feasible finite game trees given graph G grid graph Hamiltonian circuit Heilbronn Heilbronn numbers hence II-complete iteration Kindler Lemma linear log₂ loop lower semicontinuous Math Mathematical maximum minimax algorithm minimax problem minimax theorem minimax tree minimax value minimize minimum MMPC MMRA MMST nonempty NP-complete NP-hard objective function optimal solution optimization problems parallel minimax Pardalos partition peripheral triangles points polynomial polynomial-time processors Proof prove pseudo-polynomial r₁ result satisfies scenario scheduling solved spanning tree Steiner network subgraph subsets subtree Suppose theory tight topological space triples truth assignment upper bound variables vertex vertices w(Tn X-literal y₁