Existence and differential geometric properties of continuous families of periodic three-body motions with non-uniform mass distributions

Using the method of analytic continuation in an equivariant differential geometric setting, we exhibit two interesting families of vanishing angular momentum periodic orbits for the Newtonian three-body problem with non-uniform mass distributions having two equal masses which connect at the celebrated figure-8 orbit, exhibited by A. Chenciner and R. Montgomery (2000) in the case of equal masses, and yield a continuous family of periodic three-body motions in the plane.At one end of the family, when the two equal masses are infinitesimal and the third one reaches the value of +1, we arrive at a solution of a double Kepler problem; at the other end of the family, when the third mass is infinitesimal, we have a special case of periodic solution of a restricted three-body problem.     

Variational methods for the choreography solution to the three- body problem

In this paper, we give a short proof for the existence of nontrivial choreography solution to the equal-mass three-body problem, which is discovered by Chenciner and Montgomery recently.     

Symmetry of the restricted 4 + 1 body problem with equal masses

We consider the problem of symmetry of the central configurations in the restricted 4 + 1 body problem when the four positive masses are equal and disposed in symmetric configurations, namely, on a line, at the vertices of a square, at the vertices of a equilateral triangle with a mass at the barycenter, and finally, at the vertices of a regular tetrahedron [1–3]. In these situations, we show that in order to form a non collinear central configuration of the restricted 4 + 1 body problem, the null mass must be on an axis of symmetry. In our approach, we will use as the main tool the quadratic forms introduced by A. Albouy and A. Chenciner [4]. Our arguments are general enough, so that we can consider the generalized Newtonian potential and even the logarithmic case. To get our results, we identify some properties of the Newtonian potential (in fact, of the function ϕ(s) = −s ^k, with k < 0) which are crucial in the proof of the symmetry.     

A Newton’s method for perturbed second-order cone programs

We develop optimality conditions for the second-order cone program. Our optimality conditions are well-defined and smooth everywhere. We then reformulate the optimality conditions into several systems of equations. Starting from a solution to the original problem, the sequence generated by Newton’s method converges Q-quadratically to a solution of the perturbed problem under some assumptions. We globalize the algorithm by (1) extending the gradient descent method for differentiable optimization to minimizing continuous functions that are almost everywhere differentiable; (2) finding a directional derivative of the equations. Numerical examples confirm that our algorithm is good for “warm starting” second-order cone programs—in some cases, the solution of a perturbed instance is hit in two iterations. In the progress of our algorithm development, we also generalize the nonlinear complementarity function approach for two variables to several variables.     

Global optimization for a class of fractional programming problems

This paper presents a canonical dual approach to minimizing the sum of a quadratic function and the ratio of two quadratic functions, which is a type of non-convex optimization problem subject to an elliptic constraint. We first relax the fractional structure by introducing a family of parametric subproblems. Under proper conditions on the “problem-defining” matrices associated with the three quadratic functions, we show that the canonical dual of each subproblem becomes a one-dimensional concave maximization problem that exhibits no duality gap. Since the infimum of the optima of the parameterized subproblems leads to a solution to the original problem, we then derive some optimality conditions and existence conditions for finding a global minimizer of the original problem. Some numerical results using the quasi-Newton and line search methods are presented to illustrate our approach.     

About an Optimal Visiting Problem

In this paper we are concerned with the optimal control problem consisting in minimizing the time for reaching (visiting) a fixed number of target sets, in particular more than one target. Such a problem is of course reminiscent of the famous “Traveling Salesman Problem” and brings all its computational difficulties. Our aim is to apply the dynamic programming technique in order to characterize the value function of the problem as the unique viscosity solution of a suitable Hamilton–Jacobi equation. We introduce some “external” variables, one per target, which keep in memory whether the corresponding target is already visited or not, and we transform the visiting problem in a suitable Mayer problem. This fact allows us to overcome the lacking of the Dynamic Programming Principle for the originary problem. The external variables evolve with a hysteresis law and the Hamilton–Jacobi equation turns out to be discontinuous     

Variational problem in the non-negative orthant of ℝ<Superscript>3</Superscript>: reflective faces and boundary influence cones

