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.     

On Unconstrained and Constrained Stationary Points of the Implicit Lagrangian

Mangasarian and Solodov (Ref. 1) proposed to solve nonlinear complementarity problems by seeking the unconstrained global minima of a new merit function, which they called implicit Lagrangian. A crucial point in such an approach is to determine conditions which guarantee that every unconstrained stationary point of the implicit Lagrangian is a global solution, since standard unconstrained minimization techniques are only able to locate stationary points. Some authors partially answered this question by giving sufficient conditions which guarantee this key property. In this paper, we settle the issue by giving a necessary and sufficient condition for a stationary point of the implicit Lagrangian to be a global solution and, hence, a solution of the nonlinear complementarity problem. We show that this new condition easily allows us to recover all previous results and to establish new sufficient conditions. We then consider a constrained reformulation based on the implicit Lagrangian in which nonnegative constraints on the variables are added to the original unconstrained reformulation. This is motivated by the fact that often, in applications, the function which defines the complementarity problem is defined only on the nonnegative orthant. We consider the KKT-points of this new reformulation and show that the same necessary and sufficient condition which guarantees, in the unconstrained case, that every unconstrained stationary point is a global solution, also guarantees that every KKT-point of the new problem is a global solution.     

一类不可压广义neo-Hookean球体的空穴分岔问题的定性研究

研究了一类不可压的广义neo-Hookean材料组成的球体的空穴分岔问题,该类材料可以看作是带有径向摄动的均匀各向同性不可压的neo-Hookean材料,得到了球体内部空穴生成的条件．与均匀各向同性的neo-Hookean球体的情况相比,证明了当摄动参数属于某些区域时,从平凡解局部向左分岔的空穴分岔解上存在一个二次转向分岔点,空穴生成时的临界载荷会比无摄动的材料的临界载荷小．用奇点理论证明了,空穴分岔方程在临界点附近等价于具有单边约束条件的正规形．用最小势能原理分别讨论了空穴分岔解的稳定性和实际稳定的平衡状态．     

Computing eigenfunctions of singular points in nonlinear parametrized two-point BVPs

The iterative computation of singular points in parametrized nonlinear BVPs by so-called extended systems requires good starting values for the singular point itself and the corresponding eigenfunction. Using path-following techniques such starting values for the singular points should be generated automatically. However, path-following does not provide approximations for the eigenfunction if the singularity is a bifurcation point. We propose a new modification of this standard technique delivering such starting values. It is based on an extended system by which singular as well as nonsingular points can be determined.     

FJ-Invex control problem

This paper introduces a new condition on the functionals of a control problem and extends a recent characterization result of KT-invexity. We prove that the new condition, the FJ-invexity, is both necessary and sufficient in order to characterize the optimal solution set using Fritz John points.     

Convergence bounds for nonlinear programming algorithms

Bounds on convergence are given for a general class of nonlinear programming algorithms. Methods in this class generate at each interation both constraint multipliers and approximate solutions such that, under certain specified assumptions, accumulation points of the multiplier and solution sequences satisfy the Fritz John or the Kuhn—Tucker optimality conditions. Under stronger assumptions, convergence bounds are derived for the sequences of approximate solution, multiplier and objective function values. The theory is applied to an interior—exterior penalty function algorithm modified to allow for inexact subproblem solutions. An entirely new convergence bound in terms of the square root of the penalty controlling parameter is given for this algorithm.     

关于FRITZ JOHN条件

本文证明多目标问题的有效解总适合 Fritz John必要条件 ,并利用单目标规划问题最优解的一个新的 Fritz John充分条件推出多目标问题有效解的两个新的充分条件     

Enhanced Karush–Kuhn–Tucker condition and weaker constraint qualifications

In this paper we study necessary optimality conditions for nonsmooth optimization problems with equality, inequality and abstract set constraints. We derive the enhanced Fritz John condition which contains some new information even in the smooth case than the classical enhanced Fritz John condition. From this enhanced Fritz John condition we derive the enhanced Karush–Kuhn–Tucker condition and introduce the associated pseudonormality and quasinormality condition. We prove that either pseudonormality or quasinormality with regularity on the constraint functions and the set constraint implies the existence of a local error bound. Finally we give a tighter upper estimate for the Fréchet subdifferential and the limiting subdifferential of the value function in terms of quasinormal multipliers which is usually a smaller set than the set of classical normal multipliers. In particular we show that the value function of a perturbed problem is Lipschitz continuous under the perturbed quasinormality condition which is much weaker than the classical normality condition.     

A singular bifurcation problem

