On Detecting Solutions of Polynomial Nonlinear Difference Equations

In this paper a method for discovering solutions of nonlinear polynomial difference equations is presented. It is based on the concepts of i -operator and star-product. These notions create a proper algebraic background by means of which we can find linear equations "included" into the original nonlinear one and to seek for solutions among them. A corresponding algorithm and some examples are also provided.     

A Joint Tikhonov Regularization and Augmented Lagrange Approach for Ill-Posed State Constrained Control Problems with Sparse Controls

Abstract

We provide a modified augmented Lagrange method coupled with a Tikhonov regularization for solving ill-posed state constrained elliptic optimal control problems with sparse controls. We consider a linear quadratic optimal control problem without any additional L² regularization terms. The sparsity is guaranteed by an additional L¹ term. Here, the modification of the classical augmented Lagrange method guarantees us uniform boundedness of the multiplier that corresponds to the state constraints. We present a coupling between the regularization parameter introduced by the Tikhonov regularization and the penalty parameter from the augmented Lagrange method, which allows us to prove strong convergence of the controls and their corresponding states. Moreover, convergence results proving the weak convergence of the adjoint state and weak*-convergence of the multiplier are provided. Finally, we demonstrate our method in several numerical examples.     

Nonlinear rescaling and proximal-like methods in convex optimization

The nonlinear rescaling principle (NRP) consists of transforming the objective function and/or the constraints of a given constrained optimization problem into another problem which is equivalent to the original one in the sense that their optimal set of solutions coincides. A nonlinear transformation parameterized by a positive scalar parameter and based on a smooth sealing function is used to transform the constraints. The methods based on NRP consist of sequential unconstrained minimization of the classical Lagrangian for the equivalent problem, followed by an explicit formula updating the Lagrange multipliers. We first show that the NRP leads naturally to proximal methods with an entropy-like kernel, which is defined by the conjugate of the scaling function, and establish that the two methods are dually equivalent for convex constrained minimization problems. We then study the convergence properties of the nonlinear rescaling algorithm and the corresponding entropy-like proximal methods for convex constrained optimization problems. Special cases of the nonlinear rescaling algorithm are presented. In particular a new class of exponential penalty-modified barrier functions methods is introduced. Partially supported by the National Science Foundation, under Grants DMS-9201297, and DMS-9401871. Partially supported by NASA Grant NAG3-1397 and NSF Grant DMS-9403218.     

一类连续可分离背包问题的直接算法

对于一类带有单个线性约束以及盒约束的一般连续可分离二次背包问题给出了一种直接的算法,根据模型特有的结构,通过调节线性约束的拉格朗日乘子λ 的取值范围,以及在算法求解过程中通过判断目标函数一次项中的变量是否在盒约束范围内,来逐步确定所有变量的最优值, 并通过该算法得到的实验结果与其他算法的比较,说明了这种算法的可行性和有效性．     

Multiplicity of characteristics with Lagrangian boundary values on symmetric star-shaped hypersurfaces

In this paper, the multiplicity of Lagrangian orbits on C² smooth compact symmetric star-shaped hypersurfaces with respect to the origin in R2n is studied. These Lagrangian orbits begin from one Lagrangian subspace and end on another. An infinitely many existence result is proved via Z₂-index theory. This is a multiplicity result about the Arnold Chord Conjecture in some sense, and is a generalization of the problem about the multiplicity of Lagrangian orbits beginning from and ending on the same Lagrangian subspace which was considered in the authors' previous paper [F. Guo, C. Liu, Multiplicity of Lagrangian orbits on symmetric star-shaped hypersurfaces, Nonlinear Anal. 69 (4) (2008) 1425-1436].     

Seeking (and finding) Lagrangians

It is well known that for any second-order ordinary differential equation (ODE), a Lagrangian always exists, and the key to its construction is the Jacobi last multiplier. Is it possible to find Lagrangians for first-order systems of ODEs or for higher-order ODEs? We show that the Jacobi last multiplier can also play a major role in this case.     

A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

Given an undirected graph G with penalties associated with its vertices and costs associated with its edges, a Prize Collecting Steiner (PCS) tree is either an isolated vertex of G or else any tree of G, be it spanning or not. The weight of a PCS tree equals the sum of the costs for its edges plus the sum of the penalties for the vertices of G not spanned by the PCS tree. Accordingly, the Prize Collecting Steiner Problem in Graphs (PCSPG) is to find a PCS tree with the lowest weight. In this paper, after reformulating and re-interpreting a given PCSPG formulation, we use a Lagrangian Non Delayed Relax and Cut (NDRC) algorithm to generate primal and dual bounds to the problem. The algorithm is capable of adequately dealing with the exponentially many candidate inequalities to dualize. It incorporates ingredients such as a new PCSPG reduction test, an effective Lagrangian heuristic and a modification in the NDRC framework that allows duality gaps to be further reduced. The Lagrangian heuristic suggested here dominates their PCSPG counterparts in the literature. The NDRC PCSPG lower bounds, most of the time, nearly matched the corresponding Linear Programming relaxation bounds.     

Nonexistence of invariant graphs in all supercritical energy levels of mechanical Lagrangians in T 2

Let (T², g) be a smooth Riemannian structure in the torus T². We show that given ε > 0 and any C^∞ function U : T² → ℝ there exists a C¹ function U_ε with Lipschitz derivatives that is ε-C⁰ close to U for which there are no continuous invariant graphs in any supercritical energy level of the mechanical Lagrangian L_ε : TT² → ℝ given by . We also show that given n ∈ ℕ, the set of C^∞ potentials U : T² → ℝ for which there are no continuous invariant graphs in any supercritical energy level E ≤ n of is C⁰ dense in the set of C^∞ functions. Partially supported by CNPq, FAPERJ-Cientistas do nosso estado.     

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.