A new exact exponential penalty function method and nonconvex mathematical programming

A new exact penalty function method, called the l₁ exact exponential penalty function method, is introduced. In this approach, the so-called the exponential penalized optimization problem with the l₁ exact exponential penalty function is associated with the original optimization problem with both inequality and equality constraints. The l₁ exact exponential penalty function method is used to solve nonconvex mathematical programming problems with r-invex functions (with respect to the same function η). The equivalence between sets of optimal solutions of the original mathematical programming problem and of its associated exponential penalized optimization problem is established under suitable r-invexity assumption. Also lower bounds on the penalty parameter are given, for which above these values, this result is true.     

On a boundary value problem for a higher-order elliptic equation

For an elliptic 2lth-order equation with constant (and only leading) real coefficients, we consider the boundary value problem in which the (k _j ? 1)st normal derivatives, j = 1,..., l, are specified, where 1 ≤ k ₁ < ... < k _l . If k _j = j, then it becomes the Dirichlet problem; and if k _j = j + 1, then it becomes the Neumann problem. We obtain a sufficient condition for this problem to be Fredholm and present a formula for the index of the problem.     

Constrained l1 estimation via geometric programming

The l₁ and constrained l₁ estimation problems are viewed in the light of extended geometric programming. As a result of this point of view we are able to establish an equivalence between geometric and linear programming duality results for these classes of problems. In addition, the duality results provide some useful insights into the properties of the l₁ estimation problems. Finally we establish an equivalence between the l_∞ norm problem and a class of constrained l₁ estimation problems.     

Discrete time analytic semigroups and the geometry of Banach spaces

We study different notions of discrete maximal regularity for discrete-time abstract Cauchy problems in Banach spaces. First we look at l ₂-discrete maximal regularity and show that Hilbert spaces are the only Banach spaces, among spaces with an unconditional basis, in which the analyticity of the associated discrete-time semigroup is a sufficient condition to obtain this kind of regularity. We then turn to different notions of regularity, in a l ₁ and in a l _∞ sense. We link the existence of particular semigroups such that the associated Cauchy problem has one of these maximal regularities to the geometry of the underlying Banach space (more precisely, to the existence of a complemented subspace isomorphic to c ₀ or l ₁). Finally, we give some elements to compare these regularities.     

A minimization problem concerning subsets of a finite set

Let F be the set of subsets of a finite set S, and for H ? F, let H′ denote the elements of F which are contained in some element of H. Given integers m_l and m_l+1 does there exist a subset H of F consisting of exactly m_ll-element subsets of S and m_l+1 (l+1)-element subsets of S such that no two elements of H are related by set-wise inclusion, and if such sets H do exist what the smallest |(l?1)(H′)| can be, where |(l?1)(H′)| is the number of (l?1)-element subsets of S in H′? A generalization of this problem, which was posed by G. Katona, is solved in this paper with the help of the generalized Macaulay theorem [2].     

Boundary value problem with normal derivatives for a higher-order elliptic equation on the plane

For an elliptic operator of order 2l with constant (and only leading) real coefficients, we consider a boundary value problem in which the normal derivatives of order (k _j ?1), j = 1,..., l, where 1 ≤ k ₁ < ··· < k _l, are specified. It becomes the Dirichlet problem for kj = j and the Neumann problem for k _j = j + 1. We obtain a sufficient condition for the Fredholm property of which problem and derive an index formula.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.     

On the chromatic number for a set of metric spaces

We study the problem of finding the chromatic number of a metric space with a forbidden distance. Using the linear-algebraic technique in combinatorics and convex optimization methods, we obtain a set of new estimates and observe the change of the asymptotic lower bound for the chromatic number of Euclidean space under the continuous change of the metric from l ₁ to l ₂.     

Complemented subspaces of (l 2⊕l 2⊕…) p (1<p<∞) with an unconditional basis

It is proved that every infinite dimensional complemented subspace of (l ₂⊕l ₂⊕…) _p (1<p<∞) with an unconditional basis is isomorphic to one of the following four spaces:l ₂,l _p,l ₂⊕l _p, (l ₂⊕l ₂⊕…) _p .     

More on the generalized Macaulay theorem