A nonlinear and singular bifurcation problem is studied to illustrate to what extent the singularity given by a pole can influence the bifurcation behavior. Due to the singularity, well-known bifurcation analysis is not applicable. An approximation by regular problems yields the result: A compact branch which ends in a special “singular” solution bifurcates from each eigenvalue of the linearized problem.     

Fritz John Necessary Optimality Conditions of the Alternative-Type

An alternative-type version of the Fritz John optimality conditions is established at points not necessarily optimal, which covers situations where no result appearing elsewhere is applicable. As a by-product, a versatile formulation of these necessary Fritz John optimality conditions along with a simple proof is provided. This encompasses several versions appearing in the literature. A variant of the KKT conditions is also presented.     

Optimality Conditions for Nonsmooth Equilibrium Problems via Hadamard Directional Derivative

In this paper, we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. We obtain necessary conditions of Fritz John (FJ) and Karush-Kuhn-Tucker (KKT) types for a nonsmooth (MPEC) problem in terms of the lower Hadamard directional derivative. In particular sufficient conditions for MPECs are given where the involved functions have pseudoconvex sublevel sets. The functions with pseudoconvex sublevel sets is a class of generalized convex functions that include quasiconvex functions.     

A general MPCC model and its solution algorithm for continuous network design problem

This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.     

Arc-Length Method for Frictional Contact Problems Using Mathematical Programming with Complementarity Constraints

A new formulation as well as a new solution technique is proposed for an equilibrium path-following method in two-dimensional quasistatic frictional contact problems. We consider the Coulomb friction law as well as a geometrical nonlinearity explicitly. Based on a criterion of maximum dissipation of energy, we propose a formulation as a mathematical program with complementarity constraints (MPEC) in order to avoid unloading solutions in which most contact candidate nodes become stuck. A regularization scheme for the MPEC is proposed, which can be solved by using a conventional nonlinear programming approach. The equilibrium paths of various structures are computed in cases such that there exist some limit points and/or infinite number of successive bifurcation points.     

强Duffing系统的局部分岔分析

本文通过坐标变化和近恒等变化，将强Ｄｕｆｆｉｎｇ方程化成范式，从而可以得到在不同共振条件下的分合方程以及其近似解，应用奇异性理论研究了强Ｄｕｆｆｉｎｇ在开折参数及物理参数平面上的转迁集及其局部分岔图．     

Numerical stability analysis and computation of Hopf bifurcation points for delay differential equations

We present a numerical technique for the stability analysis and the computation of branches of Hopf bifurcation points in nonlinear systems of delay differential equations with several constant delays. The stability analysis of a steady-state solution is done by a numerical implementation of the argument principle, which allows to compute the number of eigenvalues with positive real part of the characteristic matrix. The technique is also used to detect bifurcations of higher singularity (Hopf and fold bifurcations) during the continuation of a branch of Hopf points. This allows to trace new branches of Hopf points and fold points.     

Huard type second-order converse duality for nonlinear programming

In this paper, we establish a Huard type converse duality for a second-order dual model in nonlinear programming using Fritz John necessary optimality conditions.     

Generalized Kojima–Functions and Lipschitz Stability of Critical Points

In this paper we consider systems of equations which are defined by nonsmooth functions of a special structure. Functions of this type are adapted from Kojima's form of the Karush–Kuhn–Tucker conditions for C²—optimization problems. We shall show that such systems often represent conditions for critical points of variational problems (nonlinear programs, complementarity problems, generalized equations, equilibrium problems and others). Our main purpose is to point out how different concepts of generalized derivatives lead to characterizations of different Lipschitz properties of the critical point or the stationary solution set maps.     

A smoothing QP-free infeasible method for nonlinear inequality constrained optimization

In this paper,a smoothing QP-free infeasible method is proposed for nonlinear inequality constrained optimization problems.This iterative method is based on the solution of nonlinear equations which is obtained by the multipliers and the smoothing Fisher-Burmeister function for the KKT first-order optimality conditions.Comparing with other QP-free methods, this method does not request the strict feasibility of iteration.In particular,this method is implementable and globally convergent without assuming the strict complementarity condition and the isolatedness of accumulation points.Furthermore,the gradients of active constraints are not requested to be linearly independent.Preliminary numerical results indicate that this smoothing QP-free infeasible method is quite promising.     

Multiobjective programming under d-invexity

In this paper, a generalization of convexity is considered in the case of nonlinear multiobjective programming problem where the functions involved are nondifferentiable. By considering the concept of Pareto optimal solution and substituting d-invexity for convexity, the Fritz John type and Karush–Kuhn–Tucker type necessary optimality conditions and duality in the sense of Mond–Weir and Wolfe for nondifferentiable multiobjective programming are given.