Perturbation Lemma for the Newton Method with Application to the SQP Newton Method

We study the convergence of a general perturbation of the Newton method for solving a nonlinear system of equations. As an application, we show that the augmented Lagrangian successive quadratic programming is locally and q-quadratically convergent in the variable x to the solution of an equality constrained optimization problem, under a mild condition on the penalty parameter and the choice of the Lagrange multipliers.     

Infinitely constrained optimization problems

A generalized cutting-plane algorithm designed to solve problems of the form min{f(x) :x X andg(x,y) 0 for ally Y} is described. Convergence is established in the general case (f,g continuous,X andY compact). Constraint dropping is allowed in a special case [f,g(·,y) convex functions,X a convex set]. Applications are made to a variety of max-min problems. Computational considerations are discussed.Dr. Falk's research was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under AFOSR Contract No. 73–2504.     

An initial value problem for a functional equation

We consider the functional equationf(A(x,y))=B(f(x),f(y)), whereA andB are averages. It is known that such a functional equation has exactly one continuous solution satisfying a given two-point condition. By analogy with the theory of differential equations, we may regard the functional equation, together with a two-point condition, as a boundary value problem. (Then each boundary value problem has a unique continuous solution.) If we replace the two-point condition with the specification of a value and derivative at just one point, we obtain an initial value problem.Consider the initial value problemsf(A(x,y))=B(f(x),f(y)),f(a)=s,f(a)=, obtained by fixinga ands and allowing to vary through the set of positive real numbers. The main result of this paper gives a necessary and sufficient condition for each of the initial value problems to have a unique continuous solution, under the hypothesis that at least one of the problems has a continuous solution. This is a partial answer to the problem of determining conditions which are sufficient for the existence of a unique continuous solution of a given initial value problem.     

Existence of Solutions for Some Quasilinear Degenerate Elliptic Inclusions in Weighted Sobolev Spaces

We consider the Dirichlet problem for a class of quasilinear degenerate elliptic inclusions of the form ?div(𝒜(x, u, ?u)) + f(x)g(u) ∈ H(x, u, ?u), where 𝒜(x, u, ?u) is allowed to be degenerate. Without the general assumption that the multivalued nonlinearity is characterized by Clarke's generalized gradient of some locally Lipschitz functions, we prove the existence of bounded solutions in weighed Sobolev space with the superlinear growth imposed on the nonlinearity g and the multifunction H(x, u, ?u) by using the Leray-Schauder fixed point theorem. Furthermore, we investigate the existence of extremal solutions and prove that they are dense in the solutions of the original system. Subsequently, a quasilinear degenerate elliptic control problem is considered and the existence theorem based on the proven results is obtained.     

On the Cauchy difference on normed spaces

LetX be a real linear normed space, (G, +) be a topological group, andK be a discrete normal subgroup ofG. We prove that if a continuous at a point or measurable (in the sense specified later) functionf:X →G fulfils the condition:f(x +y) -f(x) -f(y) ∈K whenever ‖x‖ = ‖y‖, then, under some additional assumptions onG,K, andX, there esists a continuous additive functionA :X →G such thatf(x) -A(x) ∈K.     

A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems

Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h _j (x)g(x),j=1, ,m, xX}, wheref(·),h _j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

Highly accurate tables for elementary functions

In this article we describe a fast method to obtain highly accurate tables for all elementary functions by using Bresenham's algorithm. For nearly equally spaced table-points {x _i } we construct pairs {f(x _i ),g(x _i )} such thatf(x _i ) is a machine number andg(x _i ) is very close to an exactly representable number. By a random sampling in an interval centered onx _i we can even find a triplet of nearly machine numbers. The table method together with a polynomial approximation of the function near a table value provides last bit accuracy for more than 99.8% of the argument values without using extended precision calculations [3, 4, 10, 11].     

A fixed point approach to stability of a quadratic equation

