This paper presents a new practical approach to complex Chebyshev approximation by semi-infinite linear programming. The approximation problem may be general with arbitrary complex basis functions. By the new front-end technique, the associated semi-infinite linear programming problem is solved exploiting the finiteness of the related Lagrange multipliers by adapting finite--dimensional linear programming to the dual semi--infinite problem, and thereby taking advantage of the numerical stability and efficiency of conventional linear programming software packages. Furthermore, the optimization procedure is simple to describe theoretically and straightforward to implement in computer coding. The new design technique is therefore highly accessible. The new algorithm is formally introduced as the linear Dual Nested Complex Approximation (DNCA) algorithm. The DNCA algorithm is versatile and can be applied to a variety of applications such as narrow-band as well as broad-band beamformers with any geometry, conventional Finite Impulse Response (FIR) filters, analog and digital Laguerre networks, and digital FIR equalizers. The proposed optimization technique is applied to several numerical examples dealing with the design of a narrow-band base-station antenna array for mobile communication. The flexibility and numerical efficiency of the proposed design technique are illustrated with these examples where hundreds of antenna elements are optimized without numerical difficulties.