Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

Point-to-Periodic and Periodic-to-Periodic Connections

In this work we consider computing and continuing connecting orbits in parameter dependent dynamical systems. We give details of algorithms for computing connections between equilibria and periodic orbits, and between periodic orbits. The theoretical foundation for these techniques is given by the seminal work of Beyn in 1994, “On well-posed problems for connecting orbits in dynamical systems”, where a numerical technique is also proposed. Our algorithms consist of splitting the computation of the connection from that of the periodic orbit(s). To set up appropriate boundary conditions, we follow the algorithmic approach used by Demmel, Dieci, and Friedman, for the case of connecting orbits between equilibria, and we construct and exploit the smooth block Schur decomposition of the monodromy matrices associated to the periodic orbits. Numerical examples illustrate the performance of the algorithms. This revised version was published online in July 2006 with corrections to the Cover Date.     

Topologically knotted Lagrangians in simply connected four-manifolds

Vidussi was the first to construct knotted Lagrangian tori in simply connected four-dimensional manifolds. Fintushel and Stern introduced a second way to detect such knotting. This note demonstrates that similar examples may be distinguished by the fundamental group of the exterior.

     

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

Three-dimensional steady supersonic duct flow using Lagrangian formulation

In this paper, numerical simulation of three-dimensional supersonic flow in a duct is presented. The flow field in the duct is complex and can find its applications in the inlet of air-breathing engines. A unique streamwise marching Lagrangian method is employed for solving the steady Euler equations. The method was first initiated by Loh and Hui (1990) for 2-D steady supersonic flow computations and then extended to 3-D computation by the present authors Loh and Liou (1992). The new scheme is shown to be capable of accurately resolving complicated shock or contact discontinuities and their interactions. In all the computations, a free stream of Mach numberM=4 is considered.This article was processed using Springer-Verlag T_EX Shock Waves macro package 1.0 and the AMS fonts, developed by the American Mathematical Society.     

二阶Melnikov函数及其应用

在Ｍｅｌｎｉｋｏｖ函数的种种应用中，目前常见到的仅是一阶形式。本文具体推导了二阶Ｍｅｌｎｉｋｏｖ函数的分析表达，提出了临界情况下考察双曲鞍点的稳定流形与不稳定流形相对位置的二阶判据，并成功地用于环面ｖａｎｄｅｒＰｏｌ方程的研究中。     

指数二分性与自治奇摄动系统的退化同宿分支

利用指数二分性理论和泛函分析方法，我们研究了自治奇摄动系统的同，异宿轨道的存在性，给出了高维奇摄动系统从退化系统分支出同异宿轨道的Ｍｅｌ－ｎｉｋｏｖ型函数。     

New numerical methods and some applied aspects of the p-regularity theory

The theory of p-regularity is applied to optimization problems and to singular ordinary differential equations (ODE). The special variant of the method of the modified Lagrangian function proposed by Yu.G. Evtushenko for constrained optimization problems with inequality constraints is justified on the basis of the 2-factor transformation. An implicit function theorem is given for the singular case. This theorem is used to show the existence of solutions to a boundary value problem for a nonlinear differential equation in the resonance case. New numerical methods are proposed including the p-factor method for solving ODEs with a small parameter.     

Comparison between Eulerian and Lagrangian semi-analytical models to simulate the pollutant dispersion in the PBL

In this work we display a numerical comparison, under statistical and computational point of view, between semi-analytical Eulerian and Lagrangian dispersion models to simulate the ground-level concentration values of a passive pollutant released from a low height source. The Eulerian approach is based on the solution of the advection–diffusion equation by the Laplace transform technique. The Lagrangian approach is based on solution of the Langevin equation through the Picard’s Iterative Method. Turbulence inputs are calculated according to a parameterization capable of generating continuous values in all stability conditions and in all heights of the Planetary Boundary Layer (PBL). Numerical simulations and comparisons show a good agreement between predicted and observed concentrations values. The comparison reveals the main advantages and disadvantages between the models.     

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.