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.     

Modified geometric programming problem and its applications

In this paper, we propose unconstrained and constrained posynomial Geometric Programming (GP) problem with negative or positive integral degree of difficulty. Conventional GP approach has been modified to solve some special typer of GP problems. In specific case, when the degree of difficulty is negative, the normality and the orthogonality conditions of the dual program give a system of linear equations. No general solution vector exists for this system of linear equations. But an approximate solution can be determined by the least square and also max-min method. Here, modified form of geometric programming method has been demonstrated and for that purpose necessary theorems have been derived. Finally, these are illustrated by numerical examples and applications.     

Multi-choice goal programming with utility functions

Goal programming (GP) has been, and still is, the most widely used technique for solving multiple-criteria decision problems and multiple-objective decision problems by finding a set of satisfying solutions. However, the major limitation of goal programming is that can only use aspiration levels with scalar value for solving multiple objective problems. In order to solve this problem multi-choice goal programming (MCGP) was proposed by Chang (2007a). Following the idea of MCGP this study proposes a new concept of level achieving in the utility functions to replace the aspiration level with scalar value in classical GP and MCGP for multiple objective problems. According to this idea, it is possible to use the skill of MCGP with utility functions to solve multi-objective problems. The major contribution of using the utility functions of MCGP is that they can be used as measuring instruments to help decision makers make the best/appropriate policy corresponding to their goals with the highest level of utility achieved. In addition, the above properties can improve the practical utility of MCGP in solving more real-world decision/management problems.     

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.     

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.     

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.     

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.     

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.     

New method to posynomial geometric programming of trapezoidal fuzzy numbers

This paper presents a method for solving posynomial geometric programming with fuzzy coefficients. By utilizing comparison of fuzzy numbers with a method, the programming with fuzzy coefficients is reduced to the programming with constant coefficients. Then the programming with fuzzy coefficients can be solved by using a method for posynomial geometric programming. Finally, one comparative example is used to illustrate advantage of the new method.     

Genetic programming for feature construction and selection in classification on high-dimensional data

Classification on high-dimensional data with thousands to tens of thousands of dimensions is a challenging task due to the high dimensionality and the quality of the feature set. The problem can be addressed by using feature selection to choose only informative features or feature construction to create new high-level features. Genetic programming (GP) using a tree-based representation can be used for both feature construction and implicit feature selection. This work presents a comprehensive study to investigate the use of GP for feature construction and selection on high-dimensional classification problems. Different combinations of the constructed and/or selected features are tested and compared on seven high-dimensional gene expression problems, and different classification algorithms are used to evaluate their performance. The results show that the constructed and/or selected feature sets can significantly reduce the dimensionality and maintain or even increase the classification accuracy in most cases. The cases with overfitting occurred are analysed via the distribution of features. Further analysis is also performed to show why the constructed feature can achieve promising classification performance.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A recursive algorithm for constructing complicated Dixon matrices

Whether the determinant of the Dixon matrix equals zero or not is used for determining if a system of n + 1 polynomial equations in n variables has a common root, and is a very efficient quantifier elimination approach too. But for a complicated polynomial system, it is not easy to construct the Dixon matrix. In this paper, a recursive algorithm to construct the Dixon matrix is proposed by which some problems that cannot be tackled by other methods can be solved on the same computer platform. A dynamic programming algorithm based on the recursive formula is developed and compared for speed and efficiency to the recursive algorithm.     

Optimal value bounds in nonlinear programming with interval data

We consider nonlinear programming problems the input data of which are not fixed, but vary in some real compact intervals. The aim of this paper is to determine bounds of the optimal values. We propose a general framework for solving such problems. Under some assumption, the exact lower and upper bounds are computable by using two non-interval optimization problems. While these two optimization problems are hard to solve in general, we show that for some particular subclasses they can be reduced to easy problems. Subclasses that are considered are convex quadratic programming and posynomial geometric programming.     

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.     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite cuts

In this paper, we propose to enhance Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations for polynomial programming problems by developing cutting plane strategies using concepts derived from semidefinite programming. Given an RLT relaxation, we impose positive semidefiniteness on suitable dyadic variable-product matrices, and correspondingly derive implied semidefinite cuts. In the case of polynomial programs, there are several possible variants for selecting such particular variable-product matrices on which positive semidefiniteness restrictions can be imposed in order to derive implied valid inequalities. This leads to a new class of cutting planes that we call v-semidefinite cuts. We explore various strategies for generating such cuts, and exhibit their relative effectiveness towards tightening the RLT relaxations and solving the underlying polynomial programming problems in conjunction with an RLT-based branch-and-cut scheme, using a test-bed of problems from the literature as well as randomly generated instances. Our results demonstrate that these cutting planes achieve a significant tightening of the lower bound in contrast with using RLT as a stand-alone approach, thereby enabling a more robust algorithm with an appreciable reduction in the overall computational effort, even in comparison with the commercial software BARON and the polynomial programming problem solver GloptiPoly.     

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

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

MOP/GP models for machine learning

Techniques for machine learning have been extensively studied in recent years as effective tools in data mining. Although there have been several approaches to machine learning, we focus on the mathematical programming (in particular, multi-objective and goal programming; MOP/GP) approaches in this paper. Among them, Support Vector Machine (SVM) is gaining much popularity recently. In pattern classification problems with two class sets, its idea is to find a maximal margin separating hyperplane which gives the greatest separation between the classes in a high dimensional feature space. This task is performed by solving a quadratic programming problem in a traditional formulation, and can be reduced to solving a linear programming in another formulation. However, the idea of maximal margin separation is not quite new: in the 1960s the multi-surface method (MSM) was suggested by Mangasarian. In the 1980s, linear classifiers using goal programming were developed extensively.This paper presents an overview on how effectively MOP/GP techniques can be applied to machine learning such as SVM, and discusses their problems.