A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems

In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between the original and revised algorithms. The author was partially supported by the Grand-in-Aid for Scientific Research (C)(2) 15560048 from the Japan Society for the Promotion of Science.     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

An Adaptive Dual Parametrization Algorithm for Quadratic Semi-infinite Programming Problems

The so called dual parametrization method for quadratic semi-infinite programming (SIP) problems is developed recently for quadratic SIP problems with a single infinite constraint. A dual parametrization algorithm is also proposed for numerical solution of such problems. In this paper, we consider quadratic SIP problems with positive definite objective and multiple linear infinite constraints. All the infinite constraints are supposed to be continuously dependent on their index variable on a compact set which is defined by a number equality and inequalities. We prove that in the multiple infinite constraint case, the minimu parametrization number, just as in the single infinite constraint case, is less or equal to the dimension of the SIP problem. Furthermore, we propose an adaptive dual parametrization algorithm with convergence result. Compared with the previous dual parametrization algorithm, the adaptive algorithm solves subproblems with much smaller number of constraints. The efficiency of the new algorithm is shown by solving a number of numerical examples.     

一类不可微规划的多项式型算法

本文考虑了由教育最优投资问题导出的一类不可微规划，讨论了可行解是最优解的充要条件，在对乘子作某些假设下，利用Kuhu－Tucker定理给出了求解的一种多项式算法．     

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 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.     

Solving Posynomial Geometric Programming Problems via Generalized Linear Programming

This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer.     

基于松弛策略解半无限规划模型的显式修正算法

讨论了一类线性半无限最优规划模型的求解算法.采用松弛方法解其系列子问题LP(T_k)及DLP(T_k),基于松弛策略和在适当的假设条件下,提出了一个我们称之为显式算法的新型算法.新算法的主要改进之处是算法在每一步迭代计算时,允许丢弃一些不必要的约束.在这种方式下,算法避免了求解系列太大规模的子问题.最后,基于提出的显式修正算法,并与传统割平面方法和已有文献中的松弛修正算法、对同一问题作了初步的数值比较实验.     

几何规划问题的一种分枝定界方法

本文通过指数函数变换，把解几何规划GP（Ω）等价地转化为另外一个非线优化问题NLP（－↑Ω），根据问题（－↑Ω）的结构特征，构造它的一个线性规划松驰上确定它的最优值的一个下界，由此给出问题GP（Ω）的一个新的分枝定界算法。最后证明了这个算法是收敛的。     

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.     

求广义线性比试和问题全局解的新方法

为确定广义线性比式和规划问题(GFP)的全局最优解,提出一个新的分支定界方法.在算法中,分支过程采用单纯形对分规则,且界的估计通过一些线性规划问题的求解完成.给出算法的收敛性证明.数值试验结果显示算法是有效可行的.     

A Simplicial Branch-and-Bound Method for Solving Nonconvex All-Quadratic Programs

In this paper we present an algorithm for solving nonconvex quadratically constrained quadratic programs (all-quadratic programs). The method is based on a simplicial branch-and-bound scheme involving mainly linear programming subproblems. Under the assumption that a feasible point of the all-quadratic program is known, the algorithm guarantees an -approximate optimal solution in a finite number of iterations. Computational experiments with an implementation of the procedure are reported on randomly generated test problems. The presented algorithm often outperforms a comparable rectangular branch-and-bound method.     

Semismooth Newton Methods for Solving Semi-Infinite Programming Problems

In this paper we present some semismooth Newton methods for solving the semi-infinite programming problem. We first reformulate the equations and nonlinear complementarity conditions derived from the problem into a system of semismooth equations by using NCP functions. Under some conditions a solution of the system of semismooth equations is a solution of the problem. Then some semismooth Newton methods are proposed for solving this system of semismooth equations. These methods are globally and superlinearly convergent. Numerical results are also given.     

Optimality and Duality for a Class of Nondifferentiable Multiobjective Fractional Programming Problems

In this paper, we consider a class of nondifferentiable multiobjective fractional programs in which each component of the objective function contains a term involving the support function of a compact convex set. We establish necessary and sufficient optimality conditions and duality results for weakly efficient solutions of nondifferentiable multiobjective fractional programming problems. This work was supported by Grant R01-2003-000-10825-0 from the Basic Research Program of KOSEF.     

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.     

一类特殊多项式整数规划问题的最优化算法

本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用,并且是NP难问题。对于这类问题,最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先,利用最优性必要条件,我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数,设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。     

A Global Optimization Method for Solving Convex Quadratic Bilevel Programming Problems

We use the merit function technique to formulate a linearly constrained bilevel convex quadratic problem as a convex program with an additional convex-d.c. constraint. To solve the latter problem we approximate it by convex programs with an additional convex-concave constraint using an adaptive simplicial subdivision. This approximation leads to a branch-and-bound algorithm for finding a global optimal solution to the bilevel convex quadratic problem. We illustrate our approach with an optimization problem over the equilibrium points of an n-person parametric noncooperative game.     

Cutting Plane Algorithms for Nonlinear Semi-Definite Programming Problems with Applications

We will propose an outer-approximation (cutting plane) method for minimizing a function f X subject to semi-definite constraints on the variables XR ⁿ. A number of efficient algorithms have been proposed when the objective function is linear. However, there are very few practical algorithms when the objective function is nonlinear. An algorithm to be proposed here is a kind of outer-approximation(cutting plane) method, which has been successfully applied to several low rank global optimization problems including generalized convex multiplicative programming problems and generalized linear fractional programming problems, etc. We will show that this algorithm works well when f is convex and n is relatively small. Also, we will provide the proof of its convergence under various technical assumptions.     

A Tabu Search Based Approach for Solving a Class of Bilevel Programming Problems in Chemical Engineering

In this paper an approach based on the tabu search paradigm to tackle the bilevel programming problems is presented. The algorithm has been tested for a number of benchmark problems and the results obtained show superiority of the approach over the conventional methods in solving such problems.