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

Jie Shen; Jian Lv; Fang-Fang Guo; Ya-Li Gao; Rui Zhao

doi:10.3934/jimo.2018003

Article Contents

2018, Volume 14, Issue 3: 1143-1155. Doi: 10.3934/jimo.2018003

This issue Previous Article Modeling and analyzing the chaotic behavior in supply chain networks: a control theoretic approach Next Article Solving the interval-valued optimization problems based on the concept of null set

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

1.
School of Mathematics, Liaoning Normal University, Dalian, 116029, China
2.
School of Finance, Zhejiang University of Finance and Economics, Hangzhou, 310018, China
3.
School of Mathematical Sciences, Dalian University of Technology, Dalian, 116024, China

* Corresponding author: Jie Shen
* Corresponding author: Jie Shen

Received: April 2016

Revised: August 2017

Early access: January 2018

Published: June 2018

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

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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.0000	6.62e-07	13	1.1073
7	1.0e-05(0.12, -0.12, 0.42, 0.02, -0.16, -0.02, -0.06)	2.01e-05	3.02e-06	16	1.596
8	(0.0000, 0.0000, 0.0000, -0.0010, -0.0004, 0.0001, 0.0001, 0.0001)	4.31e-7	3.40e-07	22	1.9153
9	1.0e-04(0.00, 0.032, 0.00, 0.00, -0.01, 0.01, 0.02, -0.01, -0.01)	1.30e-05	4.10e-07	36	2.5103
10	1.0e-04(0.06, -0.07, -0.09, -0.16, 0.22, 0.25, 0.03, 0.29, -0.24, -0.20)	3.26e-04	6.25e-07	36	1.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.0000	1.06e-07	13	0.5323
7	(-0.0000, 0.0000, 0.0000, -0.0000, 0.0000, 0.0000, 0.0000)	0.0000	1.03e-07	10	1.1167
8	(-0.0000, -0.0000, -0.0000, -0.0000, -0.0000, -0.0000, -0.0000, 0.0000)	0.0000	2.08e-08	27	2.1463
9	1.0e-05(0.01, 0.01, 0.01, 0.01, -0.02, -0.02, 0.01, 0.01, 0.02)	1.37e-8	2.91e-07	36	2.6105
10	1.0e-06(-0.01, 0.02, -0.02, 0.02, -0.02, 0.01, -0.02, 0.02, 0.02, 0.01)	4.32e-07	3.41e-07	39	3.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.0000	3.64e-07	16	1.0614
7	(0.0000, 0.0000, -0.0000, 0.0000, -0.0000, -0.0000, 0.0000)	0.0000	3.02e-07	19	1.9637
8	(0.0000, -0.0000, 0.0000, 0.0000, -0.0000, 0.0000, 0.0000, 0.0000)	0.0000	4.01e-07	26	1.9437
9	1.0e-06(0.03, 0.03, 0.01, -0.01, 0.00, 0.00, 0.01, -0.01, -0.01)	2.07e-7	2.14e-07	33	2.8025
10	1.0e-06(0.02, -0.02, -0.01, 0.04, -0.02, 0.04, 0.02, -0.02, -0.02, 0.01)	4.30e-08	7.19e-08	41	3.3061

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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. Fu, K. Ren, J. Shu, X. 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. Gu, V. S. Sheng, K. Y. Tay, W. 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. Gu, X. 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. Kiwiel, T. 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. Li, X. Li, B. 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. Pan, Y. 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. Shen, Z. 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. Wang, L. 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. Xia, X. Wang, X. 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. Yuan, Z. 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. Yuan, Z. 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. Zhang, Y. 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. Zhang, S. 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.