In this note, we extend the algorithms Extra [13] and subgradient-push [10] to a new algorithm ExtraPush for consensus optimization with convex differentiable objective functions over a directed network. When the stationary distribution of the network can be computed in advance, we propose a simplified algorithm called Normalized ExtraPush. Just like Extra, both ExtraPush and Normalized ExtraPush can iterate with a fixed step size. But unlike Extra, they can take a column-stochastic mixing matrix, which is not necessarily doubly stochastic. Therefore, they remove the undirected-network restriction of Extra. Subgradient-push, while also works for directed networks, is slower on the same type of problem because it must use a sequence of diminishing step sizes.
We present preliminary analysis for ExtraPush under a bounded sequence assumption. For Normalized ExtraPush, we show that it naturally produces a bounded, linearly convergent sequence provided that the objective function is strongly convex.
In our numerical experiments, ExtraPush and Normalized ExtraPush performed similarly well. They are significantly faster than subgradient-push, even when we hand-optimize the step sizes for the latter.

Higher-order singular value decomposition (HOSVD) is an efficient way for data reduction and also eliciting intrinsic structure of multi-dimensional array data. It has been used in many applications, and some of them involve incomplete data. To obtain HOSVD of the data with missing values, one can first impute the missing entries through a certain tensor completion method and then perform HOSVD to the reconstructed data. However, the two-step procedure can be inefficient and does not make reliable decomposition.
In this paper, we formulate an incomplete HOSVD problem and combine the two steps into solving a single optimization problem, which simultaneously achieves imputation of missing values and also tensor decomposition. We also present one algorithm for solving the problem based on block coordinate update (BCU). Global convergence of the algorithm is shown under mild assumptions and implies that of the popular higher-order orthogonality iteration (HOOI) method, and thus we, for the first time, give global convergence of HOOI.
In addition, we compare the proposed method to state-of-the-art ones for solving incomplete HOSVD and also low-rank tensor completion problems and demonstrate the superior performance of our method over other compared ones. Furthermore, we apply it to face recognition and MRI image reconstruction to show its practical performance.

This paper considers the collaborative resource allocation problem over a hybrid cloud center and edge server network, an emerging infrastructure for efficient Internet services. The cloud center acts as a pool of inexhaustible computation and storage powers. The edge servers often have limited computation and storage powers but are able to provide quick responses to service requests from end users. Upon receiving service requests, edge servers assign them to themselves, their neighboring edge servers, as well as the cloud center, aiming at minimizing the overall network cost.
This paper first establishes an optimization model for this problem. Second, in light of the separable structure of the optimization model, we utilize the alternating direction method of multipliers (ADMM) to develop a fully collaborative resource allocation algorithm. The edge servers and the cloud center autonomously collaborate to compute their local optimization variables and prices of network resources, and reach an optimal solution. Numerical experiments demonstrate the effectiveness of the hybrid network infrastructure as well as the proposed algorithm.

An algorithmic framework, based on the difference of convex functions algorithm (DCA), is proposed for minimizing a class of concave sparse metrics for compressed sensing problems. The resulting algorithm iterates a sequence of $ℓ_1$ minimization problems. An exact sparse recovery theory is established to show that the proposed framework always improves on the basis pursuit ($ℓ_1$ minimization) and inherits robustness from it. Numerical examples on success rates of sparse solution recovery illustrate further that, unlike most existing non-convex compressed sensing solvers in the literature, our method always out-performs basis pursuit, no matter how ill-conditioned the measurement matrix is. Moreover, the iterative $ℓ_1$ (IL1) algorithm lead by a wide margin the state-of-the-art algorithms on $ℓ_{1/2}$ and logarithimic minimizations in the strongly coherent (highly ill-conditioned) regime, despite the same objective functions. Last but not least, in the application of magnetic resonance imaging (MRI), IL1 algorithm easily recovers the phantom image with just 7 line projections.

In this paper, we consider two different formulations (one is smooth and the other one is nonsmooth) for solving linear matrix inequalities (LMIs), an important class of semidefinite programming (SDP), under a certain Slater constraint qualification assumption. We then propose two first-order methods, one based on subgradient method and the other based on Nesterov's optimal method, and show that they converge linearly for solving these formulations. Moreover, we introduce an accelerated prox-level method which converges linearly uniformly for both smooth and non-smooth problems without requiring the input of any problem parameters. Finally, we consider a special case of LMIs, i.e., linear system of inequalities, and show that a linearly convergent algorithm can be obtained under a much weaker assumption.

When the coordinates of a set of points are known, the pairwise Euclidean distances among the points can be easily computed. Conversely, if the Euclidean distance matrix is given, a set of coordinates for those points can be computed through the well known classical Multi-Dimensional Scaling (MDS). In this paper, we consider the case where some of the distances are far from being accurate (containing large noises or even missing). In such a situation, the order of the known distances (i.e., some distances are larger than others) is valuable information that often yields far more accurate construction of the points than just using the magnitude of the known distances. The methods making use of the order information are collectively known as nonmetric MDS. A challenging computational issue among all existing nonmetric MDS methods is that there are often a large number of ordinal constraints. In this paper, we cast this problem as a matrix optimization problem with ordinal constraints. We then adapt an existing smoothing Newton method to our matrix problem. Extensive numerical results demonstrate the efficiency of the algorithm, which can potentially handle a very large number of ordinal constraints.

This paper develops and analyzes multigrid semismooth Newton methods for a class of inequality-constrained optimization problems in function space which are motivated by and include linear elastic contact problems of Signorini type. We show that after a suitable Moreau-Yosida type regularization of the problem superlinear local convergence is obtained for a class of semismooth Newton methods. In addition, estimates for the order of the error introduced by the regularization are derived. The main part of the paper is devoted to the analysis of a multilevel preconditioner for the semismooth Newton system. We prove a rigorous bound for the contraction rate of the multigrid cycle which is robust with respect to sufficiently small regularization parameters and the number of grid levels. Moreover, it applies to adaptively refined grids. The paper concludes with numerical results.

In this paper, we propose an extended Levenberg-Marquardt (ELM) framework that generalizes the classic Levenberg-Marquardt (LM) method to solve the unconstrained minimization problem min $ρ(r(x))$, where $r$ : $\mathbb{R}^n$ → $\mathbb{R}^m$ and $ρ$ : $\mathbb{R}^m$ → $\mathbb{R}$. We also develop a few inexact variants which generalize ELM to the cases where the inner subproblem is not solved exactly and the Jacobian is simplified, or perturbed. Global convergence and local superlinear convergence are established under certain suitable conditions. Numerical results show that our methods are promising.