手数约束和凹交易费下的离散投资组合模型及算法

本文建立带手数约束和凹交易费的离散投资组合模型,给出求解该模型的一种精确算法。该算法是一个基于拉格朗日松弛和次梯度对偶搜索的分枝定界算法。为测试算法的有效性,用随机产生的数据对模型进行数值实验。作为其应用,用沪深300指数的真实数据实证检验该模型,并与不含交易费用的离散投资组合模型进行数值比较分析。数值分析表明算法能在合理的时间内给出模型的投资组合策略, 对解决中小规模的离散投资组合问题是有效的。     

凹整数规划的分枝定界解法

凹整数规划是一类重要的非线性整数规划问题，也是在经济和管理中有着广泛应用的最优化问题．本文主要研究用分枝定界方法求解凹整数规划问题，这一方法的基本思想是对目标函数进行线性下逼近，然后用乘子搜索法求解连续松弛问题．数值结果表明，用这种分枝定界方法求解凹整数规划是有效的．     

A new global optimization method for univariate constrained twice-differentiable NLP problems

In this paper, a new global optimization method is proposed for an optimization problem with twice-differentiable objective and constraint functions of a single variable. The method employs a difference of convex underestimator and a convex cut function, where the former is a continuous piecewise concave quadratic function, and the latter is a convex quadratic function. The main objectives of this research are to determine a quadratic concave underestimator that does not need an iterative local optimizer to determine the lower bounding value of the objective function and to determine a convex cut function that effectively detects infeasible regions for nonconvex constraints. The proposed method is proven to have a finite ε-convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering method, the index branch-and-bound algorithm, which uses the Lipschitz constant.     

Nonlinear robust optimization via sequential convex bilevel programming

In this paper, we present a novel sequential convex bilevel programming algorithm for the numerical solution of structured nonlinear min–max problems which arise in the context of semi-infinite programming. Here, our main motivation are nonlinear inequality constrained robust optimization problems. In the first part of the paper, we propose a conservative approximation strategy for such nonlinear and non-convex robust optimization problems: under the assumption that an upper bound for the curvature of the inequality constraints with respect to the uncertainty is given, we show how to formulate a lower-level concave min–max problem which approximates the robust counterpart in a conservative way. This approximation turns out to be exact in some relevant special cases and can be proven to be less conservative than existing approximation techniques that are based on linearization with respect to the uncertainties. In the second part of the paper, we review existing theory on optimality conditions for nonlinear lower-level concave min–max problems which arise in the context of semi-infinite programming. Regarding the optimality conditions for the concave lower level maximization problems as a constraint of the upper level minimization problem, we end up with a structured mathematical program with complementarity constraints (MPCC). The special hierarchical structure of this MPCC can be exploited in a novel sequential convex bilevel programming algorithm. We discuss the surprisingly strong global and locally quadratic convergence properties of this method, which can in this form neither be obtained with existing SQP methods nor with interior point relaxation techniques for general MPCCs. Finally, we discuss the application fields and implementation details of the new method and demonstrate the performance with a numerical example.     

Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and D.C. Optimization problems

A general branch-and-bound conceptual scheme for global optimization is presented that includes along with previous branch-and-bound approaches also grid-search techniques. The corresponding convergence theory, as well as the question of restart capability for branch-and-bound algorithms used in decomposition or outer approximation schemes are discussed. As an illustration of this conceptual scheme, a finite branch-and-bound algorithm for concave minimization is described and a convergent branch-and-bound algorithm, based on the previous one, is developed for the minimization of a difference of two convex functions.     

Hybrid Flow-Shop: a Memetic Algorithm Using Constraint-Based Scheduling for Efficient Search

The paper considers the hybrid flow-shop scheduling problem with multiprocessor tasks. Motivated by the computational complexity of the problem, we propose a memetic algorithm for this problem in the paper. We first describe the implementation details of a genetic algorithm, which is used in the memetic algorithm. We then propose a constraint programming based branch-and-bound algorithm to be employed as the local search engine of the memetic algorithm. Next, we present the new memetic algorithm. We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm, constraint programming based branch-and-bound algorithm, and memetic algorithm) in terms of both the quality of the solutions produced and the efficiency. These results demonstrate that the memetic algorithm produces better quality solutions and that it is very efficient.     

Finite Exact Branch-and-Bound Algorithms for Concave Minimization over Polytopes

