Table of Content

30 September 2015, Volume 3 Issue 3

Previous Issue    Next Issue

On the Sublinear Convergence Rate of Multi-block ADMM

Tian-Yi Lin · Shi-Qian Ma · Shu-Zhong Zhang

2015, 3(3):  251.  doi:10.1007/s40305-015-0092-0

Asbtract ( 11686 )   PDF  

Related Articles | Metrics

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems. Despite its success in practice, the convergence of the standard ADMM for minimizing the sum of N (N  3) convex functions, whose variables are linked by linear constraints, has remained unclear for a very long time. Recently, Chen et al. (Math Program, doi:10.1007/ s10107-014-0826-5, 2014) provided a counter-example showing that the ADMM for N  3 may fail to converge without further conditions. Since the ADMM for N  3 has been very successful when applied to many problems arising from real practice, it is worth further investigating under what kind of sufficient conditions it can be guaranteed to converge. In this paper, we present such sufficient conditions that can guarantee the sublinear convergence rate for the ADMM for N  3. Specifically, we show that if one of the functions is convex (not necessarily strongly convex) and the other N-1 functions are strongly convex, and the penalty parameter lies in a certain region, the ADMM converges with rate O(1/t) in a certain ergodic sense and o(1/t) in a certain non-ergodic sense, where t denotes the number of iterations. As a by-product, we also provide a simple proof for the O(1/t) convergence rate of two-blockADMMin terms of both objective error and constraint violation, without assuming any condition on the penalty parameter and strong convexity on the functions.

Continuous Optimization

On Some Aspects of Perturbation Analysis for Matrix Cone Optimization Induced by Spectral Norm

Shao-Yan Guo · Li-Wei Zhang · Shou-Lin Hao

2015, 3(3):  275.  doi:10.1007/s40305-015-0088-9

Asbtract ( 356 )   PDF  

Related Articles | Metrics

In this paper, we consider a cone problem of matrix optimization induced by spectral norm (MOSN). By Schur complement, MOSN can be reformulated as a nonlinear semidefinite programming (NLSDP) problem. Then we discuss the constraint nondegeneracy conditions and strong second-order sufficient conditions of MOSN and its SDP reformulation, and obtain that the constraint nondegeneracy condition of MOSN is not always equivalent to that of NLSDP. However, the strong second-order sufficient conditions of these two problems are equivalent without any assumption. Finally, a sufficient condition is given to ensure the nonsingularity of the Clarke’s generalized Jacobian of the KKT system for MOSN.

Discrete Optimization

Discrete Global Optimization Problems with a Modified Discrete Filled Function

Yong-Jian Yang · Meng-Li He · Yue-Lin Gao

2015, 3(3):  297.  doi:10.1007/s40305-015-0085-z

Asbtract ( 395 )   PDF  

Related Articles | Metrics

This paper considers discrete global optimization problems. The traditional definition of the discrete filled function is modified in this paper. Based on the modified definition, a new discrete filled function is presented and an algorithm for discrete global optimization is developed from the discrete filled function. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the efficiency of the algorithm.

Continuous Optimization

Smoothing Approximations for Some Piecewise Smooth Functions

Hao Wu · Peng Zhang · Gui-Hua Lin

2015, 3(3):  317.  doi:10.1007/s40305-015-0091-1

Asbtract ( 321 )   PDF  

Related Articles | Metrics

In this paper, we study smoothing approximations for some piecewise smooth functions.We first present two approaches for one-dimensional case: a global approach is to construct smoothing approximations over the whole domain and a local approach is to construct smoothing approximations within appropriate neighborhoods of the nonsmooth points.We obtain some error estimate results for both approaches and discuss whether the smoothing approximations can inherit the convexity of the original
functions. Furthermore, we extend the global approach to some multiple dimensional cases.

A Wide Neighborhood Interior-Point Method for Cartesian P∗(κ)-LCP over Symmetric Cones

Marzieh Sayadi Shahraki · Hossein Mansouri·Maryam Zangiabadi

2015, 3(3):  331.  doi:10.1007/s40305-015-0094-y

Asbtract ( 364 )   PDF  

Related Articles | Metrics

In this paper, we propose an infeasible-interior-point method, based on a new wide neighborhood of the central path, for linear complementarity problems over symmetric cones with the Cartesian P∗(κ)-property. The convergence is shown for commutative class of search directions.Moreover, we analyze the algorithm and obtain the complexity bounds, which coincide with the best-known results for the Cartesian P∗(κ)-SCLCPs. Some numerical tests are reported to illustrate our theoretical results.

On the Convergence Rate of a Class of Proximal-Based Decomposition Methods for Monotone Variational Inequalities

Xiang-Feng Wang

2015, 3(3):  347.  doi:10.1007/s40305-015-0086-y

Asbtract ( 300 )   PDF  

Related Articles | Metrics

A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012, while only global convergence is proved at the same time. In this paper, we give a unified proof on theO(1/t) iteration complexity, together with the linear convergence rate for this kind of proximal-based decomposition methods. Besides the ε-optimal iteration complexity result defined by variational inequality, the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order. Further, the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties, without necessary strong monotone conditions.

Convex Relaxation Algorithm for a Structured Simultaneous Low-Rank and Sparse Recovery Problem

Le Han · Xiao-Lan Liu

2015, 3(3):  363.  doi:10.1007/s40305-015-0089-8

Asbtract ( 352 )   PDF  

Related Articles | Metrics

This paper is concerned with the structured simultaneous low-rank and sparse recovery, which can be formulated as the rank and zero-norm regularized least squares problem with a hard constraint diag() = 0. For this class of NP-hard problems, we propose a convex relaxation algorithm by applying the accelerated proximal gradient method to a convex relaxation model, which is yielded by the smoothed nuclear norm and the weighted l1-norm regularized least squares problem. A theoretical guarantee is provided by establishing the error bounds of the iterates to the true solution under mild restricted strong convexity conditions. To the best of our knowledge, this work is the first one to characterize the error bound of the iterates of the algorithm to the true solution. Finally, numerical results are reported for some random test problems and synthetic data in subspace clustering to verify the efficiency of the proposed convex relaxation algorithm.

Discrete Optimization

Pareto Minimizing Total Completion Time and Maximum Cost with Positional Due Indices

Yuan Gao · Jin-Jiang Yuan

2015, 3(3):  381.  doi:10.1007/s40305-015-0083-1

Asbtract ( 558 )   PDF  

Related Articles | Metrics

In this paper, we study the Pareto optimization scheduling problem on a single machine with positional due indices of jobs to minimize the total completion time and a maximum cost. For this problem, we give two O(n4)-time algorithms.