NDLI: Min-Max Spaces and Complexity Reduction in Min-Max Expansions

Content Provider	Springer Nature Link
Author	Gaubert, Stephane McEneaney, William M.
Copyright Year	2011
Abstract	Idempotent methods have been found to be extremely helpful in the numerical solution of certain classes of nonlinear control problems. In those methods, one uses the fact that the value function lies in the space of semiconvex functions (in the case of maximizing controllers), and approximates this value using a truncated max-plus basis expansion. In some classes, the value function is actually convex, and then one specifically approximates with suprema (i.e., max-plus sums) of affine functions. Note that the space of convex functions is a max-plus linear space, or moduloid. In extending those concepts to game problems, one finds a different function space, and different algebra, to be appropriate. Here we consider functions which may be represented using infima (i.e., min-max sums) of max-plus affine functions. It is natural to refer to the class of functions so represented as the min-max linear space (or moduloid) of max-plus hypo-convex functions. We examine this space, the associated notion of duality and min-max basis expansions. In using these methods for solution of control problems, and now games, a critical step is complexity-reduction. In particular, one needs to find reduced-complexity expansions which approximate the function as well as possible. We obtain a solution to this complexity-reduction problem in the case of min-max expansions.
Starting Page	315
Ending Page	348
Page Count	34
File Format	PDF
ISSN	00954616
Journal	Applied Mathematics and Optimization
Volume Number	65
Issue Number	3
e-ISSN	14320606
Language	English
Publisher	Springer-Verlag
Publisher Date	2011-12-29
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Min-max algebra Max-plus algebra Curse of dimensionality Games Convex Duality Approximation Tropical algebra Hypo-convex Subtopical Numerical and Computational Physics Systems Theory, Control Calculus of Variations and Optimal Control; Optimization Mathematical Methods in Physics Theoretical, Mathematical and Computational Physics
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Idempotent method for dynamic games and complexity reduction in min-max expansions.

A Reduced Complexity Min-Plus Solution Method to the Optimal Control of Closed Quantum Systems

Complexity of Tropical and Min-plus Linear Prevarieties

Max-Plus Stochastic Control and Risk-Sensitivity

Semidefinite programming for min–max problems and games

Duality gap of the conic convex constrained optimization problems in normed spaces

Complete characterizations of stable Farkas’ lemma and cone-convex programming duality

Basic min-plus and max-plus calculus (2002).

Max-plus stochastic processes

Min-Max Spaces and Complexity Reduction in Min-Max Expansions

Similar Documents

Idempotent method for dynamic games and complexity reduction in min-max expansions.

A Reduced Complexity Min-Plus Solution Method to the Optimal Control of Closed Quantum Systems

Complexity of Tropical and Min-plus Linear Prevarieties

Max-Plus Stochastic Control and Risk-Sensitivity

Semidefinite programming for min–max problems and games

Duality gap of the conic convex constrained optimization problems in normed spaces

Complete characterizations of stable Farkas’ lemma and cone-convex programming duality

Basic min-plus and max-plus calculus (2002).

Max-plus stochastic processes

Min-Max Spaces and Complexity Reduction in Min-Max Expansions