Sensitivity analysis in geometric programming: Theory and computations

This paper surveys the main developments in the area of sensitivity analysis for geometric programming problems, including both the theoretical and computational aspects. It presents results which characterize solution existence, continuity, and differentiability properties for primal and dual geometric programs as well as the optimal value function differentiability properties for primal and dual programs. It also provides an overview of main computational approaches to sensitivity analysis in geometric programming which attempt to estimate new optimal solutions resulting from perturbations in some problem parameters.     

Composite geometric programming

Geometric programming is based on functions called posynomials, the terms of which are log-linear. This class of programs is extended from the composition of an exponential and a linear function to an exponential and a convex function. The resulting duality theory for composite geometric programs retains many of the qualities of geometric programming duality, while at the same time encompassing new areas of application. As an application, composite geometric programming is applied to exponential geometric programming. A pure dual is developed for the first time and used to solve a problem from the literature.This research was supported by the Air Force Office of Scientific Research, Grant No. AFOSR-83-0234.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Transcendental geometric programs

This paper treats a class of posynomial-like functions whose variables may appear also as exponents or in logarithms. It is shown that the resulting programs, called transcendental geometric programs, retain many useful properties of ordinary geometric programs, although the new class of problems need not have unique minima and cannot, in general, be transformed into convex programs. A duality theory, analogous to geometric programming duality, is formulated under somewhat more restrictive conditions. The dual constraints are not all linear, but the notion ofdegrees of difficulty is maintained in its geometric programming sense. One formulation of the dual program is shown to be a generalization of the chemical equilibrium problem where correction factors are added to account for nonideality. Some of the computational difficulties in solving transcendental programs are discussed briefly.This research was partially supported by the National Institute of Health Grant No. GM-14789; Office of Naval Research under Contract No. N00014-75-C-0276; National Science Foundation Grant No. MPS-71-03341 A03; and the US Atomic Energy Commission Contract No. AT(04-3)-326 PA #18.     

A computational study of methods for solving polynomial geometric programs

A computational comparison of several methods for dealing with polynomial geometric programs is presented. Specifically, we compare the complementary programs of Avriel and Williams (Ref. 1) with the reversed programs and the harmonic programs of Duffin and Peterson (Refs. 2, 3). These methods are used to generate a sequence of posynomial geometric programs which are solved using a dual algorithm.The authors would like to acknowledge the helpful comments of the referees. Also, they would like to acknowledge the programming assistance of Mr. S. N. Wong of The Pennsylvania State University. The first author's research was supported in part by a Research Initiation Grant awarded through The Pennsylvania State University.     

Optimality conditions for directionally differentiable multi-objective programming problems

This paper is concerned with the optimality for multi-objective programming problems with nonsmooth and nonconvex (but directionally differentiable) objective and constraint functions. The main results are Kuhn-Tucker type necessary conditions for properly efficient solutions and weakly efficient solutions. Our proper efficiency is a natural extension of the Kuhn-Tucker one to the nonsmooth case. Some sufficient conditions for an efficient solution to be proper are also given. As an application, we derive optimality conditions for multi-objective programming problems including extremal-value functions.This work was done while the author was visiting George Washington University, Washington, DC.     

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.     

Sensitivity analysis in geometric programming

A unified approach to computing first, second, or higher-order derivatives of any of the primal and dual variables or multipliers of a geometric programming problem, with respect to any of the problem parameters (term coefficients, exponents, and constraint right-hand sides) is presented. Conditions under which the sensitivity equations possess a unique solution are developed, and ranging results are also derived. The analysis for approximating second and higher-order sensitivity generalizes to any sufficiently smooth nonlinear program.     

Stochastic semidefinite programming: a new paradigm for stochastic optimization

Semidefinite programs are a class of optimization problems that have been studied extensively during the past 15 years. Semidefinite programs are naturally related to linear programs, and both are defined using deterministic data. Stochastic programs were introduced in the 1950s as a paradigm for dealing with uncertainty in data defining linear programs. In this paper, we introduce stochastic semidefinite programs as a paradigm for dealing with uncertainty in data defining semidefinite programs.The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465. The material in this paper is part of the doctoral dissertation of this author in preparation at Washington State University.     

