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.     

Second order algorithms for the posynomial geometric programming dual,part I: Analysis

In this paper we analyse algorithms for the geometric dual of posynomial programming problems, that make explicit use of second order information. Out of two possible approaches to the problem, it is shown that one is almost always superior. Interestingly enough, it is the second, inferior approach that has dominated the geometric programming literature.This work was partially supported by the National Research Council of Canada, Grant A3552 and National Science Foundation Grant ENG78-21615.Earlier versions of this paper were presented at the Optimization Days Conference in Montreal (May 1976) and the TIMS meeting in Athens (July 1977).     

On the computational utility of posynomial geometric programming solution methods

Ten codes or code variants were used to solve the five equivalent posynomial GP problem formulations. Four of these codes were general NLP codes; six were specialized GP codes. A total of forty-two test problems was solved with up to twenty randomly generated starting points per problem. The convex primal formulation is shown to be intrinsically easiest to solve. The general purpose GRG code called OPT appears to be the most efficient code for GP problem solution. The reputed superiority of the specialized GP codes GGP and GPKTC appears to be largely due to the fact that these codes solve the convex primal formulation. The dual approaches are only likely to be competitive for small degree of difficulty, tightly constrained problems.     

A general theory of dual optimization problems. II: On the perturbational dual problem corresponding to an unperturbational dual problem

Distinguishing between a problem and its instances, we redefine the perturbational dual problem corresponding to an unperturbational dual problem, by means of explicit formulas, instead of the scheme of formal replacements of [15]. We show the relations between some main perturbational dual problems and the perturbational dual problems corresponding to some main unperturbational dual problems.Invited talk at the 12 Symposium on Operations Research, Passau, September 1987.     

A dual perturbation view of linear programming

Solving standard-form linear prograrns via perturbation of the primal objective function has received much attention recently. In this paper, we investigate a new perturbation scheme which obtains a dual optimal solution by perturbing the dual feasible domain under different norms. A dual-to-primal conversion formula is also provided. We show that this new perturbation scheme actually generalizes the primal entropic perturbation approach to linear programming.Partially sponsored by the North Carolina Supercomputing Center 1994 Cray Research Grant and the National Textile Center Research Grant.     

The complementary unboundedness of dual feasible solution sets in convex programming

F.E. Clark has shown that if at least one of the feasible solution sets for a pair of dual linear programming problems is nonempty then at least one of them is both nonempty and unbounded. Subsequently, M. Avriel and A.C. Williams have obtained the same result in the more general context of (prototype posynomial) geometric programming. In this paper we show that the same result is actually false in the even more general context of convex programming — unless a certain regularity condition is satisfied.We also show that the regularity condition is so weak that it is automatically satisfied in linear programming (prototype posynomial) geometric programming, quadratic programming (with either linear or quadratic constraints),l _p -regression analysis, optimal location, roadway network analysis, and chemical equilibrium analysis. Moreover, we develop an equivalent regularity condition for each of the usual formulations of duality.Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant Number AFOSR-73-2516.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

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.     

A perturbation approach to the main duality theorem of quadratic geometric programming

Quadratic geometric programming as introduced by Hough and Goforth is an extension of posynomial geometric programming. By using the theory of generalized geometric programming, Jefferson and Scott defined its exact geometric dual. The fundamental relationship between the geometric dual and the original problem is that they assume a common value at their respective optima. This result formally stated as the main duality theorem is proved in this paper by using a dual perturbation approach and two simple geometric inequalities. As a by-product, the insight provided by this constructive proof establishes a numerically precise dual based solution procedure for quadratic geometric programs.

---

Zusammenfassung Die quadratische geometrische Optimierung wurde von Hough und Goforth eingeführt und stellt eine Erweiterung der posynomialen geometrischen Optimierung dar. Jefferson und Scott definierten unter Verwendung der verallgemeinerten geometrischen Optimierung ein duales Programm und leiteten Dualitätsbeziehungen ab, u. a. die Übereinstimmung der Optimalwerte des primalen und dualen Programms. Letzteres Resultat wird in der vorliegenden Arbeit unter Verwendung eines dualen Störproblems und zweier einfachen geometrischen Ungleichungen hergeleitet. Gleichzeitig macht die Beweismethode es möglich, ein Verfahren zur Lösung quadratischer geometrischer Optimierungsprobleme anzugeben.

     