Let k₁ ? k₂ ? … ? k_n be given positive integers and let F denote the set of vectors (l₁, …, l_n) with integer components satisfying 0 ? l_i ? k_i, i = 1, 2, …, n. If H is a subset of F, let (l)H denote the subset of H consisting of those vectors with component sum l, and let C((l)H) denote the smallest [(l)H] elements of (l)F. The generalized Macaulay theorem due to the author and B. Lindström [3] shows that |Gamma;((C)(l)(H)|, ? |Γ(C((l)H))|, where Γ((l)H) is the setof vectors in F obtainable by subtracting l from a single component of a vector in (l)H. A method is given for computing [Γ(C((l)H)] in this paper. It is analogous to the method for computing |Γ(C(l)H))| in the k₁ = … = k_n = 1 case which has been given independently by Katona [4] and Kruskal [5].     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

The critical Fujita exponent for a diffusion equation with a potential term

We study the initial-boundary-value problem of the diffusion equation u _t = Δu ^m ? V (x)u ^m + u ^p in a conelike domain D = [1,∞) × Ω, where V (x) ~ ω ₂ |x| ^?2 with ω ₂ > 0. Let ω ₁ denote the smallest Dirichlet eigenvalue for the Laplace–Beltrami operator on Ω, and let l denote the positive root of l ² + (n ? 2)l = ω ₁ + ω ₂. We prove that if m < p ≤ m + 2/(n + l), then the problem has no global nonnegative solutions for any nonnegative u ₀ unless u ₀ = 0; if p > m + 2/(n + l), then the problem has global solutions for some \( {u_0}\gneq 0 \) .     

Un semi-groupe régularisé pour un modèle de Lebowitz–RubinowA regularized semigroup for a Lebowitz–Rubinow's model

In this Note, we complete [1] and we study the Lebowitz–Rubinow's model with the biological law of perfect memory. In this model, each cell is characterized by its cell cycle length l (0?l₁<l<l₂<∞) and its age a (0<a<l). If l₁>0, a complete study of this model can be found in [1]. Here we show that if l₁=0 then this model becomes ill-posed. We use the theory of generalized semigroups to remedy to this model. To cite this article: M. Boulanouar, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 865–868.     

Identities between q-hypergeometric and hypergeometric integrals of different dimensions

Given complex numbers m₁,l₁ and nonnegative integers m₂,l₂, such that m₁+m₂=l₁+l₂, for any a,b=0,…,min(m₂,l₂) we define an l₂-dimensional Barnes type q-hypergeometric integral I_a,b(z,μ;m₁,m₂,l₁,l₂) and an l₂-dimensional hypergeometric integral J_a,b(z,μ;m₁,m₂,l₁,l₂). The integrals depend on complex parameters z and μ. We show that I_a,b(z,μ;m₁,m₂,l₁,l₂) equals J_a,b(e^μ,z;l₁,l₂,m₁,m₂) up to an explicit factor, thus establishing an equality of l₂-dimensional q-hypergeometric and m₂-dimensional hypergeometric integrals. The identity is based on the duality for the qKZ and dynamical difference equations.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

Information-Based Complexity and Nonparametric Worst-Case System Identification

In this paper we review recent results on nonparametric approaches to identification of linear dynamic systems, under nonprobabilistic assumptions on measurement uncertainties. Two main categories of problems are considered in the paper: H_∞ and l₁ settings. The H_∞ setting assumes that the true system is linear time-invariant and the available information is represented by samples of the frequency response of the system, corrupted by an l_∞-norm bounded noise. The aim is to estimate a proper, stable finite-dimensional model. The estimation error is quantified according to an H_∞ norm, measuring the "distance" of the estimated model from the worst-case system in the class of allowable systems, for the worst-case realization of the measurement error. In the l₁ setting, the aim is to identify the samples of the impulse response of an unknown linear time-invariant system. The available information is given by input/output measurements corrupted by l_∞-bounded noise and the estimation error is measured according to an l₁ norm, for the worst case with respect to allowable systems and noise. In this paper, the main results available in the literature for both settings are reviewed, with particular attention to (a) evaluation of the diameter of information under various experimental conditions, (b) convergence to zero of the diameter of information (i.e., existence of robustly convergent identification procedures), and (c) computation of optimal and almost-optimal algorithms. Some results are also reported for the l_∞ setting, similar to the l₁ setting, with the exception of the estimation error, which is measured by an l_∞ norm.     

An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence <Emphasis Type="Italic">O</Emphasis>(1/<Emphasis Type="Italic">k</Emphasis><Superscript>2</Superscript>)

In this paper, we propose and analyze an accelerated augmented Lagrangian method (denoted by AALM) for solving the linearly constrained convex programming. We show that the convergence rate of AALM is O(1/k ²) while the convergence rate of the classical augmented Lagrangian method (ALM) is O(1/k). Numerical experiments on the linearly constrained l ₁?l ₂ minimization problem are presented to demonstrate the effectiveness of AALM.     

Representation of natural numbers by sums of four squares of integers having a special form

This paper obtains an asymptotic formula for the number of solutions to the equation $ l_1^2 + { }l_2^2 + l_3^2 + l_4^2 = N $ in integers l ₁, l ₂, l ₃, l ₄ such that a < {??l _j } < b, where ?? is a quadratic irrational number, 0 ?? a < b ?? 1, j = 1, 2, 3, 4.     

Banach spaces whose duals are isomorphic to l1(Γ)

Banach spaces X whose duals are isomorphic or isometric to l₁(Γ) are characterized by certain classes of operators on X. It is proved that a separable, conjugate space isomorphic to a complemented subspace of an L₁(S, Σ, μ) space is isomorphic to l₁; a $\text{L}$₁ space contained in a separable, conjugate space is isomorphic to a subspace of l₁.