×

A cutting plane method for solving minimax problems in the complex plane. (English) Zbl 0756.65092

The author’s recent discretization and cutting plane method for general convex semi-infinite programming problems is implemented for the solution of a minimax problem in the complex plane; the problem need not be linearized. The method is illustrated on several examples.
Reviewer: J.Rohn (Praha)

MSC:

65K05 Numerical mathematical programming methods
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
90C34 Semi-infinite programming
30E10 Approximation in the complex plane

Software:

CAPROX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Barrodale, Best approximation of complex-valued data, in:Numerical Analysis, ed. G.A. Watson (Springer, Berlin/Heidelberger/New York, 1978) pp. 14–22. · Zbl 0385.41019
[2] I. Barrodale, L.M. Delves and J.C. Mason, Linear Chebyshev approximation of complex-valued functions, Math. Comp. 32 (1978) 853–863. · Zbl 0381.65007 · doi:10.1090/S0025-5718-1978-0483298-X
[3] H.-P. Blatt, U. Kaiser and B. Ruffer-Beedgen, A multiple exchange algorithm in convex programming, in:Optimization: Theory and Applications, eds. J.-B. Hiriart-Urruty, W. Oettli and J. Stoer, Lecture Notes in Pure and Applied Mathematics, vol. 86 (Marcel Dekker, New York/Basel, 1983) pp. 113–130. · Zbl 0526.49025
[4] E.W. Cheney,Introduction to Approximation Theory, 2nd ed. (Chelsea, New York, 1986). · Zbl 0606.41001
[5] E.W. Cheney and A.A. Goldstein, Newton’s method for convex programming and Tchebycheff approximation, Numer. Math. 1 (1959) 253–268. · Zbl 0113.10703 · doi:10.1007/BF01386389
[6] C.B. Dunham and J. Williams, Rate of convergence of discretization in Chebyshev approximation, Math. Comp. 37 (1981) 135–139. · Zbl 0469.41021 · doi:10.1090/S0025-5718-1981-0616366-X
[7] S.W. Ellacott and J. Williams, Linear Chebyshev approximation in the complex plane using Lawson’s algorithm, Math. Comp. 30 (1976) 35–44. · Zbl 0337.65011
[8] K. Glashoff and K. Roleff, A new method for Chebyshev approximation of complex-valued functions, Math. Comp. 36 (1981) 233–239. · Zbl 0462.30026 · doi:10.1090/S0025-5718-1981-0595055-4
[9] D. Goldfarb and A. Idnani, A numerically stable dual method for solving strictly convex quadratic programs, Math. Progr. 27 (1983) 1–33. · Zbl 0537.90081 · doi:10.1007/BF02591962
[10] G.M. Gramlich, SQP-Methoden für semiinfinite Optimierungsprobleme, Ph.D. Thesis, Fachbereich Mathematik, Universität Trier (April 1990). · Zbl 0743.90104
[11] U. Grothkopf and G. Opfer, Complex Chebyshev polynomials on circular sectors with degree six or less, Math. Comp. 39 (1982) 599–615. · Zbl 0496.65002 · doi:10.1090/S0025-5718-1982-0669652-2
[12] M.H. Gutknecht, Ein Abstiegsverfahren für gleichmässige Approximation, mit Anwendungen, Ph.D. Thesis, Eidgenössische Technische Hochschule Zürich (1973). · Zbl 0277.65004
[13] M.H. Gutknecht, Ein Abstiegsverfahren für nicht-diskrete Tschebyscheff-Approximationsprobleme, in:Numerische Methoden der Approximationstheorie, vol. 4, eds. L. Collatz, G. Meinardus and H. Werner (Birkhäuser, 1978) pp. 154–171.
[14] M.H. Gutknecht, Non-strong uniqueness in real and complex Chebyshev approximation, J. Approx. Theory 23 (1978) 204–213. · Zbl 0447.41016 · doi:10.1016/0021-9045(78)90110-7
[15] M. Hartmann and G. Opfer, Uniform approximation as a numerical tool for constructing conformal maps, J. Comput. Appl. Math. 14 (1986) 193–206. · Zbl 0587.30008 · doi:10.1016/0377-0427(86)90138-X
[16] R. Hettich, An implementation of a discretization method for semi-infinite programming, Math. Progr. 34 (1986) 354–361. · Zbl 0592.90061 · doi:10.1007/BF01582235
[17] R. Hettich and P. Zencke,Numerische Methoden der Approximation und semi-infiniten Optimierung, (B. G. Teubner, Stuttgart, 1982). · Zbl 0481.65033
[18] V. Klotz, Polynomiale und rationale Tschebyscheff-Approximation in der komplexen Ebene, Ph. D. Thesis, Friedrich-Alexander-Universität, Erlangen-Nürnberg (1974).
[19] K.O. Kortanek and Hoon No, A central cutting plane algorithm for convex semi-infinite programming problems, Working Paper Series No. 90-08, College of Business Administration, The University of Iowa, Iowa City, Iowa (revised February 1992).
[20] W. Krabs and G. Opfer, Eine Methode zur Lösung des komplexen Approximationsproblems mit einer Anwendung auf konforme Abbildungen. ZAMM 55 (1975) T208-T211. · Zbl 0302.65008
[21] B.R. Kripke, Best approximation with respect to nearby norms, Numer. Math. 6 (1964) 103–105. · Zbl 0128.34302 · doi:10.1007/BF01386060
[22] P.J. Laurent and C. Carasso, An algorithm of successive minimization in convex programming, R.A.I.R.O., Analyse numérique, Numer. Anal. 12 (1978) 377–400. · Zbl 0402.90075
[23] O.L. Mangasarian and R.R. Meyer, Nonlinear perturbation of linear programs, SIAM J. Control Optim. 17 (1979) 745–752. · Zbl 0432.90047 · doi:10.1137/0317052
[24] J.C. Mason and G. Opfer, An algorithm for complex polynomial approximation with nonlinear constraints, in:Approximation Theory V, eds. C.K. Chu, L. Schumaker and J. Ward (Academic Press, New York, 1986) pp. 471–474. · Zbl 0611.65008
[25] J.C. Mason and P. Owen, Some simple algorithms for constrained complex and rational approximation, in:Algorithms for Approximation, eds. J.C. Mason and M.G. Cox (Clarendon Press, 1987) pp. 357–369. · Zbl 0614.65009
[26] J.C. Mason and S.J. Wilde, Constrained complex approximation algorithms in communication engineering, in:Algorithms for Approximation II, eds. J.C. Mason and M.G. Cox (Chapman and Hill, London/New York, 1990) pp. 424–448. · Zbl 0746.41011
[27] J.C. Mason and S.J. Wilde, A complex minimax algorithm for phase-only adaptation in antenna arrays, in:Algorithms for Approximation II, eds. J.C. Mason, and M.G. Cox (Chapman and Hill, London/New York, 1990) pp. 466–475.
[28] J.C. Mason, S.J. Wilde and G. Opfer, Constrained minimax and least squares problems in antenna array pattern synthesis, Technical Note COMAG 1/87, Royal Military College of Science, Computational Mathematics Group, Shrivenham, Swindon, Wiltshire, England (1987).
[29] G. Meinardus,Approximation of Functions: Theory and Numerical Methods (Springer, Berlin/Heidelberg/New York, 1967). · Zbl 0152.15202
[30] G. Opfer, An algorithm for the construction of best approximations based on Kolmogorov’s criterion, J. Approx. Theory 23 (1978) 299–317. · Zbl 0417.41012 · doi:10.1016/0021-9045(78)90082-5
[31] G. Opfer, New extremal properties for constructing conformal mappings, Numer. Math. 32 (1979) 423–429. · Zbl 0432.30007 · doi:10.1007/BF01401045
[32] G. Opfer, Conformal mappings onto prescribed regions via optimization techniques, Numer. Math. 35 (1980) 189–200. · Zbl 0417.30012 · doi:10.1007/BF01396315
[33] G. Opfer, Solving complex approximation problems by semiinfinite-finite optimization techniques: a study on convergence, Numer. Math. 39 (1982) 411–420. · Zbl 0517.65005 · doi:10.1007/BF01407872
[34] G. Opfer, Anwendung komplexer Approximation auf die Lösung linearer Gleichungssysteme mit der Richardson-Iteration, ZAMM 63 (1983) T367-T369. · Zbl 0531.65016
[35] G. Opfer, Numerische Behandlung komplexer Approximationsaufgaben, Nova Acta Leopoldina NF 61, 267 (1989) 75–80. · Zbl 0701.65049
[36] P.R. Owen and J.C. Mason, The use of linear programming in the design of antenna patterns with prescribed nulls and other constraints, Int. J. Comp. Math. in EEE 3 (1984) 201–215. · Zbl 0623.90088
[37] T.W. Parks and C.S. Burrus,Digital Filter Design (Wiley, New York, 1987). · Zbl 0632.93001
[38] A. Potchinkov and R. Reemtsen, The design of FIR filters in the complex domain by a semi-infinite programming technique, Preprint, Technische Universität Berlin (April 1992). · Zbl 0875.93531
[39] R. Reemtsen, Discretization methods for the solution of semi-infinite programming problems, J. Optim. Theory Appl. 71 (1991) 85–103. · Zbl 0793.90088 · doi:10.1007/BF00940041
[40] R. Reemtsen, Outer approximation methods for semi-infinite optimization problems, Preprint No. 280/1991, Fachbereich Mathematik, TU Berlin, 1000 Berlin 12 (1991).
[41] R. Schultz, Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen, Ph.D. Thesis, Universität Hamburg, Hamburg (1977). · Zbl 0413.65010
[42] M.S. Sherrill and R.L. Streit, In situ optimal reshading of arrays with failed elements, IEEE. J. Oceanic Eng. 12 (1987) 155–162. · doi:10.1109/JOE.1987.1145245
[43] C. Spagl, Charakterisierung und Numerik in der linearen komplexen Tschebyscheff-Approximation, Ph.D. Thesis, Mathematisch-Geographische Fakultät, Katholische Universität Eichstätt (1988). · Zbl 0709.41024
[44] R.L. Streit, Algorithm 635. An algorithm for the solution of systems of complex linear equations in the Lnorm with constraints on the unknowns, ACM Trans. Math. Software 11 (1985) 242–249. · Zbl 0612.65022 · doi:10.1145/214408.214415
[45] R.L. Streit, Saddle points and overdetermined complex equations, Lin. Alg. Appl. 64 (1985) 57–76. · Zbl 0559.41020 · doi:10.1016/0024-3795(85)90266-6
[46] R.L. Streit, Solution of systems of complex linear equations in the lnorm with constraints on the unknowns, SIAM J. Sci. Stat. Comput. 7 (1986) 132–149. · Zbl 0612.65021 · doi:10.1137/0907010
[47] R.L. Streit and A.H. Nuttall, A general Chebyshev complex function approximation procedure and an application to beamforming, J. Acoust. Soc. Amer. 72 (1982) 181–190. · Zbl 0492.65009 · doi:10.1121/1.388002
[48] R.L. Streit and A.H. Nuttall, A note on the semi-infinite programming approach to complex approximation, Math. Comp. 40 (1983) 599–605. · Zbl 0518.65013 · doi:10.1090/S0025-5718-1983-0689476-0
[49] P.T.P. Tang, Chebyshev approximation on the complex plane, Ph.D. thesis, Department of Mathematics, University of California at Berkeley (May 1987).
[50] P.T.P. Tang, A fast algorithm for linear complex Chebyshev approximations, Math. Comp. 51 (1988) 721–739. · Zbl 0699.65009 · doi:10.1090/S0025-5718-1988-0935074-5
[51] P.T.P. Tang, A fast algorithm for linear complex Chebyshev approximation, in:Algorithms for Approximation II, eds. J.C. Mason and M.G. Cox (Chapman and Hill, London/New York, 1990) pp. 265–273. · Zbl 0746.41028
[52] L.N. Trefethen, Near circularity of the error curve in complex Chebyshev approximation, J. Approx. Theory 31 (1981) 344–366. · Zbl 0462.41004 · doi:10.1016/0021-9045(81)90102-7
[53] L.N. Trefethen, Rational Chebyshev approximation on the unit disk, Numer. Math. 37 (1981) 297–320. · Zbl 0443.30046 · doi:10.1007/BF01398258
[54] G.A. Watson, A method for the Chebyshev solution of an overdetermined system of complex linear equations, IMA J. Numer. Anal. 8 (1988) 461–471. · Zbl 0677.65038 · doi:10.1093/imanum/8.4.461
[55] G.A. Watson, Numerical methods for Chebyshev approximation of complex-valued functions, in:Algorithms for approximation II, eds. J.C. Mason and M.G. Cox (Chapman and Hill, London/New York, 1990) pp. 246–264. · Zbl 0747.41026
[56] J. Williams, Numerical Chebyshev approximation in the complex plane, SIAM J. Numer. Anal. 9 (1972) 638–649. · Zbl 0258.65013 · doi:10.1137/0709053
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.