Lineare Optimierung in halbgeordneten Vektorräumen

Summary The problem of linear programming in partially ordered vector spaces is formulated as an immediate generalization of the same problem in Euclidean spaces. Sufficient conditions for the existence of solutions of the problem and its dual are obtained. In the special case of function spaces the sufficient conditions for the solvability of the dual problem are satisfied if a certain regularity condition is assumed.

---

---

This research was supported by the Air Force Office of Scientific Research under grant AF-AFO SR-93 7-6 7     

Geometric programming with signomials

The difference of twoposynomials (namely, polynomials with arbitrary real exponents, but positive coefficients and positive independent variables) is termed asignomial.Each signomial program (in which a signomial is to be either minimized or maximized subject to signomial constraints) is transformed into an equivalent posynomial program in which a posynomial is to be minimized subject only to inequality posynomial constraints. The resulting class of posynomial programs is substantially larger than the class of (prototype)geometric programs (namely, posynomial programs in which a posynomial is to be minimized subject only to upper-bound inequality posynomial constraints). However, much of the (prototype) geometric programming theory is generalized by studying theequilibrium solutions to thereversed geometric programs in this larger class. Actually, some of this theory is new even when specialized to the class of prototype geometric programs. On the other hand, all of it can indirectly, but easily, be applied to the much larger class of well-posedalgebraic programs (namely, programs involving real-valued functions that are generated solely by addition, subtraction, multiplication, division, and the extraction of roots).This research was partially supported by Research Grant No. DA-AROD-31-124-6680 from the Army Research Office, Durham, North Carolina, and by a Summer Fellowship Grant from Northwestern University.     

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 optimality conditions for structured families of nonlinear programming problems

Optimality conditions for families of nonlinear programming problems inR ⁿ are studied from a generic point of view. The objective function and some of the constraints are assumed to depend on a parameter, while others are held fixed. Techniques of differential topology are used to show that under suitable conditions, certain strong second-order conditions are necessary for optimality except possibly for parameter values lying in a negligible set.Research sponsored, in part, by the Air Force Office of Scientific Research, under grants number 77-3204 and 79-0120.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

Bilinear separation of two sets inn-space

The NP-complete problem of determining whether two disjoint point sets in then-dimensional real spaceR ⁿ can be separated by two planes is cast as a bilinear program, that is minimizing the scalar product of two linear functions on a polyhedral set. The bilinear program, which has a vertex solution, is processed by an iterative linear programming algorithm that terminates in a finite number of steps a point satisfying a necessary optimality condition or at a global minimum. Encouraging computational experience on a number of test problems is reported.This material is based on research supported by Air Force Office of Scientific Research grant AFOSR-89-0410, National Science Foundation grant CCR-9101801, and Air Force Laboratory Graduate Fellowship SSN 531-56-2969.     

On solving a primal geometric program by partial dual optimization

The several published methods for mapping a dual solution estimate to a primal solution estimate in posynomial geometric programming provide no criteria for deciding how much deviation from primal feasibility, or discrepancy between the primal and dual objective function values, should be permitted before the primal solution estimate is accepted by the designer. This paper presents a new and simple dual-to-primal conversion method that uses the cost coefficients to provide a sound economic criterion for determining when to accept a primal solution estimate. The primal solution estimate generated is the exact solution to a modified primal obtained from the given primal by modifying the cost coefficients, with the exponent matrix left unchanged. The method is shown to have desirable properties when coupled with a convergent dual algorithm.     

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).     

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.     

Fuzzy正项几何规划的直接算法

将Fuzzy正项几何规划化的一变量有上、下界限制的Fuzzy正项几何规划,利用Fuzzy几何不等式,又将该变量有上、下界限制的Fuzzy正项几何规划化为单项Fuzzy正项几何规划,提出基于Fuzzy值集割平面法的两种直接算法,并通过一个数值例证实该方法的有效性。     

Geometric convergence of rational approximations toe −z in infinite sectors

