Search

DC (Difference of Convex functions) programming and DCA (DC Algorithm) play a key role in nonconvex programming framework. These tools have a rich and successful history of thirty five years of development, and the research in recent years is being increasingly explored to new trends in the development of DCA: design novel DCA variants to improve standard DCA, to deal with the scalability and with broader classes than DC programs. Following these trends, we address in this paper the two wide classes of nonconvex problems, called partial DC programs and generalized partial DC programs, and investigate an alternating approach based on DCA for them. A partial DC program in two variables $$(x,y)\in \mathbb {R}^{n}\times {\mathbb {R}}^{m}$$ takes the form of a standard DC program in each variable while fixing other variable. A so-named alternating DCA and its inexact/generalized versions are developed. The convergence properties of these algorithms are established: both exact and inexact alternating DCA converge to a weak critical point of the considered problem, in particular, when the Kurdyka–Łojasiewicz inequality property is satisfied, the algorithms furnish a Frechet/Clarke critical point. The proposed algorithms are implemented on the problem of finding an intersection point of two nonconvex sets. Numerical experiments are performed on an important application that is robust principal component analysis. Numerical results show the efficiency and the superiority of the alternating DCA comparing with the standard DCA as well as a well known alternating projection algorithm.

WOS:000543049900114; Power flows in transmission networks are driven by the structure of the network and the spatial distribution of generators and loads. Understanding the interplay between grid, generators, and loads is crucial for efficient and robust planning and management of electrical networks. Using the spectral properties of the graph Laplacian, we show that we can express power flows on the basis of Laplacian eigenvectors and reveal the dominant modes for nodal voltages and branch powers. The bus voltages are dominated by low rank modes. The power in the lines depends on the nodal distribution of generators/loads, the line impedances, and the gradient of the eigenvectors across the branches. The most loaded lines and their associated dominant mode are then identified. A modification of the bus powers is finally proposed to better share the load between the lines and, hence, to decrease the system vulnerability. Results provided for several IEEE transmission test systems prove the relevance of the approach and suggest practical guidelines to improve the operation of power systems.

International audience

International audience

Piecewise affine functions are widely used to approximate nonlinear and discontinuous functions. However, most, if not all existing models, only deal with fitting a continuous function. In this paper, we investigate the problem of fitting a discontinuous piecewise affine function to a given function defined on an arbitrary subset of an integer lattice, where no restriction on the partition of the domain is enforced (i.e., its geometric shape can be nonconvex). This is useful for segmentation and denoising when the given function corresponds to a mapping from pixels of a bitmap image to their color depth values. We propose a novel Mixed Integer Program (MIP) formulation for the piecewise affine fitting problem, where binary edge variables determine the boundary between two partitions of the function domain. To obtain a consistent partitioning (e.g., image segmentation), we include multicut constraints in the formulation. The resulting problem is $$\mathcal {NP}$$ -hard, and two techniques are introduced to improve the computation. One is to adopt a cutting plane method to add the exponentially many multicut inequalities on-the-fly. The other is to provide initial feasible solutions using a tailored heuristic algorithm. We show that the MIP formulation on grid graphs is approximate, while on king’s graph, it is exact under certain circumstances. We conduct initial experiments on synthetic images as well as real depth images, and discuss the advantages and drawbacks of the two models.

The K-partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node-cluster formulations adapted from the literature on similar problems as well as two edge-representative formulations. We introduced the first edge-representative formulation in a previous work [4] while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge-representative formulations and identify a new family of facet-defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node-cluster formulations which may account for their low performances. Finally, we propose a branch-and-cut strategy, based on the edge-representative formulations, which performs even better.

