Nonconvexities

C.D. Maranas, IP. Androulakis and C.A. Floudas, A deterministic global optimization approach for the protein folding problem, pp. 133-150 in Global minimization of nonconvex energy functions molecular conformation and protein folding (P. M. Pardalos et al., eds.), Amer. Math. Soc., Providence, RI, 1996. 

G. Ramachandran and T. Schlick. Beyond optimization Simulating the dynamics of supercoiled DNA by a macroscopic model. In P. M. Pardalos, D. Shal-loway, and G. Xue, editors. Global Minimization of Nonconvex Energy Functions Molecular Conformation and Protein Folding, volume 23 of DIM ACS Series in Discrete Mathematics and Theoretical Computer Science, pages 215-231, Providence, Rhode Island, 1996. American Mathematical Society. 

Vaidyanathan, R. and El-Halwagi, M. M. (1996). Global optimization of nonconvex MINLP s by interval analysis. In Global Optimization in Engineering Design, (I. E. Grossmann, ed.), pp. 175-194. Kluwer Academic Publishers, Dordrecht, The Netherlands. 

Visweswaran, V. and Floudas, C. A. (1990). A global optimization procedure for certain classes of nonconvex NLP s-II. application of theory and test problems. Comput. Chem. Eng, 14(2), 1419-1434. 

A more rigorous method of tackling nonconvex equilibrium without discretization has been developed by Srinivas and El-Halwagi (1994) and is beyond the scope of this book. 

Now consider the influence of the inequality constraints on the optimization problem. The effect of inequality constraints is to reduce the size of the solution space that must be searched. However, the way in which the constraints bound the feasible region is important. Figure 3.10 illustrates the concept of convex and nonconvex regions. 

The addition of inequality constraints complicates the optimization. These inequality constraints can form convex or nonconvex regions. If the region is nonconvex, then this means that the search can be attracted to a local optimum, even if the objective function is convex in the case of a minimization problem or concave in the case of a maximization problem. In the case that a set of inequality constraints is linear, the resulting region is always convex. 

Constraints (4.1), (4.2), (4.3), (4.4), (4.5) and (4.6) constitute a nonconvex nonlinear model due to constraints (4.3) and (4.4), which involve bilinear terms. Nonconvexity, and not necessarily nonlinearity, is a disadvantageous feature in any model, since global optimality cannot be guaranteed. Therefore, if can be avoided, it should. This is achieved by either linearizing the model or using convexification techniques where applicable. In this instance, the first option was proven possible as shown below. 

Constraints (4.10) still entails nonconvex bilinear terms comprising of a binary and a continuous variable. However, this type of bilinearity can be readily linearized exactly using Glover transformation (1975). Constraints (4.11), (4.12), (4.13), (4.14) and (4.15) together constitute a linearized form of constraints (4.10). In constraints (4.11), the first and the second bilinear terms from constraints (4.10) have been replaced by continuous variables Ti and T2, respectively. Ti is defined in constraints (4.12) and (4.13), and V2 in constraints (4.14) and (4.15). 

Scenario 4 Formulation for fixed water quantity with reusable water storage Constraints (4.18), (4.19), (4.3), (4.20), (4.16), (4.17), (4.21), (4.22), (4.23), (4.24), (4.25) and (4.26) together constitute a complete water reuse/recycle model for a situation in which the quantity of water in each water using operation is fixed. This is also a nonconvex MINLP for which exact linearization is not possible. 

As shown in Table 4.4, the model for scenario 2, which is a nonconvex MINLP, consists of 1195 constraints, 352 continuous and 70 binary variables. An average of 151 nodes were explored in the branch and bound algorithm over the 3 major iterations between the MILP master problem and NLP subproblems. The problem was solved in 2.48 CPU seconds with an objective value of 1.67 million. Whilst the product quantity is the same as in scenario 1, i.e. 850 t, the water requirement is only 185 t, which corresponds to 52.56% reduction in freshwater requirement. The water network to achieve this target is shown in Fig. 4.15. 