Posynomial geometric programming with interval exponents and coefficients

Geometric programming provides a powerful tool for solving nonlinear problems where nonlinear relations can be well presented by an exponential or power function. In the real world, many applications of geometric programming are engineering design problems in which some of the problem parameters are estimates of actual values. This paper develops a solution method when the exponents in the objective function, the cost and the constraint coefficients, and the right-hand sides are imprecise and represented as interval data. Since the parameters of the problem are imprecise, the objective value should be imprecise as well. A pair of two-level mathematical programs is formulated to obtain the upper bound and lower bound of the objective values. Based on the duality theorem and by applying a variable separation technique, the pair of two-level mathematical programs is transformed into a pair of ordinary one-level geometric programs. Solving the pair of geometric programs produces the interval of the objective value. The ability of calculating the bounds of the objective value developed in this paper might help lead to more realistic modeling efforts in engineering optimization areas.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

Deriving an unconstrained convex program for linear programming

Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.     

Profit maximization with quantity discount: An application of geometric programming

Profit maximization is an important issue to the firms that pursue the largest economic profit possible. Traditionally, profit maximization problem is solved by differentiating with respect to input prices. The total differentiation of the first-order conditions might give complicated equations difficult to handle. Different from traditional studies, this paper considers input quantity discount and employs geometric programming technique to derive the objective value for the profit-maximization problem. The geometric programming approach not only gives the global optimum solution but also provides the information that is able to discover the relationship between profit maximization and returns to scale in the solution process. No differentiation is required. Moreover, geometric programming can provide a computationally attractive view of sensitivity analysis for the changes in parameters. Examples are given to illustrate the idea proposed in this paper.     

Solving geometric programs using GRG: Results and comparisons

This paper describes the performance of a general-purpose GRG code for nonlinear programming in solving geometric programs. The main conclusions drawn from the experiments reported are: (i) GRG competes well with special-purpose geometric programming codes in solving geometric programs; and (ii) standard time, as defined by Colville, is an inadequate means of compensating for different computing environments while comparing optimization algorithms.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865, the US Energy Research and Development Administration, Contract No. E(04-3)-326 PA-18, and the National Science Foundation, Grant No. DCR75-04544 at Stanford University; and by the Office of Naval Research under Contract No. N00014-75-C-0240, and the National Science Foundation, Grant No. SOC74-23808, at Case Western Reserve University.     

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.     

Conjugate duality for fractional programs

A very powerful approach to duality in mathematical programming is the theory of generalised geometric programming. Here we exploit this theory to develop a duality theory for fractional programs. All previous work on duality for such programs uses Lagrangian ideas.     

基于广义几何规划的最小广义信息密度区分问题及其对偶理论

§ 1　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｑｕａｄｒａｔｉｃａｌｌｙｃｏｎｓｔｒａｉｎｅｄａｎｄｅｎｔｒｏｐｙｄｅｎｓｉｔｙｃｏｎｓｔｒａｉｎｅｄｑｕａｄｒａｔｉｃｐｒｏｇｒａｍｔｈａｔｉｓｇｏｉｎｇｔｏｂｅｓｔｕｄｉｅｄｉｎｔｈｉｓｐａｐｅｒｉｓｃｈａｒａｃｔｅｒｉｚｅｄａｓｔｈｅｆｏｌｌｏｗｉｎｇｆｏｒｍ :Ｐｒｏｇｒａｍ (Ｑ)(Ｑ)　　ｍｉｎ　Ｑ0 (ｚ)ｓ .ｔ .　Ｐｊ(ｚ)≤ 0 ,　ｊ =1 ,2 ,...,ｌ,Ｑｉ(ｚ) ≤ 0 ,　ｉ =1 ,2 ,...,ｒ ,ｚ=(ｚ1,...,ｚｎ) Ｔ ≥ 0 ,ｗｈｅｒｅＰｊ(ｚ) = ｎｋ =1ｚｋｌｏｇ ｚｋｅ…     

Lifting inequalities: a framework for generating strong cuts for nonlinear programs

In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs. The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the problem.      

Parametric methods in integer linear programming

In contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm.The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization.