Corrected sequential linear programming for sparse minimax optimization. (English) Zbl 0813.65090

An algorithm to solve the large scale nonlinear minimax problem is presented. The proposed method is first-order: Hessian matrices are not calculated. A key feature of the proposed algorithm is the use of a “corrected” or “vertical” step. A global convergence result is presented; a small collection of computational experiments and comparisons is discussed. Finally, the authors point out that nonlinear inequality constrained optimization problems can be phrased as nonlinear minimax problems. Therefore, this proposed algorithm can be used in this general setting as well.


65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
Full Text: DOI


[1] M. Arioli, I. S. Duff, and P. P. M. de Rijk,On the augmented system approach to sparse least-squares problems, Numer. Math., 55 (1989), pp. 667–684. · Zbl 0678.65024
[2] J. W. Bandler and S. H. Chen,Circuit optimization: the state of the art, IEEE Trans. Microwave Theory Tech., 36 (1988), pp. 424–443.
[3] A. Ben-Tal, and M. P. Bendsøe,A new method for optimal truss topology design, MAT-report no. 1991–08, Mathematical Institute, The Technical University of Denmark, 2800 Lyngby, Denmark, 1991.
[4] I. Bongartz, A. R. Conn, N. Gould, and Ph. L. Toint,CUTE: Constrained and unconstrained testing environment, Tech. report TR/PA/93/10, CERFACS, 42 Avenue Gustave Coriolis, 31057 Toulouse Cedex, France, 1993. · Zbl 0886.65058
[5] K. K. Chan and P. D. Patel,Optimization of contoured beams for satellite antennas, IEE Proc.-H, Microwaves, Antennas and Propagation, 132 (1985), pp. 400–406.
[6] F. H. Clarke,Optimization and Nonsmooth Analysis, J. Wiley & Sons, New York, 1983. · Zbl 0582.49001
[7] A. R. Conn, N. I. M. Gould and Ph. L. Toint,LANCELOT: A Fortran Package for Large Scale Nonlinear Optimization (Release A), Springer Series in Computational Mathematics 17, Springer Verlag, Berlin, 1992. · Zbl 0761.90087
[8] A. R. Conn and Yuying Li,An efficient algorithm for nonlinear minimax problems, report CS-88-41, University of Waterloo, Ontario, Canada, 1989.
[9] I. S. Duff and J. K. Reid,A comparison of some methods for the solution of sparse overdetermined systems of linear equation, J. Inst. Math. Applics., 17 (1976), pp. 267–280. · Zbl 0329.65026
[10] I. S. Duff and J. K. Reid,The multifrontal solution of indefinite sparse symmetric linear equations, ACM Trans. Math. Software, 9 (1983), pp. 302–323. · Zbl 0515.65022
[11] R. Fletcher,A model algorithm for composite nondifferentiable optimization problems, Math. Programming Study, 17 (1982), pp. 67–76. · Zbl 0478.90063
[12] R. Fletcher,Practical Methods of Optimization (2nd ed, J. Wiley & Sons, New York, 1987. · Zbl 0905.65002
[13] R. Fletcher,A first derivative method for nonlinear programming based on successive l 1 LP, in New Methods in Optimization and their Industrial Uses. State of the Art, Perspectives (ed. J.-P. Penot), Int. Ser. of Num. Math. 87, Birkhäuser Verlag, Basel, 1989, pp. 43–56.
[14] R. Fletcher,Resolving degeneracy in quadratic programming, Report NA/135, Dept. of Mathematical Sciences, University of Dundee, Dundee DD1 4HN, Scotland, 1991, Annals of Oper. Res., to appear. · Zbl 0796.90042
[15] R. Fletcher and E. Sainz de la Maza,Nonlinear programming and nonsmooth optimization by successive linear programming, Math. Programming, 43 (1989), pp. 235–256. · Zbl 0724.90062
[16] A. Griewank and Ph. L. Toint,Partitioned variable metric updates for large structured optimization problems, Numer. Math., 39 (1982), pp. 119–137. · Zbl 0482.65035
[17] J. Hald,MMLA1Q, a FORTRAN subroutine for linearly constrained minimax optimization, Report NI-81-01, Inst. for Num. Anal., Technical University of Denmark, 2800 Lyngby, Denmark, 1981.
[18] J. Hald and K. Madsen,Combined LP and quasi-Newton methods for minimax optimization, Math. Programming, 20 (1981), pp. 49–62. · Zbl 0441.90097
[19] S. P. Han,Variable metric methods for minimizing a class of nondifferentiable functions, Math Programming, 20 (1981), pp. 1–13. · Zbl 0441.90095
[20] W. Hock and K. Schittkowski,Test Examples for Nonlinear Programming Codes, Lecture Notes in Econ. and Math. Syst. 187, Springer Verlag, Berlin, 1981. · Zbl 0452.90038
[21] K. Jónasson,Minimax optimization using sequential linear programming with minimum norm corrective steps, Report NI-92-01, Inst. for Num. Anal., Technical University of Denmark, 2800 Lyngby, Denmark, 1992.
[22] K. Jónasson and K. Madsen,Corrected sequential linear programming for sparse minimax optimization, Report NI-92-06, Inst. for Num. Anal., Technical University of Denmark, 2800 Lyngby, Denmark, 1992. · Zbl 0813.65090
[23] K. Madsen,An algorithm for minimax solution of over-determined systems of nonlinear equations, J. Inst. Math. Applics., 16 (1975), pp. 321–328. · Zbl 0355.65038
[24] K. Madsen,Minimization of Non-linear Approximation Functions, Dr. Techn. thesis, Technical University of Denmark, 2800 Lyngby, Denmark, 1986.
[25] K. Madsen, O. Tingleff, P. C. Hansen, and W. Owczarz,Robust subroutines for non-linear optimization, Rep. NI-90-06, Inst. for Num. Anal., Technical University of Denmark, 2800 Lyngby, Denmark, 1990.
[26] K. Madsen and H. Schjær-Jacobsen,Linearly constrained mini-max optimization, Math. Programming, 14 (1978), pp. 208–223. · Zbl 0375.65034
[27] D. Q. Mayne,On the use of exact penalty functions to determine step length in optimization algorithms, in Numerical Analysis, Dundee 1979 (ed. G. A. Watson), Lecture Notes in Mathematics 773, Springer Verlag, Berlin, 1980.
[28] W. Murray and M. L. Overton,A projected Lagrangian algorithm for nonlinear minimax optimization, SIAM J. Sci. Statist. Comput., 1 (1980), pp. 345–370. · Zbl 0461.65052
[29] R. H. Nickel and J. W. Tolle,A sparse sequential quadratic programming algorithm, J. Optim. Theory Appl., 60, no. 3 (1989), pp. 453–473. · Zbl 0632.90053
[30] A. Potchinkov and R. Reemtsen,The design of FIR filters in the complex domain by a semiinfinite optimization technique, Reports no. 327/1992 and 328/1992, Technische Universität Berlin, Berlin, 1992. · Zbl 0875.93531
[31] J. M. Ortega and W. C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. · Zbl 0241.65046
[32] G. A. Watson,The minimax solution of an overdetermined system of non-linear equations, J. Inst. Math. Applics., 23 (1979), pp. 167–180. · Zbl 0406.65025
[33] J. Zhang, N. Kim, and L. Lasdon,An improved successive linear programming algorithm, Management Sci., 31 no. 10 (1985), pp. 1312–1331. · Zbl 0601.90128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.