This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize.

No abstract uploaded!

The support vector machine (SVM) has been used in a wide variety of classification problems. The original SVM uses the hinge loss function, which is non-differentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with 1 -regularization. This paper considers the Huberized SVM (HSVM), which uses a differentiable approximation of the hinge loss function. We first explore the use of the proximal gradient (PG) method to solving binary-class HSVM (B-HSVM) and then generalize it to multi-class HSVM (M-HSVM). Under strong convexity assumptions, we show that our algorithm converges linearly. In addition, we give a finite convergence result about the support of the solution, based on which we further accelerate the algorithm by a two-stage method. We present extensive numerical experiments on both synthetic and real datasets which demonstrate the superiority of our

Recent several years have witnessed the surge of asynchronous (async-) parallel computing methods due to the extremely big data involved in many modern applications and also the advancement of multi-core machines and computer clusters. In optimization, most works about async-parallel methods are on unconstrained problems or those with block separable constraints. In this paper, we propose an async-parallel method based on block coordinate update (BCU) for solving convex problems with <i>nonseparable</i> linear constraint. Running on a single node, the method becomes a novel randomized primaldual BCU for multi-block affinely constrained problems. For these problems, GaussSeidel cyclic primaldual BCU is not guaranteed to converge to an optimal solution if no additional assumptions, such as strong convexity, are made. On the contrary, assuming convexity and existence of a primaldual

We discuss a variant of the multi-task <i>n</i>-vehicle exploration problem. Instead of requiring an optimal permutation of vehicles in every group, the new problem requires all vehicles in a group to arrive at the same destination. Given <i>n</i> tasks with assigned consume-time and profit, it may also be viewed as a maximization of every processors average profit. Further, we propose a new kind of partition problem in fractional form and analyze its computational complexity. By regarding fractional partition as a special case, we prove that the average profit maximization problem is NP-hard when the number of processors is fixed and it is strongly NPhard in general. At last, a pseudo-polynomial time algorithm for the average profit maximization problem and the fractional partition problem is presented, using the idea of the pseudo-polynomial time algorithm for the classical partition problem.

No abstract uploaded!

In this paper, we propose the palindromic doubling algorithm (PDA) for the palindromic generalized eigenvalue problem (PGEP) A x= Ax. We establish a complete convergence theory of the PDA for PGEPs without unimodular eigenvalues, or with unimodular eigenvalues of partial multiplicities two (one or two for eigenvalue 1). Some important applications from the vibration analysis and the optimal control for singular descriptor linear systems will be presented to illustrate the feasibility and efficiency of the PDA.

This paper introduces algorithms for the decentralized low-rank matrix completion problem. Assume a low-rank matrix W = [W ₁ ,W ₂ , ...,W _L ]. In a network, each agent observes some entries of W  . In order to recover the unobserved entries of W via decentralized computation, we factorize the unknown matrix W as the product of a public matrix X, common to all agents, and a private matrix Y = [Y ₁ ,Y ₂ , ...,Y _L ], where Y  is held by agent . Each agent alternatively updates Y  and its local estimate of X while communicating with its neighbors toward a consensus on the estimate. Once this consensus is (nearly) reached throughout the network, each agent recovers W  = XY  , and thus W is recovered. The communication cost is scalable to the number of agents, and W  and Y  are kept private to agent to a certain extent. The algorithm is accelerated by extrapolation and compares favorably to the centralized

We extend the RayleighRitz method to the eigen-problem of periodic matrix pairs. Assuming that the deviations of the desired periodic eigenvectors from the corresponding periodic subspaces tend to zero, we show that there exist periodic Ritz values that converge to the desired periodic eigenvalues unconditionally, yet the periodic Ritz vectors may fail to converge. To overcome this potential problem, we minimize residuals formed with periodic Ritz values to produce the refined periodic Ritz vectors, which converge under the same assumption. These results generalize the corresponding well-known ones for RayleighRitz approximations and their refinement for non-periodic eigen-problems. In addition, we consider a periodic Arnoldi process which is particularly efficient when coupled with the RayleighRitz method with refinement. The numerical results illustrate that the refinement procedure produces excellent

In Chu (Syst Control Lett 56:303314, 2007), the pole assignment problem was considered for the control system \dot{x} = Ax + Bu with linear state-feedback \dot{x} = Ax + Bu An algorithm using the Schur form has been proposed, producing good suboptimal solutions which can be refined further using optimization. In this paper, the algorithm is improved, incorporating the minimization of the feedback gain \dot{x} = Ax + Bu It is also extended for the pole assignment of the descriptor system \dot{x} = Ax + Bu with linear state- and derivative-feedback \dot{x} = Ax + Bu Newton refinement for the solutions is discussed and several illustrative numerical examples are presented.