  


Iteration Bounds for Finding the $\epsilon$Stationary Points for Structured Nonconvex Optimization
Bo Jiang(isyebojiang163.com) Abstract: In this paper we study proximal conditionalgradient (CG) and proximal gradientprojection type algorithms for a blockstructured constrained nonconvex optimization model, which arises naturally from tensor data analysis. First, we introduce a new notion of $\epsilon$stationarity, which is suitable for the structured problem under consideration. %, compared with other similar solution concepts. We then propose two types of firstorder algorithms for the model based on the proximal conditionalgradient (CG) method and the proximal gradientprojection method respectively. If the nonconvex objective function is in the form of mathematical expectation, we then discuss how to incorporate randomized sampling to avoid computing the expectations exactly. For the general block optimization model, the proximal subroutines are performed for each block according to either the blockcoordinatedescent (BCD) or the maximumblockimprovement (MBI) updating rule. If the gradient of the nonconvex part of the objective $f$ satisfies $\ \nabla f(x)  \nabla f(y)\_q \le M \xy\_p^\delta$ where $\delta=p/q$ with $1/p+1/q=1$, then we prove that the new algorithms have an overall iteration complexity bound of $O(1/\epsilon^q)$ in finding an $\epsilon$stationary solution. If $f$ is concave then the iteration complexity reduces to $O(1/\epsilon)$. Our numerical experiments for tensor approximation problems show promising performances of the new solution algorithms. Keywords: constrained nonconvex optimization, block variables, iteration complexity bounds, conditional gradient algorithm Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Download: [PDF] Entry Submitted: 10/15/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  