We study an approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for the convex piecewise-linear fitting problem. The objective is to fit a given set of data points by a convex piecewise-linear function. The problem is formulated as minimizing the squared \(\ell _2\)-norm fitting error, and then reformulated as a DC program for which a standard DCA scheme is applied. Furthermore, a modified DCA scheme with successive DC decomposition is proposed with the aim to improve DCA by updating the convex approximation of the fitting error function during DCA iterations. These DCAs consist in solving a sequence of convex quadratic programs. Moreover, the modified DCA still has the same convergence properties as the standard DCA. Numerical results on synthetic/real datasets show the efficiency of our methods when comparing with the existing approaches.

We investigate a powerful nonconvex optimization approach based on Difference of Convex functions (DC) programming and DC Algorithm (DCA) for reinforcement learning, a general class of machine learning techniques which aims to estimate the optimal learning policy in a dynamic environment typically formulated as a Markov decision process (with an incomplete model). The problem is tackled as finding the zero of the so-called optimal Bellman residual via the linear value-function approximation for which two optimization models are proposed: minimizing the $$\ell _{p}$$ -norm of a vector-valued convex function, and minimizing a concave function under linear constraints. They are all formulated as DC programs for which attractive DCA schemes are developed. Numerical experiments on various examples of the two benchmarks of Markov decision process problems—Garnet and Gridworld problems, show the efficiency of our approaches in comparison with two existing DCA based algorithms and two state-of-the-art reinforcement learning algorithms.

International audience; Difference-of-Convex programming and related algorithms, which constitute the backbone of nonconvex programming and global optimization, were introduced in 1985 by Pham Dinh Tao and have been extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1994 to become now classic and increasingly popular. That algorithm is a descent method without linesearch and every limit point of its generated sequence is a critical point of the related Difference-of-Convex program. Determining its convergence rate is a challenging problem. Its knowledge is crucial from both theoretical and practical points of view. In this work, we treat this problem for the class of Difference-of-Convex programs with subanalytic data by using the nonsmooth form of the Lojasiewicz inequality. We have successfully proved that the whole sequence is convergent, if it is bounded, provided that the objective function is subanalytic continuous on its domain and one of the two Difference-of-Convex components is differentiable with locally Lipschitz derivative. We also established a result on the convergence rate, which depended on the Lojasiewicz exponent of the objective function. Finally, for both classes of trust-region subproblems and nonconvex quadratic programs, we showed that the Lojasiewicz exponent was one half, and thereby, our proposed algorithms applied to these Difference-of-Convex programs were Root-linearly convergent.

International audience; In recent years, power control and resource allocation techniques for cellular communication systems are very active research areas. Power control is typically used in wireless cellular networks in order to optimize the transmission subject to quality of service (QoS) constraints. One of the most popular power control problems is based on maximizing the weighted sum of data rates under the peak power constraints for all users. It is a difficult nonconvex optimization problem for which standard approach Geometric Programming is not applicable in large scale setting. In this paper, we propose an efficient method based on DC (Difference of Convex functions) programming and DCA (DC Algorithm), an innovative approach in nonconvex programming framework for solving this problem. The purpose is to develop fast and scalable algorithms able to handle large scale systems. The two main challenges in DC programming and DCA that are the effect of DC decomposition and the efficiency of solution methods to convex subproblems are carefully studied. The computational results on several datasets show the robustness as well as the efficiency of the proposed method in terms of both quality and rapidity, and their superiority compared with the standard approach Geometric Programming.

Major blackouts are due to cascading failures in power systems. These failures usually occur at vulnerable links of the network. To identify these, indicators have already been defined using complex network theory. However, most of these indicators only depend on the topology of the grid; they fail to detect the weak links. We introduce a new metric to identify the vulnerable lines, based on the load-flow equations and the grid geometry. Contrary to the topological indicators, ours is built from the electrical equations and considers the location and magnitude of the loads and of the power generators. We apply this new metric to the IEEE 118-bus system and compare its prediction of weak links to the ones given by an industrial software. The agreement is very well and shows that using our indicator a simple examination of the network and its generator and load distribution suffices to find the weak lines.

