Approximating Networks and Extended Ritz Method for the Solution of Functional Optimization Problems

Functional optimization problems can be solved analytically only if special assumptions are verified; otherwise, approximations are needed. The approximate method that we propose is based on two steps. First, the decision functions are constrained to take on the structure of linear combinations of basis functions containing free parameters to be optimized (hence, this step can be considered as an extension to the Ritz method, for which fixed basis functions are used). Then, the functional optimization problem can be approximated by nonlinear programming problems. Linear combinations of basis functions are called approximating networks when they benefit from suitable density properties. We term such networks nonlinear (linear) approximating networks if their basis functions contain (do not contain) free parameters. For certain classes of d-variable functions to be approximated, nonlinear approximating networks may require a number of parameters increasing moderately with d, whereas linear approximating networks may be ruled out by the curse of dimensionality. Since the cost functions of the resulting nonlinear programming problems include complex averaging operations, we minimize such functions by stochastic approximation algorithms. As important special cases, we consider stochastic optimal control and estimation problems. Numerical examples show the effectiveness of the method in solving optimization problems stated in high-dimensional settings, involving for instance several tens of state variables.     

Numerical treatment of singularly perturbed two point boundary value problems using initial-value method

In this paper, we describe an initial-value method for linear and nonlinear singularly perturbed boundary value problems in the interval [p,q]. For linear problems, the required approximate solution is obtained by solving the reduced problem and one initial-value problems directly deduced from the given problem. For nonlinear problems the original second-order nonlinear problem is linearized by using quasilinearization method. Then this linear problem is solved as previous method. The present method has been implemented on several linear and non-linear examples which approximate the exact solution. We also present the approximate and exact solutions graphically.     

Lax pairs and a new spectral method for linear and integrable nonlinear PDEs

A new transform method for solving initial-boundary value problems for linear and integrable nonlinear PDEs in two independent variables has been recently introduced in [1]. For linear PDEs this method involves: (a) formulating the given PDE as the compatibility condition of two linear equations which, by analogy with the nonlinear theory, we call a Lax pair; (b) formulating a classical mathematical problem, the so-called Riemann-Hilbert problem, by performing a simultaneous spectral analysis of both equations defining the Lax pair; (c) deriving certain global relations satisfied by the boundary values of the solution of the given PDE. Here this method is used to solve certain problems for the heat equation, the linearized Korteweg-deVries equation and the Laplace equation. Some of these problems illustrate that the new method can be effectively used for problems with complicated boundary conditions such as changing type as well as nonseparable boundary conditions. It is shown that for simple boundary conditions the global relations (c) can be analyzed using only algebraic manipulations, while for complicated boundary conditions, one needs to solve an additional Riemann-Hilbert problem. The relationship of this problem with the classical Wiener-Hopf technique is pointed out. The extension of the above results to integrable nonlinear equations is also discussed. In particular, the Korteweg-deVries equation in the quarter plane is linearized.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Minimizing a Sum of Norms Subject to Linear Equality Constraints

Numerical analysis of a class of nonlinear duality problems is presented. One side of the duality is to minimize a sum of Euclidean norms subject to linear equality constraints (the constrained MSN problem). The other side is to maximize a linear objective function subject to homogeneous linear equality constraints and quadratic inequalities. Large sparse problems of this form result from the discretization of infinite dimensional duality problems in plastic collapse analysis.The solution method is based on the l ₁ penalty function approach to the constrained MSN problem. This can be formulated as an unconstrained MSN problem for which the first author has recently published an efficient Newton barrier method, and for which new methods are still being developed.Numerical results are presented for plastic collapse problems with up to 180000 variables, 90000 terms in the sum of norms and 90000 linear constraints. The obtained accuracy is of order 10^-8 measured in feasibility and duality gap.     

Gauss-Newton and Inverse Gauss-Newton Methods for Coefficient Identification in Linear Elastic Systems

The “inverse problem” of determining parameter distributions in linear elastic structures has been explored widely in the literature. In the present article we discuss this problem in the context of a particular formulation of linear elastic systems, dividing the associated inverse problems into two classes which we call Case 1 and Case 2. In the first case the elastic parameters can be obtained by solving a certain set of linear algebraic equations, typically poorly conditioned. In the second case the corresponding problem involves nonlinear equations which usually must be solved by approximation methods, including the Gauss-Newton method for overdetermined systems. Here we discuss the application of this method and a related, empirically more stable, method which we call the inverse Gauss-Newton method. Convergence theorems are established and computational results for sample problems are presented.     

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 full multigrid method for nonlinear eigenvalue problems

