Bifurcations in parametric nonlinear programming

Bifurcation and continuation techniques are introduced as a class of methods for investigating the parametric nonlinear programming problem. Motivated by the Fritz John first-order necessary conditions, the parametric programming problem is first reformulated as a closed system of nonlinear equations which contains all Karush-Kuhn-Tucker and Fritz John points, both feasible and infeasible solutions, and relative minima, maxima, and saddle points. Since changes in the structure of the solution set and critical point type can occur only at singularities, necessary and sufficient conditions for the existence of a singularity are developed in terms of the loss of a complementarity condition, the linear dependence constraint qualification, and the singularity of the Hessian of the Lagrangian on a tangent space. After a brief introduction to elementary bifurcation theory, some simple singularities in this parametric problem are analyzed for both branching and persistence of local minima. Finally, a brief introduction to numerical continuation and bifurcation procedures is given to indicate how these facts can be used in a numerical investigation of the problem.This research was supported by the Air force Office of Scientific Research through grant number AFOSR-88-0059.     

A bifurcation analysis of the nonlinear parametric programming problem

The structure of solutions to the nonlinear parametric programming problem with a one dimensional parameter is analyzed in terms of the bifurcation behavior of the curves of critical points and the persistence of minima along these curves. Changes in the structure of the solution occur at singularities of a nonlinear system of equations motivated by the Fritz John first-order necessary conditions. It has been shown that these singularities may be completely partitioned into seven distinct classes based upon the violation of one or more of the following: a complementarity condition, a constraint qualification, and the nonsingularity of the Hessian of the Lagrangian on a tangent space. To apply classical bifurcation techniques to these singularities, a further subdivision of each case is necessary. The structure of curves of critical points near singularities of lowest (zero) codimension within each case is analyzed, as well as the persistence of minima along curves emanating from these singularities. Bifurcation behavior is also investigated or discussed for many of the subcases giving rise to a codimension one singularity.This work was supported by the National Science Foundation through NSF Grants DMS-85-10201 and DMS-87-04679 and by the Air Force Office of Scientific Research through grant number AFOSR-88-0059.     

Solving fuzzy queueing decision problems via a parametric mixed integer nonlinear programming method

This paper proposes a mathematical programming method to construct the membership functions of the fuzzy objective value of the cost-based queueing decision problem with the cost coefficients and the arrival rate being fuzzy numbers. On the basis of Zadeh’s extension principle, three pairs of mixed integer nonlinear programs (MINLP) parameterized by the possibility level α are formulated to calculate the lower and upper bounds of the minimal expected total cost per unit time at α, through which the membership function of the minimal expected total cost per unit time of the fuzzy objective value is constructed. To provide a suitable optimal service rate for designing queueing systems, the Yager’s ranking index method is adopted. Two numerical examples are solved successfully to demonstrate the validity of the proposed method. Since the objective value is completely expressed by a membership function rather than by a crisp value, it conserves the fuzziness of the input information, thus more information is provided for designing queueing systems. The successful extension of queueing decision models to fuzzy environments permits queueing decision models to have wider applications in practice.     

On a pair of nonlinear mixed integer programming problems

We consider maximin and minimax nonlinear mixed integer programming problems which are nonsymmetric in duality sense. Under weaker (pseudo-convex/pseudo-concave) assumptions, we show that the supremum infimum of the maximin problem is greater than or equal to the infimum supremum of the minimax problem. As a particular case, this result reduces to the weak duality theorem for minimax and symmetric dual nonlinear mixed integer programming problems. Further, this is used to generalize available results on minimax and symmetric duality in nonlinear mixed integer programming.     

Algorithms for parametric nonconvex programming

In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter . This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.The author would like to thank Professors R. M. Soland, T. L. Morin, and P. L. Yu for their helpful comments. Thanks also go to two anonymous reviewers for their useful comments concerning an earlier version of this paper.     

Convexity and concavity properties of the optimal value function in parametric nonlinear programming

Convexity and concavity properties of the optimal value functionf* are considered for the general parametric optimization problemP() of the form min _x f(x, ), s.t.x R(). Such properties off* and the solution set mapS* form an important part of the theoretical basis for sensitivity, stability, and parametric analysis in mathematical optimization. Sufficient conditions are given for several standard types of convexity and concavity off*, in terms of respective convexity and concavity assumptions onf and the feasible region point-to-set mapR. Specializations of these results to the general parametric inequality-equality constrained nonlinear programming problem and its right-hand-side version are provided. To the authors' knowledge, this is the most comprehensive compendium of such results to date. Many new results are given.This paper is based on results presented in the PhD Thesis of the second author completed at The George Washington University under the direction of the first author.This work was partly supported by the Office of Naval Research, Program in Logistics, Contract No. N00014-75-C-0729 and by the National Science Foundation, Grant No. ECS-82-01370 to the Institute for Management Science and Engineering, The George Washington University, Washington, DC.     

An improved sequential quadratic programming algorithm for solving general nonlinear programming problems

In this paper, a class of general nonlinear programming problems with inequality and equality constraints is discussed. Firstly, the original problem is transformed into an associated simpler equivalent problem with only inequality constraints. Then, inspired by the ideals of the sequential quadratic programming (SQP) method and the method of system of linear equations (SLE), a new type of SQP algorithm for solving the original problem is proposed. At each iteration, the search direction is generated by the combination of two directions, which are obtained by solving an always feasible quadratic programming (QP) subproblem and a SLE, respectively. Moreover, in order to overcome the Maratos effect, the higher-order correction direction is obtained by solving another SLE. The two SLEs have the same coefficient matrices, and we only need to solve the one of them after a finite number of iterations. By a new line search technique, the proposed algorithm possesses global and superlinear convergence under some suitable assumptions without the strict complementarity. Finally, some comparative numerical results are reported to show that the proposed algorithm is effective and promising.     

Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