International audience; The K-partitioning problem consists in partitioning the vertices of a weighted graph in K sets in order to minimize a function related to the edge weights. We introduce a linear mixed integer formulation with edge variables and representative variables. We investigate the polyhedral combinatorics of the problem, study several families of facet-defining inequalities and evaluate their efficiency on the linear relaxation.

In this paper, we deal with the error bounds for inequality systems and the exact penalization for constrained optimization problems. We firstly investigate the relationships between the error bound and the exact penalization. Then we establish the new error bounds for inequality systems of concave functions and of nonconvex quadratic functions over polyhedral convex sets.

International audience; Sparse optimization refers to an optimization problem involving the zero-norm in objective or constraints. In this paper, nonconvex approximation approaches for sparse optimization have been studied with a unifying point of view in DC (Difference of Convex functions) programming framework. Considering a common DC approximation of the zero-norm including all standard sparse inducing penalty functions, we studied the consistency between global minimums (resp. local minimums) of approximate and original problems. We showed that, in several cases, some global minimizers (resp. local minimizers) of the approximate problem are also those of the original problem. Using exact penalty techniques in DC programming, we proved stronger results for some particular approximations, namely, the approximate problem, with suitable parameters, is equivalent to the original problem. The efficiency of several sparse inducing penalty functions have been fully analyzed. Four DCA (DC Algorithm) schemes were developed that cover all standard algorithms in nonconvex sparse approximation approaches as special versions. They can be viewed as, an ℓ1-perturbed algorithm/reweighted-ℓ1 algorithm / reweighted-ℓ2 algorithm. We offer a unifying nonconvex approximation approach, with solid theoretical tools as well as efficient algorithms based on DC programming and DCA, to tackle the zero-norm and sparse optimization. As an application, we implemented our methods for the feature selection in SVM (Support Vector Machine) problem and performed empirical comparative numerical experiments on the proposed algorithms with various approximation functions.

The explosive development of computational tools these days is threatening security of cryptographic algorithms, which are regarded as primary traditional methods for ensuring information security. The physical layer security approach is introduced as a method for both improving confidentiality of the secret key distribution in cryptography and enabling the data transmission without relaying on higher-layer encryption. In this paper, the cooperative jamming paradigm - one of the techniques used in the physical layer is studied and the resulting power allocation problem with the aim of maximizing the sum of secrecy rates subject to power constraints is formulated as a nonconvex optimization problem. The objective function is a so-called DC (Difference of Convex functions) function, and some constraints are coupling. We propose a new DC formulation and develop an efficient DCA (DC Algorithm) to deal with this nonconvex program. The DCA introduces the elegant concept of approximating the original nonconvex program by a sequence of convex ones: at each iteration of DCA requires solution of a convex subproblem. The main advantage of the proposed approach is that it leads to strongly convex quadratic subproblems with separate variables in the objective function, which can be tackled by both distributed and centralized methods. One of the major contributions of the paper is to develop a highly efficient distributed algorithm to solve the convex subproblem. We adopt the dual decomposition method that results in computing iteratively the projection of points onto a very simple structural set which can be determined by an inexpensive procedure. The numerical results show the efficiency and the superiority of the new DCA based algorithm compared with existing approaches.

Piecewise linear optimization is one of the most frequently used optimization models in practice, such as transportation, finance and supply-chain management. In this paper, we investigate a particular piecewise linear optimization that is optimizing the norm of piecewise linear functions (NPLF). Specifically, we are interested in solving a class of Brugnano–Casulli piecewise linear systems (PLS), which can be reformulated as an NPLF problem. Speaking generally, the NPLF is considered as an optimization problem with a nonsmooth, nonconvex objective function. A new and efficient optimization approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) is developed. With a suitable DC formulation, we design a DCA scheme, named l1-DCA, for the problem of optimizing the l1-norm of NPLF. Thanks to particular properties of the problem, we prove that under some conditions, our proposed algorithm converges to an exact solution after a finite number of iterations. In addition, when a nonglobal solution is found, a numerical procedure is introduced to find a feasible point having a smaller objective value and to restart l1-DCA at this point. Several numerical experiments illustrate these interesting convergence properties. Moreover, we also present an application to the free-surface hydrodynamic problem, where the correct numerical modeling often requires to have the solution of special PLS, with the aim of showing the efficiency of the proposed method.

