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.     

An interval programming approach for developing economic order quantity model with imprecise exponents and coefficients

This paper develops an economic order quantity (EOQ) model with uncertain data. For modelling the uncertainty in real-world data, the exponents and coefficients in demand and cost functions are considered as interval data and then, the related model is designed. The proposed model maximises the profit and determines the price, marketing cost and lot sizing with the interval data. Since the model parameters are imprecise, the objective value is imprecise, too. So, the upper and lower bounds are specially formulated for the problem and then, the model is transferred to a geometric program. The resulted geometric program is solved by using the duality approach and the lower and upper bounds are found out for the objective function and variables. Two numerical examples and sensitivity analysis are further used to illustrate the performance of the proposed model.     

Posynomial Parametric Geometric Programming with Interval Valued Coefficient

The article presents solution procedure of geometric programming with imprecise coefficients. We have considered problems with imprecise data as a form of an interval in nature. Many authors have solved the imprecise problem by geometric programming technique in a different way. In this paper, we introduce parametric functional form of an interval number and then solve the problem by geometric programming technique. The advantage of the present approach is that we get optimal solution of the objective function directly without solving equivalent transformed problems. Numerical examples are presented to support of the proposed approach.     

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.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

灰色正项几何规划研究

In the model of geometric programming, values of parameters cannot be gotten owing to data fluctuation and incompletion. But reasonable bounds of these parameters can be attained. This is to say, parameters of this model can be regarded as interval grey numbers. When the model contains grey numbers, it is hard for common programming method to solve them. By combining the common programming model with the grey system theory, and using some analysis strategies, a model of grey polynomial geometric programming, a model of θpositioned geometric programming and their quasi-optimum solution or optimum solution are put forward. At the same time, we also developed an algorithm for the problem. This approach brings a new way for the application research of geometric programming. An example at the end of this paper shows the rationality and feasibility of the algorithm.     

Quantitative stability analysis for vector problems of 0–1 programming

We consider multiple objective 0–1 programming problems in the situation where parameters of objective functions and linear constraints are exposed to independent perturbations. We study quantitative characteristics of stability (stability radii) of problem solutions. An approach to deriving formulae and estimations of stability radii is presented. This approach is applied to stability analysis of the linear 0–1 programming problem and problems with two types of nonlinear objective functions: linear absolute value and quadratic.     

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.     

A successive quadratic programming method for a class of constrained nonsmooth optimization problems

In this paper we present an algorithm for solving nonlinear programming problems where the objective function contains a possibly nonsmooth convex term. The algorithm successively solves direction finding subproblems which are quadratic programming problems constructed by exploiting the special feature of the objective function. An exact penalty function is used to determine a step-size, once a search direction thus obtained is judged to yield a sufficient reduction in the penalty function value. The penalty parameter is adjusted to a suitable value automatically. Under appropriate assumptions, the algorithm is shown to produce an approximate optimal solution to the problem with any desirable accuracy in a finite number of iterations.     

Using eigenstructure of the Hessian to reduce the dimension of the intensity modulated radiation therapy optimization problem

Optimization is of vital importance when performing intensity modulated radiation therapy to treat cancer tumors. The optimization problem is typically large-scale with a nonlinear objective function and bounds on the variables, and we solve it using a quasi-Newton sequential quadratic programming method. This study investigates the effect on the optimal solution, and hence treatment outcome, when solving an approximate optimization problem of lower dimension. Through a spectral decompostion, eigenvectors and eigenvalues of an approximation to the Hessian are computed. An approximate optimization problem of reduced dimension is formulated by introducing eigenvector weights as optimization parameters, where only eigenvectors corresponding to large eigenvalues are included. The approach is evaluated on a clinical prostate case. Compared to bixel weight optimization, eigenvector weight optimization with few parameters results in faster initial decline in the objective function, but with inferior final solution. Another approach, which combines eigenvector weights and bixel weights as variables, gives lower final objective values than what bixel weight optimization does. However, this advantage comes at the expense of the pre-computational time for the spectral decomposition. A preliminary version of this paper was presented at the AAPM 46th annual meeting, held July 25–29, 2004 in Pittsburgh, PA.     

A Rigorous Lower Bound for the Optimal Value of Convex Optimization Problems

In this paper, we consider the computation of a rigorous lower error bound for the optimal value of convex optimization problems. A discussion of large-scale problems, degenerate problems, and quadratic programming problems is included. It is allowed that parameters, whichdefine the convex constraints and the convex objective functions, may be uncertain and may vary between given lower and upper bounds. The error bound is verified for the family of convex optimization problems which correspond to these uncertainties. It can be used to perform a rigorous sensitivity analysis in convex programming, provided the width of the uncertainties is not too large. Branch and bound algorithms can be made reliable by using such rigorous lower bounds.     