In this paper we consider the variational problem in the non-negative orthant of ℝ³. The solution of this problem gives the large deviation rate function for the stationary distribution of an SRBM (Semimartingal Reflecting Brownian Motion). Avram, Dai and Hasenbein (Queueing Syst. 37, 259–289, 2001) provided an explicit solution of this problem in the non-negative quadrant. Building on this work, we characterize reflective faces of the non-negative orthant of ℝ ^d , we construct boundary influence cones and we provide an explicit solution of several constrained variational problems in ℝ³. Moreover, we give conditions under which certain spiraling paths to a point on an axis have a cost which is strictly less than the cost of every direct path and path with two pieces.     

Lagrangian Relaxations on Networks by <Emphasis Type="Italic">ε</Emphasis>-Subgradient Methods

The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems by means of approximate subgradient methods. The idea is to solve the dual problem by using ε-subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ε-subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these methods some of them have been implemented and their performances computationally compared with codes that are able to solve the proposed test problems.     

Multi-job Cutting Stock Problem with Due Dates and Release Dates

The common feature of cutting stock problems is to cut some form of stock materials to produce smaller pieces of materials in quantities matching orders received. Most research on cutting stock problems focuses on either generating cutting patterns to minimize wastage or determining the required number of stock materials to meet orders. In this paper, we examine a variation of cutting stock problems that arises in some industries where meeting orders' due dates is more important than minimizing wastage of materials. We develop two two-dimensional cutting stock models with due date and release date constraints. Since adding due dates and release dates makes the traditional cutting stock problem even more difficult to solve, we develop both LP-based and non-LP-based heuristics to obtain good solutions. The computational results show that the solution procedures are easy to implement and work very well.     

Metric characterizations of <Emphasis Type="Italic">α</Emphasis>-well-posedness for symmetric quasi-equilibrium problems

The purpose of this paper is to generalize the concept of α-well-posedness to the symmetric quasi-equilibrium problem. We establish some metric characterizations of α-well-posedness for the symmetric quasi-equilibrium problem. Under some suitable conditions, we prove that the α-well-posedness is equivalent to the existence and uniqueness of solution for the symmetric quasi-equilibrium problems. The corresponding concept of α-well-posedness in the generalized sense is also investigated for the symmetric quasi-equilibrium problem having more than one solution. The results presented in this paper generalize and improve some known results in the literature.     

Reminiscences on the development of the variational approach to Davidon’s variable-metric method

In the mid-1960’s, Davidon’s method was brought to the author’s attention by M.J.D. Powell, one of its earliest proponents. Its great efficacy in solving a rather difficult computational problem in which the author was involved led to an attempt to find a “best” updating formula. “Best” seemed to suggest “least” in the sense of some norm, to further the stability of the method. This led to the idea of minimizing a generalized quadratic (Frobenius) norm with the quasi-Newton and symmetry constraints on the updates. Several interesting formulas were derived, including the Davidon-Fletcher-Powell formula (as shown by Goldfarb). This approach was extended to the derivation of updates requiring no derivatives, and to Broyden-like updates for the solution of simultaneous nonlinear equations. Attempts were made to derive minimum-norm corrections in product-form updates, with an eye to preserving positive-definiteness. In the course of this attempt, it was discovered that the DFP formula could be written as a product, leading to some interesting theoretical developments. Finally, a linearized product-form update was developed which was competitive with the best update (BFGS) of that time. Received: May 3, 1999 / Accepted: January 11, 2000?Published online March 15, 2000     

Stochastic Multiobjective Optimization: Sample Average Approximation and Applications

We investigate one stage stochastic multiobjective optimization problems where the objectives are the expected values of random functions. Assuming that the closed form of the expected values is difficult to obtain, we apply the well known Sample Average Approximation (SAA) method to solve it. We propose a smoothing infinity norm scalarization approach to solve the SAA problem and analyse the convergence of efficient solution of the SAA problem to the original problem as sample sizes increase. Under some moderate conditions, we show that, with probability approaching one exponentially fast with the increase of sample size, an ϵ-optimal solution to the SAA problem becomes an ϵ-optimal solution to its true counterpart. Moreover, under second order growth conditions, we show that an efficient point of the smoothed problem approximates an efficient solution of the true problem at a linear rate. Finally, we describe some numerical experiments on some stochastic multiobjective optimization problems and report preliminary results.     