In this paper, we introduce a novel approach in the nonconvex optimization framework for image restoration via a Markov random field (MRF) model. While image restoration is elegantly expressed in the language of MRF’s, the resulting energy minimization problem was widely viewed as intractable: it exhibits a highly nonsmooth nonconvex energy function with many local minima, and is known to be NP-hard. The main goal of this paper is to develop fast and scalable approximation optimization approaches to a nonsmooth nonconvex MRF model which corresponds to an MRF with a truncated quadratic (also known as half-quadratic) prior. For this aim, we use the difference of convex functions (DC) programming and DC algorithm (DCA), a fast and robust approach in smooth/nonsmooth nonconvex programming, which have been successfully applied in various fields in recent years. We propose two DC formulations and investigate the two corresponding versions of DCA. Numerical simulations show the efficiency, reliability and robustness of our customized DCAs with respect to the standard GNC algorithm and the Graph-Cut based method—a more recent and efficient approach to image analysis.

In this paper, we consider a well-known problem in the general area of search theory: planning a multisensor in multizone search so as to maximize the probability of detection of a target under a given resource effort to be shared. We propose a new optimization model that is a nonlinear mixed 0-1 programming problem. This problem is then reformulated as a DC (Difference of Convex) functions program via an exact penalty technique. DC programming and DCA (DC algorithm) have been investigated for solving the resulting DC program. Numerical experiments demonstrate the efficiency and the superiority of the proposed algorithm in comparison with the existing method.

Nonconvex optimization becomes an indispensable and powerful tool for the analysis and design of Communication Systems (CS) since the last decade. As an innovative approach to nonconvex programming, Difference of Convex functions (DC) programming and DC Algorithms (DCA) are increasingly used by researchers in this field. The objective of this paper is to show that many challenging problems in CS can be modeled as DC programs and solved by DCA-based algorithms. We offer the community of researchers in CS promising approaches in a unified DC programming framework to tackle various applications, such as routing, power control, congestion control of the Internet, resource allocation in networks, etc.

In this paper, we propose nonlinear programming NLP formulations and difference of convex functions DC programming approaches for the asymmetric eigenvalue complementarity problem EiCP. The EiCP has a solution if and only if these NLP formulations have zero global optimal value. We reformulate the NLP formulations as DC programs which can be efficiently solved by a DC algorithm. Some preliminary numerical results illustrate the good performance of the proposed methods.

In this letter, we consider the nonnegative matrix factorization (NMF) problem and several NMF variants. Two approaches based on DC (difference of convex functions) programming and DCA (DC algorithm) are developed. The first approach follows the alternating framework that requires solving, at each iteration, two nonnegativity-constrained least squares subproblems for which DCA-based schemes are investigated. The convergence property of the proposed algorithm is carefully studied. We show that with suitable DC decompositions, our algorithm generates most of the standard methods for the NMF problem. The second approach directly applies DCA on the whole NMF problem. Two algorithms—one computing all variables and one deploying a variable selection strategy—are proposed. The proposed methods are then adapted to solve various NMF variants, including the nonnegative factorization, the smooth regularization NMF, the sparse regularization NMF, the multilayer NMF, the convex/convex-hull NMF, and the symmetric NMF. We also show that our algorithms include several existing methods for these NMF variants as special versions. The efficiency of the proposed approaches is empirically demonstrated on both real-world and synthetic data sets. It turns out that our algorithms compete favorably with five state-of-the-art alternating nonnegative least squares algorithms.

