Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A nearest point algorithm for convex polyhedral cones and applications to positive linear approximation


Author: Don R. Wilhelmsen
Journal: Math. Comp. 30 (1976), 48-57
MSC: Primary 52A25; Secondary 65D99
DOI: https://doi.org/10.1090/S0025-5718-1976-0394439-5
MathSciNet review: 0394439
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Suppose K is a convex polyhedral cone in $ {E_n}$ and is defined in terms of some generating set $ \{ {e_1},{e_2}, \ldots ,{e_N}\} $. A procedure is devised so that, given any point $ q \in {E_n}$, the nearest point p in K to q can be found as a positive linear sum of $ {N^\ast} \leqslant n$ points from the generating set. The procedure requires at most finitely many linear steps.

The algorithm is then applied to find a positive representation

$\displaystyle Lf = \sum\limits_{i = 1}^{{N^\ast}} {{\lambda _i}f({x_i}),} \quad {\lambda _i} > 0,f \in \Phi ,$

for a positive linear functional L acting on a suitable finite-dimensional function space $ \Phi $.

References [Enhancements On Off] (What's this?)

  • [1] P. J. DAVIS, "A construction of nonnegative approximate quadratures," Math. Comp., v. 21, 1967, pp. 578-582. MR 36 #5584. MR 0222534 (36:5584)
  • [2] P. J. DAVIS, Interpolation and Approximation, Blaisdell, New York, 1963. MR 28 #393. MR 0157156 (28:393)
  • [3] A. H. STROUD, Approximate Calculation of Multiple Integrals, Prentice-Hall Ser. in Automatic Computation, Prentice-Hall, Englewood Cliffs, N. J., 1971. MR 48 #5348. MR 0327006 (48:5348)
  • [4] V. TCHAKALOFF, "Formules de cubatures mécaniques à coefficients non-négatifs," Bull. Sci. Math. (2), v. 81, 1957, pp. 123-134. MR 20 #1145. MR 0094632 (20:1145)
  • [5] D. R. WILHELMSEN, "Nonnegative cubature on convex sets," SIAM J. Numer. Anal., v. 11, 1974, pp. 332-346. MR 0347062 (49:11782)
  • [6] M. W. WILSON, "A general algorithm for nonnegative quadrature formulas," Math. Comp., V. 23, 1969, pp. 253-258. MR 39 #3705. MR 0242374 (39:3705)
  • [7] M. W. WILSON, "Necessary and sufficient conditions for equidistant quadrature formula," SIAM J. Numer. Anal., v. 7, 1970, pp. 134-141. MR 43 #8241. MR 0282530 (43:8241)
  • [8] P. WOLF, "Finding the nearest point in a polytope," Math. Programming.(To appear.) MR 0452683 (56:10962)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 52A25, 65D99

Retrieve articles in all journals with MSC: 52A25, 65D99


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1976-0394439-5
Keywords: Convex set, nearest point, projection, positive linear approximation, linear algorithm, cubature
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society