A new efficient algorithm based on DC programming and DCA for clustering

In this paper, a version of K-median problem, one of the most popular and best studied clustering measures, is discussed. The model using squared Euclidean distances terms to which the K-means algorithm has been successfully applied is considered. A fast and robust algorithm based on DC (Difference of Convex functions) programming and DC Algorithms (DCA) is investigated. Preliminary numerical solutions on real-world databases show the efficiency and the superiority of the appropriate DCA with respect to the standard K-means algorithm.      

DC programming and DCA for globally solving the value-at-risk

The value-at-risk is an important risk measure that has been used extensively in recent years in portfolio selection and in risk analysis. This problem, with its known bilevel linear program, is reformulated as a polyhedral DC program with the help of exact penalty techniques in DC programming and solved by DCA. To check globality of computed solutions, a global method combining the local algorithm DCA with a well adapted branch-and-bound algorithm is investigated. An illustrative example and numerical simulations are reported, which show the robustness, the globality and the efficiency of DCA.     

Portfolio selection under downside risk measures and cardinality constraints based on DC programming and DCA

In this paper, we consider the case of downside risk measures with cardinality and bounding constraints in portfolio selection. These constraints limit the amount of capital to be invested in each asset as well as the number of assets composing the portfolio. While the standard Markowitz’s model is a convex quadratic program, this new model is a NP-hard mixed integer quadratic program. Realizing the computational intractability for this class of problems, especially large-scale problems, we first reformulate it as a DC program with the help of exact penalty techniques in Difference of Convex functions (DC) programming and then solve it by DC Algorithms (DCA). To check globality of computed solutions, a global method combining the local algorithm DCA with a Branch-and-Bound algorithm is investigated. Numerical simulations show that DCA is an efficient and promising approach for the considered problem.      

The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems

The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R ⁿ ) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.     

A continuous approach for the concave cost supply problem via DC programming and DCA

The paper addresses an important but difficult class of concave cost supply management problems which consist in minimizing a separable increasing concave objective function subject to linear and disjunctive constraints. We first recast these problems into mixed zero-one nondifferentiable concave minimization over linear constraints problems and then apply exact penalty techniques to state equivalent nondifferentiable polyhedral DC (Difference of Convex functions) programs. A new deterministic approach based on DC programming and DCA (DC Algorithms) is investigated to solve the latter ones. Finally numerical simulations are reported which show the efficiency, the robustness and the globality of our approach.     

A transfer algorithm for hierarchical clustering

Transfer algorithms are usually used to optimize an objective function that is defined on the set of partitions of a finite set X. In this paper we define an equivalence relation ? on the set of fuzzy equivalence relations on X and establish a bijection from the set of hierarchies on X to the set of equivalence classes with respect to ?. Thus, hierarchies can be identified with fuzzy equivalence relations and the transfer algorithm can be modified in order to optimize an objective function that is defined on the set of hierarchies on X.     

DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

Errata Corrige: On an Optimality Condition in DC Optimization

We take care of an omission in Proposition 4.4 of Ref. 1.     

Complete mixed integer linear programming formulations for modularity density based clustering

Modularity density maximization is a clustering method that improves some issues of the commonly used modularity maximization approach. Recently, some Mixed-Integer Linear Programming (MILP) reformulations have been proposed in the literature for the modularity density maximization problem, but they require as input the solution of a set of auxiliary binary Non-Linear Programs (NLPs). These can become computationally challenging when the size of the instances grows. In this paper we propose and compare some explicit MILP reformulations of these auxiliary binary NLPs, so that the modularity density maximization problem can be completely expressed as MILP. The resolution time is reduced by a factor up to two order of magnitude with respect to the one obtained with the binary NLPs.     

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.     

Clustering and multifacility location with constraints via distance function penalty methods and dc programming

ABSTRACT

This paper is a continuation of our effort in using mathematical optimization involving DC programming in clustering and multifacility location. We study a penalty method based on distance functions and apply it particularly to a number of problems in clustering and multifacility location in which the centers to be found must lie in some given set constraints. We also provide numerical examples to test our method.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.     

A semistrong sufficiency condition for optimality in nonconvex programming and its connection to the perturbation problem

What happens when a nonconvex program, having a local solutionx ⁰ at which the gradients of the binding constraints are linearly independent, but without strict complementarity hypothesis, is perturbed? Under a relatively weak second-order assumption (some nonnegative second-order terms are supposed to be strictly positive), the perturbed problem has, in the neighborhood ofx ⁰, a finite number of local minima, situated on curves that are connected to some pseudo-solutions of the tangent quadratic problem.     

A continuous DC programming approach to the strategic supply chain design problem from qualified partner set

We present a new continuous approach based on the DC (difference of convex functions) programming and DC algorithms (DCA) to the problem of supply chain design at the strategic level when production of a new market opportunity has to be launched among a set of qualified partners. A well known formulation of this problem is the mixed integer linear program. In this paper, we reformulate this problem as a DC program by using an exact penalty technique. The proposed algorithm is a combination of DCA and Branch and Bound scheme. It works in a continuous domain but provides mixed integer solutions. Numerical simulations on many empirical data sets show the efficiency of our approach with respect to the standard Branch and Bound algorithm.     

Successive search methods for solving a canonical DC programming problem

In this article, we propose two successive search methods for solving a canonical DC programming problem constrained by the difference set between two compact convex sets in the case where the dimension number is greater than or equal to three. In order to find feasible solutions, the algorithms generate the directions based on a branch and bound procedure, successively. By exploring the provisional solutions throughout the intersection of the boundaries of two compact convex sets, both algorithms calculate an approximate solution.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

A nonmonotonic trust region algorithm for a class of semi-infinite minimax programming

Based on the discretization methods for solving semi-infinite programming problems, this paper presents a new nonmonotonic trust region algorithm for a class of semi-infinite minimax programming problem. Under some mild assumptions, the global convergence of the proposed algorithm is given. Numerical tests are reported that show the efficiency of the proposed method.     

On the parallel complexity of hierarchical clustering and CC‐complete problems

Complex data sets are often unmanageable unless they can be subdivided and simplified in an intelligent manner. Clustering is a technique that is used in data mining and scientific analysis for partitioning a data set into groups of similar or nearby items. Hierarchical clustering is an important and well‐studied clustering method involving both top‐down and bottom‐up subdivisions of data. In this article we address the parallel complexity of hierarchical clustering. We describe known sequential algorithms for top‐down and bottom‐up hierarchical clustering. The top‐down algorithm can be parallelized, and when there are n points to be clustered, we provide an O(log n)‐time, n²‐processor Crew Pram algorithm that computes the same output as its corresponding sequential algorithm. We define a natural decision problem based on bottom‐up hierarchical clustering, and add this HIERARCHICAL CLUSTERING PROBLEM (HCP) to the slowly growing list of CC‐complete problems, thereby showing that HCP is one of the computationally most difficult problems in the COMPARATOR CIRCUIT VALUE PROBLEM class. This class contains a variety of interesting problems, and now for the first time a problem from data mining as well. By proving that HCP is CC‐complete, we have demonstrated that HCP is very unlikely to have an NC algorithm. This result is in sharp contrast to the NC algorithm which we give for the top‐down sequential approach, and the result surprisingly shows that the parallel complexities of the top‐down and bottom‐up approaches are different, unless CC equals NC. In addition, we provide a compendium of all known CC‐complete problems. © 2008 Wiley Periodicals, Inc. Complexity, 2008