Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

Global Optimization of Nonconvex Polynomial Programming Problems Having Rational Exponents

This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.     

An Efficient Algorithm for Quadratic Sum-of-Ratios Fractional Programs Problem

The quadratic sum-of-ratios fractional program problem has a broad range of applications in practical problems. This article will present an e?cient branch-and-bound algorithm for globally solving the quadratic sum-of-ratios fractional program problem. In this algorithm, lower bounds are computed by solving a series of parametric relaxation linear programming problems, which are established by utilizing new parametric linearizing technique. To enhance the computational speed of the proposed algorithm, a rectangle reducing tactic is used to reject a part of the investigated rectangle or the whole rectangle where there does not contain any global optimal solution of the quadratic sum-of-ratios fractional program problem. Compared with the known approaches, the proposed algorithm does not need to introduce new variables and constraints. Therefore, the proposed algorithm is more suitable for application in engineering.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Strongly polynomial algorithm for solving the general problem of least modules

An algorithm of polynomial algebraic complexity (a strongly polynomial algorithm) for solving the classical problem of mathematical programming on minimizing the weighted sum of modules of part of variables with linear constraints (equalities imposed on all variables) is substantiated. The algorithm is given in its explicit form. The complexity of the algorithm is estimated. A simulation is performed.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

Sequential Semidefinite Program for Maximum Robustness Design of Structures under Load Uncertainty

A robust structural optimization scheme as well as an optimization algorithm are presented based on the robustness function. Under the uncertainties of the external forces based on the info-gap model, the maximization of the robustness function is formulated as an optimization problem with infinitely many constraints. By using the quadratic embedding technique of uncertainty and the S-procedure, we reformulate the problem into a nonlinear semidefinite programming problem. A sequential semidefinite programming method is proposed which has a global convergent property. It is shown through numerical examples that optimum designs of various linear elastic structures can be found without difficulty.The authors are grateful to the Associate Editor and two anonymous referees for handling the paper efficiently as well as for helpful comments and suggestions.     

On boundedness of (quasi-)convex integer optimization problems

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained integer problem is nonempty over any subset of .     

Linear polynomial constraints inferencing algorithm

This paper propose the inference mechanism for handling linear polynomial constraints called consistency checking algorithm based on the feasibility checking algorithm borrowed from linear programming. In contrast with other approaches, proposed algorithm can efficiently and coherented by linear polynomial forms. The developed algorithm is successfully applied to the symbolic simulation that offers a convenient means to conduct multiple, simultaneous exploration of model behaviors.     

Dual estimates in multiextremal problems

We propose a technique of improving the dual estimates in nonconvex multiextremal problems of mathematical programming, by adding some additional constraints which are the consequences of the original constraints. This technique is used for the problems of finding the global minimum of polynomial functions, and extremal quadratic and boolean quadratic problems. In the article one ecological multiextremal problem and an algorithm for finding the dual estimate for it also considered. This algorithm is based upon a scheme of decomposition and nonsmooth optimization methods.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A heuristic algorithm for a pseudo-cyclic delivery problem under window constraints

The scheduling problem for pseudo-cyclic deliveries under window constraints is presented. The problem is formulated as a linear integer programming problem, where the objective function represented the minimization of the centralized supplier capacity needed to satisfy all user requests over a discretized planning horizon of infinite length. A heuristic algorithm running in polynomial time is illustrated and an experimental analysis of its efficiency is presented.     

Inventory control and pricing for perishable products under age and price dependent stochastic demand

Multistage stochastic programming (SP) with both endogenous and exogenous uncertainties is a novel problem in which some uncertain parameters are decision-dependent and others are independent of decisions. The main difficulty of this problem is that nonanticipativity constraints (NACs) make up a significantly large constraint set, growing very fast with the number of scenarios and leading to an intractable model. Usually, a lot of these constraints are redundant and hence, identification and elimination of redundant NACs can cause a significant reduction in the problem size. Recently, a polynomial time algorithm has been proposed in the literature which is able to identify all redundant NACs in an SP problem with only endogenous uncertainty. In this paper, however, we extend the algorithm proposed in the literature and present a new method which is able to make the upper most possible reduction in the number of NACs in any SP with both exogenous and endogenous uncertain parameters. Proving the validity of this method is another innovation of this study. Computational results confirm that the proposed approach can significantly reduce the problem size within a reasonable computation time.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

Semidefinite relaxations for semi-infinite polynomial programming

This paper studies how to solve semi-infinite polynomial programming (SIPP) problems by semidefinite relaxation methods. We first recall two SDP relaxation methods for solving polynomial optimization problems with finitely many constraints. Then we propose an exchange algorithm with SDP relaxations to solve SIPP problems with compact index set. At last, we extend the proposed method to SIPP problems with noncompact index set via homogenization. Numerical results show that the algorithm is efficient in practice.     

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

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

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

On the computational complexity of a merge recognition problem

A problem arising from the work of C.A.R. Hoare on parallel programming is that of deciding whether a given string ? is a “merge” of two other given strings σ and τ. We describe a polynomial time algorithm for this problem. This algorithm can easily be extended to check, in polynomial time, whether ? is a merge of any fixed number of strings. The problem for an arbitrary number of strings is shown to be NP-complete and so is unlikely to have a polynomial time algorithm.     

The min-Knapsack problem with compactness constraints and applications in statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.     

A new approach to the weighted peak-constrained least-square error FIR digital filter optimal design problem

This paper deals with the design of linear-phase finite impulse response (FIR) digital filters using weighted peak-constrained least-squares (PCLS) optimization. The PCLS error design problem is formulated as a quadratically constrained quadratic semi-infinite programming problem. An exchange algorithm with a new exchange rule is proposed to solve the problem. The algorithm provides the approximate optimal solution after a finite number of iterations. In particular, the subproblem solved at each iteration is a quadratically constrained quadratic programming. We can rewrite it as a conic optimization problem solvable in polynomial time. For illustration, numerical examples are solved using the proposed algorithm.