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.     

Yet another geometric programming dual algorithm

We describe an algorithm for the geometric programming dual problem which uses an adaptation of the generalized LP algorithm, proposed by Dantzig et al. twenty-five years ago for the chemical equilibrium problem, and show the slack primal constraints pose no numerical difficulties for this algorithm as they do for previous dual-based algorithms.     

On geometric programming and complementary slackness

When the terms in a convex primal geometric programming (GP) problem are multiplied by slack variables whose values must be at least unity, the invariance conditions may be solved as constraints in a linear programming (LP) problem in logarithmically transformed variables. The number of transformed slack variables included in the optimal LP basis equals the degree of difficulty of the GP problem, and complementary slackness conditions indicate required changes in associated GP dual variables. A simple, efficient search procedure is used to generate a sequence of improving primal feasible solutions without requiring the use of the GP dual objective function. The solution procedure appears particularly advantageous when solving very large geometric programming problems, because only the right-hand constants in a system of linear equations change at each iteration.The influence of J. G. Ecker, the writer's teacher, is present throughout this paper. Two anonymous referees and the Associate Editor made very helpful suggestions. Dean Richard W. Barsness provided generous support for this work.     

Geometric Algorithm for Multiparametric Linear Programming

We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems.     

Posynomial Parametric Geometric Programming with Interval Valued Coefficient

The article presents solution procedure of geometric programming with imprecise coefficients. We have considered problems with imprecise data as a form of an interval in nature. Many authors have solved the imprecise problem by geometric programming technique in a different way. In this paper, we introduce parametric functional form of an interval number and then solve the problem by geometric programming technique. The advantage of the present approach is that we get optimal solution of the objective function directly without solving equivalent transformed problems. Numerical examples are presented to support of the proposed approach.     

Optimal Replacement Planning by Geometric Programming

Geometric programming (GP) is suggested as an analytical toolfor solving replacement problems with infinite time horizon.The GP solution method is described and explained through theformulation and solution of a typical replacement problem. Asimple example is worked out to demonstrate the pint that GPhas potential as an appropriate mathematical tool for the analysisof certain types of replacement problems.     

Goal programming using multiple objective tabu search

Goal programming (GP) is one of the most commonly used mathematical programming tools to model multiple objective optimisation (MOO) problems. There are numerous MOO problems of various complexity modelled using GP in the literature. One of the main difficulties in the GP is to solve their mathematical formulations optimally. Due to difficulties imposed by the classical solution techniques there is a trend in the literature to solve mathematical programming formulations including goal programmes, using the modern heuristics optimisation techniques, namely genetic algorithms (GA), tabu search (TS) and simulated annealing (SA). This paper uses the multiple objective tabu search (MOTS) algorithm, which was proposed previously by the author to solve GP models. In the proposed approach, GP models are first converted to their classical MOO equivalent by using some simple conversion procedures. Then the problem is solved using the MOTS algorithm. The results obtained from the computational experiment show that MOTS can be considered as a promising candidate tool for solving GP models.     

Current state of the art of algorithms and computer software for geometric programming

This paper attempts to consolidate over 15 years of attempts at designing algorithms for geometric programming (GP) and its extensions. The pitfalls encountered when solving GP problems and some proposed remedies are discussed in detail. A comprehensive summary of published software for the solution of GP problems is included. Also included is a numerical comparison of some of the more promising recently developed computer codes for geometric programming on a specially chosen set of GP test problems. The relative performance of these codes is measured in terms of their robustness as well as speed of computation. The performance of some general nonlinear programming (NLP) codes on the same set of test problems is also given and compared with the results for the GP codes. The paper concludes with some suggestions for future research.An earlier version of this paper was presented at the ORSA/TIMS Conference, Chicago, 1975.This work was supported in part by the National Research Council of Canada, Grant No. A-3552, Canada Council Grant No. S74-0418, and a research grant from the School of Organization and Management, Yale University. The author wishes to thank D. Himmelblau, T. Jefferson, M. Rijckaert, X. M. Martens, A. Templeman, J. J. Dinkel, G. Kochenberger, M. Ratner, L. Lasdon, and A. Jain for their cooperation in making the comparative study possible.     