Summary In this paper, we study the geometric convergence of rational approximations toe ^–z in infinite sectors symmetric about the positive real axis.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research CouncilResearch supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Atomic Energy Commission under Grant AT (11-1)-2075     

A bump triangular dynamic factorization algorithm for the simplex method

A dynamic factorization algorithm is developed which algebraically partitions the basis inverse in such a manner so that the simplex method can be executed from a series of small inverses and the basis itself. This partition is maintained dynamically so that the additional memory required to represent the basis inverse reduces to this series of small inverses for in-core implementations.The algorithm is intended for use in solving general large-scale linear programming problems. This new method of basis representation should permit rather large problems to be solved completely in-core.Preliminary computational experience is presented and comparisons are made with Reid's sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. The computational experience indicated that a significant reduction in memory requirements can usually be obtained using the dynamic factorization approach with only a slight (up to about 20%) degradation of execution time.This research was supported in part by the Air Force Office of Scientific Research, Air Force System Command, USAF, under AFOSR Contract/Grant Number AFOSR-74-2715.     

Sequential quadratic programming for certain parameter identification problems

We analyze the method of sequential quadratic programming for equality constrained minimization problems in Hilbert spaces of functions, and for the discrete approximations of such problems in the context of an elliptic parameter identification problem. We show how the discretization can be constructed so as to preserve the convergence behavior of the iterates for the infinite dimensional problem in the finite dimensional approximations. We use the structure of the parameter identification problem to reduce the size of the linear system for the SQP step and verify nondegeneracy of the constraints.Supported by National Science Foundation grants #DMS-8601139 and #DMS-8900410, and Air Force Office of Scientific Research grants #AFOSR-ISSA-860074, #AFOSR-ISSA-890044 and #AFOSR-89-0124.Supported by National Science Foundation grants #DMS-8619903, #DMS-8900984 and #ASC-8714009, and Air Force Office of Scientific Research grants #AFOSR-ISSA-870092 and #AFOSR-89-0124.     

Rough posynomial geometric programming

A rough posynomial geometric programming is put forward by the author. This model is advantageous for us to consider questions not only from the quantity of aspect, but from the quality because it contains more information than a traditional geometric programming one. Here, a rough convex function concept is advanced in rough value sets on foundation of rough sets and rough convex sets. Besides, a knowledge expression model in rough posynomial geometric programming is established and so is a mathematical one. Thirdly, solution properties are studied in mathematical model of rough posynomial geometric programming, and antinomy of the more-for-less paradox is solved with an arithmetic in rough posynomial geometric programming given, which can be changed into a rough linear programming after monomial rough posynomial geometric programming is solved. Finally, validity in model and algorithm is verified by examples.     

Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013. A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

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.     

Linear programming via a quadratic penalty function

We use quadratic penalty functions along with some recent ideas from linearl ₁ estimation to arrive at a new characterization of primal optimal solutions in linear programs. The algorithmic implications of this analysis are studied, and a new, finite penalty algorithm for linear programming is designed. Preliminary computational results are presented.Research supported by grant No. 11-0505 from the Danish Natural Science Research Council SNF.     

Adaptive Lanczos methods for recursive condition estimation

Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.Research supported by the US Air Force under grant no. AFOSR-88-0285.Research supported by the US Army under grant no. DAAL03-90-G-105.Research supported by the US Air Force under grant no. AFOSR-88-0285.     

Applications of the method of partial inverses to convex programming: Decomposition

A primal–dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.This research was sponsored, in part, by the Air Force Office of Scientific Research under grant 80-0195.     

A fixed-point representation of the generalized complementarity problem

Eaves and Kojima have separately provided fixed-point representations of the standard complementarity problem. Although the mappings used to describe their representations appear to be different, this paper shows they are essentially the same, a unification that is accomplished via a geometric programming argument in the context of a more general complementarity problem.The authors are indebted to Professor R. Saigal of Northwestern University for helpful discussions concerning this paper.This research was partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3134.