Outer approximation method incorporating a quadratic approximation for a DC programming problem
type: Item
instance of: scholarly article
title: Outer approximation method incorporating a quadratic approximation for a DC programming problem
zbMATH Open document ID: 1201.90188
author: N. E. Zubov
published in: Journal of Optimization Theory and Applications
publication date: 2010-03-05T00:00:00Z
review text: 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 inc…
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 5677803
zbMATH Keywords: DC programming problem
zbMATH Keywords: outer approximation method
zbMATH Keywords: descent method
zbMATH Keywords: quadratic approximation
reviewed by: Oleg A. Shcherbina
MaRDI profile type: Publication
full work available at URL: s10957-009-9590-8
OpenAlex ID: W2026721724
cites work: Handbook of global optimization
cites work: Q4889854
cites work: Optimization on low rank nonconvex structures
cites work: Convex analysis and global optimization
cites work: Newton's method for convex programming and Tschebyscheff approximation
cites work: Introduction to global optimization
cites work: Recent developments and trends in global optimization
cites work: An outer approximation method for globally minimizing a concave function over a compact convex set
cites work: Convex Analysis
cites work: Nonlinear Programming
DOI: 10.1007/S10957-009-9590-8
Recommended article: Q4581828
Recommended article: Q3007196
Recommended article: On solving a d.c. programming problem by a sequence of linear programs
Recommended article: Q3004785
Recommended article: Numerical solution for optimization over the efficient set by d.c. optimization algorithms
Recommended article: A method for solving d.c. programming problems. Application to fuel mixture nonconvex optimization problem
Recommended article: A finite algorithm for a particular D.C. quadratic programming problem
Recommended article: Q3798482
Recommended article: Primal and dual approximation algorithms for convex vector optimization problems
Recommended article: A branch and bound algorithm for solving a class of D-C programming
description: scientific article; zbMATH DE number 5677803