DCA based algorithms for multiple sequence alignment (MSA)

In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the multiple sequence alignment in its equivalent binary linear program, called “Maximum Weight Trace” problem. This problem is beforehand recast as a polyhedral DC program with the help of exact penalty techniques in DC programming. Our customized DCA, requiring solution of a few linear programs, is original because it converges after finitely many iterations to a binary solution while it works in a continuous domain. To scale-up large-scale (MSA), a constraint generation technique is introduced in DCA. Preliminary computational experiments on benchmark data show the efficiency of the proposed algorithm DCAMSA, which generally outperforms some standard algorithms.     

An efficient DC programming approach for portfolio decision with higher moments

Portfolio selection with higher moments is a NP-hard nonconvex polynomial optimization problem. In this paper, we propose an efficient local optimization approach based on DC (Difference of Convex functions) programming—called DCA (DC Algorithm)—that consists of solving the nonconvex program by a sequence of convex ones. DCA will construct, in each iteration, a suitable convex quadratic subproblem which can be easily solved by explicit method, due to the proposed special DC decomposition. Computational results show that DCA almost always converges to global optimal solutions while comparing with the global optimization methods (Gloptipoly, Branch-and-Bound) and it outperforms several standard local optimization algorithms.     

Strong formulations for quadratic optimization with M-matrices and indicator variables

We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms.     

Binary classification via spherical separator by DC programming and DCA

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.     

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.     

New and efficient algorithms for transfer prices and inventory holding policies in two-enterprise supply chains

We consider a multi-period problem of fair transfer prices and inventory holding policies in two enterprise supply chains. This problem was formulated as a mixed integer non-linear program by Gjerdrum et al. (Eur J Oper Res 143:582–599, 2002). Existing global optimization methods to solve this problem are computationally expensive. We propose a continuous approach based on difference of convex functions (DC) programming and DC Algorithms (DCA) for solving this combinatorial optimization problem. The problem is first reformulated as a DC program via an exact penalty technique. Afterward, DCA, an efficient local approach in non-convex programming framework, is investigated to solve the resulting problem. For globally solving this problem, we investigate a combined DCA-Branch and Bound algorithm. DCA is applied to get lower bounds while upper bounds are computed from a relaxation problem. The numerical results on several test problems show that the proposed algorithms are efficient: DCA provides a good integer solution in a short CPU time although it works on a continuous domain, and the combined DCA-Branch and Bound finds an \(\epsilon \) -optimal solution for large-scale problems in a reasonable time.     

Optimizing a multi-stage production/inventory system by DC programming based approaches

