Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.     

Inverse Problem for an Integro-Differential Equation of Acoustics

We consider the hyperbolic integro-differential equation of acoustics. The direct problem is to determine the acoustic pressure created by a concentrated excitation source located at the boundary of a spatial domain from the initial boundary-value problem for this equation. For this direct problem, we study the inverse problem, which consists in determining the onedimensional kernel of the integral term from the known solution of the direct problem at the point x = 0 for t > 0. This problem reduces to solving a system of integral equations in unknown functions. The latter is solved by using the principle of contraction mapping in the space of continuous functions. The local unique solvability of the posed problem is proved.     

The integration of an interior-point cutting plane method within a branch-and-price algorithm

This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a central dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newtons method to calculate the new analytic centre after branching. Second, we discuss the integration of ACCPM within the branch-and-price algorithm. We detail the use of ACCPM as the search goes deep in the branch and bound tree, making full utilization of past information as a warm start. We exploit dual information from ACCPM to generate incumbent feasible solutions and to guide branching. Finally, the overall approach is implemented and tested for the bin-packing problem and the capacitated facility location problem with single sourcing. We compare against Cplex-MIP 7.5 as well as a classical branch-and-price algorithm.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Solutions of an evolution equation whose inhomogeneous part is an entire function

We study the evolution equation y(t)=Ay(t)+f(t), y(0)=y₀; t [0, ), in a Banach space B, where the operator A is the infinitesimal generator of a boundedC ₀-semigroup and f(t) is an entire function. We establish sufficient conditions under which the solution can be represented in the form y(t)=v(t)+g(t), where g(t) is an entire function and v(t) is the solution of the homogeneous equation with a certain condition. We also consider the inverse problem.Translated fromMatematichni Metodi ta Fiziko-Mekhanichni Polya, Vol. 40, No. 4, 1997, pp. 119–121.     

The Saffman-Taylor problem for an extremely shear-thinning fluid

We consider a steady flow driven by pushing a finger of gasinto a highly shear-thinning power-law fluid, with exponentn, in a Hele-Shaw channel. We formulate the problem in termsof the streamfunction , which satisfies the p-Laplacian equation (with ), and investigate travelling wave solutions in the large-n (extreme shear-thinning) limit.We take a Legendre transform of the free-boundary problem for, which reduces it to a linear problem on a fixed domain. The solution to this problem is foundby using matched asymptotic expansions and the resulting shapeof the finger deduced (being, to leading order, a semi-infinitestrip). The nonlinear problem for the streamfunction is alsotreated using matched asymptotic expansion in the physical plane.The finger-width selection problem is briefly discussed in termsof our results.     

A semi-implicit monotone difference scheme for an initial-boundary value problem of a strongly degenerate parabolic equation modeling sedimentation-consolidation processes

We prove the convergence of a semi-implicit monotone finite difference scheme approximating an initial-boundary value problem for a spatially one-dimensional quasilinear strongly degenerate parabolic equation, which is supplied with two different inhomogeneous flux-type boundary conditions. This problem arises in the modeling of the sedimentation-consolidation process. We formulate the definition of entropy solution of the model in the sense of Kru kov and prove convergence of the scheme to the unique entropy solution of the problem, up to satisfaction of one of the boundary conditions.

     

Peano's theorem in an infinite-dimensional Hilbert space is false even in a weakened formulation

We formulate a continuous function FR×HH, where H is a separable Hilbert space such that the Cauchy problem. x(t)=F(t, x(t)), x(t₀)=x₀ has no solution in any neighborhood of the point t₀, no matter what t₀ R and x₀ H are considered.Translated from Matematicheskie Zametki, Vol. 15, No. 3, pp. 467–477, March, 1974.In conclusion, the author thanks O. G. Smolyanov and V. I. Averbukh for their constant interest and for a number of useful remarks.     

Stability and convergence of discrete kinetic approximations to an initial-boundary value problem for conservation laws

We present some new convergence results for a discrete velocities BGK approximation to an initial boundary value problem for a single hyperbolic conservation law. In this paper we show stability and convergence toward a unique entropy solution in the general framework without any restriction either on the data of the limit problem or on the set of velocity of the BGK model.

     

Solving the Sum-of-Ratios Problem by an Interior-Point Method

We consider the problem of minimizing the sum of a convex function and of p1 fractions subject to convex constraints. The numerators of the fractions are positive convex functions, and the denominators are positive concave functions. Thus, each fraction is quasi-convex. We give a brief discussion of the problem and prove that in spite of its special structure, the problem is -complete even when only p=1 fraction is involved. We then show how the problem can be reduced to the minimization of a function of p variables where the function values are given by the solution of certain convex subproblems. Based on this reduction, we propose an algorithm for computing the global minimum of the problem by means of an interior-point method for convex programs.     

