On k-stable functions

We prove that a k-continuous or a k-stable function cannot depend on more than k4^k?1 variables and related facts.     

A Convenient Subcategory of Tych

A map f:XY between Hausdorff topological spaces is k-continuous if its restriction f| _K to every compact subspace K of X is continuous. X is called a k _R -space if every k-continuous function from X to a Tychonoff space is continuous. In this paper we investigate the category of Tychonoff k _R -spaces, and show that it is Cartesian closed (thus convenient in the sense of Wyler).     

Remarks on Banaschewski-Fomin-Shanin extensions

The notion ofB ^*-continuous andB _c ^* -continuous maps is introduced. The problem of epireflection of Banaschewski-Fomin-Shanin extension for a general Hausdorff space is investigated with the help of_p B ^* and_P B _c ^* -continuous maps.     

Results on <Emphasis Type="Italic">F</Emphasis>-continuous graphs

For any nontrivial connected graph F and any graph G, the F-degree of a vertex v in G is the number of copies of F in G containing v. G is called F-continuous if and only if the F-degrees of any two adjacent vertices in G differ by at most 1; G is F-regular if the F-degrees of all vertices in G are the same. This paper classifies all P ₄-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph F other than the star K _1,k , k ⩾ 1, there exists a regular graph that is not F-continuous. If F is 2-connected, then there exists a regular F-continuous graph that is not F-regular.      

Determination of an unknown coefficient in a nonlinear heat equation

The problem of determining an unknown term k(u) in the equation k(u)u_t=(k(u)u_x)_x is considered in this paper. Applying Tikhonov's regularization approach, we develop a procedure to find an approximate stable solution to the unknown coefficient from the overspecified data.     

Computing Proximal Points of Convex Functions with Inexact Subgradients

Locating proximal points is a component of numerous minimization algorithms. This work focuses on developing a method to find the proximal point of a convex function at a point, given an inexact oracle. Our method assumes that exact function values are at hand, but exact subgradients are either not available or not useful. We use approximate subgradients to build a model of the objective function, and prove that the method converges to the true prox-point within acceptable tolerance. The subgradient g _k used at each step k is such that the distance from g _k to the true subdifferential of the objective function at the current iteration point is bounded by some fixed ε > 0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient.     

Shift invariant preduals of ℓ 1(ℤ)

The Banach space ? ₁(?) admits many non-isomorphic preduals, for example, C(K) for any compact countable space K, along with many more exotic Banach spaces. In this paper, we impose an extra condition: the predual must make the bilateral shift on ? ₁(?) weak*-continuous. This is equivalent to making the natural convolution multiplication on ? ₁(?) separately weak*-continuous and so turning ? ₁(?) into a dual Banach algebra. We call such preduals shift-invariant. It is known that the only shift-invariant predual arising from the standard duality between C ₀(K) (for countable locally compact K) and ? ₁(?) is c ₀(?). We provide an explicit construction of an uncountable family of distinct preduals which do make the bilateral shift weak*-continuous. Using Szlenk index arguments, we show that merely as Banach spaces, these are all isomorphic to c ₀. We then build some theory to study such preduals, showing that they arise from certain semigroup compactifications of ?. This allows us to produce a large number of other examples, including non-isometric preduals, and preduals which are not Banach space isomorphic to c ₀.     

Computation of the canonical polynomials and applications to some optimal control problems

The Tau method is a numerical technique that consists in constructing polynomial approximate solutions for ordinary differential equations. This method has two approaches: operational and recursive. The former converts the differential problem to a matrix problem and produces approximations in terms of a prescribed orthogonal polynomials basis. In the recursive approach, we construct approximate solutions in terms of a special set of polynomials {Q _k (t); k?=?0, 1, 2...} called canonical polynomials basis. In some cases, the Q _k ??s can be obtained explicitly through a recursive formula. But no analogous formulae are reported in the literature for the general cases. In this paper, utilizing the operational Tau method, we develop an algorithm that allows to generate those canonical polynomials iteratively and explicitly. In addition, we demonstrate the capability of the operational Tau method in treating quadratic optimal control problems governed by ordinary differential equations.     

