CGS algorithms for constrained extremization of functions

CGS (conjugate Gram-Schmidt) algorithms are given for computing extreme points of a real-valued functionf(x) ofn real variables subject tom constraining equationsg(x)=0,M<n. The method of approach is to solve the system $$\begin{gathered} f'(x) + g'(x)*\lambda = 0 \hfill \\ g(x) = 0 \hfill \\ \end{gathered} $$ where λ is the Lagrange multiplier vector, by means of CGS algorithms for systems of nonlinear equations. Results of the algorithms applied to test problems are given, including several problems having inequality constraints treated by adjoining slack variables.     

CGS algorithms for unconstrained minimization of functions

In 1952, Hestenes and Stiefel first established, along with the conjugate-gradient algorithm, fundamental relations which exist between conjugate direction methods for function minimization on the one hand and Gram-Schmidt processes relative to a given positive-definite, symmetric matrix on the other. This paper is based on a recent reformulation of these relations by Hestenes which yield the conjugate Gram-Schmidt (CGS) algorithm. CGS includes a variety of function minimization routines, one of which is the conjugate-gradient routine. This paper gives the basic equations of CGS, including the form applicable to minimizing general nonquadratic functions ofn variables. Results of numerical experiments of one form of CGS on five standard test functions are presented. These results show that this version of CGS is very effective.The preparation of this paper was sponsored in part by the US Army Research Office, Grant No. DH-ARO-D-31-124-71-G18.The authors wish to thank Mr. Paul Speckman for the many computer runs made using these algorithms. They served as a good check on the results which they had obtained earlier. Special thanks must go to Professor M. R. Hestenes whose constant encouragement and assistance made this paper possible.     

On a characterization of convergence for the Hestenes method of multipliers

The connection between the convergence of the Hestenes method of multipliers and the existence of augmented Lagrange multipliers for the constrained minimum problem (P): minimizef(x), subject tog(x)=0, is investigated under very general assumptions onX,f, andg.In the first part, we use the existence of augmented Lagrange multipliers as a sufficient condition for the convergence of the algorithm. In the second part, we prove that this is also a necessary condition for the convergence of the method and the boundedness of the sequence of the multiplier estimates.Further, we give very simple examples to show that the existence of augmented Lagrange multipliers is independent of smoothness condition onf andg. Finally, an application to the linear-convex problem is given.     

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).     

Rado Numbers fora(x+y)=bz

In the case of existence the smallest numberN=Ra_kis called a Rado number if it is guaranteed that anyk-coloring of the numbers 1, 2, …, Ncontains a monochromatic solution of a given system of linear equations. We will determine Ra_k(a, b) for the equationa(x+y)=bzifb=2 andb=a+1. Also, the case of monochromatic sequences {x_n} generated bya(x_n+x_n+1)=bx_n+2 is discussed.     

Approximate solution of differential equations with the use of asymptotic polynomials

We consider an approximate solution of differential equations with initial and boundary conditions. To find a solution, we use asymptotic polynomials Q _n ^f (x) of the first kind based on Chebyshev polynomials T _n (x) of the first kind and asymptotic polynomials G _n ^f (x) of the second kind based on Chebyshev polynomials U _n (x) of the second kind. We suggest most efficient algorithms for each of these solutions. We find classes of functions for which the approximate solution converges to the exact one. The remainder is represented as an expansion in linear functionals {L _n ^f } in the first case and {M _n ^f } in the second case, whose decay rate depends on the properties of functions describing the differential equation.     

Capturing Ridge Functions in High Dimensions from Point Queries

Constructing a good approximation to a function of many variables suffers from the “curse of dimensionality”. Namely, functions on ℝ ^N with smoothness of order s can in general be captured with accuracy at most O(n ^−s/N ) using linear spaces or nonlinear manifolds of dimension n. If N is large and s is not, then n has to be chosen inordinately large for good accuracy. The large value of N often precludes reasonable numerical procedures. On the other hand, there is the common belief that real world problems in high dimensions have as their solution, functions which are more amenable to numerical recovery. This has led to the introduction of models for these functions that do not depend on smoothness alone but also involve some form of variable reduction. In these models it is assumed that, although the function depends on N variables, only a small number of them are significant. Another variant of this principle is that the function lives on a low dimensional manifold. Since the dominant variables (respectively the manifold) are unknown, this leads to new problems of how to organize point queries to capture such functions. The present paper studies where to query the values of a ridge function f(x)=g(a⋅x) when both a∈ℝ ^N and g∈C[0,1] are unknown. We establish estimates on how well f can be approximated using these point queries under the assumptions that g∈C ^s [0,1]. We also study the role of sparsity or compressibility of a in such query problems.     

Asynchronous Multisplitting GAOR Method and Asynchronous Multisplitting SSOR Method for Systems of Weakly Nonlinear Equations

