Lower subdifferentiability of quadratic functions

In this paper we characterize those quadratic functions whose restrictions to a convex set are boundedly lower subdifferentiable and, for the case of closed hyperbolic convex sets, those which are lower subdifferentiable but not boundedly lower subdifferentiable.Once characterized, we will study the applicability of the cutting plane algorithm of Plastria to problems where the objective function is quadratic and boundedly lower subdifferentiable.Financial support from the Dirección General de Investigación Científica y Técnica (DGICYT), under project PS89-0058, is gratefully acknowledged.     

Optimization of convex functions on w*-compact sets

We give a direct, self-contained, and iterative proof that for any convex, Lipschitz andw ^*-lower semicontinuous function ϕ defined on aw ^*-compact convex setC in a dual Banach spaceX ^* and for any ε>0 there is anx∈X, with ‖x‖≤ε, such that ϕ+x attains its supremum at an extreme point ofC. This result is implicitly contained in the work of Lindenstrauss [9] and the work of Ghoussoub and Maurey on strongw ^*−H _σ sets [8]. In addition, we discuss the applications of this result to the geometry of convex sets. Research supported in part by the NSERC of Canada under grant OGP41983 for the first author and grant OGP7926 for the second author.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

On pointwise and analytic similarity of matrices

LetA(ε) andB(ε) be complex valued matrices analytic in ε at the origin.A(ε)≈ _p B(ε) ifA(ε) is similar toB(ε) for any |ε|<r,A(ε)≈_a B(ε) ifB(ε)=T(ε)A(ε)T ⁻¹(ε) andT(ε) is analytic and |T(ε)|≠0 for |ε|<r! In this paper we find a necessary and sufficient conditions onA(ε) andB(ε) such thatA(ε)≈ _a B(ε) provided thatA(ε)≈ _p B(ε). This problem arises in study of certain ordinary differential equations singular with respect to a parameter ε in the origin and was first stated by Wasow. Sponsored by the United States Army under Contract No. DAAG29-75-C-0024     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Worst Case Setting

We consider approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces with finite-order weights. This means we consider functions of d variables that can be represented as sums of functions of at most q^* variables. Here, q^* is fixed (and presumably small) and d may be arbitrarily large. For the univariate problem, d = 1, we assume we know algorithms A1,ε that use O(ε−p) function or linear functional evaluations to achieve an error ε in the worst case setting. Based on these algorithms A_1,ε, we provide a construction of polynomial-time algorithms A_d,ε for the general d-variate problem with the number of evaluations bounded roughly by ε^−pd^q* to achieve an error ε in the worst case setting.     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.     

Integer knapsack problems with set-up weights

The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε ²+1/ε ³) and O(1/ε ²), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn ²/ε ³) and O(k/ε ²), respectively.     

Lower subdifferentiable functions and their minimization by cutting planes

This paper introduces lower subgradients as a generalization of subgradients. The properties and characterization of boundedly lower subdifferentiable functions are explored. A cutting plane algorithm is introduced for the minimization of a boundedly lower subdifferentiable function subject to linear constraints. Its convergence is proven and the relation is discussed with the well-known Kelley method for convex programming problems. As an example of application, the minimization of the maximum of a finite number of concave-convex composite functions is outlined.The author thanks the referees for several constructive remarks.     

The central connection problem at turning points of linear differential equations

A system of linear differential equations of the vectorial form εdy/dx=A (x, ε) y is considered, where ε is a positive parameter, and the matrixA (x, ε) is holomorphic in |x|⩽x ₀, 0 < ε ⩽ ε₀ , with an asymptotic expansionsA (x, ε) ∼ ∑ _r=0 ^∞ A _r (x) ε ^r , as ε→0. The eigenvalues ofA ₀(x) are supposed to coalesce atx=0 so as to make this point a simple turning point. With the help of refinements of the representations for the inner and outer asymptotic solutions, as ε→0, that were introduced in the articles [9] and [10] by the author (see the references at the end of the paper), explicit connection formulas between these solutions are calculated. As part of this derivation it is shown that only the diagonal entries of the connection matrix are asymptotically relevant.     

