Global optimization for bilevel programming problems and applications

This thesis explores developments at a fundamental level in the theory and application of bilevel optimization. The theory involves novel techniques that can solve the general nonlinear bilevel programming problem and several classes of the mixed-integer nonlinear bilevel programming problems. For the general nonlinear case, global optimality is guaranteed for problems that involve twice differentiable nonlinear functions provided that the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, αBB (Adjiman and Floudas. 1996; Adjiman et al., 1998a,b; Androulakis et al., 1995a). Epsilon global optimality in a finite number of iterations is theoretically guaranteed.; The fundamental theoretical developments introduced in the global solution of nonlinear bilevel optimization problems are used to formulate and solve important classes of chemical engineering problems. These are (i) feasibility and flexibility analysis of design under uncertainty, and (ii) azeotrope prediction simultaneously with parameter estimation.; The first application, design under uncertainty, involves feasibility and flexibility analysis measures, that are important for characterizing the operability of a chemical process. The competitive nature of the market environment enforces high reliability on meeting product requirements and quality specifications. However, uncertainties are inevitable due to the variability of process conditions, such as temperatures or flow rates, or are inherent in the model equations. A novel approach is presented for the evaluation of design feasibility/flexibility based on the ideas of the deterministic global optimization technique. A number of examples illustrate the applicability and efficiency of the proposed global optimization framework, for both the feasibility test and flexibility index problems.; The second important contribution is in azeotrope prediction with parameter estimation. The existence of azeotropes (homogeneous, heterogeneous, or reactive) can change the design, and thereby the cost and effectiveness of a process significantly, making the correct prediction of azeotropes a critical part of chemical engineering separation process design. Through the use of the global optimization technique, the fundamental way of modeling azeotropic systems under parametric uncertainty can be altered in such a way that enables more accurate prediction of azeotropes through simultaneous estimation of the parameters.; Finally, theoretical developments in the global optimization of several classes of mixed-integer nonlinear bilevel problems are introduced. Of the two methods presented, first is an improved branch-and-bound based enumeration method for integer BLPs. The second can solve classes where the outer level can involve general mixed-integer nonlinear functions. In the inner level, functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. The technique is based on reformulation of the mixed-integer inner problem as continuous via its convex hull representation (Sherali and Adams, 1990), and solving the resulting nonlinear bilevel optimization problem by the novel deterministic global optimization framework. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies are presented in each section.