Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approx...Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions ofPPA （APPA） are developed for practical applications. In this paper, we compare two APPA methods, both of which can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ; in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm Ⅱ usually outperforms Algorithm Ⅰ. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm Ⅱ to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.展开更多
Sparse signal recovery is a topic of considerable interest,and the literature in this field is already quite immense.Many problems that arise in sparse signal recovery can be generalized as a convex programming with l...Sparse signal recovery is a topic of considerable interest,and the literature in this field is already quite immense.Many problems that arise in sparse signal recovery can be generalized as a convex programming with linear conic constraints.In this paper,we present a new proximal point algorithm(PPA) termed as relaxed-PPA(RPPA) contraction method,for solving this common convex programming.More precisely,we first reformulate the convex programming into an equivalent variational inequality(VI),and then efficiently explore its inner structure.In each step,our method relaxes the VI-subproblem to a tractable one,which can be solved much more efficiently than the original VI.Under mild conditions,the convergence of the proposed method is proved.Experiments with l1 analysis show that RPPA is a computationally efficient algorithm and compares favorably with the recently proposed state-of-the-art algorithms.展开更多
基金Project (No. 1027054) supported by the National Natural Science Foundation of China
文摘Proximal point algorithms （PPA） are attractive methods for solving monotone variational inequalities （MVI）. Since solving the sub-problem exactly in each iteration is costly or sometimes impossible, various approximate versions ofPPA （APPA） are developed for practical applications. In this paper, we compare two APPA methods, both of which can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. By extending the general forward-backward splitting methods, we obtain Algorithm Ⅰ; in the same way, Algorithm Ⅱ is proposed by spreading the general extra-gradient methods. Our analysis explains theoretically why Algorithm Ⅱ usually outperforms Algorithm Ⅰ. For computation practice, we consider a class of MVI with a special structure, and choose the extending Algorithm Ⅱ to implement, which is inspired by the idea of Gauss-Seidel iteration method making full use of information about the latest iteration. And in particular, self-adaptive techniques are adopted to adjust relevant parameters for faster convergence. Finally, some numerical experiments are reported on the separated MVI. Numerical results showed that the extending Algorithm II is feasible and easy to implement with relatively low computation load.
基金the National Natural Science Foundation of China(No.70901018)
文摘Sparse signal recovery is a topic of considerable interest,and the literature in this field is already quite immense.Many problems that arise in sparse signal recovery can be generalized as a convex programming with linear conic constraints.In this paper,we present a new proximal point algorithm(PPA) termed as relaxed-PPA(RPPA) contraction method,for solving this common convex programming.More precisely,we first reformulate the convex programming into an equivalent variational inequality(VI),and then efficiently explore its inner structure.In each step,our method relaxes the VI-subproblem to a tractable one,which can be solved much more efficiently than the original VI.Under mild conditions,the convergence of the proposed method is proved.Experiments with l1 analysis show that RPPA is a computationally efficient algorithm and compares favorably with the recently proposed state-of-the-art algorithms.
