A nonlinear simplex algorithm for minimum order solutions

A nonlinear simplex algorithm is developed for solving a special class of linearly constrained optimization problems. The cost for this class of problem is a sequence of functionals indexed by the positive integers P such that for P=1 the problem reduces to a standard linear programming problem and for P→∞ the cost function selects the solution with the minimum number of nonzero elements in the solution vector. Two theorems, analogous to the fundamental theorem of linear programming, are given as the basis for the nonlinear simplex algorithm. Applications of this technique are discussed for system design and signal processing problems in which an optimally sparse solution vector is desired. Examples of such problems include FIR filter design, placement of beamformer arrays and seismic deconvolution