This paper concerns a single-group multicasting relay network comprising of multiple amplify-and-forward relays forwarding signal from a single source to multiple destinations. The source, relays and destinations are equipped by single antennas. In this scenario, we deal with the problem of maximizing the minimum Quality of Service (QoS) assessed by the Signal to Noise Ratio (SNR) of the destinations subject to power constraints. This problem is actually a nonconvex optimization one with nonconvex constraints, which can be reformulated as a DC (Difference of Convex functions) program with DC constraints. We will apply an extension of DC programming and DCA (DC Algorithms) for solving it. Numerical experiments are carried out on several networks simulated under realistic conditions.

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.

In this paper, we investigate the robust optimization for the minimum sum-of squares clustering (MSSC) problem. Each data point is assumed to belong to a box-type uncertainty set. Following the robust optimization paradigm, we obtain a robust formulation that can be interpreted as a combination of MSSC and k-median clustering criteria. A DCA-based algorithm is developed to solve the resulting robust problem. Preliminary numerical results on real datasets show that the proposed robust optimization approach is superior than MSSC and k-median clustering approaches.

The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in the deployment of network routing protocol problems and in the planning of freight distribution problems. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is efficient.

In the present paper, we are concerned with conditions ensuring the exact penalty for nonconvex programming. Firstly, we consider problems with concave objective and constraints. Secondly, we establish various results on error bounds for systems of DC inequalities and exact penalty, with/without error bounds, in DC programming. They permit to recast several class of difficult nonconvex programs into suitable DC programs to be tackled by the efficient DCA.

Substitution boxes, aka S-boxes, are a key component of modern crypto-systems. Several studies and developments were carried out on the problem of building high-quality S-boxes in the last few years. Qualities of such boxes, such as nonlinearity and balance, steer the robustness of modern block ciphers. This work is concerned with the construction of highly nonlinear balanced Boolean functions. A deterministic optimization model which is the minimization of a polyhedral convex function on a convex polytope with 0---1 variables is introduced. A local deterministic optimization approach called DCA (Difference of Convex functions Algorithm) is investigated. For finding a good starting point of DCA we propose two versions of a combined DCA---GA (Genetic Algorithm) method. Numerical simulations prove that DCA is a promising approach for this problem. Moreover the combination of DCA---GA improves the efficiency of DCA and outperforms other standard approaches.

We address a class of particularly hard-to-solve portfolio optimization problems, namely the portfolio optimization under step increasing transaction costs. The step increasing functions are approximated, as closely as desired by a difference of polyhedral convex functions. Then we apply the difference of convex functions algorithm (DCA) to the resulting polyhedral DC program. For testing the efficiency of the DCA we compare it with CPLEX and the branch and bound algorithm proposed by Konno et al.

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.

We present a fast and robust nonconvex optimization approach for Fuzzy C-Means (FCM) clustering model. Our approach is based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) that have been successfully applied in various fields of applied sciences, including Machine Learning. The FCM model is reformulated in the form of three equivalent DC programs for which different DCA schemes are investigated. For accelerating the DCA, an alternative FCM-DCA procedure is developed. Experimental results on several real world problems that include microarray data illustrate the effectiveness of the proposed algorithms and their superiority over the standard FCM algorithm, with respect to both running-time and accuracy of solutions.

500 pages; International audience

In this paper, we consider the problem of resource allocation in emerging area of cooperative physical layer security, whose objective function is of the difference of two convex functions, called DC function, and whose some constraints are coupling. We propose a novel DC decomposition for the objective function and use DCA (DC algorithms) to solve this problem. The main advantage of the proposed DC decomposition is that it leads to strongly convex quadratic sub-problems that can be easily solved by both distributed and centralized methods. The numerical results show the efficiency of this DC decomposition compared with the one proposed in ([2]). The DC decomposition technique in this article may be applied for a wide range of multiuser DC problems in communication systems, signal processing and networking.