On the Growth of Meromorphic Solutions of an Algebraic Differential Equation in a Neighborhood of a Logarithmic Singular Point

We prove that if an analytic function f with an isolated singular point at is a solution of the differential equation P(zlnz, f, f) = 0, where P is a polynomial in all variables, then f has finite order. We study the asymptotic properties of a meromorphic solution with logarithmic singularity.     

A free boundary problem for a singular system of differential equations: An application to a model of tumor growth

In this paper we consider a free boundary problem for a nonlinear system of two ordinary differential equations, one of which is singular at some points, including the initial point . Because of the singularity at , the initial value problem has a one-parameter family of solutions. We prove that there exists a unique solution to the free boundary problem. The proof of existence employs two ``shooting' parameters. Analysis of the profiles of solutions of the initial value problem and tools such as comparison theorems and weak limits of solutions play an important role in the proof. The system considered here is motivated by a model in tumor growth, but the methods developed should be applicable to more general systems.

     

An extension of the simplex algorithm for semi-infinite linear programming

We present a primal method for the solution of the semi-infinite linear programming problem with constraint index setS. We begin with a detailed treatment of the case whenS is a closed line interval in . A characterization of the extreme points of the feasible set is given, together with a purification algorithm which constructs an extreme point from any initial feasible solution. The set of points inS where the constraints are active is crucial to the development we give. In the non-degenerate case, the descent step for the new algorithm takes one of two forms: either an active point is dropped, or an active point is perturbed to the left or right. We also discuss the form of the algorithm when the extreme point solution is degenerate, and in the general case when the constraint index set lies in ^p . The method has associated with it some numerical difficulties which are at present unresolved. Hence it is primarily of interest in the theoretical context of infinite-dimensional extensions of the simplex algorithm.     

Mathematical modeling of a thin viscous layer adhering to an infinite plate withdrawn at an angle

We consider the problem of a thin viscous layer adhering to an inclined plate. Systems of boundary-layer equations and capillary-statics equations are used. The solutions of the two systems are matched at a certain point, which ensures a smooth profile of the free surface of the liquid.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 73, pp. 57–61, 1992.     

Classification of solutions for an integral equation

Let n be a positive integer and let 0 < α < n. Consider the integral equation We prove that every positive regular solution u(x) is radially symmetric and monotone about some point and therefore assumes the form with some constant c = c(n, α) and for some t > 0 and x₀ ? ?ⁿ. This solves an open problem posed by Lieb 12 . The technique we use is the method of moving planes in an integral form, which is quite different from those for differential equations. From the point of view of general methodology, this is another interesting part of the paper. Moreover, we show that the family of well‐known semilinear partial differential equations is equivalent to our integral equation (0.1), and we thus classify all the solutions of the PDEs. © 2005 Wiley Periodicals, Inc.     

Finite element approximation of viscoelastic fluid flow: Existence of approximate solutions and error bounds

Summary We study a finite element approximation of viscoelastic fluid flow obeying an Oldroyd B type constitutive law. The approximate stress, velocity and pressure are respectivelyP ₁ discontinuous,P ₂ continuous,P ₁ continuous. We use the method of Lesaint-Raviart for the convection of the extra stress tensor. We suppose that the continuous problem admits a sufficiently smooth and sufficiently small solution. We show by a fixed point method that the approximate problem has a solution and we give an error bound.This work has been supported in part by the GDR CNRS 901 Rhéologie der polymères fondus.     

On Universality of Critical Behavior in the Focusing Nonlinear Schrödinger Equation, Elliptic Umbilic Catastrophe and the Tritronquée Solution to the Painlevé-I Equation

We argue that the critical behavior near the point of “gradient catastrophe” of the solution to the Cauchy problem for the focusing nonlinear Schrödinger equation $i\epsilon \varPsi _{t}+\frac{\epsilon^{2}}{2}\varPsi _{xx}+|\varPsi |^{2}\varPsi =0We argue that the critical behavior near the point of “gradient catastrophe” of the solution to the Cauchy problem for the focusing nonlinear Schr?dinger equation , ε ≪1, with analytic initial data of the form is approximately described by a particular solution to the Painlevé-I equation.      

A Deterministic Approach to Linear Programs with Several Additional Multiplicative Constraints

We consider a global optimization problem of minimizing a linear function subject to p linear multiplicative constraints as well as ordinary linear constraints. We show that this problem can reduce to a 2p-dimensional reverse convex program, and present an algorithm for solving the resulting problem. Our algorithm converges to a globally optimal solution and yields an -approximate solution in finite time for any > 0. We also report some results of computational experiment.