Improved algorithms for several network location problems with equality measures

We consider single facility location problems with equity measures, defined on networks. The models discussed are, the variance, the sum of weighted absolute deviations, the maximum weighted absolute deviation, the sum of absolute weighted differences, the range, and the Lorenz measure. We review the known algorithmic results and present improved algorithms for some of these models.     

Parallel algorithms for continuous multifacility competitive location problems

We consider a continuous location problem in which a firm wants to set up two or more new facilities in a competitive environment. Both the locations and the qualities of the new facilities are to be found so as to maximize the profit obtained by the firm. This hard-to-solve global optimization problem has been addressed in Redondo et al. (Evol. Comput.17(1), 21–53, 2009) using several heuristic approaches. Through a comprehensive computational study, it was shown that the evolutionary algorithm uego is the heuristic which provides the best solutions. In this work, uego is parallelized in order to reduce the computational time of the sequential version, while preserving its capability at finding the optimal solutions. The parallelization follows a coarse-grain model, where each processing element executes the uego algorithm independently of the others during most of the time. Nevertheless, some genetic information can migrate from a processor to another occasionally, according to a migratory policy. Two migration processes, named Ring-Opt and Ring-Fusion2, have been adapted to cope the multiple facilities location problem, and a superlinear speedup has been obtained.     

The $$ \ell _1 $$-Analysis in Phase Retrieval with Redundant Dictionary

This article presents new results concerning the recovery of a signal from the magnitude only measurements where the signal is not sparse in an orthonormal basis but in a redundant dictionary, which we call it phase retrieval with redundant dictionary for short. To solve this phaseless problem, we analyze the \( \ell _1 \)-analysis model. Firstly we investigate the noiseless case with presenting a null space property of the measurement matrix under which the \( \ell _1 \)-analysis model provides an exact recovery. Secondly we introduce a new property (S-DRIP) of the measurement matrix. By solving the \( \ell _1 \)-analysis model, we prove that this property can guarantee a stable recovery of real signals that are nearly sparse in overcomplete dictionaries.     

An $$\ell _{2}$$-neighborhood infeasible interior-point algorithm for linear complementarity problems

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an \(\varepsilon \)-approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound \(O\left(n\log \varepsilon ^{-1}\right)\) which coincides with the best known iteration bound for infeasible interior-point methods.     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

Isoperimetric problem for exponential measure on the plane with $$\ell _1$$-metric

We give a solution to the isoperimetric problem for the exponential measure on the plane with the \(\ell _1\)-metric. As it turns out, among all sets of a given measure, the simplex or its complement (i.e. the ball in the \(\ell _1\)-metric or its complement) has the smallest boundary measure. The proof is based on a symmetrisation (along the sections of equal \(\ell _1\)-distance from the origin).     

Second-order orthant-based methods with enriched Hessian information for sparse $$\ell _1$$-optimization

We present a second order algorithm, based on orthantwise directions, for solving optimization problems involving the sparsity enhancing \(\ell _1\)-norm. The main idea of our method consists in modifying the descent orthantwise directions by using second order information both of the regular term and (in weak sense) of the \(\ell _1\)-norm. The weak second order information behind the \(\ell _1\)-term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identification of the active set. We also prove that a reduced version of our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a specific choice of the algorithm parameters. We present several computational experiments to show the efficiency of our approach compared to other state-of-the-art algorithms.     

Planar Weber location problems with barriers and block norms

The Weber problem for a given finite set of existing facilities Ex={Ex₁,Ex₂,...,Ex_M}⊂∝² with positive weights w_m (m=1,...,M) is to find a new facility X^*∈∝² such that Σ _m=1 ^M w_md(X,Ex_m) is minimized for some distance function d. In this paper we consider distances defined by block norms. A variation of this problem is obtained if barriers are introduced which are convex polyhedral subsets of the plane where neither location of new facilities nor traveling is allowed. Such barriers, like lakes, military regions, national parks or mountains, are frequently encountered in practice. From a mathematical point of view barrier problems are difficult, since the presence of barriers destroys the convexity of the objective function. Nevertheless, this paper establishes a discretization result: one of the grid points in the grid defined by the existing facilities and the fundamental directions of the polyhedral distances can be proved to be an optimal location. Thus the barrier problem can be solved with a polynomial algorithm. This revised version was published online in June 2006 with corrections to the Cover Date.     