In this article, we introduce two new asynchronous multisplitting methods for solving the system of weakly nonlinear equations Ax = G(x) in which A is an n × n real matrix and G(x) = (g ₁(x), g ₂(x), . . . , g _n (x)) ^T is a P-bounded mapping. First, by generalized accelerated overrelaxation (GAOR) technique, we introduce the asynchronous parallel multisplitting GAOR method (including the synchronous parallel multisplitting AOR method as a special case) for solving the system of weakly nonlinear equations. Second, asynchronous parallel multisplitting method based on symmetric successive overrelaxation (SSOR) multisplitting is introduced, which is called asynchronous parallel multisplitting SSOR method. Then under suitable conditions, we establish the convergence of the two introduced methods. The given results contain synchronous multisplitting iterations as a special case.     

Existence of the mild solution for some fractional differential equations with nonlocal conditions

We are concerned in this paper with the existence of mild solutions to the Cauchy Problem for the fractional differential equation with nonlocal conditions: D ^q x(t)=Ax(t)+t ⁿ f(t,x(t),Bx(t)), t∈[0,T], n∈ℤ⁺, x(0)+g(x)=x ₀, where 0<q<1, A is the infinitesimal generator of a C ₀-semigroup of bounded linear operators on a Banach space X.     

An Improved Interval Linearization for Solving Nonlinear Problems

Let f(x) denote a system of n nonlinear functions in m variables, m≥n. Recently, a linearization of f(x) in a box x has been suggested in the form L(x)=Ax+b where A is a real n×m matrix and b is an interval n-dimensional vector. Here, an improved linearization L(x,y)=Ax+By+b, x∈x, y∈y is proposed where y is a p-dimensional vector belonging to the interval vector y while A and B are real matrices of appropriate dimensions and b is a real vector. The new linearization can be employed in solving various nonlinear problems: global solution of nonlinear systems, bounding the solution set of underdetermined systems of equations or systems of equalities and inequalities, global optimization. Numerical examples illustrating the superiority of L(x,y)=Ax+By+b over L(x)=Ax+b have been solved for the case where the problem is the global solution of a system of nonlinear equations (n=m).     

Picard iterates for positive solutions of a class of nonlinear eigenvalue problems

Summary We study positive solutions of the nonlinear eigenvalue problemF(u)=G(u) with some monotone operatorsF andG. In particular, we consider the case of nonlinear elliptic differential equations of second order and chooseF(u)=–divA(x, gradu)+b(x,u) and G(u)=g (x,u). Positive solutions are obtained by the Picard iterationsu ₀=0 andF(u _n+1)=G(u _n ).In order to get convergence of the sequenceu _n ,one has to study some comparison principles for the operatorF. Finally, the Picard iteration scheme allows a-priori estimates and bifurcation results for the admissible eigenvalue parameter.

---

Zusammenfassung Für gewisse monotone OperatorenF andG untersuchen wir positive Lösungen des nichtlinearen EigenwertproblemsF(u)=G(u). Insbesondere betrachten wir nichtlineare elliptische Differentialgleichungen zweiter Ordnung und wählenF(u)=–divA(x, gradu)+b(x,u) sowieG(u)=g(x,u). Man erhält positive Lösungen durch das Picard-Iterationsverfahrenu ₀=0 undF(u _n+1)=G(u _n ).Um die Konvergenz der Folgeu _n nachzuweisen, benötigt man Vergleichsprinzipien fürF. Dann gestattet das Iterationsschema sogar a-priori Abschätzungen und Verzweigungsaussagen für die zulässigen Eigenwertparameter.

---

---

Supported by the Deutscher Akademischer Austauschdienst (DAAD) and DICYT-University of Santiago de Chile.     

Convex envelopes of products of convex and component-wise concave functions

In this paper, we consider functions of the form f(x,y)=f(x)g(y){\phi(x,y)=f(x)g(y)} over a box, where f(x), x ? \mathbb R{f(x), x\in {\mathbb R}} is a nonnegative monotone convex function with a power or an exponential form, and g(y), y ? \mathbb Rⁿ{g(y), y\in {\mathbb R}^n} is a component-wise concave function which changes sign over the vertices of its domain. We derive closed-form expressions for convex envelopes of various functions in this category. We demonstrate via numerical examples that the proposed envelopes are significantly tighter than popular factorable programming relaxations.     

Nonlinear functional equations satisfied by orthogonal polynomials