An accelerated subspace minimization three-term conjugate gradient algorithm for unconstrained optimization

A three-term conjugate gradient algorithm for large-scale unconstrained optimization using subspace minimizing technique is presented. In this algorithm the search directions are computed by minimizing the quadratic approximation of the objective function in a subspace spanned by the vectors: ?g _k+1, s _k and y _k . The search direction is considered as: d _k+1 = ?g _k+1 + a _k s _k + b _k y _k , where the scalars a _k and b _k are determined by minimization the affine quadratic approximate of the objective function. The step-lengths are determined by the Wolfe line search conditions. We prove that the search directions are descent and satisfy the Dai-Liao conjugacy condition. The suggested algorithm is of three-term conjugate gradient type, for which both the descent and the conjugacy conditions are guaranteed. It is shown that, for uniformly convex functions, the directions generated by the algorithm are bounded above, i.e. the algorithm is convergent. The numerical experiments, for a set of 750 unconstrained optimization test problems, show that this new algorithm substantially outperforms the known Hestenes and Stiefel, Dai and Liao, Dai and Yuan and Polak, Ribiére and Poliak conjugate gradient algorithms, as well as the limited memory quasi-Newton method L-BFGS and the discrete truncated-Newton method TN.     

An efficient gradient method with approximate optimal stepsize for large-scale unconstrained optimization

In this paper, we introduce a new concept of approximate optimal stepsize for gradient method, use it to interpret the Barzilai-Borwein (BB) method, and present an efficient gradient method with approximate optimal stepsize for large unconstrained optimization. If the objective function f is not close to a quadratic on a line segment between the current iterate x _k and the latest iterate x _k?1, we construct a conic model to generate the approximate optimal stepsize for gradient method if the conic model is suitable to be used. Otherwise, we construct a new quadratic model or two other new approximation models to generate the approximate optimal stepsize for gradient method. We analyze the convergence of the proposed method under some suitable conditions. Numerical results show the proposed method is very promising.     

Global convergence of a modified BFGS-type method for unconstrained non-convex minimization

To the unconstrained programme of non-convex function, this article give a modified BFGS algorithm associated with the general line search model. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equationB _k +1s _k =y _k ^* ,, wherey _k ^* is the sum ofy _k andA _k s _k , andA _k is some matrix. The global convergence properties of the algorithm associating with the general form of line search is proved.     

A modified BFGS method and its superlinear convergence in nonconvex minimization with general line search rule

In this paper, a modification of the BFGS algorithm for unconstrained nonconvex optimization is proposed. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equation B _k+1 s _k =y _k ^* , where y _k ^* is the sum of y _k and t _k ‖g(x _k )‖s _k . The global convergence property of the algorithm associated with the general line search rule is prove.     

A proximal iterative approach to a non-convex optimization problem

We consider a variable Krasnosel’skii-Mann algorithm for approximating critical points of a prox-regular function or equivalently for finding fixed-points of its proximal mapping prox_λf. The novelty of our approach is that the latter is not non-expansive any longer. We prove that the sequence generated by such algorithm (via the formula x_k+1=(1−α_k)x_k+α_kprox_λkfx_k, where (α_k) is a sequence in (0,1)), is an approximate fixed-point of the proximal mapping and converges provided that the function under consideration satisfies a local metric regularity condition.     

L p -continuous extreme selectors of multifunctions with decomposable values: Existence theorems

The existence theorems of L _p -continuous selectors that values are extreme points are proved for a class of multivalued maps. Applications to multivalued maps appearing in multivalued differential equations are presented.     

On convergence of the inexact Rayleigh quotient iteration with the Lanczos method used for solving linear systems

