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 42.
4. lappuse
... set technique and the Hahn - Banach theorem . In fact , the techniques of [ 37 ] and [ 38 ] really belonged in a ... convex functions in finite dimensional situations , which he extended in [ 102 ] to the infinite dimensional case . In these ...
... set technique and the Hahn - Banach theorem . In fact , the techniques of [ 37 ] and [ 38 ] really belonged in a ... convex functions in finite dimensional situations , which he extended in [ 102 ] to the infinite dimensional case . In these ...
8. lappuse
... convex set in some vector space , and the topology of X replaced by the natural topology of all the line segments in X. More results in the direction of Theorem 9 were proved by Ricceri in [ 100 ] . This discussion will be continued in ...
... convex set in some vector space , and the topology of X replaced by the natural topology of all the line segments in X. More results in the direction of Theorem 9 were proved by Ricceri in [ 100 ] . This discussion will be continued in ...
9. lappuse
... set and Y be a nonempty compact topological space . Let f X x Y IR be lower ... sets X and Y by statements about the convexity of the functional values of f ... convex subset of E. Then there exists a linear functional L on E such that L ...
... set and Y be a nonempty compact topological space . Let f X x Y IR be lower ... sets X and Y by statements about the convexity of the functional values of f ... convex subset of E. Then there exists a linear functional L on E such that L ...
12. lappuse
... convex metric spaces see [ 59 ] and [ 60 ] , and also the paper [ 98 ] on minimax risk by Pinelis . - 8. Mixed ... set and Y be a nonempty compact topological space . Let f : X x Y → IR be lower semicontinuous on Y. Suppose that , for ...
... convex metric spaces see [ 59 ] and [ 60 ] , and also the paper [ 98 ] on minimax risk by Pinelis . - 8. Mixed ... set and Y be a nonempty compact topological space . Let f : X x Y → IR be lower semicontinuous on Y. Suppose that , for ...
15. lappuse
... set by C11 = { x : x = X , y ¢ Cx } : = Kindler proved in [ 55 ] that the sets { C } rex have the finite ... convex , complete subset of a locally convex space E with dual space E * , and inf sup ( x , y ) yЄY TEX = sup_inf ( x , y ) TEX ...
... set by C11 = { x : x = X , y ¢ Cx } : = Kindler proved in [ 55 ] that the sets { C } rex have the finite ... convex , complete subset of a locally convex space E with dual space E * , and inf sup ( x , y ) yЄY TEX = sup_inf ( x , y ) TEX ...
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₁