Parameter estimation in systems of nonlinear equations

Summary. A numerical method is presented to determine parameters in a system of non\-linear equations in the following sense: Proceeding from given experimental data, e.g., observation times and measurements, the minimum least-squares distance of the measured data from a fitting criterion depending on the solution of a system of nonlinear equations is to be computed. Specifically coupled mass equilibrium models are described in more detail that are used in pharmaceutical applications for receptor-ligand binding studies. They are used for instance for the radioimmunological determination of Fenoterol or related substances. Numerical results based on laboratory data are included to test the robustness of the algorithm implemented. Received May 24, 1993/Revised version received February 13, 1994     

Convex programming for disjunctive convex optimization

Given a finite number of closed convex sets whose algebraic representation is known, we study the problem of finding the minimum of a convex function on the closure of the convex hull of the union of those sets. We derive an algebraic characterization of the feasible region in a higher-dimensional space and propose a solution procedure akin to the interior-point approach for convex programming. Received November 27, 1996 / Revised version received June 11, 1999?Published online November 9, 1999     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

On existence and uniqueness of stationary points in semi-infinite optimization

The paper deals with semi-infinite optimization problems which are defined by finitely many equality constraints and infinitely many inequality constraints. We generalize the concept of strongly stable stationary points which was introduced by Kojima for finite problems; it refers to the local existence and uniqueness of a stationary point for each sufficiently small perturbed problem, where perturbations up to second order are allowed. Under the extended Mangasarian-Fromovitz constraint qualification we present equivalent conditions for the strong stability of a considered stationary point in terms of first and second derivatives of the involved functions. In particular, we discuss the case where the reduction approach is not satisfied. Received June 30, 1995 / Revised version received October 9, 1998? Published online June 11, 1999     

Quadratic convergence of potential-reduction methods for degenerate problems

Global and local convergence properties of a primal-dual interior-point pure potential-reduction algorithm for linear programming problems is analyzed. This algorithm is a primal-dual variant of the Iri-Imai method and uses modified Newton search directions to minimize the Tanabe-Todd-Ye (TTY) potential function. A polynomial time complexity for the method is demonstrated. Furthermore, this method is shown to have a unique accumulation point even for degenerate problems and to have Q-quadratic convergence to this point by an appropriate choice of the step-sizes. This is, to the best of our knowledge, the first superlinear convergence result on degenerate linear programs for primal-dual interior-point algorithms that do not follow the central path. Received: February 12, 1998 / Accepted: March 3, 2000?Published online January 17, 2001     

Scenario tree generation for multiperiod financial optimization by optimal discretization

Multiperiod financial optimization is usually based on a stochastic model for the possible market situations. There is a rich literature about modeling and estimation of continuous-state financial processes, but little attention has been paid how to approximate such a process by a discrete-state scenario process and how to measure the pertaining approximation error.?In this paper we show how a scenario tree may be constructed in an optimal manner on the basis of a simulation model of the underlying financial process by using a stochastic approximation technique. Consistency relations for the tree may also be taken into account. Received: December 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Modeling languages and Condor: metacomputing for optimization

A generic framework is postulated for utilizing the computational resources provided by a metacomputer to concurrently solve a large number of optimization problems generated by a modeling language. An example of the framework using the Condor resource manager and the AMPL and GAMS modeling languages is provided. A mixed integer programming formulation of a feature selection problem from machine learning is used to test the mechanism developed. Due to this application’s computational requirements, the ability to perform optimizations in parallel is necessary in order to obtain results within a reasonable amount of time. Details about the simple and easy to use tool and implementation are presented so that other modelers with applications generating many independent mathematical programs can take advantage of it to significantly reduce solution times. Received: October 28, 1998 / Accepted: December 01, 1999?Published online June 8, 2000     

On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems

Infeasible-interior-point paths , a positive vector, for a horizontal linear complementarity problem are defined as the solution of () If the path converges for , then it converges to a solution of . This paper deals with the analyticity properties of and its derivatives with respect to r near r = 0 for solvable monotone complementarity problems . It is shown for with a strictly complementary solution that the path , , has an extension to which is analytic also at . If has no strictly complementary solution, then , , has an extension to that is analytic at . Received May 24, 1996 / Revised version received February 25, 1998     

Characterization of the smoothness and curvature of a marginal function for a trust-region problem

Received May 28, 1996 / Revised version received May 1, 1998 Published online October 9, 1998     

Inexact implicit methods for monotone general variational inequalities

Solving a variational inequality problem is equivalent to finding a solution of a system of nonsmooth equations. Recently, we proposed an implicit method, which solves monotone variational inequality problem via solving a series of systems of nonlinear smooth (whenever the operator is smooth) equations. It can exploit the facilities of the classical Newton–like methods for smooth equations. In this paper, we extend the method to solve a class of general variational inequality problems Moreover, we improve the implicit method to allow inexact solutions of the systems of nonlinear equations at each iteration. The method is shown to preserve the same convergence properties as the original implicit method. Received July 31, 1995 / Revised version received January 15, 1999? Published online May 28, 1999     

Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on the Kojima-Shindoh-Hara family of directions

