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.     

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.     

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.     

An efficient combined DCA and B&;B using DC/SDP relaxation for globally solving binary quadratic programs

This paper addresses a new continuous approach based on the DC (Difference of Convex functions) programming and DC algorithms (DCA) to Binary quadratic programs (BQP) which play a key role in combinatorial optimization. DCA is completely different from other avalaible methods and featured by generating a convergent finite sequence of feasible binary solutions (obtained by solving linear programs with the same constraint set) with decreasing objective values. DCA is quite simple and inexpensive to handle large-scale problems. In particular DCA is explicit, requiring only matrix-vector products for Unconstrained Binary quadratic programs (UBQP), and can then exploit sparsity in the large-scale setting. To check globality of solutions computed by DCA, we introduce its combination with a customized Branch-and-Bound scheme using DC/SDP relaxation. The combined algorithm allows checking globality of solutions computed by DCA and restarting it if necessary and consequently accelerates the B&B approach. Numerical results on several series test problems provided in OR-Library (Beasley in J Global Optim, 8:429–433, 1996), show the robustness and efficiency of our algorithm with respect to standard methods. In particular DCA provides ϵ-optimal solutions in almost all cases after only one restarting and the combined DCA-B&B-SDP always provides (ϵ−)optimal solutions.     

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.     

A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems

In this paper we propose a new branch and bound algorithm using a rectangular partition and ellipsoidal technique for minimizing a nonconvex quadratic function with box constraints. The bounding procedures are investigated by d.c. (difference of convex functions) optimization algorithms, called DCA. This is based upon the fact that the application of the DCA to the problems of minimizing a quadratic form over an ellipsoid and/or over a box is efficient. Some details of computational aspects of the algorithm are reported. Finally, numerical experiments on a lot of test problems showing the efficiency of our algorithm are presented.     

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.     

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.     

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.     

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.     

Properties of two DC algorithms in quadratic programming

Some new properties of the Projection DC decomposition algorithm (we call it Algorithm A) and the Proximal DC decomposition algorithm (we call it Algorithm B) Pham Dinh et al. in Optim Methods Softw, 23(4): 609–629 (2008) for solving the indefinite quadratic programming problem under linear constraints are proved in this paper. Among other things, we show that DCA sequences generated by Algorithm A converge to a locally unique solution if the initial points are taken from a neighborhood of it, and DCA sequences generated by either Algorithm A or Algorithm B are all bounded if a condition guaranteeing the solution existence of the given problem is satisfied.     

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.     

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 algorithm for globally minimizing a quadratic function under convex quadratic constraints

In this paper we investigate two approaches to minimizing a quadratic form subject to the intersection of finitely many ellipsoids. The first approach is the d.c. (difference of convex functions) optimization algorithm (abbr. DCA) whose main tools are the proximal point algorithm and/or the projection subgradient method in convex minimization. The second is a branch-and-bound scheme using Lagrangian duality for bounding and ellipsoidal bisection in branching. The DCA was first introduced by Pham Dinh in 1986 for a general d.c. program and later developed by our various work is a local method but, from a good starting point, it provides often a global solution. This motivates us to combine the DCA and our branch and bound algorithm in order to obtain a good initial point for the DCA and to prove the globality of the DCA. In both approaches we attempt to use the ellipsoidal constrained quadratic programs as the main subproblems. The idea is based upon the fact that these programs can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms, among them the DCA with restarting procedure recently proposed by Pham Dinh and Le Thi has been shown to be the most robust and fast for large-scale problems. Several numerical experiments with dimension up to 200 are given which show the effectiveness and the robustness of the DCA and the combined DCA-branch-and-bound algorithm. Received: April 22, 1999 / Accepted: November 30, 1999?Published online February 23, 2000     

An Interior-Point Method for a Class of Saddle-Point Problems

We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization formulations of convex quadratic programming problems with uncertain input parameters. As an application of our approach, we discuss a robust formulation of the Markowitz portfolio selection model.     

随机模糊的等比例-最小方差投资组合优化研究

Markowitz的均值-方差模型在投资组合优化中得到了广泛的运用和拓展,其中多数拓展模型仅局限于对随机投资组合或模糊投资组合的研究,而忽略了实际问题同时包含了随机信息和模糊信息两个方面。本文首先定义随机模糊变量的方差用以度量投资组合的风险,提出具有阀值约束的最小方差随机模糊投资组合模型,基于随机模糊理论,将该模型转化为具有线性等式和不等式约束的凸二次规划问题。为了提高上述模型的有效性,本文以投资者期望效用最大化为压缩目标对投资组合权重进行压缩,构建等比例-最小方差混合的随机模糊投资组合模型,并求解该模型的最优解。最后,运用滚动实际数据的方法,比较上述两个模型的夏普比率以验证其有效性。     

Portfolio selection under possibilistic mean–variance utility and a SMO algorithm

In this paper, we propose a new portfolio selection model with the maximum utility based on the interval-valued possibilistic mean and possibilistic variance, which is a two-parameter quadratic programming problem. We also present a sequential minimal optimization (SMO) algorithm to obtain the optimal portfolio. The remarkable feature of the algorithm is that it is extremely easy to implement, and it can be extended to any size of portfolio selection problems for finding an exact optimal solution.     

A distributed computation algorithm for solving portfolio problems with integer variables

A portfolio problem with integer variables can facilitate the use of complex models, including models containing discrete asset values, transaction costs, and logical constraints. This study proposes a distributed algorithm for solving a portfolio program to obtain a global optimum. For a portfolio problem with n integer variables, the objective function first is converted into an ellipse function containing n separated quadratic terms. Next, the problem is decomposed into m equal-size separable programming problems solvable by a distributed computation system composed of m personal computers linked via the Internet. The numerical examples illustrate that the proposed method can obtain the global optimum effectively for large scale portfolio problems involving integral variables.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

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.