Outer approximation method incorporating a quadratic approximation for a DC programming problem (Q848730)

The authors consider a DC programming problem, i.e., an optimization problem with a linear function to be minimized over a set defined by a convex set \(Y\) and the complement of the interior of a compact convex set \(X\). In the case where \(X\) is a polytope, a solution method using duality has been proposed [see, e.g., \textit{R. Horst} and \textit{P. M. Pardalos}, Handbook of global optimization. Dordrecht: Kluwer Academic Publishers (1995; Zbl 0805.00009); \textit{R. Horst} and \textit{H. Tuy}, Global optimization. Deterministic approaches. 3rd rev. a. enl. ed. Berlin: Springer (1996; Zbl 0867.90105); \textit{H. Konno, P. T. Thach} and \textit{H. Tuy}, Optimization on low rank nonconvex structures. Dordrecht: Kluwer Academic Publishers (1997; Zbl 0879.90171); \textit{H. Tuy}, Convex analysis and global optimization. Dordrecht: Kluwer Academic Publishers (1998; Zbl 0904.90156)]. An outer approximation method for a DC problem is proposed in the case where \(X\) is not a polytope. The algorithm utilizes outer approximation of \(Y \cap X\) by a sequence of polytopes. It is shown that every accumulation point of the sequence of the provisional solutions is an optimal solution of a DC problem. In order to calculate the provisional solutions on the feasible set as much as possible, the authors incorporate a quadratic approximation to the algorithm; that is, the search direction for a feasible solution is determined by analyzing the relation among eigenvectors of the Hessian matrices of the constraint functions. The organization of this paper is as follows. In Sect. 2, Problem (DC) is explained. In Sect. 3, an outer approximation algorithm for the Problem (DC) is formulated and the convergence of the algorithm is established. The difference of the objective function value between an approximate solution calculated by the proposed algorithm and the exact optimal solution is smaller than a tolerance selected at the initialization step. In Sect. 4, a descent method is incorporated in the algorithm proposed in Sect. 3. By incorporating a descent method, the procedure bounding the feasible set will be expedited. In Sect. 5, a quadratic programming problem is described to find a feasible solution of the Problem (DC). Moreover, another algorithm is formulated incorporating a procedure for solving such a quadratic programming problem. In Sect. 6, are described a numerical example and computational experiments of the algorithm proposed in Sect. 5.