Using the fixed point alternative theorem we establish the orthogonal stability of the quadratic functional equation of Pexider type f (x+y)+g(x−y) = h(x)+k(y), where f, g, h, k are mappings from a symmetric orthogonality space to a Banach space, by orthogonal additive mappings under a necessary and sufficient condition on f.     

On the method of multipliers for mathematical programming problems

In this paper, the numerical solution of the basic problem of mathematical programming is considered. This is the problem of minimizing a functionf(x) subject to a constraint (x)=0. Here,f is a scalar,x is ann-vector, and is aq-vector, withq<n.The approach employed is based on the introduction of the augmented penalty functionW(x,,k)=f(x)+ ^T (x)+k ^T (x) (x). Here, theq-vector is an approximation to the Lagrange multiplier, and the scalark>0 is the penalty constant.Previously, the augmented penalty functionW(x, ,k) was used by Hestenes in his method of multipliers. In Hestenes' version, the method of multipliers involves cycles, in each of which the multiplier and the penalty constant are held constant. After the minimum of the augmented penalty function is achieved in any given cycle, the multiplier is updated, while the penalty constantk is held unchanged.In this paper, two modifications of the method of multipliers are presented in order to improve its convergence characteristics. The improved convergence is achieved by (i) increasing the updating frequency so that the number of iterations in a cycle is shortened to N=1 for the ordinary-gradient algorithm and the modified-quasilinearization algorithm and N=n for the conjugate-gradient algorithm, (ii) imbedding Hestenes' updating rule for the multiplier into a one-parameter family and determining the scalar parameter so that the error in the optimum condition is minimized, and (iii) updating the penalty constantk so as to cause some desirable effect in the ordinary-gradient algorithm, the conjugate-gradient algorithm, and the modified-quasilinearization algorithm. For the sake of identification, Hestenes' method of multipliers is called Method MM-1, the modification including (i) and (ii) is called Method MM-2, and the modification including (i), (ii), (iii) is called Method MM-3.Evaluation of the theory is accomplished with seven numerical examples. The first example pertains to a quadratic function subject to linear constraints. The remaining examples pertain to non-quadratic functions subject to nonlinear constraints. Each example is solved with the ordinary-gradient algorithm, the conjugate-gradient algorithm, and the modified-quasilinearization algorithm, which are employed in conjunction with Methods MM-1, MM-2, and MM-3.The numerical results show that (a) for given penalty constantk, Method MM-2 generally exhibits faster convergence than Method MM-1, (b) in both Methods MM-1 and MM-2, the number of iterations for convergence has a minimum with respect tok, and (c) the number of iterations for convergence of Method MM-3 is close to the minimum with respect tok of the number of iterations for convergence of Method MM-2. In this light, Method MM-3 has very desirable characteristics.This research was supported by the National Science Foundation, Grant No. GP-32453. The authors are indebted to Messieurs E. E. Cragg and A. Esterle for computational assistance.     

Positive solutions for nonlinear Robin problems with convection

We consider a nonlinear Robin problem driven by the p‐Laplacian and with a convection term f(z,x,y). Without imposing any global growth condition on f(z,·,·) and using topological methods (the Leray‐Schauder alternative principle), we show the existence of a positive smooth solution.     

The calculation of Stieltjes' integral

A method is proposed for the evaluation of integrals of the type f( ^p ) (x)g( ^q ) (x)dx in terms of function values off(x) andg (x). The method is based on extrapolation and is very similar to Romberg Integration. Some of the properties of the method, including its ultimate convergence, are discussed.Work performed under the auspices of the U. S. Atomic Energy Commission.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

Computation of generalized differentials in nonlinear complementarity problems