This paper deals with optimizing the cost of set up, transportation and inventory of a multi-stage production system in presence of bottleneck. The considered optimization model is a mixed integer nonlinear program. We propose two methods based on DC (Difference of Convex) programming and DCA (DC Algorithm)—an innovative approach in nonconvex programming framework. The mixed integer nonlinear problem is first reformulated as a DC program and then DCA is developed to solve the resulting problem. In order to globally solve the problem, we combine DCA with a Branch and Bound algorithm (BB-DCA). A convex minorant of the objective function is introduced. DCA is used to compute upper bounds while lower bounds are calculated from a convex relaxation problem. The numerical results compared with those of COUENNE (http://www.coin-or.org/download/binary/Couenne/), a solver for mixed integer nonconvex programming, show the rapidity and the ?-globality of DCA in almost cases, as well as the efficiency of the combined DCA-Branch and Bound algorithm. We also propose a simple heuristic algorithm which is proved by experimental results to be better than an existing heuristic in the literature for this problem.     

A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem

In this paper, we investigate a DC (Difference of Convex functions) programming technique for solving large scale Eigenvalue Complementarity Problems (EiCP) with real symmetric matrices. Three equivalent formulations of EiCP are considered. We first reformulate them as DC programs and then use DCA (DC Algorithm) for their solution. Computational results show the robustness, efficiency, and high speed of the proposed algorithms.     

Monotonic optimization for sensor cover energy problem

We study the sensor cover energy problem (SCEP) in wireless communication—a difficult nonconvex problem with nonconvex constraints. A local approach based on DC programming called DCA was proposed by Astorino and Miglionico (Optim Lett 10(2):355–368, 2016) for solving this problem. In the present paper, we propose a global approach to (SCEP) based on the theory of monotonic optimization. By using an appropriate reformulation of (SCEP) we propose an algorithm for finding quickly a local optimal solution along with an efficient algorithm for computing a global optimal solution. Computational experiments are reported which demonstrate the practicability of the approach.     

On solving Linear Complementarity Problems by DC programming and DCA

In this paper, we consider four optimization models for solving the Linear Complementarity (LCP) Problems. They are all formulated as DC (Difference of Convex functions) programs for which the unified DC programming and DCA (DC Algorithms) are applied. The resulting DCA are simple: they consist of solving either successive linear programs, or successive convex quadratic programs, or simply the projection of points on \mathbbR₊²ⁿ\mathbb{R}_{+}^{2n}. Numerical experiments on several test problems illustrate the efficiency of the proposed approaches in terms of the quality of the obtained solutions, the speed of convergence, and so on. Moreover, the comparative results with Lemke algorithm, a well known method for the LCP, show that DCA outperforms the Lemke method.     

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.      

Virtually semisimple modules and a generalization of the Wedderburn-Artin theorem

A widely used result of Wedderburn and Artin states that “every left ideal of a ring R is a direct summand of R if and only if R has a unique decomposition as a finite direct product of matrix rings over division rings.” Motivated by this, we call a module M virtually semisimple if every submodule of M is isomorphic to a direct summand of M and M is called completely virtually semisimple if every submodule of M is virtually semisimple. We show that the left R-module R is completely virtually semisimple if and only if R has a unique decomposition as a finite direct product of matrix rings over principal left ideal domains. This shows that R is completely virtually semisimple on both sides if and only if every finitely generated (left and right) R-module is a direct sum of a singular module and a projective virtually semisimple module. The Wedderburn-Artin theorem follows as a corollary from our result.     

Visualizing data as objects by DC (difference of convex) optimization

In this paper we address the problem of visualizing in a bounded region a set of individuals, which has attached a dissimilarity measure and a statistical value, as convex objects. This problem, which extends the standard Multidimensional Scaling Analysis, is written as a global optimization problem whose objective is the difference of two convex functions (DC). Suitable DC decompositions allow us to use the Difference of Convex Algorithm (DCA) in a very efficient way. Our algorithmic approach is used to visualize two real-world datasets.     

Long-Short Portfolio Optimization Under Cardinality Constraints by Difference of Convex Functions Algorithm

In the matter of Portfolio selection, we consider an extended version of the Mean-Absolute Deviation (MAD) model, which includes discrete asset choice constraints (threshold and cardinality constraints) and one is allowed to sell assets short if it leads to a better risk-return tradeoff. Cardinality constraints limit the number of assets in the optimal portfolio and threshold constraints limit the amount of capital to be invested in (or sold short from) each asset and prevent very small investments in (or short selling from) any asset. The problem is formulated as a mixed 0–1 programming problem, which is known to be NP-hard. Attempting to use DC (Difference of Convex functions) programming and DCA (DC Algorithms), an efficient approach in non-convex programming framework, we reformulate the problem in terms of a DC program, and investigate a DCA scheme to solve it. Some computational results carried out on benchmark data sets show that DCA has a better performance in comparison to the standard solver IBM CPLEX.     

Using scenario trees and progressive hedging for stochastic inventory routing problems

The Stochastic Inventory Routing Problem is a challenging problem, combining inventory management and vehicle routing, as well as including stochastic customer demands. The problem can be described by a discounted, infinite horizon Markov Decision Problem, but it has been showed that this can be effectively approximated by solving a finite scenario tree based problem at each epoch. In this paper the use of the Progressive Hedging Algorithm for solving these scenario tree based problems is examined. The Progressive Hedging Algorithm can be suitable for large-scale problems, by giving an effective decomposition, but is not trivially implemented for non-convex problems. Attempting to improve the solution process, the standard algorithm is extended with locking mechanisms, dynamic multiple penalty parameters, and heuristic intermediate solutions. Extensive computational results are reported, giving further insights into the use of scenario trees as approximations of Markov Decision Problem formulations of the Stochastic Inventory Routing Problem.     

A combined DCA: GA for constructing highly nonlinear balanced boolean functions in cryptography

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.     

Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones

Summary The problem of finding optimal cycles in a doubly weighted directed graph (Problem A) is closely related to the problem of approximating bivariate functions by the sum of two univariate functions with respect to the supremum norm (Problem B). The close relationship between Problem A and Problem B is detected by the characterization (7.4) of the distance dist (f, t) of Problem B.In Part 1 we construct an algorithm for Problem A where the essential role is played by the minimal lengthsy _j(k) defined by (2.3). If weight functiont1 then the minimum of Problem A is computed by equality (2.4). Ift1 then the minimum is obtained by a binary search procedure, Algorithm 3.In Part 2 we construct our algorithms for solving Problem B by following exactly the ideas of Part 1. By Algorithm 4 we compute the minimal pseudolengthsh _k(y, M) defined by (7.5). If weight functiont1 then the infimum dist(f,t) of Problem B is obtained by equality (7.12) which is closely related to (2.4). Ift1 we compute the infimum dist(f,t) by the binary search procedure Algorithm 5.Additionally, Algorithm 4 leads to a constructive proof of the existence of continuous optimal solutions of Problem B (see Theorem 7.1e) which is already known in caset1 but unknown in caset1.Interesting applications to the steady-state behaviour of industrial processes with interference (Sect. 3) and the solution of integral equations (Problem C) are included.Supported by Deutsche Forschungsgemeinschaft Grant No. GO 270/3     

Irreducible Numerical Semigroups Having Toms Decomposition

In this article we prove that if S is an irreducible numerical semigroup and S is generated by an interval or S has multiplicity 3 or 4, then it enjoys Toms decomposition. We also prove that if a numerical semigroup can be expressed as an expansion of a numerical semigroup generated by an interval, then it is irreducible and has Toms decomposition.     

On the use of rational iterations and domain decomposition methods for the Helmholtz problem

An iterative algorithm for the numerical solution of the Helmholtz problem is considered. It is difficult to solve the problem numerically, in particular, when the imaginary part of the wave number is zero or small. We develop a parallel iterative algorithm based on a rational iteration and a nonoverlapping domain decomposition method for such a non-Hermitian, non-coercive problem. Algorithm parameters (artificial damping and relaxation) are introduced to accelerate the convergence speed of the iteration. Convergence analysis and effective strategies for finding efficient algorithm parameters are presented. Numerical results carried out on an nCUBE2 are given to show the efficiency of the algorithm. To reduce the boundary reflection, we employ a hybrid absorbing boundary condition (ABC) which combines the first-order ABC and the physical $Q$ ABC. Computational results comparing the hybrid ABC with non-hybrid ones are presented. Received May 19, 1994 / Revised version received March 25, 1997     

A Zero-Space algorithm for Negative Cost Cycle Detection in networks

This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. The Negative Cost Cycle Detection (NCCD) problem is one of the more fundamental problems in network design and finds applications in a number of domains ranging from Network Optimization and Operations Research to Constraint Programming and System Verification. As per the literature, approaches to this problem have been either Relaxation-based or Contraction-based. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the NCCD problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is as efficient as the fastest known comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes O(mn) time to detect the presence of a negative cost cycle or to report that none exists. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require Ω(n) extra space. It is well known that the NCCD problem is closely related to the Single Source Shortest Paths (SSSP) problem, i.e., the problem of determining the shortest path distances of all the vertices in a network, from a specified source; indeed most algorithms in the literature for the NCCD problem are modifications of approaches to the SSSP problem. At this juncture, it is not clear whether the Stressing Algorithm could be extended to solve the SSSP problem, even if O(n) extra space is available.