Stability achievement scalarization function for multiobjective nonlinear programming problems

In this paper, we present a method to determine the stability of nondominated criterion vectors using a modified weighted achievement scalarization metric. This method is based on the application of a particular objective function which scalarizes and parameterizes the original multiobjective nonlinear programming problem. Also, we show that this modified weighted achievement metric coincides with the metric introduced by Choo and Atkins [E.-U. Choo, D.R. Atkins, Proper efficiency in nonconvex multicriteria programming, Math. Oper. Res. 8 (1983) 467–470] and Kaliszewski [I. Kaliszewski, A modified weighted Tchebycheff metric for multiple objective programming, Comput. Oper. Res. 14 (1987) 315–323] in cases when sets of all criterion vectors are finite or polyhedral.     

Solving nonlinear principal-agent problems using bilevel programming

While significant progress has been made, analytic research on principal-agent problems that seek closed-form solutions faces limitations due to tractability issues that arise because of the mathematical complexity of the problem. The principal must maximize expected utility subject to the agent’s participation and incentive compatibility constraints. Linearity of performance measures is often assumed and the Linear, Exponential, Normal (LEN) model is often used to deal with this complexity. These assumptions may be too restrictive for researchers to explore the variety of relationships between compensation contracts offered by the principal and the effort of the agent. In this paper we show how to numerically solve principal-agent problems with nonlinear contracts. In our procedure, we deal directly with the agent’s incentive compatibility constraint. We illustrate our solution procedure with numerical examples and use optimization methods to make the problem tractable without using the simplifying assumptions of a LEN model. We also show that using linear contracts to approximate nonlinear contracts leads to solutions that are far from the optimal solutions obtained using nonlinear contracts. A principal-agent problem is a special instance of a bilevel nonlinear programming problem. We show how to solve principal-agent problems by solving bilevel programming problems using the ellipsoid algorithm. The approach we present can give researchers new insights into the relationships between nonlinear compensation schemes and employee effort.     

Perturbation theory for mathematical programming problems

Mathematical programming (MP) problems depending on a small parameter are investigated. Attention is paid to the cases where the solutions to the reduced program and/or the solutions to the dual reduced program are not unique. Conditions are given for the convergence of perturbed solutions to a point of the reduced problem solution set, if the small parameter tends to zero. It is shown how to find this point and how to construct an approximate solution to the perturbed program. A singular situation may appear if the dual solution set is unbounded. In this case, a gap between perturbed and reduced solutions may arise. However, it is shown that the perturbed solutions are close to the solutions of some modified reduced problem. The practical usefulness of perturbation theory is demonstrated by considering the two LP problems. Decomposition and aggregation procedures are constructed on the base of general results to find suboptimal solutions of these problems.     

Reductions of interval nonlinear programming problem

A general nonlinear programming problem with interval functions is considered. Two reductions of this problem to the deterministic nonlinear programming problem are proposed, and illustrative examples are discussed.     

A branch-and-bound algorithm for 0–1 parametric mixed integer programming

A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained.     

Bifurcation of nonlinear problems modeling flows through porous media

This paper deals with a class of nonlinear boundary value problems which appears in the study of models of flows through porous media. Existence results of asymptotic bifurcation and continua are reported both for operator equations and for boundary value problems. This work is supported in part by NSF of Shandong Province and NNSF of China     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

Solving special nonlinear fractional programming problems via parametric linear programming

A new procedure is developed to solve a generalized linear fractional programming problem. We find the optimal solutions in two steps. First we solve a parametric linear programming problem. Using the results of this step we then define a simple optimization problem in the second step. This yields an optimal value which together with the results of the parametric analysis provides the optimal solutions of the considered fractional programming problem.     

An exact penalty function method with global convergence properties for nonlinear programming problems

In this paper a new continuously differentiable exact penalty function is introduced for the solution of nonlinear programming problems with compact feasible set. A distinguishing feature of the penalty function is that it is defined on a suitable bounded open set containing the feasible region and that it goes to infinity on the boundary of this set. This allows the construction of an implementable unconstrained minimization algorithm, whose global convergence towards Kuhn-Tucker points of the constrained problem can be established.     

On the solution of indefinite systems arising in nonlinear programming problems

This work is concerned with the convergence properties and the numerical analysis of the preconditioned conjugate gradient (PCG) method applied to the solution of indefinite linear systems arising in nonlinear optimization. Our approach is based on the choice of quasidefinite preconditioners and of a suitable factorization routine. Some theoretical and numerical results about these preconditioners are obtained. Furthermore, we show the behaviour of the PCG method for different formulations of the indefinite system and we compare the effectiveness of the proposed variants. Copyright © 2007 John Wiley & Sons, Ltd.     

A new augmented Lagrangian function for inequality constraints in nonlinear programming problems

In this paper, a new augmented Lagrangian function is introduced for solving nonlinear programming problems with inequality constraints. The relevant feature of the proposed approach is that, under suitable assumptions, it enables one to obtain the solution of the constrained problem by a single unconstrained minimization of a continuously differentiable function, so that standard unconstrained minimization techniques can be employed. Numerical examples are reported.