NLPQL: A fortran subroutine solving constrained nonlinear programming problems

NLPQL is a FORTRAN implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions. At each iteration, the search direction is the solution of a quadratic programming subproblem. This paper discusses the organization of NLPQL, including the formulation of the subproblem and the information that must be provided by a user. A summary is given of the performance of different algorithmic options of NLPQL on a collection of test problems (115 hand-selected or application problems, 320 randomly generated problems). The performance of NLPQL is compared with that of some other available codes.     

NLPQL: A fortran subroutine solving constrained nonlinear programming problems

NLPQL is a FORTRAN implementation of a sequential quadratic programming method for solving nonlinearly constrained optimization problems with differentiable objective and constraint functions. At each iteration, the search direction is the solution of a quadratic programming subproblem. This paper discusses the organization of NLPQL, including the formulation of the subproblem and the information that must be provided by a user. A summary is given of the performance of different algorithmic options of NLPQL on a collection of test problems (115 hand-selected or application problems, 320 randomly generated problems). The performance of NLPQL is compared with that of some other available codes.     

A linear programming approach for linear multi-level programming problems

In an earlier paper, we proposed a modified fuzzy programming method to handle higher level multi-level decentralized programming problems (ML(D)PPs). Here we present a simple and practical method to solve the same. This method overcomes the subjectivity inherent in choosing the tolerance values and the membership functions. We consider a linear ML(D)PP and apply linear programming (LP) for the optimization of the system in a supervised search procedure, supervised by the higher level decision maker (DM). The higher level DM provides the preferred values of the decision variables under his control to enable the lower level DM to search for his optimum in a narrower feasible space. The basic idea is to reduce the feasible space of a decision variable at each level until a satisfactory point is sought at the last level.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

A language for nonlinear programming problems

An algebraic-like language for nonlinear programming problems is described. The rationale for the computation of the function values, gradients, and scond partial derivatives of the functions from their algebraic representation is developed. Each function is translated into an explicit factorable form or hierarchical representation which is used interpretively to compute the function value, gradient, and second partials of the function at each point for which such values are required. Computational efficiency is achieved by computing the matrix of second partials as the sum of a set of vector outer products, the vectors having resulted from the gradient computation, plus a diagonal matrix. An experimental computer program which implements the language and ties it to SUMT is described. In the experience with this program the computer times required have ranged from 4 to 30 times those times required by computer solutions to the same problems by using analyst-prepared programs to compute the function values, gradients, and second partial derivatives. A program based on a compiler approach to implementing the language, rather than the interpretative approach of the experimental program, will probably result in computer times between one and two times those required by using analyst-prepared programs.     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is 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.     

A new algorithm for multi-dimensional dynamic programming problems

The new algorithm presented here solves medium size multi-dimensional dynamic programming problems in a relatively short computational time with no fast-memory restraints. The algorithm converges to the global optimal solution under some differentiability and convexity assumptions.The procedure is to solve a succession of dynamic programming problems, the state sets of which are limited to only a very small subset of the original state space. The interrelated definition of state sets for successive subproblems facilitates an algorithmic convergence while moving the subsets to contain the optimal states at the end.     

A combined scalarizing method for multiobjective programming problems

In this paper, a new general scalarization technique for solving multiobjective optimization problems is presented. After studying the properties of this formulation, two problems as special cases of this general formula are considered. It is shown that some well-known methods such as the weighted sum method, the ?$?$-constraint method, the Benson method, the hybrid method and the elastic ?$?$-constraint method can be subsumed under these two problems. Then, considering approximate solutions, some relationships between ε$\epsilon$-(weakly, properly) efficient points of a general (without any convexity assumption) multiobjective optimization problem and ?$?$-optimal solutions of the introduced scalarized problem are achieved.     

A quadratically-convergent algorithm for general nonlinear programming problems

This paper presents an algorithm for solving nonlinearly constrained nonlinear programming problems. The algorithm reduces the original problem to a sequence of linearly-constrained minimization problems, for which efficient algorithms are available. A convergence theorem is given which states that if the process is started sufficiently close to a strict second-order Kuhn—Tucker point, then the sequence produced by the algorithm exists and convergesR-quadratically to that point.Work sponsored by the United States Army under Contract No. DA-31-124-ARO-D-462.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A duality theorem for continuous-time linear programming problems