We introduce a type of full multigrid method for the nonlinear eigenvalue problem. The main idea is to transform the solution of the nonlinear eigenvalue problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and nonlinear eigenvalue problems on the coarsest finite element space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient iteration methods for solving boundary value problems can serve as the linear problem solver. We prove that the computational work of this new scheme is truly optimal, the same as solving the linear corresponding boundary value problem. In this case, this type of iteration scheme certainly improves the overfull efficiency of solving nonlinear eigenvalue problems. Some numerical experiments are presented to validate the efficiency of the new method.     

An inexact Newton method for nonlinear two-point boundary-value problems

The method of quasilinearization for nonlinear two-point boundary-value problems is an application of Newton's method to a nonlinear differential operator equation. Since the linear boundary-value problem to be solved at each iteration must be discretized, it is natural to consider quasilinearization in the framework of an inexact Newton method. More importantly, each linear problem is only a local model of the nonlinear problem, and so it is inefficient to try to solve the linear problems to full accuracy. Conditions on size of the relative residual of the linear differential equation can then be specified to guarantee rapid local convergence to the solution of the nonlinear continuous problem. If initial-value techniques are used to solve the linear boundary-value problems, then an integration step selection scheme is proposed so that the residual criteria are satisfied by the approximate solutions. Numerical results are presented that demonstrate substantial computational savings by this type of economizing on the intermediate problems.This work was supported in part by DOE Contract DE-AS05-82-ER13016 and NSF Grant RII-89-17691 and was part of the author's doctoral thesis at Rice University. It is a pleasure to thank the author's thesis advisors, Professor R. A. Tapia and Professor J. E. Dennis, Jr.     

On a method of solving physically nonlinear problems in the bending of thick rectangular plates

We study the three-dimensional boundary-value problem of the physically nonlinear theory of elasticity for bending of a homogeneous isotropic thick plate by transverse forces. We assume that the intensity of the load is such that the connection between the stresses and small strains within the elastic limit can be described by nonlinear relations in the form of H. Kauderer. We develop an approximate analytic method that makes it possible to reduce the original nonlinear boundary-value problem to a recursive sequence of corresponding linear boundary-value problems. Translated fromMatematichni Metodi i Fiziko-mekhanichni Polya, No. 40, 1997, pp. 30–35.     

On the ball spanned by balls

The procedure for linear programming in linear time in fixed dimension is extended to solve in linear time certain nonlinear problems. Examples are the problem of finding the smallest ball enclosingn given balls, and the weighted-center problem in fixed dimension.     

Method for solving nonlinear initial value problems by combining homotopy perturbation and reproducing kernel Hilbert space methods

The nonlinear singular initial value problems including generalized Lane–Emden-type equations are investigated by combining homotopy perturbation method (HPM) and reproducing kernel Hilbert space method (RKHSM). He’s HPM is based on the use of traditional perturbation method and homotopy technique and can reduce a nonlinear problem to some linear problems and generate a rapid convergent series solution in most cases. RKHSM is also an analytical technique, which can overcome the difficulty at the singular point of non-homogeneous, linear singular initial value problems; especially when the singularity appears on the right-hand side of this type of equations, so it can solve powerfully linear singular initial value problems. Therefore, using advantages of these two methods, more general nonlinear singular initial value problems can be solved powerfully. Some numerical examples are presented to illustrate the strength of the method.     

Calculation of bounds on variables satisfying nonlinear inequality constraints

Existing techniques for solving nonconvex programming problems often rely on the availability of lower and upper bounds on the problem variables. This paper develops a method for obtaining these bounds when not all of them are availablea priori. The method is a generalization of the method of Fourier which finds bounds on variables satisfying linear inequality constraints. First, nonlinear inequality constraints are converted to equivalent sets of separable constraints. Generalized variable elimination techniques are used to reduce these to constraints in one variable. Bounds on that variable are obtained and an inductive process yields bounds on the others.Research Sponsored by the Office of Naval Research Grant N00014-89-J-1537.     

On the numerical solution of stochastic quadratic integral equations via operational matrix method

In this paper, stochastic operational matrix of integration based on delta functions is applied to obtain the numerical solution of linear and nonlinear stochastic quadratic integral equations (SQIEs) that appear in modelling of many real problems. An important advantage of this method is that it dose not need any integration to compute the constant coefficients. Also, this method can be utilized to solve both linear and nonlinear problems. By using stochastic operational matrix of integration together collocation points, solving linear and nonlinear SQIEs converts to solve a nonlinear system of algebraic equations, which can be solved by using Newton's numerical method. Moreover, the error analysis is established by using some theorems. Also, it is proved that the rate of convergence of the suggested method is O(h²). Finally, this method is applied to solve some illustrative examples including linear and nonlinear SQIEs. Numerical experiments confirm the good accuracy and efficiency of the proposed method.     

