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.     

Bundle-based descent method for nonsmooth multiobjective DC optimization with inequality constraints

Multiobjective DC optimization problems arise naturally, for example, in data classification and cluster analysis playing a crucial role in data mining. In this paper, we propose a new multiobjective double bundle method designed for nonsmooth multiobjective optimization problems having objective and constraint functions which can be presented as a difference of two convex (DC) functions. The method is of the descent type and it generalizes the ideas of the double bundle method for multiobjective and constrained problems. We utilize the special cutting plane model angled for the DC improvement function such that the convex and the concave behaviour of the function is captured. The method is proved to be finitely convergent to a weakly Pareto stationary point under mild assumptions. Finally, we consider some numerical experiments and compare the solutions produced by our method with the method designed for general nonconvex multiobjective problems. This is done in order to validate the usage of the method aimed specially for DC objectives instead of a general nonconvex method.     

On Global Optimality Conditions and Cutting Plane Algorithms

We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems.     

Constructing a DC decomposition for ordered median problems

In this paper we show how to express ordered median problems as a difference between two convex functions (DC). Such an expression can be exploited in solving ordered median problems by using the special methodology available for DC optimization. The approach is demonstrated for solving ordered one median problems in the plane. Computational experiments demonstrated the effectiveness of the approach.     

Some characterizations of duality for DC optimization with composite functions

In this paper, by virtue of the epigraph technique, we first introduce some new regularity conditions and then obtain some complete characterizations of the Fenchel–Lagrange duality and the stable Fenchel–Lagrange duality for a new class of DC optimization involving a composite function. Moreover, we apply the strong and stable strong duality results to obtain some extended (stable) Farkas lemmas and (stable) alternative type theorems for this DC optimization problem. As applications, we obtain the corresponding results for a composed convex optimization problem, a DC optimization problem, and a convex optimization problem with a linear operator, respectively.     

$${{\mathcal {D}(\mathcal {C})}}$$-optimization and robust global optimization

For solving global optimization problems with nonconvex feasible sets existing methods compute an approximate optimal solution which is not guaranteed to be close, within a given tolerance, to the actual optimal solution, nor even to be feasible. To overcome these limitations, a robust solution approach is proposed that can be applied to a wide class of problems called D(C){{\mathcal {D}(\mathcal {C})}}-optimization problems. DC optimization and monotonic optimization are particular cases of D(C){{\mathcal {D}(\mathcal {C})}}-optimization, so this class includes virtually every nonconvex global optimization problem of interest. The approach is a refinement and extension of an earlier version proposed for dc and monotonic optimization.     

A multiobjective optimization model for processing and distributing biosolids to reuse fields

Advanced wastewater treatment plants remove deleterious nutrients, chemicals, and microorganisms from wastewater and produce biosolids products to be reused at farms and other sites. These biosolids are carefully regulated by environmental restrictions but still may be malodorous to the local populations. In this paper, we develop a multiobjective optimization model to simultaneously minimize the biosolids odours as well as processing and distribution costs. The model employs a linear odour function and bilinear costs; the latter being approximated via Schur's decomposition and special ordered set (SOS) type 2 variables resulting in a mixed integer linear multiobjective optimization problem. Such a model can be used proactively by these plants to produce the least malodorous product at minimal costs. We demonstrate use of the model with a case study for the Blue Plains advanced wastewater treatment plant run by the DC Water and Sewer Authority in Washington, DC.     

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.     

Optimization based DC programming and DCA for hierarchical clustering

One of the most promising approaches for clustering is based on methods of mathematical programming. In this paper we propose new optimization methods based on DC (Difference of Convex functions) programming for hierarchical clustering. A bilevel hierarchical clustering model is considered with different optimization formulations. They are all nonconvex, nonsmooth optimization problems for which we investigate attractive DC optimization Algorithms called DCA. Numerical results on some artificial and real-world databases are reported. The results demonstrate that the proposed algorithms are more efficient than related existing methods.     

Equilibrium investment strategy for DC pension plan with default risk and return of premiums clauses under CEV model

This paper considers an optimal investment problem for a defined contribution (DC) pension plan with default risk in a mean–variance framework. In the DC plan, contributions are supposed to be a predetermined amount of money as premiums and the pension funds are allowed to be invested in a financial market which consists of a risk-free asset, a defaultable bond and a risky asset satisfied a constant elasticity of variance (CEV) model. Notice that a part of pension members could die during the accumulation phase, and their premiums should be withdrawn. Thus, we consider the return of premiums clauses by an actuarial method and assume that the surviving members will share the difference between the return and the accumulation equally. Taking account of the pension fund size and the volatility of the accumulation, a mean–variance criterion as the investment objective for the DC plan can be formulated, and the original optimization problem can be decomposed into two sub-problems: a post-default case and a pre-default case. By applying a game theoretic framework, the equilibrium investment strategies and the corresponding equilibrium value functions can be obtained explicitly. Economic interpretations are given in the numerical simulation, which is presented to illustrate our results.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

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.     

