Global Convergence of a Modified Gradient Projection Method for Convex Constrained Problems

In this paper, the continuously differentiable optimization problem min{f（x） ： x∈Ω}, where Ω ∈ R^n is a nonempty closed convex set, the gradient projection method by Calamai and More （Math. Programming, Vol.39. P.93-116, 1987） is modified by memory gradient to improve the convergence rate of the gradient projection method is considered. The convergence of the new method is analyzed without assuming that the iteration sequence {x^k} of bounded. Moreover, it is shown that, when f（x） is pseudo-convex （quasiconvex） function, this new method has strong convergence results. The numerical results show that the method in this paper is more effective than the gradient projection method.     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

The long-step method of analytic centers for fractional problems

We develop a long-step surface-following version of the method of analytic centers for the fractional-linear problem min{t ₀ |t ₀ B(x) −A(x) εH, B(x) εK, x εG}, whereH is a closed convex domain,K is a convex cone contained in the recessive cone ofH, G is a convex domain andB(·),A(·) are affine mappings. Tracing a two-dimensional surface of analytic centers rather than the usual path of centers allows to skip the initial “centering” phase of the path-following scheme. The proposed long-step policy of tracing the surface fits the best known overall polynomial-time complexity bounds for the method and, at the same time, seems to be more attractive computationally than the short-step policy, which was previously the only one giving good complexity bounds. The research was partly supported by the Israeli-American Binational Science Foundation (BSF).     

Joint bounds for the Perron roots of nonnegative matrices with applications

Given a finite set {A_x}_{x ∈ X} of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices D⁻¹ A^(x) D, x ∈ X, where D is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices A^(x) and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable. Bibliography: 20 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 30–56.     

Convergence Properties of the Regularized Newton Method for the Unconstrained Nonconvex Optimization

The regularized Newton method (RNM) is one of the efficient solution methods for the unconstrained convex optimization. It is well-known that the RNM has good convergence properties as compared to the steepest descent method and the pure Newton’s method. For example, Li, Fukushima, Qi and Yamashita showed that the RNM has a quadratic rate of convergence under the local error bound condition. Recently, Polyak showed that the global complexity bound of the RNM, which is the first iteration k such that ‖∇ f(x _k )‖≤ε, is O(ε ⁻⁴), where f is the objective function and ε is a given positive constant. In this paper, we consider a RNM extended to the unconstrained “nonconvex” optimization. We show that the extended RNM (E-RNM) has the following properties. (a) The E-RNM has a global convergence property under appropriate conditions. (b) The global complexity bound of the E-RNM is O(ε ⁻²) if ∇ ² f is Lipschitz continuous on a certain compact set. (c) The E-RNM has a superlinear rate of convergence under the local error bound condition.     

Random walks in random environments on metric groups

Random walks in random environments on countable metric groups with bounded jumps of the walking particle are considered. The transition probabilities of such a random walk from a pointx εG (whereG is the group in question) are described by a vectorp(x) ε ℝ^|W| (whereW ⊏G is fixed and |W|<∞). The set {p(x),x εG} is assumed to consist of independent identically distributed random vectors. A sufficient condition for this random walk to be transient is found. As an example, the groups ℤ ^d , free groups, and the free product of finitely many cyclic groups of second order are considered. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 129–135, January, 2000.     

Dominated estimates of convex combinations of commuting isometries

The principal result of this paper is that the convex combination of two positive, invertible, commuting isometries ofL _p(X,F, μ) 1<p<+∞, one of which is periodic, admits a dominated estimate with constantp/p−1. In establishing this, the following analogue of Linderholm’s theorem is obtained: Let σ and ε be two commuting non-singular point transformations of a Lebesgue Space with τ periodic. Then given ε>O, there exists a periodic non-singular point transformation σ′ such that σ′ commutes with τ and μ(x:σ′x≠σx}<ε. Byan approximation argument, the principal result is applied to the convex combination of two isometries ofL _p (0, 1) induced by point transformations of the form τx=x ^k,k>0 to show that such convex combinations admit a dominated estimate with constantp/p−1. Research supported in part by NSF Grant No. GP-7475. A portion of the contents of this paper is based on the author’s doctoral dissertation written under the direction of Professor R. V. Chacon of the University of Minnesota.     

The Effect of Corners on the Complexity of Approximate Range Searching

Given an n-element point set in ℝ ^d , the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary. In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space. A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality, allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear space, the query time is at least . In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε ^d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups. In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)^(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)^(d−1)/2). This bound is in the decision-tree model and holds irrespective of space. A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006. The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E. The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office of Naval Research under grant N00014-08-1-1015.     

Dynamics of neighborhoods of points under a continuous mapping of an interval

