This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ...This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,展开更多
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.展开更多
In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an exis...In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an existence theorem of solutions for generalized strongly nonlinear quasivariational inclusion is established and a new proximal point algorithm with errors is suggested for finding approximate solutions which strongly converge to the exact solution of the generalized strongly, nonlinear quasivariational inclusion. As special cases, some known results in this field are also discussed.展开更多
In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde...In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.展开更多
We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approx...We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approximate solutions, which strongly converge to the exact solution of a fuzzy set-valued variational inclusion with (H,η)-monotone. The results improved and generalized the general quasi-variational inclusions with fuzzy set-valued mappings proposed by Jin and Tian Jin MM, Perturbed proximal point algorithm for general quasi-variational inclusions with fuzzy set-valued mappings, OR Transactions, 2005, 9(3): 31-38, (In Chinese); Tian YX, Generalized nonlinear implicit quasi-variational inclusions with fuzzy mappings, Computers & Mathematics with Applications, 2001, 42: 101-108.展开更多
Optimization problem of cardinality constrained mean-variance(CCMV)model for sparse portfolio selection is considered.To overcome the difficulties caused by cardinality constraint,an exact penalty approach is employed...Optimization problem of cardinality constrained mean-variance(CCMV)model for sparse portfolio selection is considered.To overcome the difficulties caused by cardinality constraint,an exact penalty approach is employed,then CCMV problem is transferred into a difference-of-convex-functions(DC)problem.By exploiting the DC structure of the gained problem and the superlinear convergence of semismooth Newton(ssN)method,an inexact proximal DC algorithm with sieving strategy based on a majorized ssN method(siPDCA-mssN)is proposed.For solving the inner problems of siPDCA-mssN from dual,the second-order information is wisely incorporated and an efficient mssN method is employed.The global convergence of the sequence generated by siPDCA-mssN is proved.To solve large-scale CCMV problem,a decomposed siPDCA-mssN(DsiPDCA-mssN)is introduced.To demonstrate the efficiency of proposed algorithms,siPDCA-mssN and DsiPDCA-mssN are compared with the penalty proximal alternating linearized minimization method and the CPLEX(12.9)solver by performing numerical experiments on realword market data and large-scale simulated data.The numerical results demonstrate that siPDCA-mssN and DsiPDCA-mssN outperform the other methods from computation time and optimal value.The out-of-sample experiments results display that the solutions of CCMV model are better than those of other portfolio selection models in terms of Sharp ratio and sparsity.展开更多
In this paper,an accelerated proximal gradient algorithm is proposed for Hankel tensor completion problems.In our method,the iterative completion tensors generated by the new algorithm keep Hankel structure based on p...In this paper,an accelerated proximal gradient algorithm is proposed for Hankel tensor completion problems.In our method,the iterative completion tensors generated by the new algorithm keep Hankel structure based on projection on the Hankel tensor set.Moreover,due to the special properties of Hankel structure,using the fast singular value thresholding operator of the mode-s unfolding of a Hankel tensor can decrease the computational cost.Meanwhile,the convergence of the new algorithm is discussed under some reasonable conditions.Finally,the numerical experiments show the effectiveness of the proposed algorithm.展开更多
Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization term.Proximal stochastic gradient methods are popular for solving such composite optimization proble...Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization term.Proximal stochastic gradient methods are popular for solving such composite optimization problems.We propose a minibatch proximal stochastic recursive gradient algorithm SRG-DBB,which incorporates the diagonal Barzilai–Borwein(DBB)stepsize strategy to capture the local geometry of the problem.The linear convergence and complexity of SRG-DBB are analyzed for strongly convex functions.We further establish the linear convergence of SRGDBB under the non-strong convexity condition.Moreover,it is proved that SRG-DBB converges sublinearly in the convex case.Numerical experiments on standard data sets indicate that the performance of SRG-DBB is better than or comparable to the proximal stochastic recursive gradient algorithm with best-tuned scalar stepsizes or BB stepsizes.Furthermore,SRG-DBB is superior to some advanced mini-batch proximal stochastic gradient methods.展开更多
Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact cus...Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.展开更多
A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces.The cost function consists of a separable term, in which each component is modeled through its own pote...A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces.The cost function consists of a separable term, in which each component is modeled through its own potential,and of a coupling term, in which constraints on linear transformations of the components are penalized with smooth functionals.An algorithm with guaranteed weak convergence to a solution to the problem is provided.Various multicomponent signal decomposition and recovery applications are discussed.展开更多
The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-regularized problems and inspired many applications in sparse-approximation and image-processing fields.Recently,so...The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-regularized problems and inspired many applications in sparse-approximation and image-processing fields.Recently,some convergence results are established for the proximal scheme of IHT,namely proximal iterative hard thresholding(PIHT)algorithm(Blumensath and Davies,in J Fourier Anal Appl 14:629–654,2008;Hu et al.,Methods 67:294–303,2015;Lu,Math Program 147:125–154,2014;Trzasko et al.,IEEE/SP 14th Workshop on Statistical Signal Processing,2007)on solving the related l_(0)-optimization problems.However,the complexity analysis for the PIHT algorithm is not well explored.In this paper,we aim to provide some complexity estimations for the PIHT sequences.In particular,we show that the complexity of the sequential iterate error is at o(1/k).Under the assumption that the objective function is composed of a quadratic convex function and l_(0)regularization,we show that the PIHT algorithm has R-linear convergence rate.Finally,we illustrate some applications of this algorithm for compressive sensing reconstruction and sparse learning and validate the estimated error bounds.展开更多
The problem of low accuracy of POI(Points of Interest)recommendation in LBSN(Location-Based Social Networks)has not been effectively solved.In this paper,a POI recommendation algorithm based on non-convex regularized ...The problem of low accuracy of POI(Points of Interest)recommendation in LBSN(Location-Based Social Networks)has not been effectively solved.In this paper,a POI recommendation algorithm based on non-convex regularized tensor completion is proposed.The fourth-order tensor is constructed by using the current location category,the next location category,time and season,the regularizer is added to the objective function of tensor completion to prevent over-fitting and reduce the error of the model.The proximal algorithm is used to solve the objective function,and the adaptive momentum is introduced to improve the efficiency of the solution.The experimental results show that the algorithm can improve recommendation accuracy while reducing the time cost.展开更多
In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions ...In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.展开更多
This paper introduces and considers a new system of generalized mixed variational inequal- ities in a Hilbert space, which includes many new and known systems of variational inequalities and generalized variational in...This paper introduces and considers a new system of generalized mixed variational inequal- ities in a Hilbert space, which includes many new and known systems of variational inequalities and generalized variational inequalities as special cases. By using the two concepts of η-subdifferential and η-proximal mappings of a proper function, the authors try to demonstrate that the system of generalized mixed variational inequalities is equivalence with a fixed point problem. By applying the equivalence, a new and innovative η-proximal point algorithm for finding approximate solutions of the system of generalized mixed variational inequalities will be suggested and analyzed. The authors also study the convergence analysis of the new iterative method under much weaker conditions. The results can be viewed as a refinement and improvement of the previously known results for variational inequalities.展开更多
The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields,and the proximal point algorithm(PPA)is among the fundamental a...The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields,and the proximal point algorithm(PPA)is among the fundamental algorithms for solving the zero-finding problem.PPA not only provides a very general framework of analyzing convergence and rate of convergence of many algorithms,but also can be very efficient in solving some structured problems.In this paper,we give a survey on the developments of PPA and its variants,including the recent results with linear proximal term,with the nonlinear proximal term,as well as the inexact forms with various approximate criteria.展开更多
The proximal point algorithm has many interesting applications,such as signal recovery,signal processing and others.In recent years,the proximal point method has been extended to Riemannian manifolds.The main advantag...The proximal point algorithm has many interesting applications,such as signal recovery,signal processing and others.In recent years,the proximal point method has been extended to Riemannian manifolds.The main advantages of these extensions are that nonconvex problems in classic sense may become geodesic convex by introducing an appropriate Riemannian metric,constrained optimization problems may be seen as unconstrained ones.In this paper,we propose an inexact proximal point algorithm for geodesic convex vector function on Hadamard manifolds.Under the assumption that the objective function is coercive,the sequence generated by this algorithm converges to a Pareto critical point.When the objective function is coercive and strictly geodesic convex,the sequence generated by this algorithm converges to a Pareto optimal point.Furthermore,under the weaker growth condition,we prove that the inexact proximal point algorithm has linear/superlinear convergence rate.展开更多
A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012,while only global convergence is proved at the same time.In this paper,we...A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012,while only global convergence is proved at the same time.In this paper,we give a unified proof on theO(1/t)iteration complexity,together with the linear convergence rate for this kind of proximal-based decomposition methods.Besides theε-optimal iteration complexity result defined by variational inequality,the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order.Further,the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties,without necessary strong monotone conditions.展开更多
In this paper,the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems,where the nonconvex term is possibly nonsmooth.Their al...In this paper,the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems,where the nonconvex term is possibly nonsmooth.Their algorithm adopts the proximal gradient algorithm with extrapolation and a safe-guarding policy to minimize the smoothed objective function for better practical and theoretical performance.Moreover,the algorithm uses a easily checking rule to update the smoothing parameter to ensure that any accumulation point of the generated sequence is an(afne-scaled)Clarke stationary point of the original nonsmooth and nonconvex problem.Their experimental results indicate the effectiveness of the proposed algorithm.展开更多
In this paper,we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers.The stopping criterion is easy to verify,and the computational cost is much less ...In this paper,we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers.The stopping criterion is easy to verify,and the computational cost is much less than the classical stopping criterion in the highly influential paper by Boyd et al.(Found Trends Mach Learn 3(1):1–122,2011).展开更多
L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure e...L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure equipment. A novel PP mitigation approach is proposed in this paper. Firstly, a deformed PP detection(DPPD) method that combines a filter bank, correlation detection, and rescanning is proposed to detect the deformed PPs(DPPs) which are caused by multiple filters in the receiver. Secondly, a finite impulse response(FIR) model is used to approximate the overall characteristic of filters, and then the waveform of DPP can be acquired by the original waveform of PP and the FIR model. Finally, sparse representation is used to estimate the position and amplitude of each DPP, and then reconstruct each DPP. The reconstructed DPPs will be subtracted from the contaminated signal to mitigate interference. Numerical experiments show that the bit error rate performance of our approach is about 5 dB better than that of recent works and is closer to interference-free environment.展开更多
文摘This paper proposes two kinds of approximate proximal point algorithms （APPA） for monotone variational inequalities, both of which can be viewed as two extended versions of Solodov and Svaiter＇s APPA in the paper ＂Error bounds for proximal point subproblems and associated inexact proximal point algorithms＂ published in 2000. They are both prediction- correction methods which use the same inexactness restriction; the only difference is that they use different search directions in the correction steps. This paper also chooses an optimal step size in the two versions of the APPA to improve the profit at each iteration. Analysis also shows that the two APPAs are globally convergent under appropriate assumptions, and we can expect algorithm 2 to get more progress in every iteration than algorithm 1. Numerical experiments indicate that algorithm 2 is more efficient than algorithm 1 with the same correction step size,
基金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.
文摘In this paper, a class of generalized strongly nonlinear quasivariational inclusions are studied. By using the properties of the resolvent operator associated with a maximal monotone; mapping in Hilbert space, an existence theorem of solutions for generalized strongly nonlinear quasivariational inclusion is established and a new proximal point algorithm with errors is suggested for finding approximate solutions which strongly converge to the exact solution of the generalized strongly, nonlinear quasivariational inclusion. As special cases, some known results in this field are also discussed.
基金Supported both by the Teaching and Research Award Fund for Outstanding Young Teachers inHigher Educational Institutions of MOEChinaand by the Dawn Program Fund in Shanghai
文摘In order to find roots of maximal monotone operators, this paper introduces and studies the modified approximate proximal point algorithm with an error sequence {e k} such that || ek || \leqslant hk || xk - [(x)\tilde]k ||\left\| { e^k } \right\| \leqslant \eta _k \left\| { x^k - \tilde x^k } \right\| with ?k = 0￥ ( hk - 1 ) < + ￥\sum\limits_{k = 0}^\infty {\left( {\eta _k - 1} \right)} and infk \geqslant 0 hk = m\geqslant 1\mathop {\inf }\limits_{k \geqslant 0} \eta _k = \mu \geqslant 1 . Here, the restrictions on {η k} are very different from the ones on {η k}, given by He et al (Science in China Ser. A, 2002, 32 (11): 1026–1032.) that supk \geqslant 0 hk = v < 1\mathop {\sup }\limits_{k \geqslant 0} \eta _k = v . Moreover, the characteristic conditions of the convergence of the modified approximate proximal point algorithm are presented by virtue of the new technique very different from the ones given by He et al.
基金the Natural Science Foundation of China (No. 10471151)the Educational Science Foundation of Chongqing (KJ051307).
文摘We introduced a new class of fuzzy set-valued variational inclusions with (H,η)-monotone mappings. Using the resolvent operator method in Hilbert spaces, we suggested a new proximal point algorithm for finding approximate solutions, which strongly converge to the exact solution of a fuzzy set-valued variational inclusion with (H,η)-monotone. The results improved and generalized the general quasi-variational inclusions with fuzzy set-valued mappings proposed by Jin and Tian Jin MM, Perturbed proximal point algorithm for general quasi-variational inclusions with fuzzy set-valued mappings, OR Transactions, 2005, 9(3): 31-38, (In Chinese); Tian YX, Generalized nonlinear implicit quasi-variational inclusions with fuzzy mappings, Computers & Mathematics with Applications, 2001, 42: 101-108.
基金supported by the National Natural Science Foundation of China(Grant No.11971092)supported by the Fundamental Research Funds for the Central Universities(Grant No.DUT20RC(3)079)。
文摘Optimization problem of cardinality constrained mean-variance(CCMV)model for sparse portfolio selection is considered.To overcome the difficulties caused by cardinality constraint,an exact penalty approach is employed,then CCMV problem is transferred into a difference-of-convex-functions(DC)problem.By exploiting the DC structure of the gained problem and the superlinear convergence of semismooth Newton(ssN)method,an inexact proximal DC algorithm with sieving strategy based on a majorized ssN method(siPDCA-mssN)is proposed.For solving the inner problems of siPDCA-mssN from dual,the second-order information is wisely incorporated and an efficient mssN method is employed.The global convergence of the sequence generated by siPDCA-mssN is proved.To solve large-scale CCMV problem,a decomposed siPDCA-mssN(DsiPDCA-mssN)is introduced.To demonstrate the efficiency of proposed algorithms,siPDCA-mssN and DsiPDCA-mssN are compared with the penalty proximal alternating linearized minimization method and the CPLEX(12.9)solver by performing numerical experiments on realword market data and large-scale simulated data.The numerical results demonstrate that siPDCA-mssN and DsiPDCA-mssN outperform the other methods from computation time and optimal value.The out-of-sample experiments results display that the solutions of CCMV model are better than those of other portfolio selection models in terms of Sharp ratio and sparsity.
文摘In this paper,an accelerated proximal gradient algorithm is proposed for Hankel tensor completion problems.In our method,the iterative completion tensors generated by the new algorithm keep Hankel structure based on projection on the Hankel tensor set.Moreover,due to the special properties of Hankel structure,using the fast singular value thresholding operator of the mode-s unfolding of a Hankel tensor can decrease the computational cost.Meanwhile,the convergence of the new algorithm is discussed under some reasonable conditions.Finally,the numerical experiments show the effectiveness of the proposed algorithm.
基金the National Natural Science Foundation of China(Nos.11671116,11701137,12071108,11991020,11991021 and 12021001)the Major Research Plan of the NSFC(No.91630202)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(No.XDA27000000)the Natural Science Foundation of Hebei Province(No.A2021202010)。
文摘Many machine learning problems can be formulated as minimizing the sum of a function and a non-smooth regularization term.Proximal stochastic gradient methods are popular for solving such composite optimization problems.We propose a minibatch proximal stochastic recursive gradient algorithm SRG-DBB,which incorporates the diagonal Barzilai–Borwein(DBB)stepsize strategy to capture the local geometry of the problem.The linear convergence and complexity of SRG-DBB are analyzed for strongly convex functions.We further establish the linear convergence of SRGDBB under the non-strong convexity condition.Moreover,it is proved that SRG-DBB converges sublinearly in the convex case.Numerical experiments on standard data sets indicate that the performance of SRG-DBB is better than or comparable to the proximal stochastic recursive gradient algorithm with best-tuned scalar stepsizes or BB stepsizes.Furthermore,SRG-DBB is superior to some advanced mini-batch proximal stochastic gradient methods.
基金the National Natural Science Foundation of China(Nos.11971238 and 11871279)。
文摘Proximal point algorithm(PPA)is a useful algorithm framework and has good convergence properties.Themain difficulty is that the subproblems usually only have iterative solutions.In this paper,we propose an inexact customized PPA framework for twoblock separable convex optimization problem with linear constraint.We design two types of inexact error criteria for the subproblems.The first one is absolutely summable error criterion,under which both subproblems can be solved inexactly.When one of the two subproblems is easily solved,we propose another novel error criterion which is easier to implement,namely relative error criterion.The relative error criterion only involves one parameter,which is more implementable.We establish the global convergence and sub-linear convergence rate in ergodic sense for the proposed algorithms.The numerical experiments on LASSO regression problems and total variation-based image denoising problem illustrate that our new algorithms outperform the corresponding exact algorithms.
基金supported by the Agence Nationale de la Recherche under grant ANR-08-BLAN-0294-02
文摘A convex variational formulation is proposed to solve multicomponent signal processing problems in Hilbert spaces.The cost function consists of a separable term, in which each component is modeled through its own potential,and of a coupling term, in which constraints on linear transformations of the components are penalized with smooth functionals.An algorithm with guaranteed weak convergence to a solution to the problem is provided.Various multicomponent signal decomposition and recovery applications are discussed.
基金supported by the National Natural Science Foundation of China(No.91330102)973 program(No.2015CB856000).
文摘The iterative hard thresholding(IHT)algorithm is a powerful and efficient algorithm for solving l_(0)-regularized problems and inspired many applications in sparse-approximation and image-processing fields.Recently,some convergence results are established for the proximal scheme of IHT,namely proximal iterative hard thresholding(PIHT)algorithm(Blumensath and Davies,in J Fourier Anal Appl 14:629–654,2008;Hu et al.,Methods 67:294–303,2015;Lu,Math Program 147:125–154,2014;Trzasko et al.,IEEE/SP 14th Workshop on Statistical Signal Processing,2007)on solving the related l_(0)-optimization problems.However,the complexity analysis for the PIHT algorithm is not well explored.In this paper,we aim to provide some complexity estimations for the PIHT sequences.In particular,we show that the complexity of the sequential iterate error is at o(1/k).Under the assumption that the objective function is composed of a quadratic convex function and l_(0)regularization,we show that the PIHT algorithm has R-linear convergence rate.Finally,we illustrate some applications of this algorithm for compressive sensing reconstruction and sparse learning and validate the estimated error bounds.
文摘The problem of low accuracy of POI(Points of Interest)recommendation in LBSN(Location-Based Social Networks)has not been effectively solved.In this paper,a POI recommendation algorithm based on non-convex regularized tensor completion is proposed.The fourth-order tensor is constructed by using the current location category,the next location category,time and season,the regularizer is added to the objective function of tensor completion to prevent over-fitting and reduce the error of the model.The proximal algorithm is used to solve the objective function,and the adaptive momentum is introduced to improve the efficiency of the solution.The experimental results show that the algorithm can improve recommendation accuracy while reducing the time cost.
基金This work was supported by the National Natural Science Foundation of China,the Oversea ExchangeFund of Nanjing Normal University,and CNPq of Brazil
文摘In this paper we present some algorithms for minimization of DC function (difference of two convex functions). They are descent methods of the proximal-type which use the convex properties of the two convex functions separately. We also consider an approximate proximal point algorithm. Some properties of the ε-subdifferential and the ε-directional derivative are discussed. The convergence properties of the algorithms are established in both exact and approximate forms. Finally, we give some applications to the concave programming and maximum eigenvalue problems.
基金supported by the Natural Science Foundation of China under Grant No.11001287the Natural Science Foundation Project of CSTC under Grant No.2010BB9254
文摘This paper introduces and considers a new system of generalized mixed variational inequal- ities in a Hilbert space, which includes many new and known systems of variational inequalities and generalized variational inequalities as special cases. By using the two concepts of η-subdifferential and η-proximal mappings of a proper function, the authors try to demonstrate that the system of generalized mixed variational inequalities is equivalence with a fixed point problem. By applying the equivalence, a new and innovative η-proximal point algorithm for finding approximate solutions of the system of generalized mixed variational inequalities will be suggested and analyzed. The authors also study the convergence analysis of the new iterative method under much weaker conditions. The results can be viewed as a refinement and improvement of the previously known results for variational inequalities.
基金Xing-Ju Cai and Fan Jiang were supported by the National Natural Science Foundation of China(Nos.11871279 and 11571178)Ke Guo was supported by the National Natural Science Foundation of China(Nos.11801455,11871059 and 11971238)+8 种基金China Postdoctoral Science Foundation(Nos.2019M663459 and 2020T130081)the Applied Basic Project of Sichuan Province(No.2020YJ0111)the Fundamental Research Funds of China West Normal University(No.18B031)the Open Project of Key Laboratory(No.CSSXKFKTM202004)School of Mathematical Sciences,Chongqing Normal University.Kai Wang was supported by the National Natural Science Foundation of China(No.11901294)Natural Science Foundation of Jiangsu Province(No.BK20190429)Zhong-Ming Wu was supported by the National Natural Science Foundation of China(No.12001286)the Startup Foundation for Introducing Talent of NUIST(No.2020r003)De-Ren Han was supported by the National Natural Science Foundation of China(Nos.12131004 and 12126603)。
文摘The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields,and the proximal point algorithm(PPA)is among the fundamental algorithms for solving the zero-finding problem.PPA not only provides a very general framework of analyzing convergence and rate of convergence of many algorithms,but also can be very efficient in solving some structured problems.In this paper,we give a survey on the developments of PPA and its variants,including the recent results with linear proximal term,with the nonlinear proximal term,as well as the inexact forms with various approximate criteria.
文摘The proximal point algorithm has many interesting applications,such as signal recovery,signal processing and others.In recent years,the proximal point method has been extended to Riemannian manifolds.The main advantages of these extensions are that nonconvex problems in classic sense may become geodesic convex by introducing an appropriate Riemannian metric,constrained optimization problems may be seen as unconstrained ones.In this paper,we propose an inexact proximal point algorithm for geodesic convex vector function on Hadamard manifolds.Under the assumption that the objective function is coercive,the sequence generated by this algorithm converges to a Pareto critical point.When the objective function is coercive and strictly geodesic convex,the sequence generated by this algorithm converges to a Pareto optimal point.Furthermore,under the weaker growth condition,we prove that the inexact proximal point algorithm has linear/superlinear convergence rate.
基金The work was supported in part by the Shanghai Youth Science and Technology Talent Sail Plan(No.15YF1403400)the National Natural Science Foundation of China(No.61321064).
文摘A unified efficient algorithm framework of proximal-based decomposition methods has been proposed for monotone variational inequalities in 2012,while only global convergence is proved at the same time.In this paper,we give a unified proof on theO(1/t)iteration complexity,together with the linear convergence rate for this kind of proximal-based decomposition methods.Besides theε-optimal iteration complexity result defined by variational inequality,the non-ergodic relative error of adjacent iteration points is also proved to decrease in the same order.Further,the linear convergence rate of this algorithm framework can be constructed based on some special variational inequality properties,without necessary strong monotone conditions.
基金supported by the National Natural Science Foundation of China(No.12001144)Zhejiang Provincial Natural Science Foundation of China(No.LQ20A010007)NSF/DMS-2152961。
文摘In this paper,the authors propose a novel smoothing descent type algorithm with extrapolation for solving a class of constrained nonsmooth and nonconvex problems,where the nonconvex term is possibly nonsmooth.Their algorithm adopts the proximal gradient algorithm with extrapolation and a safe-guarding policy to minimize the smoothed objective function for better practical and theoretical performance.Moreover,the algorithm uses a easily checking rule to update the smoothing parameter to ensure that any accumulation point of the generated sequence is an(afne-scaled)Clarke stationary point of the original nonsmooth and nonconvex problem.Their experimental results indicate the effectiveness of the proposed algorithm.
文摘In this paper,we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers.The stopping criterion is easy to verify,and the computational cost is much less than the classical stopping criterion in the highly influential paper by Boyd et al.(Found Trends Mach Learn 3(1):1–122,2011).
基金supported in part by the National Natural Science Foundation (Nos. U1533107 and U1433105)the Civil Aviation Science and Technology Innovation Foundation (No. MHRD20130217)the Fundamental Research Funds for the Central Universities of CAUC (No. 3122016D003)
文摘L-band digital aeronautical communication system 1(L-DACS1) is a promising candidate data-link for future air-ground communication, but it is severely interfered by the pulse pairs(PPs) generated by distance measure equipment. A novel PP mitigation approach is proposed in this paper. Firstly, a deformed PP detection(DPPD) method that combines a filter bank, correlation detection, and rescanning is proposed to detect the deformed PPs(DPPs) which are caused by multiple filters in the receiver. Secondly, a finite impulse response(FIR) model is used to approximate the overall characteristic of filters, and then the waveform of DPP can be acquired by the original waveform of PP and the FIR model. Finally, sparse representation is used to estimate the position and amplitude of each DPP, and then reconstruct each DPP. The reconstructed DPPs will be subtracted from the contaminated signal to mitigate interference. Numerical experiments show that the bit error rate performance of our approach is about 5 dB better than that of recent works and is closer to interference-free environment.