In this paper, we consider a well-known problem in the general area of search theory: planning a multisensor in multizone search so as to minimize the probability of non-detection of a moving target under a given resource effort to be shared. The solution method is based on a combination of the forward-backward split technique and DC programming. Numerical experiments demonstrate the efficiency of the proposed algorithm in comparison with the existing method.

We present in this paper some results for solving the Quadratic Eigenvalue Complementarity Problem (QEiCP) by using DC(Difference of Convex functions) programming approaches. Two equivalent Nonconvex Polynomial Programming (NLP) formulations of QEiCP are introduced. We focus on the construction of the DC programming formulations of the QEiCP from these NLPs. The corresponding numerical solution algorithms based on the classical DC Algorithm (DCA) are also discussed.

We suggest a novel approach to the sparse covariance matrix estimation (SCME) problem using the l1-norm. The resulting optimization problem is nonconvex and very hard to solve. Fortunately, it can be reformulated as DC (Difference of Convex functions) programs to which DC programming and DC Algorithms can be investigated. The main contribution of this paper is to propose a more suitable DC decomposition for solving the SCME problem. The experimental results on both simulated datasets and two real datasets in classification problem illustrate the efficiency of the proposed algorithms.

A so-called DCA method based on a d.c.\ (difference of convex functions) optimization approach (algorithm) for solving large-scale distance geometry problems is developed. Different formulations of equivalent d.c.\ programs in the $l_{1}$-approach are stated via the Lagrangian duality without gap relative to d.c.\ programming, and new nonstandard nonsmooth reformulations in the $l_{\infty }$-approach (resp., the $l_{1}-l_{\infty }$-approach) are introduced. Substantial subdifferential calculations permit us to compute sequences of iterations in the DCA quite simply. The computations actually require matrix-vector products and only one Cholesky factorization (resp., with an additional solution of a convex program) in the $l_{1}$-approach (resp., the $l_{1}-l_{\infty }$-approach) and allow the exploitation of sparsity in the large-scale setting. Two techniques---respectively, using shortest paths between all pairs of atoms to generate the complete dissimilarity matrix and the spanning trees procedure---are investigated in order to compute a good starting point for the DCA. Finally, many numerical simulations of the molecular optimization problems with up to 12567 variables are reported, which prove the practical usefulness of the nonstandard nonsmooth reformulations, the globality of found solutions, and the robustness and efficiency of our algorithms.

The Tikhonov regularization method for non-linear ill-posed problems requires us to globally solve non-convex optimization problem which have been very little studied in the inverse problems community. In this paper we suggest a method which is applicable to the Tikhonov method for a wide class of non-linear ill-posed problems. This is a class of problems when the Tikhonov functional for them can be represented by the difference of two convex functionals. Our method for these problems is a combination of the recently developed algorithm DCA in dc programming with the branch-and-bound techniques. To cite this article: Le Thi Hoai An et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 1073–1078.

International audience

The Multidimensional Assignment Problem (MAP) is a higher dimensional version of the linear assignment problem, where we find tuples of elements from given sets, such that the total cost of the tuples is minimal. The MAP has many recognized applications such as data association, target tracking, and resource planning. While the linear assignment problem is solvable in polynomial time, the MAP is NP-hard. In this work, we develop a new approach based on the Cross-Entropy (CE) methods for solving the MAP. Exploiting the special structure of the MAP, we propose an appropriate family of discrete distributions on the feasible set of the MAP that allow us to design an efficient and scalable CE algorithm. The efficiency and scalability of our method are proved via several tests on large-scale problems with up to 5 dimensions and 20 elements in each dimension, which is equivalent to a 0---1 linear program with 3.2 millions binary variables and 100 constraints.

