Abstract
A constrained minimax problem is converted to minimization of a sequence of unconstrained and continuously differentiable functions in a manner similar to Morrison's method for constrained optimization. One can thus apply any efficient gradient minimization technique to do the unconstrained minimization at each step of the sequence. Based on this approach, two algorithms are proposed, where the first one is simpler to program, and the second one is faster in general. To show the efficiency of the algorithms even for unconstrained problems, examples are taken to compare the two algorithms with recent methods in the literature. It is found that the second algorithm converges faster with respect to the other methods. Several constrained examples are also tried and the results are presented.
Similar content being viewed by others
References
J.W. Bandler and T.V. Srinivasan, “Constrained minimax optimization by grazor search”,Proceedings of sixth Hawaii international conference on system sciences (1973) 125–128.
J.W. Bandler, T.V. Srinivasan and C. Charalambous, “Minimax optimization of networks by grazor search”,IEEE Transactions on Microwave Theory and Techniques, MTT-20 (1972) 596–604.
C. Charalambous and J.W. Bandler, “New Algorithms for network optimization”,IEEE Transactions on Microwave Theory and Techniques, MTT-21 (1973) 815–818.
C. Charalambous and A.R. Conn, “Optimization of microwave networks”,IEEE Transactions on Microwave Theory and Techniques, MTT-23 (1975) 834–838.
C. Charalambous, “A unified review of optimization”,IEEE Transactions on Microwave Theory and Techniques, MTT-22 (3) (March 1974).
O. Einarsson, “Minimax optimization by algorithms employing modified Lagrangians”,IEEE Transactions on Microwave Theory and Techniques MTT-23 (1975) 838–841.
R. Fletcher, “A new approach to variable metric algorithms”,The Computer Journal, 13 (Aug. 1970) 317–322.
J. Kowalik, M.R. Osborne and D.M. Ryan, “A new method for constrained optimization problems”,Operations Research 17 (1969) 973–983.
F.A. Lootsma, “A survey of methods for solving constrained minimization problems via unconstrained minimization”, in: F.A. Lootsma, ed.,Numerical methods for nonlinear optimization (Academic Press, New York, 1972).
K. Madsen, H. Schjaer-Jacobsen and J. Woldby, “Automated minimax design of networks”,IEEE Transactions on Circuits and Systems, CAS-22 (1975) 791–796.
K. Madsen, O. Nielsen, H. Schjaer-Jacobsen and L. Thrane, “Efficient minimax design of networks without using derivatives”,IEEE Transactions on Microwave Theory and Techniques MTT-23 (1975) 803–809.
D.D. Morrison, “Optimization by least-squares”,SIAM Journal on Numerical Analysis 5 (1) (1968) 83–88.
M.R. Osborne and G.A. Watson, “An algorithm for minimax approximation in the nonlinear case”,Computer Journal 12 (1968) 63–68.
G.C. Temes and D.A. Calahan, “Computer aided network optimization, the state-of-the-art”,Proceedings of IEEE 55 (11) (1967) 1832–1863.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dutta, S.R.K., Vidyasagar, M. New algorithms for constrained minimax optimization. Mathematical Programming 13, 140–155 (1977). https://doi.org/10.1007/BF01584333
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584333