A quadratically convergent method for minimizing a sum of euclidean norms

We consider the problem of minimizing a sum of Euclidean norms. \(F(x) = \sum\nolimits_{i = 1}^m {||r_i } (x)||\) here the residuals {r _i(x)} are affine functions fromR ⁿ toR ¹ (n≥1≥2,m>-2). This arises in a number of applications, including single-and multi-facility location problems. The functionF is, in general, not differentiable atx if at least oner _i (x) is zero. Computational methods described in the literature converge quite slowly if the solution is at such a point. We present a new method which, at each iteration, computes a direction of search by solving the Newton system of equations, projected, if necessary, into a linear manifold along whichF is locally differentiable. A special line search is used to obtain the next iterate. The algorithm is closely related to a method recently described by Calamai and Conn. The new method has quadratic convergence to a solutionx under given conditions. The reason for this property depends on the nature of the solution. If none of the residuals is zero at^* x, thenF is differentiable at^* x and the quadratic convergence follows from standard properties of Newton's method. If one of the residuals, sayr _i ^* x), is zero, then, as the iteration proceeds, the Hessian ofF becomes extremely ill-conditioned. It is proved that this illconditioning, instead of creating difficulties, actually causes quadratic convergence to the manifold (x?r _i (x)=0}. If this is a single point, the solution is thus identified. Otherwise it is necessary to continue the iteration restricted to this manifold, where the usual quadratic convergence for Newton's method applies. If several residuals are zero at^* x, several stages of quadratic convergence take place as the correct index set is constructed. Thus the ill-conditioning property accelerates the identification of the residuals which are zero at the solution. Numerical experiments are presented, illustrating these results.     

Gradient methods for minimizing composite functions

In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two terms: one is smooth and given by a black-box oracle, and another is a simple general convex function with known structure. Despite the absence of good properties of the sum, such problems, both in convex and nonconvex cases, can be solved with efficiency typical for the first part of the objective. For convex problems of the above structure, we consider primal and dual variants of the gradient method (with convergence rate $O\left({1 \over k}\right)$ ), and an accelerated multistep version with convergence rate $O\left({1 \over k^2}\right)$ , where $k$ is the iteration counter. For nonconvex problems with this structure, we prove convergence to a point from which there is no descent direction. In contrast, we show that for general nonsmooth, nonconvex problems, even resolving the question of whether a descent direction exists from a point is NP-hard. For all methods, we suggest some efficient “line search” procedures and show that the additional computational work necessary for estimating the unknown problem class parameters can only multiply the complexity of each iteration by a small constant factor. We present also the results of preliminary computational experiments, which confirm the superiority of the accelerated scheme.     

A unified approach to evaluation algorithms for multivariate polynomials

We present a unified framework for most of the known and a few new evaluation algorithms for multivariate polynomials expressed in a wide variety of bases including the Bernstein-Bézier, multinomial (or Taylor), Lagrange and Newton bases. This unification is achieved by considering evaluation algorithms for multivariate polynomials expressed in terms of L-bases, a class of bases that include the Bernstein-Bézier, multinomial, and a rich subclass of Lagrange and Newton bases. All of the known evaluation algorithms can be generated either by considering up recursive evaluation algorithms for L-bases or by examining change of basis algorithms for L-bases. For polynomials of degree in variables, the class of up recursive evaluation algorithms includes a parallel up recurrence algorithm with computational complexity , a nested multiplication algorithm with computational complexity and a ladder recurrence algorithm with computational complexity . These algorithms also generate a new generalization of the Aitken-Neville algorithm for evaluation of multivariate polynomials expressed in terms of Lagrange L-bases. The second class of algorithms, based on certain change of basis algorithms between L-bases, include a nested multiplication algorithm with computational complexity , a divided difference algorithm, a forward difference algorithm, and a Lagrange evaluation algorithm with computational complexities , and per point respectively for the evaluation of multivariate polynomials at several points.

     

A unified approach to fractional derivatives

A new fractional derivative of the Grüwald–Letnikov type is proposed and some properties are studied. The new definition incorporates both the forward and backward Grüwald–Letnikov and the two-sided fractional derivatives. Several properties of such generalized operator are presented, and some particular cases deduced.     

A unified approach for constructing fast two-step Newton-like methods

We introduce some new very general ways of constructing fast two-step Newton-like methods to approximate a locally unique solution of a nonlinear operator equation in a Banach space setting. We provide existence-uniqueness theorems as well as an error analysis for the iterations involved using Newton-Kantorovich-type hypotheses and the majorant method. Our results depend on the existence of a Lipschitz function defined on a closed ball centered at a certain point and of a fixed radius and with values into the positive real axis. Special choices of this function lead to favorable comparisons with results already in the literature. Some applications to the solution of nonlinear integral equations appearing in radiative transfer as well as to the solution of integral equations of Uryson-type are also provided.     

A unified approach for solving nonlinear regular perturbation problems

This aritcle describes a simple alternative unified method of solving nonlinear regular perturbation problems. The procedure is based upon the manipulation of Taylor's approximation for the expansion of the nonlinear term in the perturbed equation.

