Search

This paper is concerned with ℓq (0

This note is concerned with a class of nonmonotone descent methods for minimizing a proper lower semicontinuous Kurdyka-Łojasiewicz (KL) function Φ, which generates a sequence satisfying a nonmonotone decrease condition and a relative error tolerance. Under suitable assumptions, we prove that the whole sequence converges to a limiting critical point of Φ, and, when Φ is a KL function of exponent θ∈[0,1), the convergence admits a linear rate if θ∈[0,1/2] and a sublinear rate associated to θ if θ∈(1/2,1). These assumptions are shown to be sufficient and necessary if in addition Φ is weakly convex on a neighborhood of the set of critical points. Our results not only extend the convergence results of monotone descent methods for KL optimization problems but also resolve the convergence problem on the iterate sequence generated by a class of nonmonotone line search algorithms for nonconvex and nonsmooth problems. [ABSTRACT FROM AUTHOR]

This paper concerns itself with the rank regularized minimization problem with a spectral norm ball constraint. We reformulate this NP-hard problem as an equivalent MPGCC (mathematical program with a generalized complementarity constraint) and show that the penalty problem, yielded by moving the generalized complementarity constraint to the objective, is exact in the sense that it has the same global optimal solution set as the MPGCC does when the penalty parameter is over a threshold. Then, by solving the exact penalty problem in an alternating way, we propose a multistage convex relaxation approach, and provide its theoretical guarantee for the rank regularized least squares problem with a spectral norm ball constraint. Specifically, we derive the error and approximate rank bounds for the optimal solution of each stage and quantify the reduction of the error and approximate rank bounds of the first stage convex relaxation (which is exactly the nuclear norm relaxation) in the subsequent stages. In particular, we establish the geometric convergence in a statistical sense for the error sequence, which reduces to the linear convergence in the noiseless case and implies the exact recoverability of the multistage convex relaxation approach. Numerical experiments are conducted on some low-rank matrix recovery examples to confirm the theoretical results. [ABSTRACT FROM AUTHOR]

We reformulate the zero-norm minimization problem as an equivalent mathematical program with equilibrium constraints and establish that its penalty problem, induced by adding the complementarity constraint to the objective, is exact. Then, by the special structure of the exact penalty problem, we propose a decomposition method that can seek a global optimal solution of the zero-norm minimization problem under the null space condition in [M. A. Khajehnejad et al. IEEE Trans. Signal. Process., 59 (2011), pp. 1985-2001] by solving a finite number of weighted l1-norm minimization problems. To handle the weighted l1-norm subproblems, we develop a partial proximal point algorithm where the subproblems may be solved approximately with the limited memory BFGS (L-BFGS) or the semismooth Newton-CG. Finally, we apply the exact penalty decomposition method with the weighted l1-norm subproblems solved by combining the L-BFGS with the semismooth Newton-CG to several types of sparse optimization problems, and compare its performance with that of the penalty decomposition method [Z. Lu and Y. Zhang, SIAM J. Optim., 23 (2013), pp. 2448-2478], the iterative support detection method [Y. L. Wang and W. T. Yin, SIAM J. Sci. Comput., 3 (2010), pp. 462-491], and the state-of-the-art code FPC AS [Z. W. Wen et al., SIAM J. Sci. Comput., 32 (2010), pp. 1832-1857]. Numerical comparisons indicate that the proposed method is very efficient in terms of the recoverability and the required computing time. [ABSTRACT FROM AUTHOR]

For a locally optimal solution to the nonlinear semi definite programming problem, under Robinson's constraint qualification, we show that the nonsingularity of Clarke's Jacobian of the Fischer Burmeister (FB) nonsmooth system is equivalent to the strong regularity of the Karush- Kuhn Tucker point. Consequently, from Sun's paper [Math. Oper. Res., 31 (2006), pp. 761 776] the semi smooth Newton method applied to the FB system may attain the locally quadratic convergence under the strong second order sufficient condition and constraint nondegeneracy. [ABSTRACT FROM AUTHOR]