Several Algorithms For Nonsmooth Convex Optimization

1In this thesis, we study the nonsmooth optimization problem where the objective function is convex. Nonmonotone and filter technique have been proved very successful in smooth nonlinear optimization. We aplly these techniques to nonsmooth optimization and get three algorithms for nonsmooth optimization problems. These algorithms have been proved to be convergent globally and superlinearly.Grippo etc have studied nonmonotone line search technique, Facchinei and Lucidi proposed nonmonotone bundle-type scheme for convex nonsmooth minimization. We combine the nonmonotone technique with the algorithm proposed by Schramm and Zowe and we get a new algorithm. The major difference is that we use the different rule to accept a serious step. We don't use the nonmonotone line search, and our method is an "implicit" trust region method. We prove the global convergence of the algorithm.The nonsmooth minimization problem min f(x) can be transformed into a differentiable convex minimization problem minF(x), where F(x) is the Moreau-Yosida regularization of f(x). We first find an approximate proximal point and approximate subgradient by utilizing a cutting plane technique. Then we construct a trust region subproblem by using the approximate subgradient and approximate Hessian. We solve this subproblem by truncated CG method to obtain a search direction and decide to accept it by nonmonotone trust region method. The method converges globally and the rate of convergence is superlinear.Finally, we consider the application of the filter technique in nonsmooth optimization problem. Two problems of minimizing f and minimizing F are equivalent in the sense that the solution sets of both problems coincide with each other. We first find an approximate proximal point p^α(x_k) of x_k by utilizing a cutting plane technique such that for someε_k∈(0,α||v_k||], where a is a constant. Then we use g^α(x_k) := v_k as an approximation of g(x_k) in a quasi-Newton method and construct B₍k+1 by using t_k := g^α(x_k+1) - g^α(x_k). Compute h⁽(k+1) := ||v_k|| and f^(k+1) := f(p^α(x_k) + d_k), and we define the filter by using (h^(k), f^(k)). If (h^(k+1), f^(k+1) are accepted by the filter, we set x_k+1= p^α(x_k) + d_k and (h^(k+1), f^(k+1)) are added to the filter. Otherwise, we set x_k+1= p^α(x_k). The method converges globally and superlinearly.