A new necessary and sufficient global optimality condition for canonical DC problems

The paper proposes a new necessary and sufficient global optimality condition for canonical DC optimization problems. We analyze the rationale behind Tuy’s standard global optimality condition for canonical DC problems, which relies on the so-called regularity condition and thus can not deal with the widely existing non-regular instances. Then we show how to modify and generalize the standard condition to a new one that does not need regularity assumption, and prove that this new condition is equivalent to other known global optimality conditions. Finally, we show that the cutting plane method, when associated with the new optimality condition, could solve the non-regular canonical DC problems, which significantly enlarges the application of existing cutting plane (outer approximation) algorithms.     

DC approach to weakly convex optimization and nonconvex quadratic optimization problems

Motivated by weakly convex optimization and quadratic optimization problems, we first show that there is no duality gap between a difference of convex (DC) program over DC constraints and its associated dual problem. We then provide certificates of global optimality for a class of nonconvex optimization problems. As an application, we derive characterizations of robust solutions for uncertain general nonconvex quadratic optimization problems over nonconvex quadratic constraints.     

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.     

Demand selection decisions for a multi-echelon inventory distribution system

In this paper, we study an integrated demand selection and multi-echelon inventory control problem that generalizes the classical deterministic single distribution centre (DC) multi-retailer model by incorporating demand selection decisions. In addition to the ordering and holding cost components, a concave operating cost of the DC and a capacity on the total market demand served are also considered. For given revenue and cost parameters, the problem is to determine which sets of demand to fulfill and which multi-echelon inventory control policy to implement so as to maximize the net profit. We show that the problem can be formulated as a nonlinear discrete optimization model. We analyse the structural properties of the model and, based on these, outline an approach to solve the model efficiently. We also present some interesting managerial insights obtained from the numerical experiments.     

Some new Farkas-type results for inequality systems with DC functions

We present some Farkas-type results for inequality systems involving finitely many DC functions. To this end we use the so-called Fenchel-Lagrange duality approach applied to an optimization problem with DC objective function and DC inequality constraints. Some recently obtained Farkas-type results are rediscovered as special cases of our main result.     

A DC programming approach for feature selection in support vector machines learning

Feature selection consists of choosing a subset of available features that capture the relevant properties of the data. In supervised pattern classification, a good choice of features is fundamental for building compact and accurate classifiers. In this paper, we develop an efficient feature selection method using the zero-norm l ₀ in the context of support vector machines (SVMs). Discontinuity at the origin for l ₀ makes the solution of the corresponding optimization problem difficult to solve. To overcome this drawback, we use a robust DC (difference of convex functions) programming approach which is a general framework for non-convex continuous optimisation. We consider an appropriate continuous approximation to l ₀ such that the resulting problem can be formulated as a DC program. Our DC algorithm (DCA) has a finite convergence and requires solving one linear program at each iteration. Computational experiments on standard datasets including challenging feature-selection problems of the NIPS 2003 feature selection challenge and gene selection for cancer classification show that the proposed method is promising: while it suppresses up to more than 99% of the features, it can provide a good classification. Moreover, the comparative results illustrate the superiority of the proposed approach over standard methods such as classical SVMs and feature selection concave.     

Truncated-newtono algorithms for large-scale unconstrained optimization

We present an algorithm for large-scale unconstrained optimization based onNewton's method. In large-scale optimization, solving the Newton equations at each iteration can be expensive and may not be justified when far from a solution. Instead, an inaccurate solution to the Newton equations is computed using a conjugate gradient method. The resulting algorithm is shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence. Some numerical results on a 916 vriable test problem are given. Finally, we contrast the computational behavior of our algorithm with Newton's method and that of a nonlinear conjugate gradient algorithm. This research was supported in part by DOT Grant CT-06-0011, NSF Grant ENG-78-21615 and grants from the Norwegian Research Council for Sciences and the Humanities and the Norway-American Association. This paper was originally presented at the TIMS-ORSA Joint National Meeting, Washington, DC, May 1980.     

On DC optimization algorithms for solving minmax flow problems

We formulate minmax flow problems as a DC optimization problem. We then apply a DC primal-dual algorithm to solve the resulting problem. The obtained computational results show that the proposed algorithm is efficient thanks to particular structures of the minmax flow problems.     

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.