Let c be a linear functional defined by its moments c(xⁱ)=c_i for i=0,1,…. We proved that the nonlinear functional equations P(t)=c(P(x)P(αx+t)) and P(t)=c(P(x)P(xt)) admit polynomial solutions which are the polynomials belonging to the family of formal orthogonal polynomials with respect to a linear functional related to c. This equation relates the polynomials of the family with those of the scaled and shifted family. Other types of nonlinear functional equations whose solutions are formal orthogonal polynomials are also presented. Applications to Legendre and Chebyshev polynomials are given. Then, orthogonality with respect to a definite inner product is studied. When c is an integral functional with respect to a weight function, the preceding functional equations are nonlinear integral equations, and these results lead to new characterizations of orthogonal polynomials on the real line, on the unit circle, and, more generally, on an algebraic curve.     

On complex manifolds polarized by an ample line bundle of sectional genus q ( X ) + 2

Let (X,L) be a polarized manifold with dim X = n. In this paper, we classify (X,L) with n = 3, , and g(L)=q(X) + 2. Moreover we also classify (X,L) with , g(L)=q(x) + 2, and . Received February 12, 1999     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Norm inequalities for vector functions

We study vector functions of Rn into itself, which are of the form x?g(|x|)x, where g:(0,∞)→(0,∞) is a continuous function and call these radial functions. In the case when g(t)=tc for some c∈R, we find upper bounds for the distance of image points under such a radial function. Some of our results refine recent results of L. Maligranda and S.S. Dragomir. In particular, we study quasiconformal mappings of this simple type and obtain norm inequalities for such mappings.     

Functional equations on semigroups

Summary. We determine the general solution g:S? F g:S\to F of the d'Alembert equation¶¶g(x+y)+g(x+sy)=2g(x)g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)g(y)\qquad (x,y\in S) ,¶the general solution g:S? G g:S\to G of the Jensen equation¶¶g(x+y)+g(x+sy)=2g(x)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)\qquad (x,y\in S) ,¶and the general solution g:S? H g:S\to H of the quadratic equation¶¶g(x+y)+g(x+sy)=2g(x)+2g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)+2g(y)\qquad (x,y\in S) ,¶ where S is a commutative semigroup, F is a quadratically closed commutative field of characteristic different from 2, G is a 2-cancellative abelian group, H is an abelian group uniquely divisible by 2, and s \sigma is an endomorphism of S with s(s(x)) = x \sigma(\sigma(x)) = x .     

A Numerical solution to the linear and nonlinear Fredholm integral equations using Legendre wavelet functions

Two methods for solving the Fredholm integral equation of the second kind in linear case, i.e. f (x) – λ ∫_a^b K (x,y)f (y)dy = g (x), and nonlinear case, i.e., f (x) = g (x) + λ ∫_a^b K (x,y)F (f (y))dy, are proposed. In order to solve the linear equation, the kernel K (x,y) as well as the functions f and g are initially approximated through Legendre wavelet functions. This leads to a system of linear equations its solution culminates in a solution to the Fredholm integral equation. In nonlinear case only K (x,y) is approximated by Legendre wavelet base functions. This leads to a separable kernel and makes it possible to employ a number of earlier methods in solving nonlinear Fredholm integral equation with separable kernels. Another feature of the proposed method is that it finds the solution as a function instead of specific solution points, what is done by the majority of the existing methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A computational method for minimization with nonlinear constraints

An iterative technique is developed to solve the problem of minimizing a functionf(y) subject to certain nonlinear constraintsg(y)=0. The variables are separated into the basic variablesx and the independent variablesu. Each iteration consists of a gradient phase and a restoration phase. The gradient phase involves a movement (on a surface that is linear in the basic variables and nonlinear in the independent variables) from a feasible point to a varied point in a direction based on the reduced gradient. The restoration phase involves a movement (in a hyperplane parallel tox-space) from the nonfeasible varied point to a new feasible point.The basic scheme is further modified to implement the method of conjugate gradients. The work required in the restoration phase is considerably reduced when compared with the existing methods.     

Periodic solutions of non-smooth friction oscillators

We study the differential equation x"+g(x￠)+m(x) sgn x￠+f(x)=j(t)x''+g(x')+\mu(x)\,{\rm sgn}\, x'+f(x)=\varphi(t) with T-periodic right-hand side, which models e.g. a mechanical system with one degree of freedom subjected to dry friction and periodic external force. If, in particular, the damping term g is present and acts, up to a bounded difference, like a linear damping, we get existence of a T-periodic solution.¶In the more difficult case g = 0, we concentrate on the model equation x"+m(x) sgn x￠+x=j(t)x''+\mu(x)\,{\rm sgn}\,x'+x=\varphi(t) and obtain sufficient conditions for the existence of a T-periodic solution by application of Brouwer's fixed point theorem. For this purpose we show that a certain associated autonomous differential equation admits a periodic orbit such that the surrounded set (minus some neighborhood of the equilibria) is forward invariant for the equation above. Under additional assumptions on 7 we prove boundedness of all solutions.¶Finally, we provide a principle of linearized stability for periodic solutions without deadzones, where the "linearized" differential equation is an impulsive Hill equation.