A branch and reduce approach for solving a class of low rank d.c. programs

Various classes of d.c. programs have been studied in the recent literature due to their importance in applicative problems. In this paper we consider a branch and reduce approach for solving a class of d.c. problems. Seven partitioning rules are analyzed and some techniques aimed at improving the overall performance of the algorithm are proposed. The results of a computational experience are provided in order to point out the performance effectiveness of the proposed techniques.     

Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. Algorithms

Linearly constrained indefinite quadratic problems play an important role in global optimization. In this paper we study d.c. theory and its local approachto such problems. The new algorithm, CDA, efficiently produces local optima and sometimes produces global optima. We also propose a decomposition branch andbound method for globally solving these problems. Finally many numericalsimulations are reported.     

ON CONE D.C. OPTIMIZATION AND CONJUGATE DUALITY

This paper derives first order necessary and sufficient conditions for unconstrained cone d.c. programming problems where the underlined space is partially ordered with respect to a cone. These conditions are given in terms of directional derivatives and subdifferentials of the component functions. Moreover, conjugate duality for cone d.c. optimization is discussed and weak duality theorem is proved in a more general partially ordered linear topological vector space (generalizing the results in [11]).     

On Covering Methods for D.C. Optimization

Covering methods constitute a broad class of algorithms for solving multivariate Global Optimization problems. In this note we show that, when the objective f is d.c. and a d.c. decomposition for f is known, the computational burden usually suffered by multivariate covering methods is significantly reduced. With this we extend to the (non-differentiable) d.c. case the covering method of Breiman and Cutler, showing that it is a particular case of the standard outer approximation approach. Our computational experience shows that this generalization yields not only more flexibility but also faster convergence than the covering method of Breiman-Cutler.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

On solving a D.C. programming problem by a sequence of linear programs

We are dealing with a numerical method for solving the problem of minimizing a difference of two convex functions (a d.c. function) over a closed convex set in ⁿ . This algorithm combines a new prismatic branch and bound technique with polyhedral outer approximation in such a way that only linear programming problems have to be solved.Parts of this research were accomplished while the third author was visiting the University of Trier, Germany, as a fellow of the Alexander von Humboldt foundation.     

A D.C. biobjective location model

In this paper we address the biobjective problem of locating a semiobnoxious facility, that must provide service to a given set of demand points and, at the same time, has some negative effect on given regions in the plane. In the model considered, the location of the new facility is selected in such a way that it gives answer to these contradicting aims: minimize the service cost (given by a quite general function of the distances to the demand points) and maximize the distance to the nearest affected region, in order to reduce the negative impact. Instead of addressing the problem following the traditional trend in the literature (i.e., by aggregation of the two objectives into a single one), we will focus our attention in the construction of a finite -dominating set, that is, a finite feasible subset that approximates the Pareto-optimal outcome for the biobjective problem. This approach involves the resolution of univariate d.c. optimization problems, for each of which we show that a d.c. decomposition of its objective can be obtained, allowing us to use standard d.c. optimization techniques.     

A Method for Converting a Class of Univariate Functions into d.c. Functions

D.c. functions are functions that can be expressed as the sum of a concave function and a convex function (or as the difference of two convex functions). In this paper, we extend the class of univariate functions that can be represented as d.c. functions. This expanded class is very broad including a large number of nonlinear and/or nonsmooth univariate functions. In addition, the procedure specifies explicitly the functional and numerical forms of the concave and convex functions that comprise the d.c. representation of the univariate functions. The procedure is illustrated using two numerical examples. Extensions of the conversion procedure for discontinuous univariate functions is also discussed.     

Solving an Inverse Problem for an Elliptic Equation by d.c. Programming

An inverse problem of determination of a coefficient in an elliptic equation is considered. This problem is ill-posed in the sense of Hadamard and Tikhonov's regularization method is used for solving it in a stable way. This method requires globally solving nonconvex optimization problems, the solution methods for which have been very little studied in the inverse problems community. It is proved that the objective function of the corresponding optimization problem for our inverse problem can be represented as the difference of two convex functions (d.c. functions), and the difference of convex functions algorithm (DCA) in combination with a branch-and-bound technique can be used to globally solve it. Numerical examples are presented which show the efficiency of the method.     