On solving optimization problems with proportion-constraints

The purpose of this paper is to establish sufficient conditions for the existence of solutions to mathematical programs where the variables of the solution satisfy given proportions. These conditions rely on convergence properties of powers of nonnegative matrices when these powers form a bounded sequence. We assume that if an arbitrary vectorx is premultiplied by elements of this sequence, the limit of the sequence (which might be a Cesaro (C, 1) limit) gives an improvement of the objective.This research was supported by NSF Grants ENG 76-15599 and ENG76-12266 and ONR Contract N00014-75-C-0493.     

A global quadratic algorithm for solving a system of mixed equalities and inequalities

A new algorithm is proposed which, under mild assumptions, generates a sequence{x _i } that starting at any point inR ⁿ will converge to a setX defined by a mixed system of equations and inequalities. Any iteration of the algorithm requires the solution of a linear programming problem with relatively few constraints. By only assuming that the functions involved are continuously differentiable a superlinear rate of convergence is achieved. No convexity whatsoever is required by the algorithm.     

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.     

Hanson's duality theorem in nonsmooth programming

A nonlinear program with inequality and equality constraints, generated by lipschitzian functions in a real Banach space is considered. The sufficiency of the Kuhn-Tucker optimality conditions at a point is established, using the function subdifferentials which generate the program. Also. in nonsmooth frame, Hanson's converse duality theorem from the convex programming is generalized     

Comparative computer results of a new complementary pivot algorithm for solving equality and inequality constrained optimization problems

This paper reports the development of a new algorithm for solving the general constrained optimization problem (that of optimizing an objective function subject to both equality and inequality constraints). The approach is based on the complementary pivoting algorithms which have been developed to solve certain classes of fixed point problems. The specific approach is to use the equality constraints to solve for some variables in terms of the remaining ones thus enabling one to eliminate the equality constraints altogether. The result, under certain circumstances, is an optimization problem which may be transformed into a fixed point problem in such a way that a complementary pivoting code may be used to search for a solution.Seventeen test problems have been solved by this method and the results are compared against those obtained from GRG (Generalized Reduced Gradient method). The results of the tests indicate that the fixed point approach is robust (all 17 problems were solved by this method where as GRG solved 16). As to the computer times, the fixed point code proved to be as fast or faster than GRG on the lower dimensional problems; however, as the dimension increased, the trend reversed and on a 40 dimensional problem GRG was approximately 11 times faster. The conclusion from these tests is that when the dimension of the original problem can be reduced sufficiently by the equality constraints, the fixed point approach appears to be more effective than GRG.     

Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach

We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature. This work is supported by National Science Foundation grants DMI-0217190 and DMI-0355433.     

Improved algorithm for mixed-integer quadratic programs and a computational study

In a recent paper [6] we suggested an algorithm for solving complicated mixed-integer quadratic programs, based on an equivalent formulation that employs a nonsingular transformation of variables. The objectives of the present paper are two. First, to present an improved version of this algorithm, which reduces substantially its computational requirements; second, to report on the results of a computational study with the revised algorithm.     

A polynomially bounded algorithm for a singly constrained quadratic program

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.     

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.     

Generalized capacities in linear programming

Within the framework of linear programming in paired spaces (Duffin, Kretschmer) we introduce quantities which are analogs of direct and adjoint capacity in potential theory (Ohtsuka), and we give conditions for these quantities to be equal     

A dual differentiable exact penalty function

A new penalty function is associated with an inequality constrained nonlinear programming problem via its dual. This penalty function is globally differentiable if the functions defining the original problem are twice globally differentiable. In addition, the penalty parameter remains finite. This approach reduces the original problem to a simple problem of maximizing a globally differentiable function on the product space of a Euclidean space and the nonnegative orthant of another Euclidean space. Many efficient algorithms exist for solving this problem. For the case of quadratic programming, the penalty function problem can be solved effectively by successive overrelaxation (SOR) methods which can handle huge problems while preserving sparsity features. Sponsored by the United States Army under Contract No. DAAG 29-80-C-0041. This material is based upon work supported by the National Science Foundation under Grants No. MCS-790166 and ENG-7903881.