The foregoing constraints constitute the full heat storage model. With the exception of constraints (11.3)—(11.5), all the constraints are linear. Constraints (11.3)—(11.5) entail nonconvex bilinear terms which render the overall model a nonconvex MINLP. However, the type of bilinearity exhibited by these constraints can be readily removed without compromising the accuracy of the model using the so called Glover transformation, which has been used extensively in the foregoing chapters of this book. This is demonstrated underneath using constraints (11.3). 

As shown in Fig. 3-53, optimization problems that arise in chemical engineering can be classified in terms of continuous and discrete variables. For the former, nonlinear programming (NLP) problems form the most general case, and widely applied specializations include linear programming (LP) and quadratic programming (QP). An important distinction for NLP is whether the optimization problem is convex or nonconvex. The latter NLP problem may have multiple local optima, and an important question is whether a global solution is required for the NLP. Another important distinction is whether the problem is assumed to be differentiable or not. 

We consider first methods that find only local solutions to nonconvex problems, as more difficult (and expensive) search procedures are required to find a global solution. Local methods are currently very... 

Nonconvex polynomial terms can be replaced by a set of binary terms, with new variables introduced to define the higher-order polynomials. 

It fix) and g(x) are nonconvex, additional difficulties can occur. In this case, nonunique, local solutions can be obtained at intermediate nodes, and consequently lower bounding properties would be lost. In addition, the nonconvexity in g(x) can lead to locally infeasible problems at intermediate nodes, even if feasible solutions can be found in the corresponding leaf node. To overcome problems with nonconvexities, global solutions to relaxed NLPs can be solved at the intermediate nodes. This preserves the lower bounding information and allows nonlinear branch and bound to inherit the convergence properties from the linear case. However, as noted above, this leads to much more expensive solution strategies. 

Note, that this approximation is a second source of nonconvex nonlinear constraints. 

Both the mixing process and the approximation of the product profiles establish nonconvex nonlinearities. The inclusion of these nonlinearities in the model leads to a relatively precise determination of the product profiles but do not affect the feasibility of the production schedules. A linear representation of both equations will decrease the precision of the objective but it will also eliminate the nonlinearities yielding a mixed-integer linear programming model which is expected to be less expensive to solve. 

Often results obtained under assumptions of convexity can give insight into the properties of more general problems. Sometimes, such results may even be carried over to nonconvex problems, but in a weaker form. 

For example, it is usually impossible to prove that a given algorithm will find the global minimum of a nonlinear programming problem unless the problem is convex. For nonconvex problems, however, many such algorithms find at least a local minimum. Convexity thus plays a role much like that of linearity in the study of dynamic systems. For example, many results derived from linear theory are used in the design of nonlinear control systems. 

Table 9.1 shows how outer approximation, as implemented in the DICOPT software, performs when applied to the process selection model in Example 9.3. Note that this model does not satisfy the convexity assumptions because its equality constraints are nonlinear. Still DICOPT does find the optimal solution at iteration 3. Note, however, that the optimal MILP objective value at iteration 3 is 1.446, which is not an upper bound on the optimal MINLP value of 1.923 because the convexity conditions are violated. Hence the normal termination condition that the difference between upper and lower bounds be less than some tolerance cannot be used, and DICOPT may fail to find an optimal solution. Computational experience on nonconvex problems has shown that retaining the best feasible solution found thus far, and stopping when the objective value of the NLP subproblem fails to improve, often leads to an optimal solution. DICOPT stopped in this example because the NLP solution at iteration 4 is worse (lower) than that at iteration 3. 

Any problem containing discretely valued variables is nonconvex, and such problems may also be solved by the methods described in this chapter. The search methods discussed in Section 10.5 are often applied to supply chain and productionsequencing problems. 

The methods mentioned earlier are general-purpose procedures, applicable to almost any problem. Many specialized global optimization procedures exist for specific classes of nonconvex problems. See Pinter (1996a) for a brief review and further references. Typical problems are... 

---