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.     

Sensitivity analysis in posynomial geometric programming

Sensitivity analysis results for general parametric posynomial geometric programs are obtained by utilizing recent results from nonlinear programming. Duality theory of geometric programming is exploited to relate the sensitivity results derived for primal and dual geometric programs. The computational aspects of sensitivity calculations are also considered.This work was part of the doctoral dissertation completed in the Department of Operations Research, George Washington University, Washington, DC. The author would like to express his gratitude to the thesis advisor, Prof. A. V. Fiacco, for overall guidance and stimulating discussions which inspired the development of this research work.     

A comparison of computational strategies for geometric programs

Numerous algorithms for the solution of geometric programs have been reported in the literature. Nearly all are based on the use of conventional programming techniques specialized to exploit the characteristic structure of either the primal or the dual or a transformed primal problem. This paper attempts to elucidate, via computational comparisons, whether a primal, a dual, or a transformed primal solution approach is to be preferred.The authors wish to thank Captain P. A. Beck and Dr. R. S. Dembo for making available their codes. This research was supported in part under ONR Contract No. N00014-76-C-0551 with Purdue University.     

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.     

Fenchel's duality theorem in generalized geometric programming

Fenchel's duality theorem is extended to generalized geometric programming with explicit constraints—an extension that also generalizes and strengthens Slater's version of the Kuhn-Tucker theorem.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

Generalized geometric programming applied to problems of optimal control: I. Theory

The interest in convexity in optimal control and the calculus of variations has gone through a revival in the past decade. In this paper, we extend the theory of generalized geometric programming to infinite dimensions in order to derive a dual problem for the convex optimal control problem. This approach transfers explicit constraints in the primal problem to the dual objective functional.The authors are indebted to the referees for suggestions leading to improvement of the paper.     

Generalized geometric programming applied to problems of optimal control: Part I,theory

A modification to the formulation in Ref. 1 is given.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

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.     

Dual to primal conversion in geometric programming

The aim of this paper is not to derive new results, but rather to provide insight that will hopefully aid researchers involved in the design and coding of algorithms for geometric programs. The main contributions made here are: (i) a computationally useful interpretation of the Lagrange multipliers associated with the dual orthogonality constraints, (ii) a computationally useful interpretation of the Lagrange multiplier associated with the dual normality constraint, and (iii) an analysis of the much-avoided issue of subsidiary problems.This work was supported in part by the National Research Council of Canada, Grant No. A3552.The author would like to acknowledge the contribution of an anonymous referee, whose constructive criticism led to this improved version of the original paper.     

On zero-degree stochastic geometric programs

The Mellin transform is used to encode randomness in the constraint and objective function coefficients using the substituted dual function. This enables one to obtain statistical moments and the probability distribution of the optimal objective valueZ*. Advantage is taken of the form of the dual function and the limiting property of the lognormal distribution to prove that the probability distribution ofZ* approximates the lognormal distribution, independent of the distribution of the parameters. This is of importance because those probability distributions are seldom known; even if they are, a derivation of the distribution ofZ* is apt to be elusive. Further, the larger the number of stochastic parameters in the geometric program, the more closely, in general, does the distribution ofZ* approximate the lognormal distribution. Illustrative examples are provided.Credit is due to Keith R. Weiss who developed the examples. The Office of Naval Research supported the work under Contract No. N000-14-75-C-0254.     

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.     

Scaling nonlinear programs

An automatic procedure for scaling the variables and constraints of a nonlinear optimization problem is proposed and tested. The procedure attempts to reduce the spread of element values of the problem Jacobian. Results obtained using a GRG code show that the proposed scaling method in not consistently successful. Ideas for future work are presented.     

Constrained duality via unconstrained duality in generalized geometric programming

A specialization of unconstrained duality (involving problems without explicit constraints) to constrained duality (involving problems with explicit constraints) provides an efficient mechanism for extending to the latter many important theorems that were previously established for the former.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

Optimality conditions in generalized geometric programming

Generalizations of the Kuhn-Tucker optimality conditions are given, as are the fundamental theorems having to do with their necessity and sufficiency.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

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.     

Saddle points and duality in generalized geometric programming

Extensions of the ordinary Lagrangian are used both in saddle-point characterizations of optimality and in a development of duality theory.This research was sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-73-2516.     

Global optimization of signomial geometric programming problems

This paper presents a global optimization approach for solving signomial geometric programming problems. In most cases nonconvex optimization problems with signomial parts are difficult, NP-hard problems to solve for global optimality. But some transformation and convexification strategies can be used to convert the original signomial geometric programming problem into a series of standard geometric programming problems that can be solved to reach a global solution. The tractability and effectiveness of the proposed successive convexification framework is demonstrated by seven numerical experiments. Some considerations are also presented to investigate the convergence properties of the algorithm and to give a performance comparison of our proposed approach and the current methods in terms of both computational efficiency and solution quality.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

Discrepancy of Certain Kronecker Sequences Concerning Transcendental Numbers

Let ω1,..., ωs be a set of real transcendental numbers satisfying a certain Diophantine inequality. The upper bound for the discrepancy of the Kronecker sequence （{nω1},..., {nωs}）（1 ≤ n ≤ N） is given. In particular, some low-discrepancy sequences are constructed.