Robust PCA and subspace tracking from incomplete observations using \ell _0-surrogates

Many applications in data analysis rely on the decomposition of a data matrix into a low-rank and a sparse component. Existing methods that tackle this task use the nuclear norm and \(\ell _1\) -cost functions as convex relaxations of the rank constraint and the sparsity measure, respectively, or employ thresholding techniques. We propose a method that allows for reconstructing and tracking a subspace of upper-bounded dimension from incomplete and corrupted observations. It does not require any a priori information about the number of outliers. The core of our algorithm is an intrinsic Conjugate Gradient method on the set of orthogonal projection matrices, the so-called Grassmannian. Non-convex sparsity measures are used for outlier detection, which leads to improved performance in terms of robustly recovering and tracking the low-rank matrix. In particular, our approach can cope with more outliers and with an underlying matrix of higher rank than other state-of-the-art methods.     

Complexity and nonlinear semidefinite programming reformulation of \ell _1-constrained nonconvex quadratic optimization

In this article, we show that the $\ell _1$ -constrained nonconvex quadratic optimization problem (QPL1) is NP-hard, even when the off-diagonal elements are all nonnegative. Then we give an answer to Pinar and Teboulle’s open problem on the nonlinear semidefinite programming relaxation of (QPL1). The analytical approach is extended to $\ell _p$ -constrained quadratic programs with $1<p<2$ .     

Duality for constrained multifacility location problems with mixed norms and applications

A dual problem is developed for the constrained multifacility minisum location problems involving mixed norms. General optimality conditions are also obtained providing new algorithms based on the concept of partial inverse of a multifunction. These algorithms which are decomposition methods, generate sequences globally converging to a primal and a dual solution respectively. Numerical results are reported.     

Young walls and graded dimension formulas for finite quiver Hecke algebras of type A^{(2)}_{2\ell } and D^{(2)}_{\ell +1}

We study graded dimension formulas for finite quiver Hecke algebras \(R^{\Lambda _0}(\beta )\) of type \(A^{(2)}_{2\ell }\) and \(D^{(2)}_{\ell +1}\) using combinatorics of Young walls. We introduce the notion of standard tableaux for proper Young walls and show that the standard tableaux form a graded poset with lattice structure. We next investigate Laurent polynomials associated with proper Young walls and their standard tableaux arising from the Fock space representations consisting of proper Young walls. Then, we prove the graded dimension formulas described in terms of the Laurent polynomials. When evaluating at \(q=1\) , the graded dimension formulas recover the dimension formulas for \(R^{\Lambda _0}(\beta )\) described in terms of standard tableaux of strict partitions.     

A generalized elastic net regularization with smoothed $$\ell _{q}$$ penalty for sparse vector recovery

In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q} (0<q \le 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising.     

Polynomial algorithms for parametric minquantile and maxcovering planar location problems with locational constraints

A location is sought within some convex region of the plane for the central site of some public service to a finite number of demand points. The parametric maxcovering problem consists in finding for eachR>0 the point from which the total weight of the demand points within distanceR is maximal. The parametric minimal quantile problem asks for each percentage α the point minimising the distance necessary for covering demand points of total weight at least α. We investigate the properties of these two closely related problems and derive polynomial algorithms to solve them both in case of either (possibly inflated) Euclidean or polyhedral distances. The research of the first author is partially supported by Grant PB96-1416-C02-02 of Ministerio de Educación y Cultura, Spain.     

Orthogonality in \ell _p-spaces and its bearing on ordered Banach spaces

We introduce a notion of \(p\) -orthogonality in a general Banach space for \(1 \le p \le \infty \) . We use this concept to characterize \(\ell _p\) -spaces among Banach spaces and also among complete order smooth \(p\) -normed spaces as (ordered) Banach spaces with a total \(p\) -orthonormal set (in the positive cone). We further introduce a notion of \(p\) -orthogonal decomposition in order smooth \(p\) -normed spaces. We prove that if the \(\infty \) -orthogonal decomposition holds in an order smooth \(\infty \) -normed space, then the \(1\) -orthogonal decomposition holds in the dual space. We also give an example to show that the above said decomposition may not be unique.