We present a natural extension of DC programming and DCA for modeling and solving general DC programs with DC constraints. Two resulting approaches consist in reformulating those programs as standard DC programs in order to use standard DCAs for their solutions. The first one is based on penalty techniques in DC programming, while the second linearizes concave functions in DC constraints to build convex inner approximations of the feasible set. They are proved to converge to KKT points of general DC programs under usual constraints qualifications. Both designed algorithms can be viewed as a sequence of standard DCAs with updated penalty (resp. relaxation) parameters.

In this chapter, a so-called DCA method based on a DC (difference of convex functions) optimization approach for solving large-scale distance geometry problems is developed. Two main problems are considered: the exact and the general distance geometry problems. Different formulations of equivalent DC programs are introduced. Substantial subdifferential calculations permit to compute sequences of iterations in the DCA quite simply and allow exploiting sparsity in the large-scale setting. For improving the computational efficiency of the DCA schemes we investigate several techniques. A two-phase algorithm using shortest paths between all pairs of atoms to generate the complete dissimilarity matrix, a spanning trees procedure, and a smoothing technique are investigated in order to compute a good starting point (SP) for the DCAs. An important issue in the DC optimization approach is well exploited, say the nice effect of DC decompositions of the objective functions. For this purpose we propose several equivalent DC formulations based on the stability of Lagrangian duality and the regularization techniques. Finally, many numerical simulations of the molecular optimization problems with up to 12,567 variables are reported which prove the practical usefulness of the nonstandard nonsmooth reformulations, the globality of found solutions, the robustness, and the efficiency of our algorithms.

Network Utility Maximisation for nonconcave utility functions is a challenging problem in Communication Systems. We propose an innovative approach in nonconvex programming framework for the Network Sigmoidal Utility Maximisation which has many applications, in particular in Multimedia and Internet congestion control. Our method is based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which have been successfully applied to many large-scale (smooth or nonsmooth) nonconvex programs in various areas. A simple DC formulation is proposed that leads to a fast and scalable DCA based algorithm. A distributed version of DCA is developed and some numerical examples are considered. Our algorithm given a global optimal solution in all cases.

In this paper, we consider a binary supervised classification problem, called spherical separation, that consists of finding, in the input space or in the feature space, a minimal volume sphere separating the set $${\mathcal{A}}$$ from the set $${\mathcal{B}}$$ (i.e. a sphere enclosing all points of $${ \mathcal{A}}$$ and no points of $${\mathcal{B}}$$ ). The problem can be cast into the DC (Difference of Convex functions) programming framework and solved by DCA (DC Algorithm) as shown in the works of Astorino et al. (J Glob Optim 48(4):657---669, 2010). The aim of this paper is to investigate more attractive DCA based algorithms for this problem. We consider a new optimization model and propose two interesting DCA schemes. In the first scheme we have to solve a quadratic program at each iteration, while in the second one all calculations are explicit. Numerical simulations show the efficiency of our customized DCA with respect to the methods developed in Astorino et al.

In this paper, we consider the problem of feature selection and classification under uncertain data that is inherently prevalent in almost all datasets. Using principles of Robust Optimization, we propose a robust scheme to handle data with ellipsoidal model uncertainty. The difficulty in treating zero-norm l0 in feature selection problem is overcome by using an appropriate approximation and DC (Difference of Convex functions) programming and DCA (DC Algorithm). The computational results show that the proposed robust optimization approach is more performant than a traditional approach in immunizing perturbation of the data.

Efficient design of wireless networks is a challenging task. Recently, the concept of cross-layer design in wireless networks has been investigated extensively. In this work, we present a cross-layer optimization framework, i.e., joint rate control, routing, link scheduling and power control for multi-hop time division multiple access (TDMA) networks. In particular, we study a centralized controller that coordinates the routing process and transmissions of links such that the network lifetime is maximized. We show that the aforementioned design can be formulated as a mixed integer-linear program (MILP) which has worst case exponential complexity to compute the optimal solution. Therefore, our main contribution is to propose a computationally efficient approach to solve the cross-layer design problem. Our design methodology is based on a so-called Difference of Convex functions algorithm (DCA) to provide either optimal or near-optimal solutions with finite convergence. The numerical results are encouraging and demonstrate the effectiveness of the proposed approach. One of the advantages of the proposed design is the capability to handle very large-scale problems which are the usual scenarios encountered in practice.