In this paper simplicial branch-and-bound algorithms for concave minimization problems are discussed. Some modifications of the basic algorithm are presented, mainly consisting in rules to start local searches, introduction of cuts and updates of the original objective function. While some of these tools are not new in the literature, it is the first time, to the authors' knowledge, that they are used to guarantee the finiteness of a simplicial branch-and-bound approach.     

A branch-and-bound algorithm for solving a fixed charge problem in the profit optimization of sawn timber production

This paper deals with the problem of profit optimization in sawn timber production, utilizing a special type of sawmill. Expected rejects and resetting costs are taken into consideration. The present problem is formulated as a fixed charge linear programming problem involving identical fixed charges, one equality constraint and explicit bounds on the variables. Based on the greedy sorting of the variables we develop a branch-and-bound algorithm working on a special subset of all solutions. Through usage of the problem structure for constructing bounds we arrive at an acceptable CPU-time (on a 80386 personal computer) for practical purposes.     

A Lagrangian Based Branch-and-Bound Algorithm for Production-transportation Problems

We propose a branch-and-bound algorithm of Falk–Soland's type for solving the minimum cost production-transportation problem with concave production costs. To accelerate the convergence of the algorithm, we reinforce the bounding operation using a Lagrangian relaxation, which is a concave minimization but yields a tighter bound than the usual linear programming relaxation in O(mn log n) additional time. Computational results indicate that the algorithm can solve fairly large scale problems.     

A Finite Algorithm for Global Minimization of Separable Concave Programs

Researchers first examined the problem of separable concave programming more than thirty years ago, making it one of the earliest branches of nonlinear programming to be explored. This paper proposes a new algorithm that finds the exact global minimum of this problem in a finite number of iterations. In addition to proving that our algorithm terminates finitely, the paper extends a guarantee of finiteness to all branch-and-bound algorithms for concave programming that (1) partition exhaustively using rectangular subdivisions and (2) branch on the incumbent solution when possible. The algorithm uses domain reduction techniques to accelerate convergence; it solves problems with as many as 100 nonlinear variables, 400 linear variables and 50 constraints in about five minutes on an IBM RS/6000 Power PC. An industrial application with 152 nonlinear variables, 593 linear variables, and 417 constraints is also solved in about ten minutes.     

A branch-and-bound algorithm for maximizing the sum of several linear ratios

In this paper, we develop a branch-and-bound algorithm for maximizing a sum of p (slant2) linear ratios on a polytope. The problem is embedded into a 2p-dimensional space, in which a concave polyhedral function overestimating the optimal value is constructed for the bounding operation. The branching operation is carried out in a p-dimensional space, in a way similar to the usual rectangular branch-and-bound method. We discuss the convergence properties and report some computational results.     

On a Finite Branch and Bound Algorithm for the Global Minimization of a Concave Power Law Over a Polytope

In this paper, a finite branch-and-bound algorithm is developed for the minimization of a concave power law over a polytope. Linear terms are also included in the objective function. Using the first order necessary conditions of optimality, the optimization problem is transformed into an equivalent problem consisting of a linear objective function, a set of linear constraints, a set of convex constraints, and a set of bilinear complementary constraints. The transformed problem is then solved using a finite branch-and-bound algorithm that solves two convex problems at each of its nodes. The method is illustrated by means of an example from the literature.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems

In this paper, we develop a simplicial branch-and-bound algorithm for generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each bounding operation, we solve a linear programming problem whose constraints are exactly the same as the target problem. Although the lower bound worsens as a natural consequence, we offset this weakness by using an inexpensive bound tightening procedure based on Lagrangian relaxation. After giving a proof of the convergence, we report a numerical comparison with existing algorithms. T. Kuno was partially supported by the Grand-in-Aid for Scientific Research (C) 17560050 from the Japan Society for the Promotion of Sciences.     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.     

Decomposition approach for the global minimization of biconcave functions over polytopes

A decomposition approach is proposed for minimizing biconcave functions over polytopes. Important special cases include concave minimization, bilinear and indefinite quadratic programming for which new algorithms result. The approach introduces a new polyhedral partition and combines branch-and-bound techniques, outer approximation, and projection of polytopes in a suitable way.The authors are indebted to two anonymous reviewers for suggestions which have considerably improved this article.     

Global optimization of mixed-integer nonlinear programs: A theoretical and computational study

This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.The research was supported in part by ExxonMobil Upstream Research Company, National Science Foundation awards DMII 95-02722, BES 98-73586, ECS 00-98770, and CTS 01-24751, and the Computational Science and Engineering Program of the University of Illinois.