Let {I, f, Z ⁺} be a dynamical system induced by a continuous mapping f of a closed bounded interval I into itself. To describe the dynamics of neighborhoods of points unstable under the mapping f, we propose the concept of the εω-set ω ^{f, ε}(x) of a point x as the ω-limit set of the ε-neighborhood of the point x. We investigate the relationship between the εω-set and the domain of influence of a point. It is also shown that the domain of influence of an unstable point is always a cycle of intervals. The results obtained can be directly used in the theory of difference equations with continuous time and similar equations. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 11, pp. 1534–1547, November, 2005.     

Laws of iterated logarithm for state variables with applications

Letx _k be the state variable (solution) of a stochastic difference equation. This paper gives the laws of iterated logarithm for {x _k} and {x _kx _k ^τ }, which being strongly correlated, are neither stationary nor ergodic. The results obtained are then applied to Kalman filter and LQG control problem. Work supported by National Natural Science Foundation of China and the TWAS Research Grant No. 87-43.     

Some Convergence Properties of Descent Methods

In this paper, we discuss the convergence properties of a class of descent algorithms for minimizing a continuously differentiable function f on R ⁿ without assuming that the sequence { x _k } of iterates is bounded. Under mild conditions, we prove that the limit infimum of is zero and that false convergence does not occur when f is convex. Furthermore, we discuss the convergence rate of { } and { f(x _k )} when { x _k } is unbounded and { f(x _k )} is bounded.     

On finitely convergent iterative methods for the convex feasibility problem

Iterative algorithms for the Convex Feasibility Problem can be modified so that at iterationk the original convex sets are perturbed with a parameter ε_k which tends to zero ask increases. We establish conditions on such algorithms which guarantee existence of a sequence of perturbation parameters which make them finitely convergent when applied to a convex feasibility problem whose feasible set has non empty interior.     

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.     

Existence and multiplicity of solutions for a nonlinear Neumann problem

We consider a Neumann problem of the type -εΔu+F ^′(u(x))=0 in an open bounded subset Ω of R ⁿ , where F is a real function which has exactly k maximum points. Using Morse theory we find that, for ε suitably small, there are at least 2k nontrivial solutions of the problem and we give some qualitative information about them. Received: October 30, 1999 Published online: December 19, 2001     

Convergence analysis of iterative sequences for a pair of mappings in Banach spaces

Let C be a nonempty closed convex subset of a real Banach space E. Let S ： C→ C be a quasi-nonexpansive mapping, let T ： C→C be an asymptotically demicontractive and uniformly Lipschitzian mapping, and let F ：= {x ∈C ： Sx = x and Tx = x}≠Ф Let {xn}n≥0 be the sequence generated irom an arbitrary x0∈Cby xn＋i=（1-cn）Sxn＋cnT^nxn, n≥0.We prove the necessary and sufficient conditions for the strong convergence of the iterative sequence {xn} to an element of F. These extend and improve the recent results of Moore and Nnoli.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

Bergman kernel asymptotics for generalized Fock spaces

Letm(t)dt be a positive measure onR ⁺. We investigate the relations among the growth ofm, the growth of its moment sequence {y_n}, the growth of its Bergman kernel functionk x=Σγ{_n/^-1}x ⁿ, and the growth of the kernel function associated to the measureK(t) ⁻¹m(t) dt. For a large class of measures, we find that these quantities satisfy asymptotic relations similar to the simple exact relations which hold in the model casem(t)=e ⁻¹. Supported in part by a grant from the National Science Foundation.     

Efficient Subspace Approximation Algorithms

We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in ℝ ^d . The fit of a subspace F is measured by the L _τ norm, that is, it is defined as the τ-root of the sum of the τth powers of the Euclidean distances of the points in P from F, for some τ≥1. Our main result is a randomized algorithm that takes as input P, k, and a parameter 0<ε<1; runs in nd ·2^{O(\fractk2e log2 \frac ke)}nd \cdot2^{O(\frac{\tau k^{2}}{\varepsilon} \log^{2} \frac {k}{\varepsilon})} time, and returns a k-subspace that with probability at least 1/2 has a fit that is at most (1+ε) times that of the optimal k-subspace.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

Approximating common fixed points of asymptotically nonexpansive mappings by composite algorithm in Banach spaces

Let E be a uniformly convex Banach space and K a nonempty convex closed subset which is also a nonexpansive retract of E. Let T ₁, T ₂ and T ₃: K → E be asymptotically nonexpansive mappings with {k _n }, {l _n } and {j _n }. [1, ∞) such that Σ _n=1 ^∞ (k _n − 1) < ∞, Σ _n=1 ^∞ (l _n − 1) < ∞ and Σ _n=1 ^∞ (j _n − 1) < ∞, respectively and F nonempty, where F = {x ∈ K: T _1x = T _2x = T ₃ x} = x} denotes the common fixed points set of T ₁, _{T 2} and T ₃. Let {α _n }, {α′ _n } and {α″ _n } be real sequences in (0, 1) and ∈ ≤ {α _n }, {α′ _n }, {α″ _n } ≤ 1 − ∈ for all n ∈ N and some ∈ > 0. Starting from arbitrary x ₁ ∈ K define the sequence {x _n } by