Solving a class of low rank d.c. programs via a branch and bound approach: A computational experience

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 bound approach for solving a class of d.c. problems. Both stack policies and partitioning rules are analyzed, pointing out their performance effectiveness by means of the results of a computational experience.     

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 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.     

Branch-and-bound approaches to standard quadratic optimization problems

This paper explores several possibilities for applying branch-and-bound techniques to a central problem class in quadratic programming, the so-called Standard Quadratic Problems (StQPs), which consist of finding a (global) minimizer of a quadratic form over the standard simplex. Since a crucial part of the procedures is based on efficient local optimization, different procedures to obtain local solutions are discussed, and a new class of ascent directions is proposed, for which a convergence result is established. Main emphasis is laid upon a d.c.-based branch-and-bound algorithm, and various strategies for obtaining an efficient d.c. decomposition are discussed.     

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]).     

Multicategory ψ-Learning and Support Vector Machine: Computational Tools

Many margin-based binary classification techniques such as support vector machine (SVM) and ψ-learning deliver high performance. An earlier article proposed a new multicategory ψ-learning methodology that shows great promise in generalization ability. However,ψ-learning is computationally difficult because it requires handling a nonconvex minimization problem. In this article, we propose two computational tools for multicategory ψ-learning. The first one is based on d.c. algorithms and solved by sequential quadratic programming, while the second one uses the outer approximation method, which yields the global minimizer via sequential concave minimization. Numerical examples show the proposed algorithms perform well.     

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.     

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 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.     

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.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

Local search in problems with nonconvex constraints

Nonconvex optimization problems with an inequality constraint given by the difference of two convex functions (by a d.c. function) are considered. Two methods for finding local solutions to this problem are proposed that combine the solution of partially linearized problems and descent to a level surface of the d.c. function. The convergence of the methods is analyzed, and stopping criterions are proposed. The methods are compared by testing them in a numerical experiment.     

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)     

Hybrid stress analysis of boundary and finite elements by a super-element method

This paper is concerned with the hybrid method of boundary element and finite element techniques by means of an “external-super-element” function of the commercial finite element method code . The proposed super-element method preserves the modelling simplicity of the boundary element method and the generality of . Two- and three-dimensional elastostatic analyses are performed to demonstrate the accuracy of this method as well as its applicability to practical problems.     

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.     

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 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.     

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.     

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).     

A neural fuzzy control system with structure and parameter learning

A general connectionist model, called neural fuzzy control network (NFCN), is proposed for the realization of a fuzzy logic control system. The proposed NFCN is a feedforward multilayered network which integrates the basic elements and functions of a traditional fuzzy logic controller into a connectionist structure which has distributed learning abilities. The NFCN can be constructed from supervised training examples by machine learning techniques, and the connectionist structure can be trained to develop fuzzy logic rules and find membership functions. Associated with the NFCN is a two-phase hybrid learning algorithm which utilizes unsupervised learning schemes for structure learning and the backpropagation learning scheme for parameter learning. By combining both unsupervised and supervised learning schemes, the learning speed converges much faster than the original backpropagation algorithm. The two-phase hybrid learning algorithm requires exact supervised training data for learning. In some real-time applications, exact training data may be expensive or even impossible to obtain. To solve this problem, a reinforcement neural fuzzy control network (RNFCN) is further proposed. The RNFCN is constructed by integrating two NFCNs, one functioning as a fuzzy predictor and the other as a fuzzy controller. By combining a proposed on-line supervised structure-parameter learning technique, the temporal difference prediction method, and the stochastic exploratory algorithm, a reinforcement learning algorithm is proposed, which can construct a RNFCN automatically and dynamically through a reward-penalty signal (i.e., “good” or “bad” signal). Two examples are presented to illustrate the performance and applicability of the proposed models and learning algorithms.