We consider a single-period portfolio selection problem which consists of minimizing the total transaction cost subject to different types of constraints on feasible portfolios. The transaction cost function is separable, i.e., it is the sum of the transaction cost associated with each trade, but discontinuous. This optimization problem is nonconvex and very hard to solve. We investigate in this work a DC (Difference of Convex functions) programming framework for the solution methods. First, the objective function is approximated by a DC function. Then a DC formulation for the resulting problem is proposed for which two approaches are developed: DCA (DC Algorithm) and a hybridization of Branch and Bound and DCA.

In this paper we outline a d.c. optimization scheme and use it for (locally) maximizing a concave, a convex or a quadratic function f over the efficient set of a multiple objective convex program. We also propose a decomposition method for globally solving this problem with f concave. Numerical experiences are discussed.

International audience; The global minimization ofan indefinite quadratic function over a bounded polyhedralset using a décomposition branch and bound approach is considered. The objective functionconsists ofan unseparated convex part and a separated concave part The large-scale problems arecharacterized by hoving the number of convex variables much more thon that of concave variables.The advantages of the method is that it uses the rectangular subdivision on the subspace of concavevariables. Using a easily constmcted convex underestimating function îo the objective function,a lower bound is obtained by solving a convex quadratic programming problem. Three variantsusing exhaustive, adaptive and w-subdivision are discussed. Computational results are presentedfor problems with 10-20 concave variables and up to 200 convex variables.; La minimisation globale d'une forme quadratique indéfinie sur un polyèdre convexeborné par une méthode décomposition-séparation et évaluation est étudiée dans ce papier. Lafonction objectif est la somme d'une forme quadratique convexe et d'une forme quadratique concaveséparable en ses variables. Les problèmes de grande dimension sont caractérisés par le fait quele nombre des variables convexes est beaucoup plus grand que celui des variables concaves.L'avantage de la méthode réside dans l'utilisation de la subdivision rectangulaire uniquementdans le sous-espace des variables concaves. A l'aide d'une minorante très simple à calculer de lapartie concave, une borne inférieure est obtenue en résolvant un programme quadratique convexe.Trois variantes utilisant la subdivision exhautive, la subdivision adaptive et la w-subdivision sontconsidérées. Les simulations numériques sont présentés pour les problèmes ayant 10-20 variablesconcaves et jusqu'à 200 variables convexes.

A decomposition branch and bound approach is considered for the global minimization of an indefinite quadratic function over a polytope. The objective function is a sum of a nonseparable convex part and a separable concave part. In many large-scale problems the number of convex variables is much larger than that of concave variables. Taking advantage of this we use a branch and bound method where branching proceeds by rectangular subdivision of the subspace of concave variables. With the help of an easily constructed convex underestimator of the objective function, a lower bound is obtained by solving a convex quadratic programming problem. Three variants using exhaustive, adaptive and w-subdivision are discussed. Computational results are presented for problems with 10-20 concave variables and up to 200 convex variables.

Car pooling problem (CPP) is a well known transport solution that consists in sharing a car between a driver and passengers sharing the same route, or part of it. The challenge is to minimize both the number of required cars and the additional cost in terms of time for the drivers. There are two resulting problems that are interdependent and NP-complete: assigning passengers to cars and finding the shortest path for the drivers so that the overall cost is minimized. In this paper, we consider a multiobjective dynamic car pooling problem, where both the cost and the total travel time of drivers are to be minimized. We based on labeling algorithms for solving the multiobjective shortest problem investigate a new algorithm to solve this problem. Preliminary numerical results in a real scenario are reported. They show that our proposed algorithm is efficient and promising to real time applications.