An integral strong law of large numbers for processes with independent increments

For a stochastically continuous stochastic process with independent increments overD[0,T], letN(t,ε) be the number of smaple function jumps that occur in the interval [0,t] of sizes less than −ε or greater than ε, where ε>0. LetM(t,ε)=EN(t,ε), and assumeM(t,0+)=∞ for 0<t≦T. If lim_{ε ↓0}(M(t,ε)/M(T,ε)) exists and is positive for eacht∈(0,T], then lim_{ε ↓0}(N(t,ε)/M(T,ε)) for allt∈(0,T] with probability one. The research of Howard G. Tucker was supported in part by the National Science Foundation, Grant No. MCS76-03591A01.     

Asymptotic analysis of a boundary-value problem with nonlinear multiphase boundary interactions in a perforated domain

We consider a boundary-value problem for the second-order elliptic differential operator with rapidly oscillating coefficients in a domain Ω _ε that is ε-periodically perforated by small holes. The holes are split into two ε-periodic sets depending on the boundary interaction via their boundary surfaces. Therefore, two different nonlinear boundary conditions σ _ε (u _ε ) + εκ _m (u _ε ) = εg _ε ^(m) , m = 1, 2, are given on the corresponding boundaries of the small holes. The asymptotic analysis of this problem is performed as ε → 0, namely, the convergence theorem for both the solution and the energy integral is proved without using an extension operator, asymptotic approximations for the solution and the energy integral are constructed, and the corresponding approximation error estimates are obtained.     

Imbedding of power series spaces and spaces of analytic functions

The diametral dimension of a nuclear Fréchet spaceE, which satisfies (DN) and (Ω), is related to power series spaces Λ₁(ε) and Λ_∞(ε) for some exponent sequence ε. It is proved thatE contains a complemented copy of Λ_∞(ε) provided the diametral dimensions ofE and Λ_∞(ε) are equal and ε is stable. Assuming Λ₁(ε) is nuclear, any subspace of Λ₁(ε) which satisfies (DN), can be imbedded intoE. Applications of these results to spaces of analytic functions are given. Support of Turkish Scientific and Technical Research Council is gratefully acknowledged.     

Polynomial-Time Algorithms for Multivariate Linear Problems with Finite-Order Weights: Average Case Setting

We study multivariate linear problems in the average case setting with respect to a zero-mean Gaussian measure whose covariance kernel has a finite-order weights structure. This means that the measure is concentrated on a Banach space of d-variate functions that are sums of functions of at most q ^* variables and the influence of each such term depends on a given weight. Here q ^* is fixed whereas d varies and can be arbitrarily large. For arbitrary finite-order weights, based on Smolyak’s algorithm, we construct polynomial-time algorithms that use standard information. That is, algorithms that solve the d-variate problem to within ε using of order function values modulo a power of ln ε ⁻¹. Here p is the exponent which measures the difficulty of the univariate (d=1) problem, and the power of ln ε ⁻¹ is independent of d. We also present a necessary and sufficient condition on finite-order weights for which we obtain strongly polynomial-time algorithms, i.e., when the number of function values is independent of d and polynomial in ε ⁻¹. The exponent of ε ⁻¹ may be, however, larger than p. We illustrate the results by two multivariate problems: integration and function approximation. For the univariate case we assume the r-folded Wiener measure. Then p=1/(r+1) for integration and for approximation.      

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right.     

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right. The research of the first author was supported in part by the NSF Grant DMS 0100078.     

Robust Shape Fitting via Peeling and Grating Coresets

Let P be a set of n points in ℝ ^d . A subset of P is called a (k,ε)-kernel if for every direction, the directional width of ε-approximates that of P, when k “outliers” can be ignored in that direction. We show that a (k,ε)-kernel of P of size O(k/ε ^(d−1)/2) can be computed in time O(n+k ²/ε ^d−1). The new algorithm works by repeatedly “peeling” away (0,ε)-kernels from the point set. We also present a simple ε-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and works by repeatedly “grating” critical points into a working set, till the working set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear ε-approximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems. A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P. is supported by a NSF CAREER award CCR-0132901.     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.