Sandwich approximation of univariate convex functions with an application to separable convex programming. (English) Zbl 0755.90066
An algorithm is developed which gives an approximation to a convex function of one variable defined on a bounded interval from above and below with piecewise linear convex functions within a given accuracy. The given function is required to be continuous at the endpoints and the one- sided derivatives should be finite at the endpoints.
For updating it is required that a value of the function and its left and right derivative can be computed at one (but arbitrary) point at a time. The error term decreases quadratically with the number of iterations. The proofs presented are combinatorial in nature. The algorithm is applied to the approximation of separable convex programs.
For updating it is required that a value of the function and its left and right derivative can be computed at one (but arbitrary) point at a time. The error term decreases quadratically with the number of iterations. The proofs presented are combinatorial in nature. The algorithm is applied to the approximation of separable convex programs.
Reviewer: T.B.Andersen (Aarhus)
MSC:
| 90C25 | Convex programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
References:
| [1] | Aneja, ”Bicriteria Transportation Problem,”, Management Science 25 pp 73– (1979) · Zbl 0442.90056 · doi:10.1287/mnsc.25.1.73 |
| [2] | Bazaraa, Nonlinear Programming. Theory and Algorithms (1979) |
| [3] | Burkard, ”Approximation of Convex Functions and Applications in Mathematical Programming” (1987) |
| [4] | Cox, ”An Algorithm for Approxmating Convex Functions by Means of First Degree Splines,”, The Computer Journal 14 pp 272– (1971) · Zbl 0225.65016 · doi:10.1093/comjnl/14.3.272 |
| [5] | Dembo, ”A Scaled Reduced Gradient Algorithm for Network Flow Problems with Convex Separable Costs,”, Mathematical Programming Study 15 pp 125– (1981) · Zbl 0477.90025 · doi:10.1007/BFb0120941 |
| [6] | Fruhwirth, ”Approximation of Convex Curves with Application to the Bicriteria Minimum Cost Flow Problem,”, European Journal of Operational Research 42 pp 326– (1989) · Zbl 0684.65069 · doi:10.1016/0377-2217(89)90443-8 |
| [7] | Geoffrion, ”Objective Function Approximation in Mathematical Programming,”, Mathematical Programming 13 pp 23– (1977) · Zbl 0356.90062 · doi:10.1007/BF01584321 |
| [8] | Gruber, Convexity and its Applications pp 131– (1983) · doi:10.1007/978-3-0348-5858-8_7 |
| [9] | Kamesam, ”Multipoint Methods for Separable Nonlinear Networks,”, Mathematical Programming Study 22 pp 185– (1984) · Zbl 0553.90037 · doi:10.1007/BFb0121016 |
| [10] | Kao, ”Secant Approximation Methods for Convex Optimization,”, Mathematical Programming Study 14 pp 143– (1981) · Zbl 0449.90081 · doi:10.1007/BFb0120926 |
| [11] | Kurozumi, ”Polygonal Approximation by the Minimax Method,”, Computer Graphics and Image Processing 19 pp 248– (1982) · Zbl 0534.65096 · doi:10.1016/0146-664X(82)90011-9 |
| [12] | Meyer, ”Computational Aspects of Two-Segment Separable Programming,”, Mathematical Programming 26 pp 21– (1983) · Zbl 0516.90058 · doi:10.1007/BF02591890 |
| [13] | Phillips, ”Algorithms for Piecewise Straightline Approximations,”, The Computuer Journal 11 pp 211– (1968) · doi:10.1093/comjnl/11.2.211 |
| [14] | Rockafellar, Network Flows and Monotropic Optimization (1984) · Zbl 0596.90055 |
| [15] | Rote , G. ”The Convergence Rate of the Sandwich Algorithm for approximating Convex Figures in the Plane (extended abstract),” Proceedings of the Second Canadian Conference in Computational Geometry, Ottawa, August 6-10 1990 287 290 |
| [16] | Rote , G. ”The Convergence Rate of the Sandwich Algorithm for Approximating Convex Functions,” Technische Universität Graz · Zbl 0787.65006 |
| [17] | Salem, ”Optimal Linear Approximation in Project Compression,”, IEEE Transactions 16 pp 339– (1984) · doi:10.1080/07408178408975253 |
| [18] | Sonnevend, ”An Optimal Sequential Algorithm for the Uniform Approximation of Convex Functions on [0, 1]2”, Appl. Math. Optimization 10 pp 127– (1983) · Zbl 0527.65010 · doi:10.1007/BF01448382 |
| [19] | Sonnevend, ”Sequential Algorithms of Optimal Order Global Error for the Uniform Recovery of Functions with Monotone (r-1) Derivatives,”, Analysis Mathematica 10 pp 311– (1984) · Zbl 0577.65002 · doi:10.1007/BF01904781 |
| [20] | Thakur, ”Error analysis for Convex Separable Programs,”, SIAM Journal of Applied Mathematics 34 pp 704– (1978) · Zbl 0379.90084 · doi:10.1137/0134059 |
| [21] | Thakur, ”Error Analysis for Convex Separable Programs: The Bounds on the Optimal Solution and the Dual Optimal Solution,”, Journal of Mathematical Analysis and Applications 74 pp 486– (1980) · Zbl 0463.65043 · doi:10.1016/0022-247X(80)90096-7 |
| [22] | Thakur, ”Successive Approximation in Separable Programming: An Improved Procedure for Convex Separable Programs,”, Naval Research Logistics Quarterly 33 pp 325– (1986) · Zbl 0596.90074 · doi:10.1002/nav.3800330213 |
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.