An essential feature of this technique is the relative simplicity used and the associated unified computational procedure that is employed. As such it should be of interest to teachers of applied mathematics courses, particularly those courses which include perturbation methods.

One of the merits of this approach is that it leads on naturally to a scheme based on Taylor's expansions and, consequently, allows the regular perturbation method to be introduced into a course much earlier than is currently common.

The method is illustrated by implementing it to four perturbation problems, including two algebraic equations and two initial-value problems. The new approach is compared and contrasted with the traditional perturbation scheme in order to demonstrate its relative merit.     

Local properties of algorithms for minimizing nonsmooth composite functions

This paper considers local convergence and rate of convergence results for algorithms for minimizing the composite functionF(x)=f(x)+h(c(x)) wheref andc are smooth buth(c) may be nonsmooth. Local convergence at a second order rate is established for the generalized Gauss—Newton method whenh is convex and globally Lipschitz and the minimizer is strongly unique. Local convergence at a second order rate is established for a generalized Newton method when the minimizer satisfies nondegeneracy, strict complementarity and second order sufficiency conditions. Assuming the minimizer satisfies these conditions, necessary and sufficient conditions for a superlinear rate of convergence for curvature approximating methods are established. Necessary and sufficient conditions for a two-step superlinear rate of convergence are also established when only reduced curvature information is available. All these local convergence and rate of convergence results are directly applicable to nonlinearing programming problems.This work was done while the author was a Research fellow at the Mathematical Sciences Research Centre, Australian National University.     

A unified approach to controllability analysis for hybrid control systems

A unified approach is proposed for controllability analysis of a class of hybrid control systems, employing the controllability concept defined in [M. Tittus, B. Egardt, Control design for integrator hybrid systems, IEEE Transactions on Automatic Control 43 (4) (1998) 491–500; J.H. van Schuppen, A Sufficient Condition for Controllability of a Class of Hybrid Systems, in: LNCS, vol. 1386, Springer, 1998, pp. 374–383; Z. Yang, M. Verhaegen, Y.J. Wang, Z.J. Chen, Hybrid controllability of linear switched systems, in: Proceedings of 37th Control and Decision Conference, Tampa, FL, USA, December 1998, pp. 3920–3925]. The unified approach comprises global reachability analysis at the discrete event system level, local reachability analysis at the continuous-time dynamical system level and a merging of the results of these two methods using a discrete-path search algorithm. The proposed method is demonstrated useful for controllability analysis of complex hybrid control systems. The method is illustrated by analyzing the controllability of a linear switched system.     

A unified approach to fuzzy pattern recognition

Goldfarb has proposed a unified approach to pattern recognition. In Goldfarb's approach the data from a pseudometric space are isometrically embedded in a pseudo-Euclidean space. The data representation is built for every particular data set. The resulting data space will be data dependent. The aim of this paper is to extend Goldfarb's approach for fuzzy clustering. A fuzzy clustering procedure for a pseudometric data set is given. A generalisation of this algorithm to obtain the cluster substructure of a fuzzy class is also proposed.     

A unified approach to theories of shadowing

This paper introduces the notion of a general approximation property, which encompasses many existing types of shadowing. It is proven that there exists a metric space X such that the sets of maps with many types of general approximation properties (including the classic shadowing, the L _p -shadowing, limit shadowing, and the s-limit shadowing) are not dense in C(X), S(X), and H(X) (the space of continuous self-maps of X, continuous surjections of X onto itself, and self-homeomorphisms of X) and that there exists a manifold M such that the sets of maps with general approximation properties of nonlocal type (including the average shadowing property and the asymptotic average shadowing property) are not dense in C(M), S(M), and H(M). Furthermore, it is proven that the sets of maps with a wide range of general approximation properties (including the classic shadowing, the L _p -shadowing, and the s-limit shadowing) are dense in the space of continuous self-maps of the Cantor set. A condition is given that guarantees transfer of general approximation property from a map on X to the map induced by it on the hyperspace of X. It is also proven that the transfer in the opposite direction always takes place.     

A unified approach to evaluation of expressions

It is demonstrated here that by introduction of three new operators, namely,position, fraction, andconcatenation, expressions of typical programming languages can be executed with a unified method starting from the character string. This method eliminates the pre-formation of constants and variables and suggests a new way of looking at parsing. The approach is particularly suitable for the development of packages for on-line, desk-calculator type operations in a time-sharing environment.     

A unified approach to projective lattice geometries

The interest in pursuing projective geometry on modules has led to several lattice theoretic generalizations of the classical synthetic concept of projective geometry on vector spaces.Introduced in this paper is an approach that is capable of unifying various attempts within a new conceptual frame. This approach reflects algebraic properties from a lattice-geometric point of view. Together with new results we are presenting results from previous publications which have been improved in the frame of this work.     

On the optimality conditions for the problem of minimizing a sum of euclidean norms

The problem of minimizing is considered. The subdifferential ofF(X) is computed for anyX and, as a consequence, the necessary and sufficient optimality conditions are stated in a more general form than the ones up to now known.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.