Received August 29, 1996 / Revised version received May 1, 1998 Published online October 21, 1998     

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

Collocation methods for solving linear differential-algebraic boundary value problems

Summary. We consider boundary value problems for linear differential-algebraic equations with variable coefficients with no restriction on the index. A well-known regularisation procedure yields an equivalent index one problem with d differential and a=n-d algebraic equations. Collocation methods based on the regularised BVP approximate the solution x by a continuous piecewise polynomial of degree k and deliver, in particular, consistent approximations at mesh points by using the Radau schemes. Under weak assumptions, the collocation problems are uniquely and stably solvable and, if the unique solution x is sufficiently smooth, convergence of order min {k+1,2k-1} and superconvergence at mesh points of order 2k-1 is shown. Finally, some numerical experiments illustrating these results are presented. Received October 1, 1999 / Revised version received April 25, 2000 / Published online December 19, 2000     

On a decoupled algorithm for solving a finite element problem for the approximation of viscoelastic fluid flow

Summary. The aim of this work is to study a decoupled algorithm of a fixed point for solving a finite element (FE) problem for the approximation of viscoelastic fluid flow obeying an Oldroyd B differential model. The interest for this algorithm lies in its applications to numerical simulation and in the cost of computing. Furthermore it is easy to bring this algorithm into play. The unknowns are the viscoelastic part of the extra stress tensor, the velocity and the pressure. We suppose that the solution is sufficiently smooth and small. The approximation of stress, velocity and pressure are resp. discontinuous, continuous, continuous FE. Upwinding needed for convection of , is made by discontinuous FE. The method consists to solve alternatively a transport equation for the stress, and a Stokes like problem for velocity and pressure. Previously, results of existence of the solution for the approximate problem and error bounds have been obtained using fixed point techniques with coupled algorithm. In this paper we show that the mapping of the decoupled fixed point algorithm is locally (in a neighbourhood of ) contracting and we obtain existence, unicity (locally) of the solution of the approximate problem and error bounds. Received July 29, 1994 / Revised version received March 13, 1995     

An inexactQP-based method for nonlinear complementarity problems

Summary. We consider a quadratic programming-based method for nonlinear complementarity problems which allows inexact solutions of the quadratic subproblems. The main features of this method are that all iterates stay in the feasible set and that the method has some strong global and local convergence properties. Numerical results for all complementarity problems from the MCPLIB test problem collection are also reported. Received February 24, 1997 / Revised version received September 5, 1997     

On an a posteriori parameter choice strategy for Tikhonov regularization of nonlinear ill-posed problems

Summary. In the study of the choice of the regularization parameter for Tikhonov regularization of nonlinear ill-posed problems, Scherzer, Engl and Kunisch proposed an a posteriori strategy in 1993. To prove the optimality of the strategy, they imposed many very restrictive conditions on the problem under consideration. Their results are difficult to apply to concrete problems since one can not make sure whether their assumptions are valid. In this paper we give a further study on this strategy, and show that Tikhonov regularization is order optimal for each with the regularization parameter chosen according to this strategy under some simple and easy-checking assumptions. This paper weakens the conditions needed in the existing results, and provides a theoretical guidance to numerical experiments. Received August 8, 1997 / Revised version received January 26, 1998     

Finite volume element methods for non-definite problems

Summary. The error estimates for finite volume element method applied to 2 and 3-D non-definite problems are derived. A simple upwind scheme is proven to be unconditionally stable and first order accurate. Received August 27, 1997 / Revised version received May 12, 1998     

A new inexact alternating directions method for monotone variational inequalities

The alternating directions method (ADM) is an effective method for solving a class of variational inequalities (VI) when the proximal and penalty parameters in sub-VI problems are properly selected. In this paper, we propose a new ADM method which needs to solve two strongly monotone sub-VI problems in each iteration approximately and allows the parameters to vary from iteration to iteration. The convergence of the proposed ADM method is proved under quite mild assumptions and flexible parameter conditions. Received: January 4, 2000 / Accepted: October 2001?Published online February 14, 2002     

Conditioning of semidefinite programs

theory. This approach also quantifies the size of permissible perturbations. We include a discussion of these results for block diagonal semidefinite programs, of which linear programming is a special case. Received November 26, 1995 / Revised version received November 1, 1998 Published online February 25, 1999     

On the locking phenomenon for a class of elliptic problems

Summary. In this paper we study the numerical behaviour of elliptic problems in which a small parameter is involved and an example concerning the computation of elastic arches is analyzed using this mathematical framework. At first, the statements of the problem and its Galerkin approximations are defined and an asymptotic analysis is performed. Then we give general conditions ensuring that a numerical scheme will converge uniformly with respect to the small parameter. Finally we study an example in computation of arches working in linear elasticity conditions. We build one finite element scheme giving a locking behaviour, and another one which does not. Revised version received October 25, 1993