Summary In dealing with dynamic economic policy models one encounters optimization problems whose objective function is an integral of a linear function of a finite number of continuous variables and whose constraints are linear integral inequalities. A set of intertemporal efficiency conditions (equilibrium conditions) yielding the optimal policy are given. By approximating the continuous problem by a set of discrete problems and appealing to a well known convergence theorem in functional analysis a continuous analog of the duality theorem is proved.

---

Zusammenfassung Bei der Beschäftigung mit dynamischen Modellen der ökonomischen Politik stößt man auf Optimierungsprobleme, deren Zielfunktion ein Integral einer linearen Funktion von einer endlichen Anzahl stetiger Variablen ist und deren Beschränkungen lineare Integral-Ungleichungen sind. Eine Menge intertemporaler Effizienz-Bedingungen (Gleichgewichtsbedingungen), die zur optimalen Politik führen, sind gegeben. Durch Approximation des kontinuierlichen Problems mittels einer Menge von diskreten Problemen und Berufung auf einen wohlbekannten Konvergenzsatz aus der Funktionalanalysis wird ein stetiges Analogon des Dualitätstheorems bewiesen.

---

---

The author is indebted to Mr.Arnold Faden for helpful suggestions and to ProfessorKarl A. Fox andGerhard Tintner for encouragement during the preparation of the paper. This research has been partially supported by a grant from the Ford Foundation to the School of Business Administration administered by the Center for Research in Management Science, University of California, Berkeley.

---

Vorgel. v.:G. Tintner.     

A cutting-plane method for quadratic semi infinite programming problems

A cutting plane algorithm for solving convex quadratic semi-infinite programming problems is presented. Nonbinding constraints can be dropped. Its arithmetic convergence rate is proved by taking into consideration the error of the approximate solution of the auxiliary problem to calculate the most violate constraint. An implementable variant of this method is described which is due to the adaptive discretization of the index set and its stability is shown. Computational experiments show the behaviour of the method.     

A global optimization method for nonconvex separable programming problems

Conventional methods of solving nonconvex separable programming (NSP) problems by mixed integer programming methods requires adding numerous 0–1 variables. In this work, we present a new method of deriving the global optimum of a NSP program using less number of 0–1 variables. A separable function is initially expressed by a piecewise linear function with summation of absolute terms. Linearizing these absolute terms allows us to convert a NSP problem into a linearly mixed 0–1 program solvable for reaching a solution which is extremely close to the global optimum.     

A new technique for generating quadratic programming test problems

This paper describes a new technique for generating convex, strictly concave and indefinite (bilinear or not) quadratic programming problems. These problems have a number of properties that make them useful for test purposes. For example, strictly concave quadratic problems with their global maximum in the interior of the feasible domain and with an exponential number of local minima with distinct function values and indefinite and jointly constrained bilinear problems with nonextreme global minima, can be generated.Unlike most existing methods our construction technique does not require the solution of any subproblems or systems of equations. In addition, the authors know of no other technique for generating jointly constrained bilinear programming problems.Support of this work has been provided by the Instituto Nacional de Investigação Científica de Portugal (INIC) under contract 89/EXA/5 and by the Natural Sciences and Engineering Research Council of Canada operating grant 5671.Much of this paper was completed while this author was on a research sabbatical at the Universidade de Coimbra, Portugal.     

A trajectory-based method for mixed integer nonlinear programming problems

A local trajectory-based method for solving mixed integer nonlinear programming problems is proposed. The method is based on the trajectory-based method for continuous optimization problems. The method has three phases, each of which performs continuous minimizations via the solution of systems of differential equations. A number of novel contributions, such as an adaptive step size strategy for numerical integration and a strategy for updating the penalty parameter, are introduced. We have shown that the optimal value obtained by the proposed method is at least as good as the minimizer predicted by a recent definition of a mixed integer local minimizer. Computational results are presented, showing the effectiveness of the method.     

Approximations for chance-constrained programming problems

This paper proposes an approximation approach to the solution of chance-constrained stochastic programming problems. The results rely in a fundamental way on the theory of convergence of sequences of measurable multifunctions. Particular results are presented for stochastic linear programming problems.     

A statistical generalized programming algorithm for stochastic optimization problems

In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasigradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes.This paper has been partially supported by the Italian MURST 40% project on Flexible Manufacturing Systems.