Stability estimates for the solution to the problem of determining the kernel of a viscoelastic equation

For an integrodifferential equation corresponding to a two-dimensional viscoelastic problem, we study the problem of defining the spatial part of the kernel involved in the integral term of the equation. The support of the sought function is assumed to belong to a compact domain Ω. As information for solving this inverse problem, the traces of the solution to the direct Cauchy problem and its normal derivative are given for some finite time interval on the boundary of Ω. An important feature in the statement of the problem is the fact that the solution of the direct problem corresponds to the zero initial data and a force impulse in time localized on a fixed straight line disjoint with Ω. The main result of the article consists in obtaining a Lipschitz estimate for the conditional stability of the solution to the inverse problem under consideration.     

Combined ℓ<Subscript>2</Subscript> data and gradient fitting in conjunction with ℓ<Subscript>1</Subscript> regularization

We are interested in minimizing functionals with ℓ₂ data and gradient fitting term and ℓ₁ regularization term with higher order derivatives in a discrete setting. We examine the structure of the solution in 1D by reformulating the original problem into a contact problem which can be solved by dual optimization techniques. The solution turns out to be a ’smooth’ discrete polynomial spline whose knots coincide with the contact points while its counterpart in the contact problem is a discrete version of a spline with higher defect and contact points as knots. In 2D we modify Chambolle’s algorithm to solve the minimization problem with the ℓ₁ norm of interacting second order partial derivatives as regularization term. We show that the algorithm can be implemented efficiently by applying the fast cosine transform. We demonstrate by numerical denoising examples that the ℓ₂ gradient fitting term can be used to avoid both edge blurring and staircasing effects.      

Finite Factor Representations of 2-Step Nilpotent Groups and the Orbit Method

In this paper, we describe factor representations of discrete 2-step nilpotent groups with 2-divisible center in the spirit of the orbit method. We show that some standard theorems of the orbit method are valid for these groups. In the case of countable 2-step nilpotent groups we explain how to construct a factor representation starting with an orbit of the “coadjoint representation.” We also prove that every factor representation (more precisely, every trace) can be obtained by this construction, and prove a theorem on the decomposition of a factor representation restricted to a subgroup. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 307, 2004, pp. 120–140.     

Smoothing Newton Method for Minimizing the Sum of <Emphasis Type="Italic">p</Emphasis>-Norms

Consider the problem of minimizing the sum of p-norms, where p is a fixed real number in the interval [1,2]. This nondifferentiable problem arises in many applications, including the VLSI (very-large-scale-integration) layout problem, the facilities location problem and the Steiner minimum tree problem under a given topology. In this paper, we establish the optimality conditions, duality and uniqueness results for the problem. We then present a smoothing Newton method by the semismooth equations which are derived from the optimality conditions. The method is globally and superlinearly convergent, and moreover, it is quadratically convergent when p∈[1,3/2]∪{2}. Particularly, the quadratic convergence is proved for the case wherep∈(1,3/2]∪{2} without requiring strict complementarity. Preliminary numerical results are reported, which indicate that the method proposed is extremely promising. The work was supported by the Starting-Up Foundation (B13-B6050640) of Guangdong Province.     

Convex Hulls of Orbits and Orientations of a Moving Protein Domain

We study the facial structure and Carathéodory number of the convex hull of an orbit of the group of rotations in ℝ³ acting on the space of pairs of anisotropic symmetric 3×3 tensors. This is motivated by the problem of determining the structure of some proteins in an aqueous solution.     

The Wirtinger-Steklov inequality between the norm of a periodic function and the norm of the positive cutoff of its derivative

We prove that there is no single uniform tight frame in Euclidean (unitary) space such that a solution of the ℓ ₁-norm minimization problem for the frame representation is attained on the frame coefficients. Then we find an exact solution of the ℓ ₁-minimization problem for the Mercedes-Benz frame in ℝ ^N . We also give some examples of connections between optimization problems of various types.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.