For the Hermitian inexact Rayleigh quotient iteration(RQI),we consider the local convergence of the in exact RQI with the Lanczos method for the linear systems involved.Some attractive properties are derived for the residual,whose norm is ξk,of the linear system obtained by the Lanczos method at outer iteration k+1.Based on them,we make a refned analysis and establish new local convergence results.It is proved that(i) the inexact RQI with Lanczos converges quadratically provided that ξk≤ξ with a constant ξ1 and (ii) the method converges linearly provided that ξk is bounded by some multiple of1/||rk|| with rkthe residual norm of the approximate eigenpair at outer iteration k.The results are fundamentally diferent from the existing ones that always require ξk<1,and they have implications on efective implementations of the method.Based on the new theory,we can design practical criteria to control ξkto achieve quadratic convergence and implement the method more efectively than ever before.Numerical experiments confrm our theory and demonstrate that the inexact RQI with Lanczos is competitive to the inexact RQI with MINRES.     

A polynomial time approximation algorithm for the two-commodity splittable flow problem

We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity ${i \in \{1, 2\}}$ can be split into a bounded number k _i of equally-sized chunks that can be routed on different paths. We show that in contrast to the single-commodity case this problem is NP-hard, and hard to approximate to within a factor of α > 1/2. We present a polynomial time 1/2-approximation algorithm for the case of uniform chunk size over both commodities and show that for even k _i and a mild cut condition it can be modified to yield an exact method. The uniform case can be used to derive a 1/4-approximation for the maximum concurrent (k ₁, k ₂)-splittable flow without chunk size restrictions for fixed demand ratios.     

L p-Continuous extreme selectors of multifunctions with decomposable values: Relaxation theorems

Some density theorems of L _p-continuous selectors whose values are extreme points are proved for a class of multivalued maps. applications to the Darboux problem for a differential inclusion are presented.     

A two-phase heuristic for the bottleneck k-hyperplane clustering problem

In the bottleneck hyperplane clustering problem, given n points in $\mathbb{R}^{d}$ and an integer k with 1≤k≤n, we wish to determine k hyperplanes and assign each point to a hyperplane so as to minimize the maximum Euclidean distance between each point and its assigned hyperplane. This mixed-integer nonlinear problem has several interesting applications but is computationally challenging due, among others, to the nonconvexity arising from the ? ₂-norm. After comparing several linear approximations to deal with the ? ₂-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the ? _∞-approximation and the problem geometry, and then it is converted into an ? ₂-approximate solution. Computational experiments on realistic randomly generated instances and instances arising from piecewise affine maps show that our heuristic provides good quality solutions in a reasonable amount of time.     

Combinatorial models for the finite-dimensional Grassmannians

Let ? ⁿ be a linear hyperplane arrangement in ? ⁿ . We define two corresponding posetsG _k (? ⁿ andV _k (? ⁿ ) of oriented matroids, which approximate the GrassmannianG _k (? ⁿ ) and the Stiefel manifoldV _k (? ⁿ ). The basic conjectures are that the “OM-Grassmannian”G _k (? ⁿ ) has the homotopy type ofG _k (? ⁿ ), and that the “OM-Stiefel bundle” Δπ: ΔV _k (? ⁿ ) → ΔG _k (? ⁿ ) is a surjective map. These conjectures can be proved in some cases: we survey the known results and add some new ones. The conjectures fail if they are generalized to nonrealizable oriented matroids ? ⁿ .     

f I-sets and decomposition of R I C-continuity

First, we introduce the notion of f _I-sets and investigate their properties in ideal topological spaces. Then, we also introduce the notions of R _I C-continuous, f _I-continuous and contra*-continuous functions and we show that a function f: (X,τ,I) to (Y,φ) is R _I C -continuous if and only if it is f _I-continuous and contra*-continuous. This revised version was published online in June 2006 with corrections to the Cover Date.