An Algorithm for Approximate Multiparametric Convex Programming

For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation of several optimization-based feedback control strategies.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

灰色正项几何规划研究

In the model of geometric programming, values of parameters cannot be gotten owing to data fluctuation and incompletion. But reasonable bounds of these parameters can be attained. This is to say, parameters of this model can be regarded as interval grey numbers. When the model contains grey numbers, it is hard for common programming method to solve them. By combining the common programming model with the grey system theory, and using some analysis strategies, a model of grey polynomial geometric programming, a model of θpositioned geometric programming and their quasi-optimum solution or optimum solution are put forward. At the same time, we also developed an algorithm for the problem. This approach brings a new way for the application research of geometric programming. An example at the end of this paper shows the rationality and feasibility of the algorithm.     

符号几何规划的一种分解方法

针对符号几何规划提出了一种直接的分解方法,将难于求解的符号几何规划问题等价地转化为一个非线性程度很低的可分离规划,为寻求困难度高且规模较大的符号几何规划问题的求解提供了一种方法,特别是经此方法分解后的每个子问题均易于求解,最后给出了数值实例,验证了此方法的有效性．     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

Comparison of a special-purpose algorithm with general-purpose algorithms for solving geometric programming problems

We study the performance of four general-purpose nonlinear programming algorithms and one special-purpose geometric programming algorithm when used to solve geometric programming problems. Experiments are reported which show that the special-purpose algorithm GGP often finds approximate solutions more quickly than the general-purpose algorithm GRG2, but is usually not significantly more efficient than GRG2 when greater accuracy is required. However, for some of the most difficult test problems attempted, GGP was dramatically superior to all of the other algorithms. The other algorithms are usually not as efficient as GGP or GRG2. The ellipsoid algorithm is most robust.This work was supported in part by the National Science Foundation, Grant No. MCS-81-02141.     

A new algorithm for geometric programming based on the linear structure of its dual problem

In this article, we present an algorithm for the resolution of a nonlinear optimization problem, concretely the posynomial geometric programming model. The solution procedure that we develop extends the condensation techniques for geometric programming, allowing us to find the optimal solutions to the dual geometric problems that we get from the interior of the corresponding feasible regions, in the line that interior point methods for linear programming work, which leads us to obtain considerable computational advantages with respect of the classical solution procedures.     

Dynamic Programming Method for Constrained Discrete-Time Optimal Control

A dynamic programming method is presented for solving constrained, discrete-time, optimal control problems. The method is based on an efficient algorithm for solving the subproblems of sequential quadratic programming. By using an interior-point method to accommodate inequality constraints, a modification of an existing algorithm for equality constrained problems can be used iteratively to solve the subproblems. Two test problems and two application problems are presented. The application examples include a rest-to-rest maneuver of a flexible structure and a constrained brachistochrone problem.     

广义几何规划的全局优化算法

对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性.     

整数规划的布谷鸟算法

布谷鸟搜索算法是一种新型的智能优化算法．本文采用截断取整的方法将基本布谷鸟搜索算法用于求解整数规划问题．通过对标准测试函数进行仿真实验并与粒子群算法进行比较,结果表明本文所提算法比粒子群算法拥有更好的性能和更强的全局寻优能力,可以作为一种实用方法用于求解整数规划问题．     

On solving the discrete location problems when the facilities are prone to failure

The classical discrete location problem is extended here, where the candidate facilities are subject to failure. The unreliable location problem is defined by introducing the probability that a facility may become inactive. The formulation and the solution procedure have been motivated by an application to model and solve a large size problem for locating base stations in a cellular communication network. We formulate the unreliable discrete location problems as 0–1 integer programming models, and implement an enhanced dual-based solution method to determine locations of these facilities to minimize the sum of fixed cost and expected operating (transportation) cost. Computational tests of some well-known problems have shown that the heuristic is efficient and effective for solving these unreliable location problems.