No abstract uploaded!

No abstract uploaded!

Higher-order low-rank tensors naturally arise in many applications including hyperspectral data recovery, video inpainting, seismic data recon-struction, and so on. We propose a new model to recover a low-rank tensor by simultaneously performing low-rank matrix factorizations to the all-mode ma-tricizations of the underlying tensor. An alternating minimization algorithm is applied to solve the model, along with two adaptive rank-adjusting strategies when the exact rank is not known.

No abstract uploaded!

In this paper, we propose a randomized primaldual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its <i>O</i>(1/<i>t</i>) convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primaldual method for bilinear saddle-point problems (PD-S), the proximal Jacobian alternating direction method of multipliers (Prox-JADMM) and a randomized variant of the ADMM for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new

Stochastic gradient (SG) method has been popularly applied to solve optimization problems with objective that is stochastic or an average of many functions. Most existing works on SG assume that the underlying problem is unconstrained or has an easy-to-project constraint set. In this paper, we consider problems that have a stochastic objective and also many functional constraints. For such problems, it could be extremely expensive to project a point to the feasible set, or even compute subgradient and/or function value of all constraint functions. To find solutions of these problems, we propose a novel SG method based on the augmented Lagrangian function. Within every iteration, it inquires a stochastic subgradient of the objective, a subgradient and function value of one randomly sampled constraint function, and function value of another sampled constraint function. Hence, the per-iteration complexity is low. We establish its convergence rate for convex and also strongly convex problems. It can achieve the optimal O (1/\sqrt {k}) convergence rate for convex case and nearly optimal O (1/\sqrt {k}) rate for strongly convex case. Numerical experiments on quadratically constrained quadratic programming are conducted to demonstrate its efficiency.

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

No abstract uploaded!

Recent years have witnessed the rapid development of block coordinate update (BCU) methods, which are particularly suitable for problems involving large-sized data and/or variables. In optimization, BCU first appears as the coordinate descent method that works well for smooth problems or those with separable nonsmooth terms and/or separable constraints. As nonseparable constraints exist, BCU can be applied under primal-dual settings. In the literature, it has been shown that for weakly convex problems with nonseparable linear constraints, BCU with fully Gauss--Seidel updating rule may fail to converge and that with fully Jacobian rule can converge sublinearly. However, empirically the method with Jacobian update is usually slower than that with Gauss--Seidel rule. To maintain their advantages, we propose a hybrid Jacobian and Gauss--Seidel BCU method for solving linearly constrained multiblock

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.

We propose an algorithm for the state feedback pole assignment problem. The algorithm is the first of its kind, making use of the Schur form and minimizing the departure from normality of the closed-loop poles by Newtons method. Eleven illustrative examples, comparing our algorithm with three other existing ones, are given.

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

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.

The trust-region problem,which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

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.

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

No abstract uploaded!

No abstract uploaded!

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.

High-dimensional data contain not only redundancy but also noises produced by the sensors. These noises are usually non-Gaussian distributed. The metrics based on Euclidean distance are not suitable for these situations in general. In order to select the useful features and combat the adverse effects of the noises simultaneously, a robust sparse subspace learning method in unsupervised scenario is proposed in this paper based on the maximum correntropy criterion that shows strong robustness against outliers. Furthermore, an iterative strategy based on half quadratic and an accelerated block coordinate update is proposed. The convergence analysis of the proposed method is also carried out to ensure the convergence to a reliable solution. Extensive experiments are conducted on real-world data sets to show that the new method can filter out the outliers and outperform several state-of-the-art unsupervised

No abstract uploaded!

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices <i>X</i> and <i>Y</i> so that the product <i>XY</i> approximates a nonnegative data matrix <i>M</i> whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of <i>M</i> are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to