D.c. sets,d.c. functions and nonlinear equations

Ad.c. set is a set which is the difference of two convex sets. We show that any set can be viewed as the image of a d.c. set under an appropriate linear mapping. Using this universality we can convert any problem of finding an element of a given compact set in ⁿ into one of finding an element of a d.c. set. On the basis of this approach a method is developed for solving a system of nonlinear equations—inequations. Unlike Newton-type methods, our method does not require either convexity, differentiability assumptions or an initial approximate solution.The revision of this paper was produced during the author's stay supported by a Sophia lecturing-research grant at Sophia University (Tokyo, Japan).     

Conditions Characterizing Minima of the Difference of Functions

 Optimization problems involving differences of functions arouse interest as generalizations of so-called d.c. problems, i.e. problems involving the difference of two convex functions. The class of d.c. functions is very rich, so d.c. problems are rather general optimization problems. Several global optimality conditions for these d.c. problems have been proposed in the optimization literature. We provide a survey of these conditions and try to detect their common basis. This enables us to give generalizations of the conditions to situations when the objective function is no longer a difference of convex functions, but the difference of two functions which are representable as the upper envelope of an arbitrary family of functions. (Received 6 February 2001; in revised form 11 October 2001)     

A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems

In this paper we propose a new branch and bound algorithm using a rectangular partition and ellipsoidal technique for minimizing a nonconvex quadratic function with box constraints. The bounding procedures are investigated by d.c. (difference of convex functions) optimization algorithms, called DCA. This is based upon the fact that the application of the DCA to the problems of minimizing a quadratic form over an ellipsoid and/or over a box is efficient. Some details of computational aspects of the algorithm are reported. Finally, numerical experiments on a lot of test problems showing the efficiency of our algorithm are presented.     

A D.C. optimization method for single facility location problems

The single facility location problem with general attraction and repulsion functions is considered. An algorithm based on a representation of the objective function as the difference of two convex (d.c.) functions is proposed. Convergence to a global solution of the problem is proven and extensive computational experience with an implementation of the procedure is reported for up to 100,000 points. The procedure is also extended to solve conditional and limited distance location problems. We report on limited computational experiments on these extensions.This research was supported in part by the National Science Foundation Grant DDM-91-14489.     

There is no low maximal d. c. e. degree – Corrigendum

We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

A unifying approach to solve a class of rank-three programs involving linear and quadratic functions

The aim of this paper is two-fold. First, the so-called ‘optimal level solutions’ method is described in a new unifying framework with the aim to provide an algorithmic scheme able to approach various different classes of problems. Then, the ‘optimal level solutions’ method is used to solve a class of low-rank programmes involving linear and quadratic functions and having a polyhedral feasible region. In particular, the considered class of programmes covers, among all, rank-three d.c., multiplicative and fractional programmes. Some optimality conditions are used to improve the performance of the proposed algorithm.     

Linearly constrained global minimization of functions with concave minorants

In this note, we show how a recent approach for solving linearly constrained multivariate Lipschitz optimization problems and corresponding systems of inequalities can be generalized to solve optimization problems where the objective function is only assumed to possess a concave minorant at each point. This class of functions includes not only Lipschitz functions and some generalizations, such as certain -convex functions and Hölder functions with exponent greater than one, but also all functions which can be expressed as differences of two convex functions (d.c. functions). Thus, in particular, a new approach is obtained for the important problem of minimizing a d.c. function over a polytope.     

A Splitting with Infimum in the d‐c. e. Degrees

In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d‐c. e. degrees.     

A Finite Algorithm for a Particular D.C. Quadratic Programming Problem

In this paper a particular quadratic minimum program, having a particular d.c. objective function, is studied. Some theoretical properties of the problem are stated and the existence of minimizers is characterized. A solution algorithm, based on the so called optimal level solutions approach, is finally proposed.