Multi-Duality in Minimal Surface—Type Problems

The multi-duality of the nonlinear variational problem inf J(u, Λu) is studied for minimal surfaces-type problems. By using the method developed by Gao and Strang [1], the Fenchel-Rockafellar's duality theory is generalized to the problems with affine operator Λ. Two dual variational principles are established for nonparametric surfaces with constant mean curvature. We show that for the same primal problem, there may exist different dual problems. The primal problem may or may not possess a solution, whereas each dual problem possesses a unique solution. An evolutionary method for solving the nonlinear optimal-shape design problem is presented with numerical results.     

On the SQH Scheme to Solve Nonsmooth PDE Optimal Control Problems

A sequential quadratic Hamiltonian (SQH) scheme for solving different classes of nonsmooth and nonconvex partial differential equation (PDE) optimal control problems is investigated considering seven different benchmark problems with increasing difficulty. These problems include linear and nonlinear PDEs with linear and bilinear control mechanisms, nonconvex, and discontinuous costs of the controls, L¹ tracking terms, and the case of state constraints. The SQH method is based on the characterization of optimality of PDE optimal control problems by the Pontryagin’s maximum principle (PMP). For each problem, a theoretical discussion of the PMP optimality condition is given and results of numerical experiments are presented that demonstrate the large range of applicability of the SQH scheme.     

Nonreflecting Boundary Conditions for Nonlinear Problems of Fluid Dynamics

External problems of fluid dynamics are modeled on artificially bounded regions. A method is proposed for applying nonreflecting boundary conditions to the linearized Euler equations obtained from the original nonlinear problem. The nonreflecting conditions are modified to allow for viscosity and nonhomogeneity of unperturbed background flow in linear Euler, Navier–Stokes, and quasi-fluid-dynamic models. One-dimensional test problems are computed in the linear and nonlinear cases.     

An analytic method of studying the nonlinearly elastic equilibrium of a rectangular plate of variable thickness under bending

We propose an approximate analytic method of solving three-dimensional boundary-value problems of the physically nonlinear theory of elasticity for thick rectangular plates of variable thickness subject to a transverse load. The method is used to seek a solution of this problem in the form of double power series in small dimensionless parameters. In arbitrary approximation the original problem is reduced to a sequence of linear inhomogeneous boundary-value problems for plates of constant thickness. Bibliography: 6 titles. Translated fromTeoreticheskaya i Prikladnaya Mekhanika, No. 28, 1998, pp. 36–40     

Approximate solution methods in mechanics analysis of a class of nonlinear seepage problems by a finite-element method

We analyze the nonlinear boundary-value problem of seepage under a subsurface hydrotechnical construction over an inclined rectilinear aquifer. The method of inverse boundary-value problems is applied, using the velocity hodograph plane in which the original problem is reduced to a linear problem. The linear problem is solved in the general case using the finite-element method. A computer program realizing the proposed algorithms has been developed. We have used this program to run a series of numerical experiments, reaching certain conclusions about the behavior of the main seepage characteristics.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 55, pp. 75–80, 1985.     

Numerical implementation of iteration processes applied in the study of nonlinear boundary value problems of the theory of elasticity and filtration

Nonlinear elastic problems for hardening media are solved by applying the universal iteration process proposed by A.I. Koshelev in his works on the regularity of solutions to quasilinear elliptic and parabolic systems. This requires numerically solving a linear elliptic system at each step of the iteration procedure. The method is numerically implemented in the MATLAB environment by using its PDE Toolbox. A modification of the finite-element procedure is suggested in order to solve a linear algebraic system at each iteration step. The computer model is tested on simple examples. The same nonlinear problems are also solved by the method of elastic solutions, which consists in replacing the Laplace operator in the universal iteration process by the Lamé operator of linear elasticity. As is known, this iteration process converges to a weak solution of the nonlinear problem, provided that the displacements are fixed on the boundary. The method is tested on examples with stresses on the boundary. The third part of the paper is devoted to the nonlinear filtration problem. General properties of the iteration process for nonlinear parabolic systems have been studied by A.I. Koshelev and V.M. Chistyakov. The numerical implementation is based on slightly modified PDE Toolbox procedures. The program is tested on simple examples.