Linearly constrained global optimization: a general solution algorithm with applications

摘要

This paper presents an efficient enumerative approach to solve general linearly constrained optimization problems. This class of optimization problems includes fractional, nonlinear network models, quadratic, convex and non-convex programs. The unified approach is accomplished by converting the constrained optimization problem to an unconstrained optimization problem through a parametric representation of its feasible region. The proposed solution algorithm consists of three phases. In phase 1 it finds all interior critical points. In phase 2 the parametric representation of the feasible region is constructed to identify any critical points on the edges and faces of the feasible region. This is done by a modified version of an algorithm for finding the V-representation of the polyhedron. Then, in phase 3, the global optimal value of the objective function is found by evaluating the objective function at the critical points as well as at the vertices. For an illustration of the algorithm and a comparison with the existing methods small-size numerical examples are presented.