General Robust-Optimization Formulation for Nonlinear Programming

Most research in robust optimization has been focused so far on inequality-only, convex conic programming with simple linear models for the uncertain parameters. Many practical optimization problems, however, are nonlinear and nonconvex. Even in linear programming, the coefficients may still be nonlinear functions of the uncertain parameters. In this paper, we propose robust formulations that extend the robust-optimization approach to a general nonlinear programming setting with parameter uncertainty involving both equality and inequality constraints. The proposed robust formulations are valid in a neighborhood of a given nominal parameter value and are robust to the first-order, thus suitable for applications where reasonable parameter estimations are available and uncertain variations are moderate. This work was supported in part by NSF Grant DMS-0405831     

Rational approximation of vertical segments

In many applications, observations are prone to imprecise measurements. When constructing a model based on such data, an approximation rather than an interpolation approach is needed. Very often a least squares approximation is used. Here we follow a different approach. A natural way for dealing with uncertainty in the data is by means of an uncertainty interval. We assume that the uncertainty in the independent variables is negligible and that for each observation an uncertainty interval can be given which contains the (unknown) exact value. To approximate such data we look for functions which intersect all uncertainty intervals. In the past this problem has been studied for polynomials, or more generally for functions which are linear in the unknown coefficients. Here we study the problem for a particular class of functions which are nonlinear in the unknown coefficients, namely rational functions. We show how to reduce the problem to a quadratic programming problem with a strictly convex objective function, yielding a unique rational function which intersects all uncertainty intervals and satisfies some additional properties. Compared to rational least squares approximation which reduces to a nonlinear optimization problem where the objective function may have many local minima, this makes the new approach attractive.     

Quality control system design through the goal programming model and the satisfaction functions

The goal programming (GP) model has been utilized for designing a quality control system (QCS) where several features are simultaneously considered. In the context of the quality control, the parameters can be imprecise and expressed through intervals. The aim of this paper is to propose two formulations for designing a QCS based on the imprecise GP model. The concept of satisfaction functions will be utilized to integrate explicitly the decision-maker’s preference. The developed formulations are illustrated through an example of a paper factory.     

Optimal value range in interval linear programming

We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).     

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

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

An Adaptive Neural Network Model for Nonlinear Programming Problems

In this paper a canonical neural network with adaptively changing synaptic weights and activation function parameters is presented to solve general nonlinear programming problems. The basic part of the model is a sub-network used to find a solution of quadratic programming problems with simple upper and lower bounds. By sequentially activating the sub-network under the control of an external computer or a special analog or digital processor that adjusts the weights and parameters, one then solves general nonlinear programming problems. Convergence proof and numerical results are given.     

Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems

Many global optimization approaches for solving signomial geometric programming problems are based on transformation techniques and piecewise linear approximations of the inverse transformations. Since using numerous break points in the linearization process leads to a significant increase in the computational burden for solving the reformulated problem, this study integrates the range reduction techniques in a global optimization algorithm for signomial geometric programming to improve computational efficiency. In the proposed algorithm, the non-convex geometric programming problem is first converted into a convex mixed-integer nonlinear programming problem by convexification and piecewise linearization techniques. Then, an optimization-based approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using fewer break points in the linearization process, therefore decreasing the required CPU time. Several numerical experiments are presented to demonstrate the advantages of the proposed method in terms of both computational efficiency and solution quality.     

An Algorithm for Approximate Multiparametric Convex Programming

For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation of several optimization-based feedback control strategies.     

Algorithms for the bounded set-up knapsack problem

The Bounded Set-up Knapsack Problem (BSKP) is a generalization of the Bounded Knapsack Problem (BKP), where each item type has a set-up weight and a set-up value that are included in the knapsack and the objective function value, respectively, if any copies of that item type are in the knapsack. This paper provides three dynamic programming algorithms that solve BSKP in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS). A key implication from these results is that the dynamic programming algorithms and the FPTAS can also be applied to BKP. One of the dynamic programming algorithms presented solves BKP with the same time and space bounds of the best known dynamic programming algorithm for BKP. Moreover, the FPTAS improves the worst-case time bound for obtaining approximate solutions to BKP as compared to using FPTASs designed for BKP or the 0-1 Knapsack Problem.