Research On BB-like Methods For Several Optimization Problems

The Barzilai-Borwein (BB) method is an efficient method for solving unconstrained opti-mization problems. Due to its simplicity, low memory requirement and efficiency, the BB method has attracted much attention. The BB method has been extended to constrained optimization and nonsmooth optimization. Moreover, it has been utilized in many appli-cations including support vector machine, image processing, compressive sensing and etc. Designing effective BB-like methods for different problems is one of the hotspots in recent years. However, the objective functions of many optimization problems are often nonconvex, nonsmooth and even non-Lipschitz. Right now there are few methods for solving such kind of problems. This thesis focuses on several common optimization problems including the smooth convex constrained problem, the nonsmooth unconstrained problem, the nonsmooth problem with nonnegative constraints and the non-Lipschitz constrained problem. We propose BB-like methods for solving these problems respectively. Details are listed as follows:1. We study the smooth convex constrained optimization problems where the objective function is continuously differentiable and the constraint set is a closed convex set. The existence convergence analysis of the projected gradient method requires the gradient of the objective function to be Lipschitz continuous. However, few of the projected gradient meth-ods make use of the information of the Lipschitz constant. We employ the Lipschitz constant of the gradient to construct a quadratic regularization approximation of the objective at the current iteration. By combining the projection strategy and the nonmonotone line search, we propose a quadratic regularization projected BB method. The global convergence of the proposed method is established. We apply our method to nonnegative matrix factorization and compare it with several existence methods. Although our methods needs to compute two gradients and projections at each iteration, numerical results show that it can obtain a satisfactory solution in less iterations and shorter CPU time.2. We study a class of nonsmooth unconstrained optimization problems, where the ob-jective is the sum of a smooth function and a convex function. This class of problems contains the smooth convex constrained optimization problem as a special instance. By employing the nonmonotone line search, we propose a BB-like method and analyze its convergence. We prove that the proposed method converges sublinearly for a convex smooth term while the rate of convergence is R-linear when the smooth term is strongly convex. The numerical results on l2-l1 problems, image deblurring problems, group-separable regularization problems and total variation regularization problems show that the new method is efficient.3. We consider a class of nonsmooth optimization problems with nonnegative con-straints. By combining the smoothing technique and active strategy, we propose a smoothing affine-scaling BB method. Under mild conditions, we prove that the proposed method converges to a stationary point associated with the smoothing function. We apply our method to the expected residual minimization (ERM) formulation of the stochastic linear complementarity problems (SLCPs). Preliminary numerical results show that, compared with the smoothing projected gradient method, the new method can obtain a solution with higher accuracy in less iterations and shorter CPU time.4. We study a class of non-Lipschitz constrained optimization problems, where the objective is the sum of a smooth function and a non-Lipschitz function. By combining the smoothing technique and projection strategy, we propose a smoothing projected BB method. Under mild conditions, we prove that the proposed method converges to a scaled stationary point. When the objective function is locally Lipschitz continuous, then the proposed method converges to a Clarke stationary point. The numerical results on l1-l2 problems, image restoration problems and ERM formulation of SLCPs demonstrate the efficiency of the new method.