Data processing: artificial intelligence – Adaptive system
Reexamination Certificate
2011-08-02
2011-08-02
Gaffin, Jeffrey A (Department: 2129)
Data processing: artificial intelligence
Adaptive system
Reexamination Certificate
active
07991713
ABSTRACT:
A novel method is disclosed for efficiently solving minimax problems, and in particular, for efficiently solving minimax problems wherein the corresponding matrix is large. In particular, the novel method solves minimax problems in O(n2T) operation count, where n denotes the problem size and T is reversely proportional to the required duality gap as one skilled in the art will understand. Further disclosed herein is a method for solving linear programming (LP) problems by converting such problems into minimax problems, and then using the novel minimax solution method disclosed herein.
REFERENCES:
patent: 4744026 (1988-05-01), Vanderbei
patent: 5325445 (1994-06-01), Herbert
patent: 5649068 (1997-07-01), Boser et al.
patent: 6510746 (2003-01-01), Kotwicki
patent: 6546379 (2003-04-01), Hong et al.
patent: 6714893 (2004-03-01), Busche et al.
patent: 7024033 (2006-04-01), Li et al.
patent: 7099505 (2006-08-01), Li et al.
patent: 7301314 (2007-11-01), Schuellein et al.
patent: 7301341 (2007-11-01), Hargreaves et al.
patent: 7301615 (2007-11-01), Fukagawa et al.
patent: 7305641 (2007-12-01), Tang
patent: 2005/0192865 (2005-09-01), Boutilier et al.
patent: 2007/0026406 (2007-02-01), El Ghaoui et al.
patent: 2007/0053563 (2007-03-01), Tu et al.
patent: 2007/0104222 (2007-05-01), Luss
patent: WO 2007/007249 (2007-01-01), None
Sun “On the Convergence of an Iterative Method for the Minimax Problem”, J. Austral. Math. Soc. Ser. B 39(1997), 280-292.
Rockafellar, “Linear-quadratic programming and optimal control”, SIAM Journal on Control and Optimization 25 (1987) 781-814.
C. Zhu et al., “Primal-dual projected gradient algorithms for extended linear quadratic programming”, SIAM J. Optimization 3 (1993) 751-783.
Ge, “Solving Linear Programming Problems via Linear Minimax Problems”, Applied Mathematics and Computatzon 46:59-77 (1991).
Hedar, et al., “Heuristic Pattern Search and Its Hybridization with Simulated Annealing for Nonlinear Global Optimization”, Optimization Methods and Software 19 (2004) 291-308.
Ermoliev, “Stochastic Quasigradient Methods and Their Application I N Systems Optimization”, WP-81-2, 1981, No. of pages: 51.
Adler et al., “An Implementation of Karmarkar's Algorithm for Linear Programming”, dated Mar. 14, 1989 (revised May 25, 1995), pp. 1-36.
Ferguson “Linear Programming—A Concise Introduction”, date unknown, pp. 1-50.
Freund et al., “A decision-theoretic generalization of on-line learning and an application to boosting”, AT&T Bell Laboratories, Sep. 20, 1995, pp. 1-34.
Freund et al., “Adaptive game playing using multiplicative weights”, Games and Economic Behavior, Nov. 20, 1997, pp. 1-19.
Greenberg “An Algorithm for Determining Redundant Inequalities and All solutions to Convex Polyhedra”, Numer. Math., vol. 24, 1975, pp. 19-26.
Hespanha “A Proof of the Minimax Theorem”, Apr. 14, 2003, pp. 1-2.
Karmarkar “A New Polynomial-Time Algorithm for Linear Programming” AT&T Bell Laboratories, ACM, 1984, pp. 302-311.
Li et al., “FloatBoost Learning for Classification”, Microsoft Research Asia, date unknown, 8 pages.
Markowitz “Portfolio Selection Efficient Diversification of Investments” Cowles Foundation for Research in Economics at Yale University, 1959, 356 pages.
Meir et al., “An Introduction to Boosting and Leveraging”, date unknown, pp. 119-184.
Ratsch et al., “Maximizing the Margin with Boosting”, J. Kivinen and R. H. Sloan (Eds.): COLT 2002, LNAI 2375, 2002, pp. 334-350.
Vanderbei “Linear Programming: Foundations and Extensions”, Robert J. Vanderbei, 2001, 466 pages.
Viola et al., “Robust Real-time Object Detection”, Secon International Wrokshop on Statistical and Computational Theories of Vision—Modeling, Learning, Computing, and Sampling, Vancouver, Canada, Jul. 13, 2001, pp. 1-25.
Morud “Studies on the Dynamics and Operation of Integrated Plants”, Thesis, University of Trondheim, Norway, Dec. 1995, 166 pages.
McGuigan et al., “Web Chapter B Linear-Programming Applications”, Managerial Economics: Applications, Strategy and Tactics, 2002, pp. 1-26.
McGuigan et al., “Web Chapter A Optimization Techniques”, Managerial Economics: Applications, Strategy and Tactics, 2002, pp. 1-27.
Chang Li-Wu
Dupray Dennis J.
Gaffin Jeffrey A
Sheridan & Ross P.C.
LandOfFree
Method for solving minimax and linear programming problems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for solving minimax and linear programming problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for solving minimax and linear programming problems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2771995