Abstract
We consider unconstrained minimax problem where the objective function is the maximum of a finite number of smooth convex functions. We present an iterative method to compute the optimal solution for the unconstrained convex finite minimax problem. The algorithm developed estimates the direction of steepest-descent rapidly and using Armijo’s condition proceeds towards the solution. Owing to the highly parallel nature of the algorithm, it is highly suitable for large minimax problems. Algorithm is implemented on Nvidia Tesla C1060 graphics card using CUDA and numerical comparisons with RGA & CFSQP are presented.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Xu, S.: Smoothing Method for Minimax Problems. Computational Optimization and Applications 20, 267–279 (2001)
Parpas, P., Rustem, B.: An Algorithm for the Global Optimization of a Class of Continuous Minimax Problems. Journal of Optimization Theory and Applications 141, 461–473 (2009)
Pillo, G.D., Grippo, L., Lucidi, S.: A Smooth Method for the Finite Minimax Problem. Math. Program. 60, 187–214 (1993)
Rustem, B., Zakovic, S., Parpas, P.: An Interior Point Algorithm for Continuous Minimax. Journal of Optimization Theory and Applications 136, 87–103 (2008)
Polak, E., Womersley, R.S., Yin, H.X.: An Algorithm Based on Active Sets and Smoothing for Discretized Semi-Infinite Minimax Problems. Journal of Optimization Theory and Applications 138, 311–328 (2008)
Sun, W.: Non-Monotone Trust Region Method for Solving Optimization Problem. Applied Mathematics and Computation 156, 159–174 (2004)
Charalamous, C., Conn, A.: An Efficient Method to Solve the Minimax Problem Directly. SIAM J. Numer. Anal. 15, 162–187 (1978)
Chen, R.: Solution of Minimax Problem using Equivalent Differentiable Functions. Comp. and Maths. with Appls. 11, 1165–1169 (1985)
Gaudioso, M., Monaco, M.F.: A Bundle Type Approach to the Unconstrained Minimization of Convex Non-Smooth Functions. Mathematical Programming 23, 216–226 (1982)
Zhua, Z., Cai, X., Jian, J.: An Improved SQP Algorithm for Solving Minimax Problems. Applied Mathematical Letters 22, 464–469 (2009)
Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. Springer, Heidelberg (1996)
Vardi, A.: New Minimax Algorithm. Journal of Optimization Theory and Applications (1992)
Wang, F., Zhang, K.: A Hybrid Algorithm for Nonlinear Minimax Problems. Annals of Operation Research (2008)
Goldberg, D.E.: Genetic Algorithms for Search, Optimization, and Machine Learning. Addison-Wesley, Reading (1989)
Deb, K., et al.: A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization. Evol. Comput. 10(4), 371–395 (2002)
Hansen, N., Muller, S., Koumoutsakos, P.: Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation 11(1), 1–18 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arora, R., Upadhyay, U., Tulshyan, R., Dutta, J. (2010). A Parallel Algorithm for Solving Large Convex Minimax Problems. In: Deb, K., et al. Simulated Evolution and Learning. SEAL 2010. Lecture Notes in Computer Science, vol 6457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17298-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-17298-4_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17297-7
Online ISBN: 978-3-642-17298-4
eBook Packages: Computer ScienceComputer Science (R0)