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 68.
1. lappuse
... assumed for X and Y , but various quantitative properties are assumed for ƒ and , finally , mixed minimax theorems in which the quantitative and the topological properties are mixed . Recent developments have included unifying ...
... assumed for X and Y , but various quantitative properties are assumed for ƒ and , finally , mixed minimax theorems in which the quantitative and the topological properties are mixed . Recent developments have included unifying ...
2. lappuse
... assume that all topological spaces are Hausdorff . 2. The First Minimax Theorem The first minimax theorem was proved by von Neumann in 1928 using topological arguments : Theorem 1 ( [ 124 ] ) Let A be an m × n matrix , and X and Y be ...
... assume that all topological spaces are Hausdorff . 2. The First Minimax Theorem The first minimax theorem was proved by von Neumann in 1928 using topological arguments : Theorem 1 ( [ 124 ] ) Let A be an m × n matrix , and X and Y be ...
7. lappuse
... assumed in Theo- rem 8 and Theorem 9 are stronger than the topological conditions actually assumed in [ 115 ] and [ 61 ] . We have adopted these simplifications so as not to overburden the reader with too many technicalities , and also ...
... assumed in Theo- rem 8 and Theorem 9 are stronger than the topological conditions actually assumed in [ 115 ] and [ 61 ] . We have adopted these simplifications so as not to overburden the reader with too many technicalities , and also ...
13. lappuse
... assumed . This idea was pursued by Simons with the introduction in 1992 of the concept of pseudoconnectedness . We say that sets Ho and H1 are joined by a set H if HCHOUH1 , Ho Ho and H H1 0 . We say that a family H of sets is ...
... assumed . This idea was pursued by Simons with the introduction in 1992 of the concept of pseudoconnectedness . We say that sets Ho and H1 are joined by a set H if HCHOUH1 , Ho Ho and H H1 0 . We say that a family H of sets is ...
17. lappuse
... assumed to be com- pact , and that Theorem 24 actually unifies the theory of minimax theorems and the theory of variational inequalities . Theorem 24 was extended even further by Ben - El - Mechaiekh , Deguire and Granas who proved ...
... assumed to be com- pact , and that Theorem 24 actually unifies the theory of minimax theorems and the theory of variational inequalities . Theorem 24 was extended even further by Ben - El - Mechaiekh , Deguire and Granas who proved ...
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₁