Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

Decomposition Branch-and-Bound Based Algorithm for Linear Programs with Additional Multiplicative Constraints

This article presents an algorithm for globally solving a linear program (P) that contains several additional multiterm multiplicative constraints. To our knowledge, this is the first algorithm proposed to date for globally solving Problem (P). The algorithm decomposes the problem to obtain a master problem of low rank. To solve the master problem, the algorithm uses a branch-and-bound scheme where Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems in the algorithm are ordinary linear programs. Convergence of the algorithm is shown and a solved sample problem is given.     

Global Optimization Algorithm for the Nonlinear Sum of Ratios Problem

This article presents a branch-and-bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm economizes the required computations by conducting the branch-and-bound search in ^p, rather than in ⁿ, where p is the number of ratios in the objective function of problem (P) and n is the number of decision variables in problem (P). To implement the algorithm, the main computations involve solving a sequence of convex programming problems for which standard algorithms are available.     

Global Minimization via Piecewise-Linear Underestimation

Given a function on Rⁿ with many multiple local minima we approximate it from below, via concave minimization, with a piecewise-linear convex function by using sample points from the given function. The piecewise-linear function is then minimized using a single linear program to obtain an approximation to the global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.57%, of the global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly.     

Sufficient Optimality Criterion for Linearly Constrained,Separable Concave Minimization Problems

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive.In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution.The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.This research was supported by a Bolyai János Research Fellowship BO/00334/00 of the Hungarian Academy of Science and by the Hungarian Scientific Research Foundation, Grant OTKA T038027.     

A Branch-and-Bound Algorithm for Concave Network Flow Problems

In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.     

A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization

Based on a review of existing algorithms, a general branch-and-bound concept in global optimization is presented. A sufficient and necessary convergence condition is established, and a broad class of realizations is derived that include existing and several new approaches for concave minimization problems.     

A Simple Finite Cone Covering Algorithm for Concave Minimization

In 1964, in a seminal paper, Tuy proposed a simple algorithm for concave minimization over a polytope. This algorithm was shown to cycle some years later. Recently however it has been shown that despite this possibility of cycling, Tuy's algorithm always finds the optimal solution of the problem. We present a modification of it which simplifies the cycle detection.     

A Finite Branch-and-Bound Algorithm for Linear Multiplicative Programming

On the basis of Soland's rectangular branch-and-bound, we develop an algorithm for minimizing a product of p (2) affine functions over a polytope. To tighten the lower bound on the value of each subproblem, we install a second-stage bounding procedure, which requires O(p) additional time in each iteration but remarkably reduces the number of branching operations. Computational results indicate that the algorithm is practical if p is less than 15, both in finding an exact optimal solution and an approximate solution.     

解可分离约束双凹规划问题的一种外逼近方法[英文]

在本文中，我们提出了双凹规划问题和更一般的广义凹规划问题。我们给出了双凹规划问题的整体最优性条件，并构造了一个有限终止外逼近算法。     

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.     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

Treating Free Variables in Generalized Geometric Global Optimization Programs

Generalized geometric programming (GGP) problems occur frequently in engineering design and management. Recently, some exponential-based decomposition methods [Maranas and Floudas, 1997,Computers and Chemical Engineering 21(4), 351–370; Floudas et al., 1999 , Handbook of Test Problems in Local and Global Optimization, Kluwer Academic Publishers, Boston, pp. 5–105; Floudas, 2000 Deterministic Global Optimizaion: Theory, Methods and Application, Kluwer Academic Publishers, Boston, pp. 257–306] have been developed for GGP problems. These methods can only handle problems with positive variables, and are incapable of solving more general GGP problems. This study proposes a technique for treating free (i.e., positive, zero or negative) variables in GGP problems. Computationally effective convexification rules are also provided for signomial terms with three variables.     

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

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

An Algorithm of Global Optimization for Rational Functions with Rational Constraints

To solve a system of nonlinear equations, Wu wen-tsun introduced a new formative elimination method. Based on Wu's method and the theory of nonlinear programming, we here propose a global optimization algorithm for nonlinear programming with rational objective function and rational constraints. The algorithm is already programmed and the test results are satisfactory with respect to precision and reliability.     

A New Successive Partition Algorithm for Concave Minimization Based on Cone Decomposition and Decomposition Cuts

In this paper we propose a new partition algorithm for concave minimization. The basic structure of the algorithm resembles that of conical algorithms. However, we make extensive use of the cone decomposition concept and derive decomposition cuts instead of concavity cuts to perform the bounding operation. Decomposition cuts were introduced in the context of pure cutting plane algorithms for concave minimization and has been shown to be superior to concavity cuts in numerical experiments. Thus by using decomposition cuts instead of concavity cuts to perform the bounding operation, unpromising parts of the feasible region can be excluded from further explorations at an earlier stage. The proposed successive partition algorithm finds an -global optimal solution in a finite number of iterations.     

A Finite Algorithm for a Class of Nonlinear Multiplicative Programs

The nonconvex problem of minimizing the product of a strictly convex quadratic function and the p-th power of a linear function over a convex polyhedron is considered. Some theoretical properties of the problem, such as the existence of minimum points and the generalized convexity of the objective function, are deepened on and a finite algorithm which solves the problem is proposed.     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

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.