Outer approximation primal problem

The Outer Approximation OA addresses problems with nonlinear inequalities, and creates sequences of upper and lower bounds as the GBD, but it has the distinct feature of using primal information, that is the solution of the upper bound problems, so as to linearize the objective and constraints around that point. The lower bounds in OA are based upon the accumulation of the linearized objective function and constraints, around the generated primal solution points. 

The basic idea in OA is similar to the one in GBD that is, at each iteration we generate an upper bound and a lower bound on the MINLP solution. The upper bound results from the solution of the problem which is problem (6.13) with fixed y variables (e.g., y = yk). The lower bound results from the solution of the master problem. The master problem is derived using primal information which consists of the solution point xk of the primal and is based upon an outer approximation (linearization) of the nonlinear objective and constraints around the primal solution xk. The solution of the master problem, in addition to the lower bound, provides information on the next set of fixed y variables (i.e., y = yt+ ) to be used in the next primal problem. As the iterations proceed, two sequences of updated upper bounds and lower bounds are generated which are shown to be nonincreasing and nondecreasing respectively. Then, it is shown that these two sequences converge within e in a finite number of iterations. 

Remark 2 The right-hand sides of the first three sets of constraints are the support functions that are represented as outer approximations (or linearizations) at the current solution point xk of the primal problem. If condition Cl is satisfied then these supports are valid underestimators and as a result the relaxed master problem provides a valid lower bound on the global solution of the MINLP problem. 

Remark 7 The constraints (6.48) define the set of y G Y D V, and hence we can now formulate the master problem correctly. Note that we replace the sety G Y n V with constraints (6.48) that are the outer approximations at the points yk for which the primal is infeasible and the feasibility problem (6.41) has as solution xk. 

Generalized Outer Approximation with Exact Penalty, GOA/EP 6.7.6.1 The Primal Problem... 

Section 6.4 discusses the Outer Approximation OA approach. Sections 6.4.1 and 6.4.2 present the formulation, conditions, and the basic idea of OA. Section 6.4.3 presents the development of the primal and master problem, as well as the geometrical interpretation of the master problem. Section 6.4.4 presents the OA algorithm and its finite e-convergence. 

Section 6.7 presents the Generalized Outer Approximation GOA approach. After a brief discussion on the problem formulation, the primal and master subproblem formulations are developed, and the GOA algorithm is stated in section 6.7.4. In Section 6.7.5, the worst case analysis of GOA is discussed, while in section 6.7.6 the Generalized Outer Approximation with exact Penalty GOA/EP and its finite convergence are discussed. 

---