Let f and g be continuously differentiable functions on R ⁿ . The nonlinear complementarity problem NCP(f,g), 0≤f(x)⊥g(x)≥0, arises in many applications including discrete Hamilton-Jacobi-Bellman equations and nonsmooth Dirichlet problems. A popular method to find a solution of the NCP(f,g) is the generalized Newton method which solves an equivalent system of nonsmooth equations F(x)=0 derived by an NCP function. In this paper, we present a sufficient and necessary condition for F to be Fréchet differentiable, when F is defined by the “min” NCP function, the Fischer-Burmeister NCP function or the penalized Fischer-Burmeister NCP function. Moreover, we give an explicit formula of an element in the Clarke generalized Jacobian of F defined by the “min” NCP function, and the B-differential of F defined by other two NCP functions. The explicit formulas for generalized differentials of F lead to sharper global error bounds for the NCP(f,g).     

Principal Eigenvalues and Anti – Maximum Principle for Some Quasilinear Elliptic Equations on ℝN

We improve some previous existence and nonexistence results for positive principal eigenvalues of the problem —Δ_pu = λg(x)ψ^p(u), x ∈ ℝ^N, lim_{‖x‖⇒+∞}u(x) = 0. Also we discuss existence, nonexistence and antimaximum principle questions concerning the perturbed problem —Δ_pu = λg(x)ψ^p(u) + f(x), x∈ ℝ^N.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. 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. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

(g,f)-Factorizations of graphs orthogonal to [1,2]-subgraph

LetG be a simple graph. Letg(x) andf(x) be integer-valued functions defined onV(G) withf(x)g(x)1 for allxV(G). It is proved that ifG is an (mg+m–1,mf–m+1)-graph andH is a [1,2]-subgraph withm edges, then there exists a (g,f)-factorization ofG orthogonal toH.This work is supported by China Postdoctoral Science Foundation and Shandong Youth Science Foundation.     

Direct problem and inverse problem for the supersonic plane flow past a curved wedge

In this paper, we consider the isentropic irrotational steady plane flow past a curved wedge. First, for a uniform supersonic oncoming flow, we study the direct problem: For a given curved wedge y = f(x), how to globally determine the corresponding shock y = g(x) and the solution behind the shock? Then, we solve the corresponding inverse problem: How to globally determine the curved wedge y = f(x) under the hypothesis that the position of the shock y = g(x) and the uniform supersonic oncoming flow are given? This kind of problems plays an important role in the aviation industry. Under suitable assumptions, we obtain the global existence and uniqueness for both problems. Copyright © 2011 John Wiley & Sons, Ltd.     

Singular and nonsingular first-order initial value problems

Under barrier strip type arguments we investigate the existence of global solutions to the initial value problem x^′=f(t,x,x^′), x(0)=A, where the scalar function f(t,x,p) may be singular at x=A.     

Rational functions with partial quotients of small degree in their continued fraction expansion

For a rational functionf/g=f(x)/g(x) over a fieldF with ged (f,g)=1 and deg (g)1 letK(f/g) be the maximum degree of the partial quotients in the continued fraction expansion off/. ForfF[x] with deg (f)=k1 andf(O)O putL(f)=K(f(x)/x ^k ). It is shown by an explicit construction that for every integerb with 1bk there exists anf withL(f)=b. IfF=F ₂, the binary field, then for everyk there is exactly onefF ₂[x] with deg (f)=k,f(O)O, andL(f)=1. IfF _q is the finite field withq elements andgF _q [x] is monic of degreek1, then there exists a monic irreduciblefF _q [x] with deg (f)=k, gcd (f,g)=1, andK(f/g)<2+2 (logk)/logq, where the caseq=k=2 andg(x)=x ²+x+1 is excluded. An analogous existence theorem is also shown for primitive polynomials over finite fields. These results have applications to pseudorandom number generation.     

A General Duality Scheme for Nonconvex Minimization Problems with a Strict Inequality Constraint

We establish a duality formula for the problem Minimize f(x)+g(x) for h(x)+k(x)<0 where g, k are extended-real-valued convex functions and f, h belong to the class of functions that can be written as the lower envelope of an arbitrary family of convex functions. Applications in d.c. and Lipschitzian optimization are given.