Advanced Search
Article Contents
Article Contents

A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence

  • * Corresponding author: Jie Shen

    * Corresponding author: Jie Shen 
The first author is supported by the National Natural Science Foundation of China under Project No. 11301246, No. 11671183, No. 11601061 and the Natural Science Foundation Plan Project of Liaoning Province No.20170540573, the Foundation of Educational Committee of Liaoning Province No.LF201783607 and the Fundamental Research Funds for the Central Universities of China No.DUT16LK07.
Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by
  • Motivated by the proximal-like bundle method [K. C. Kiwiel, Journal of Optimization Theory and Applications, 104(3) (2000), 589-603.], we establish a new proximal Chebychev center cutting plane algorithm for a type of nonsmooth optimization problems. At each step of the algorithm, a new optimality measure is investigated instead of the classical optimality measure. The convergence analysis shows that an $\varepsilon$-optimal solution can be obtained within $O(1/\varepsilon^3)$ iterations. The numerical result is presented to show the validity of the conclusion and it shows that the method is competitive to the classical proximal-like bundle method.

    Mathematics Subject Classification: Primary: 90C25; Secondary: 65K05.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Test results obtained by $pc^3pa$ algorithm for $\min\limits_{x \in R^n} f_{1}(x)$

    $ n$$x^*$${\tt f_{final}}$${\tt \|g^k\|_{final}}$$ {\tt Ni}$$ {\tt Time}$
    6(-0.0000, 0.0000, -0.0000, 0.0000 0.0000, -0.0000)0.00006.62e-07131.1073
    71.0e-05(0.12, -0.12, 0.42, 0.02, -0.16, -0.02, -0.06)2.01e-053.02e-06161.596
    8(0.0000, 0.0000, 0.0000, -0.0010, -0.0004, 0.0001, 0.0001, 0.0001)4.31e-73.40e-07221.9153
    91.0e-04(0.00, 0.032, 0.00, 0.00, -0.01, 0.01, 0.02, -0.01, -0.01)1.30e-054.10e-07362.5103
    101.0e-04(0.06, -0.07, -0.09, -0.16, 0.22, 0.25, 0.03, 0.29, -0.24, -0.20)3.26e-046.25e-07361.8299
     | Show Table
    DownLoad: CSV

    Table 2.  Test results obtained by $pc^3pa$ algorithm for $\min\limits_{x \in R^n} f_{2}(x)$

    ${\tt n} $$x^*$${\tt f_{final}}$${\tt \|g^k\|_{final}}$$ {\tt Ni}$${\tt Time} $
    6(0.0000, 0.0000, 0.0000, 0.0000, 0.0000, 0.0000)0.00001.06e-07130.5323
    7(-0.0000, 0.0000, 0.0000, -0.0000, 0.0000, 0.0000, 0.0000)0.00001.03e-07101.1167
    8(-0.0000, -0.0000, -0.0000, -0.0000, -0.0000, -0.0000, -0.0000, 0.0000)0.00002.08e-08272.1463
    91.0e-05(0.01, 0.01, 0.01, 0.01, -0.02, -0.02, 0.01, 0.01, 0.02)1.37e-82.91e-07362.6105
    101.0e-06(-0.01, 0.02, -0.02, 0.02, -0.02, 0.01, -0.02, 0.02, 0.02, 0.01)4.32e-073.41e-07393.3611
     | Show Table
    DownLoad: CSV

    Table 3.  Test results obtained by $pc^3pa$ algorithm for $\min\limits_{x \in R^n} f_{3}(x)$

    ${\tt n} $$x^*$${\tt f_{final}}$${\tt \|g^k\|_{final}}$${\tt Ni} $${\tt Time} $
    6(0.0000, -0.0000, -0.0000, 0.0000, -0.0000, 0.0000)0.00003.64e-07161.0614
    7(0.0000, 0.0000, -0.0000, 0.0000, -0.0000, -0.0000, 0.0000)0.00003.02e-07191.9637
    8(0.0000, -0.0000, 0.0000, 0.0000, -0.0000, 0.0000, 0.0000, 0.0000)0.00004.01e-07261.9437
    91.0e-06(0.03, 0.03, 0.01, -0.01, 0.00, 0.00, 0.01, -0.01, -0.01)2.07e-72.14e-07332.8025
    101.0e-06(0.02, -0.02, -0.01, 0.04, -0.02, 0.04, 0.02, -0.02, -0.02, 0.01)4.30e-087.19e-08413.3061
     | Show Table
    DownLoad: CSV
  • [1] J. Baptiste, H. Urruty and C. Lemaéchal, Convex Analysis and Minimization Algorithms, Springer, Berlin, 1993.
    [2] F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer, New York, 1998.
    [3] R. Correa and C. Lemaréchal, Convergence of some algorithms for convex minimization, Math. Program., 62 (1993), 261-275.  doi: 10.1007/BF01585170.
    [4] Z. FuK. RenJ. ShuX. Sun and F. Huang, Enabling personalized search over encrypted out-sourced data with efficiency improvement, IEEE Transactions on Parallel and Distributed Systems, (2015). 
    [5] B. GuV. S. ShengK. Y. TayW. Romano and S. Li, Incremental support vector learning for ordinal regression, IEEE Transactions on Neural Networks and Learning Systems, 26 (2015), 1403-1416.  doi: 10.1109/TNNLS.2014.2342533.
    [6] B. Gu and V. S. Sheng, A robust regularization path algorithm for ν-support vector classification, IEEE Transactions on Neural Networks and Learning Systems, 28 (2017), 1241-1248.  doi: 10.1109/TNNLS.2016.2527796.
    [7] J. GuX. Xiao and L. Zhang, A subgradient-based convex approximations method for DC programming and its applications, Journal of Industrial Management Optimization, 12 (2016), 1349-1366.  doi: 10.3934/jimo.2016.12.1349.
    [8] K. C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lectures Notes in Mathematics, Springer, Berlin, 1985.
    [9] K. C. Kiwiel, Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., 46 (1990), 105-122.  doi: 10.1007/BF01585731.
    [10] K. C. Kiwiel, Efficiency of the analytic center cutting plane method for convex minimization, SIAM J. Optim., 7 (1997), 336-346.  doi: 10.1137/S1052623494275768.
    [11] K. C. Kiwiel, The efficiency of subgradient projection methods for convex optimization. Part 1: General level methods, SIAM Journal on Control and Optimization, 34 (1996), 660-676.  doi: 10.1137/0334031.
    [12] K. C. KiwielT. Larsson and P. O. Lindberg, The efficiency of ball step subgradient level methods for convex optimization, Mathematics of Operations Research, 24 (1999), 237-254.  doi: 10.1287/moor.24.1.237.
    [13] K. C. Kiwiel, Efficiency of proximal bundle methods, Journal of Optimization Theory and Applications, 104 (2000), 589-603.  doi: 10.1023/A:1004689609425.
    [14] J. LiX. LiB. Yang and X. Sun, Segmentation-based image copy-move forgery detection scheme, IEEE Transactions on Information Forensics and Security, 10 (2015), 507-518. 
    [15] E. S. Mistakidis and G. E. Stavroulakis, Nonconvex Optimization in Mechanics. Smooth and Nonsmooth Algorithms, Heuristics and Engineering Applications, F. E. M. Kluwer Academic Publisher, Dordrecht, 1998.
    [16] J. J. Moreau, P. D. Panagiotopoulos and G. Strang (Eds. ), Topics in Nonsmooth Mechanics, Birkhäuser Verlag, Basel, 1988.
    [17] A. Ouorou, A proximal cutting plane method using Chebychev center for nonsmooth convex optimization, Math. Program. Ser. A, 119 (2009), 239-271.  doi: 10.1007/s10107-008-0209-x.
    [18] J. Outrata, M. Kočvara and J. Zowe, Nonsmooth Approach to Optimization Problems With Equilibrium Constraints. Theory, Applications and Numerical Results, Kluwer Academic Publishers, Dordrecht, 1998.
    [19] Z. PanY. Zhang and S. Kwong, Efficient motion and disparity estimation optimization for low complexity multiview video coding, IEEE Transactions on Broadcasting, 61 (2015), 166-176. 
    [20] H. Schramm and J. Zowe, A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim., 2 (1992), 121-152.  doi: 10.1137/0802008.
    [21] J. Shen, D. Li and L. Pang, A cutting plane and level stabilization bundle method with inexact data for minimizing nonsmooth nonconvex functions, Abstract and Applied Analysis, 2014 (2014), Article ID 192893, 6pp.
    [22] J. Shen and L. Pang, An approximate bundle-type auxiliary problem method for generalized variational inequality, Mathematical and Computer Modeling, 48 (2008), 769-775.  doi: 10.1016/j.mcm.2007.11.005.
    [23] J. Shen, X. Liu, F. Guo and S. Wang, An approximate redistributed proximal bundle method with inexact data for minimizing nonsmooth nonconvex functions, Mathematical Problems in Engineering, 2015 (2015), Article ID 215310, 9pp.
    [24] J. ShenZ. Xia and L. Pang, A proximal bundle method with inexact data for convex nondifferentiable minimization, Nonlinear Analysis A : theory, method and applications, 66 (2007), 2016-2027.  doi: 10.1016/j.na.2006.02.039.
    [25] K. WangL. Xu and D. Han, A new parallel splitting descent method for structured variational inequalities, Journal of Industrial Management Optimization, 10 (2014), 461-476. 
    [26] Z. XiaX. WangX. Sun and Q. Wang, A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data, IEEE Transactions on Parallel and Distributed Systems, 27 (2016), 340-352.  doi: 10.1109/TPDS.2015.2401003.
    [27] G. YuanZ. Wei and G. Li, A modified Polak-Ribiére-Polyak conjugate gradient algorithm for nonsmooth convex programs, Journal of Computational and Applied Mathematics, 255 (2014), 86-96.  doi: 10.1016/j.cam.2013.04.032.
    [28] G. YuanZ. Meng and Y. Li, A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, Journal of Optimization Theory and Applications, 168 (2016), 129-152.  doi: 10.1007/s10957-015-0781-1.
    [29] G. Yuan and M. Zhang, A three-terms Polak-Ribiére-Polyak conjugate gradient algorithm for large-scale nonlinear equations, Journal of Computational and Applied Mathematics, 286 (2015), 186-195.  doi: 10.1016/j.cam.2015.03.014.
    [30] J. ZhangY. Li and L. Zhang, On the coderivative of the solution mapping to a second-order cone constrained parametric variational inequality, Journal of Global Optimization, 61 (2015), 379-396.  doi: 10.1007/s10898-014-0181-3.
    [31] J. ZhangS. Lin and L. Zhang, A log-exponential regularization method for a mathmatical program with general vertical complementarity constraints, Journal of Industrial Management Optimization, 9 (2013), 561-577.  doi: 10.3934/jimo.2013.9.561.
  • 加载中



Article Metrics

HTML views(1663) PDF downloads(268) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint