Technical Note—A General Inner Approximation Algorithm for Nonconvex Mathematical Programs

Abstract

Inner approximation algorithms have had two major roles in the mathematical programming literature. Their first role was in the construction of algorithms for the decomposition of large-scale mathematical programs, such as in the Dantzig-Wolfe decomposition principle. However, recently they have been used in the creation of algorithms that locate Kuhn-Tucker solutions to nonconvex programs. Avriel and Williams' (Avriel, M., A. C. Williams. 1970. Complementary geometric programming. SIAM J. Appl. Math. 19 125–141.) complementary geometric programming algorithm, Duffin and Peterson's (Duffin, R. J., E. L. Peterson. 1972. Reversed geometric programs treated by harmonic means. Indiana Univ. Math. J. 22 531–550.) reversed geometric programming algorithms, Reklaitis and Wilde’s (Reklaitis, G. V., D. J. Wilde. 1974. Geometric programming via a primal auxiliary problem. AIIE Trans. 6 308–317.) primal reversed geometric programming algorithm, and Bitran and Novaes' (Bitran, G. R., A. G. Novaes. 1973. Linear programming with a fractional objective function. Opns. Res. 21 22–29.) linear fractional programming algorithm are all examples of this class of inner approximation algorithms. A sequence of approximating convex programs are solved in each of these algorithms. Rosen's (Rosen, J. B. 1966. Iterative solution of nonlinear optimal control problems. SIAM J. Control 4 223–244.) inner approximation algorithm is a special case of the general inner approximation algorithm presented in this note.