Non-smoothness in classification problems

References

• Astorino , A. and Fuduli , A. 2007 . Non-smooth optimization techniques for semisupervised classification . IEEE Trans. Pattern Anal. Mach. Intell. , 29 : 2135 – 2142 .
   PubMed Web of Science ®Google Scholar
• Astorino , A. and Gaudioso , M. 2002 . Polyhedral separability through successive LP . J. Optim. Theory Appl. , 112 : 265 – 293 .
   Web of Science ®Google Scholar
• Astorino , A. and Gaudioso , M. 2005 . Ellipsoidal separation for classification problems . Optim. Methods Softw. , 20 : 261 – 270 .
   Google Scholar
• Astorino , A. , Fuduli , A. and Gaudioso , M. 1997 . “ Analysis of regularization techniques in convex non-differentiable optimization ” . In Operations Research Proceedings 1996 20 – 25 . Berlin, Heidelberg
   Google Scholar
• Bagirov , A. M. 1999 . Derivative-free methods for unconstrained non-smooth optimization and its numerical analysis . Investigacao Operacional , 19 : 75 – 93 .
   Google Scholar
• Bagirov , A. M. 1999 . “ Minimization methods for one class of nonsmooth functions and calculation of semi-equilibrium prices ” . In Progress in Optimization: Contribution from Australasia , Edited by: Eberhard , A. 147 – 175 . Kluwer Academic Publishers .
   Google Scholar
• Bagirov , A. M. 2003 . Continuous subdifferential approximations and their applications . J. Math. Sci. , 115 : 2567 – 2609 .
   Google Scholar
• Bagirov , A. M. 2005 . Max-min separability . Optim. Methods Softw. , 20 : 271 – 290 .
   Web of Science ®Google Scholar
• Bagirov , A. M. and Yearwood , J. 2006 . A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems . Eur. J. Oper. Res , 270 : 578 – 596 .
   Google Scholar
• Bagirov , A. M. , Rubinov , A. and Yearwood , J. 2002 . A global optimization approach to classification . Optim. Eng. , 3 : 129 – 155 .
   Web of Science ®Google Scholar
• Bagirov , A. M. , Ferguson , B. , Ivkovic , S. , Saunders , G. and Yearwood , J. 2003 . New algorithms for multi-class cancer diagnosis using tumor gene expression signatures . Bioinformatics , 19 : 1800 – 1807 .
   PubMed Web of Science ®Google Scholar
• Bagirov , A. M. , Rubinov , A. M. , Soukhoroukova , N. and Yearwood , J. 2003 . Unsupervised and supervised data classification via nonsmooth and global optimization . TOP , 11 : 1 – 75 .
   Google Scholar
• Bagirov , A. M. , Karasözen , B. and Sezer , M. 2008 . Discrete gradient method: derivative-free method for nonsmooth optimization . J. Optim. Theory Appl. , 137 : 317 – 334 .
   Web of Science ®Google Scholar
• Bennett , K. P. and Demiriz , A. 1998 . “ Semi-supervised support vector machines ” . In Advances in Neural Information Processing Systems , Edited by: Kearns , M. S. , Solla , S. A. and Cohn , D. A. Vol. 12 , 368 – 374 . Cambridge, MA : MIT Press .
   Google Scholar
• Bennett , K. P. and Mangasarian , O. L. 1992 . Robust linear programming discrimination of two linearly inseparable sets . Optim. Meth. Softw. , 1 : 23 – 34 .
   Google Scholar
• Bennett , K. P. and Parrado-Hernández , E. 2006 . The interplay of optimization and machine learning research . J. Mach. Learn. Res , 7 : 1265 – 1281 .
   Web of Science ®Google Scholar
• Bertsekas , D. P. 1975 . Nondifferentiable optimization via approximation . Math. Program. Study , 3 : 1 – 25 .
   Google Scholar
• Bonnans , J. F. , Gilbert , J. C. , Lemaréchal , C. and Sagastizábal , C. A. 1995 . A family of variable metric proximal methods . Math. Program , 68 : 15 – 47 .
   Web of Science ®Google Scholar
• Brännlund , U. , Kiwiel , K. C. and Lindberg , P. O. 1995 . A descent proximal level bundle method for convex nondifferentiable optimization . Oper. Res. Lett. , 17 : 121 – 126 .
   Web of Science ®Google Scholar
• Burke , J. V. , Lewis , A. S. and Overton , M. L. 2005 . A robust gradient sampling algorithm for nonsmooth, nonconvex optimization . SIAM J. Optim. , 15 : 751 – 779 .
   Web of Science ®Google Scholar
• Cappanera , P. and Frangioni , A. 2003 . Symmetric and asymmetric parallelization of a cost-decomposition algorithm for multicommodity flow problems . INFORMS J. Comput. , 15 : 369 – 384 .
   Web of Science ®Google Scholar
• Chapelle , O. and Zien , A. Semi-supervised classification by low density separation . Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics . pp. 57 – 64 .
   Google Scholar
• Charalambous , C. and Bandler , J. 1976 . Non-linear minimax optimization as a sequence of least p-th optimization with finite values of p . Int. J. Syst. Sci. , 7 : 377 – 391 .
   Web of Science ®Google Scholar
• Chen , X. and Fukushima , M. 1999 . Proximal quasi-Newton methods for nondifferentiable convex optimization . Math. Program , 85 : 313 – 334 .
   Web of Science ®Google Scholar
• Clarke , F. H. 1983 . Optimization and nonsmooth analysis , John Wiley and Sons .
   Google Scholar
• Collobert , R. , Sinz , F. , Weston , J. and Bottou , L. Trading convexity for scalability . ICML 2006 - Proceedings of the 23rd International Conference on Machine Learning . pp. 201 – 208 .
   Google Scholar
• Cristianini , N. and Shawe-Taylor , J. 2000 . An introduction to support vector machines and other kernel-based learning methods , Cambridge University Press .
   Google Scholar
• De Leone , R. , Gaudioso , M. and Monaco , M. F. 1993 . Nonsmooth optimization methods for parallel decomposition of multicommodity flow problems . Ann. Oper. Res. , 44 : 299 – 311 .
   Google Scholar
• Demyanov , V. F. 2005 . Mathematical diagnostics via nonsmooth analysis . Optim. Meth. Softw. , 20 : 197 – 218 .
   Web of Science ®Google Scholar
• Demyanov , A. V. and Gaudioso , M. 2005 . An approach to classification based on separation of sets by means of several ellipsoids . Optimization , 54 : 579 – 593 .
   Web of Science ®Google Scholar
• Demyanov , V. F. , Astorino , A. and Gaudioso , M. 2001 . Nonsmooth problems in mathematical diagnostics, Advances in Convex Analysis and Global Optimization , Vol. 54 , 11 – 30 . Dordrecht : Kluwer Academic Publisher . Nonconvex Optimization and its Applications
   Google Scholar
• Ferris , M. C. and Horn , J. D. 1998 . Partitioning mathematical problems for parallel solution . Math. Program , 80 : 35 – 61 .
   Google Scholar
• Frangioni , A. 2002 . Generalized bundle methods . SIAM J. Optim. , 13 : 117 – 156 .
   Web of Science ®Google Scholar
• Frangioni , A. and Gallo , G. 1999 . A bundle type dual-ascent approach to linear multicommodity min cost flow problems . INFORMS J. Comput. , 11 : 370 – 393 .
   Web of Science ®Google Scholar
• Fuduli , A. and Gaudioso , M. 2000 . Fixed and virtual stability center methods for convex nonsmooth minimization, Nonlinear Optimization and Applications 2 , Edited by: Di Pillo , G. and Giannessi , F. 105 – 122 . Kluwer Academic Publishers .
   Google Scholar
• Fuduli , A. and Gaudioso , M. 2006 . Tuning strategy for the proximity parameter in convex minimization . J. Optim. Theory Appl. , 130 : 95 – 112 .
   Web of Science ®Google Scholar
• Fuduli , A. , Gaudioso , M. and Giallombardo , G. 2004 . A DC piecewise affine model and bundling technique in nonconvex nonsmooth minimization . Optim. Meth. Softw. , 18 : 89 – 102 .
   Google Scholar
• Fuduli , A. , Gaudioso , M. and Giallombardo , G. 2004 . Minimizing nonconvex nonsmooth functions via cutting planes and proximity control . SIAM J. Optim. , 14 : 743 – 756 .
   Web of Science ®Google Scholar
• Fukushima , M. 1984 . A descent algorithm for nonsmooth convex optimization . Math. Program , 30 : 163 – 175 .
   Web of Science ®Google Scholar
• Fukushima , M. and Qi , L. 1996 . A globally and superlinearly convergent algorithm for nonsmooth convex minimization . SIAM J. Optim. , 6 : 1106 – 1120 .
   Web of Science ®Google Scholar
• Fung , G. and Mangasarian , O. L. 2001 . Semi-supervised support vector machines for unlabeled data classification . Optim. Meth. Softw. , 15 : 29 – 44 .
   Web of Science ®Google Scholar
• Gasimov , R. N. and Ozturk , G. Polyhedral separability through nonlinear programming . 35th International Conference on Computers and Industrial Engineering . June , Istanbul, Turkey. pp. 763 – 768 .
   Google Scholar
• Gasimov , R. N. and Ozturk , G. 2006 . Separation via polyhedral conic functions . Optim. Meth. Softw. , 21 : 527 – 540 .
   Web of Science ®Google Scholar
• Gaudioso , M. 2002 . “ Nonsmooth optimization ” . In Handbook of Applied Optimization , Edited by: Resende , M. G.C. and Pardalos , P. M. 299 – 310 . New York : Oxford University Press .
   Google Scholar
• Gaudioso , M. and Monaco , M. F. 1982 . A bundle type approach to the unconstrained minimization of convex nonsmooth functions . Math. Program , 23 : 216 – 223 .
   Web of Science ®Google Scholar
• Gaudioso , M. and Monaco , M. F. 1991 . Quadratic approximations in convex nondifferentiable optimization . SIAM J. Control Optim. , 29 : 1 – 10 .
   Google Scholar
• Gaudioso , M. and Monaco , M. F. 1992 . Variants to the cutting plane approach for convex non-differentiable optimization . Optimization , 25 : 65 – 72 .
   Google Scholar
• Guignard , M. 2003 . Lagrangean relaxation . TOP , 11 : 151 – 228 .
   Google Scholar
• Hiriart-Urruty , J. B. and Lemaréchal , C. 1993 . Convex analysis and minimization algorithms Vols. I and II , Springer-Verlag .
   Google Scholar
• Joachims , T. Transductive inference for text classification using support vector machines . International Conference on Machine Learning . pp. 200 – 209 .
   Google Scholar
• Kiwiel , K. C. 1985 . “ Methods of descent for nondifferentiable optimization ” . In Lecture Notes in Mathematics , Vol. 1133 , Springer-Verlag .
   Google Scholar
• Kiwiel , K. C. 1990 . Proximity control in bundle methods for convex nondifferentiable minimization . Math. Program , 46 : 105 – 122 .
   Web of Science ®Google Scholar
• Kiwiel , K. C. 1991 . A tilted cutting plane proximal bundle method for convex nondifferentiable optimization . Oper. Res. Lett. , 10 : 75 – 81 .
   Web of Science ®Google Scholar
• Kiwiel , K. C. 1995 . Proximal level bundle methods for convex nondifferentiable optimization, saddle point problems and variational inequalities . Math. Program , 69 : 89 – 109 .
   Web of Science ®Google Scholar
• Kiwiel , K. C. 1999 . A bundle Bregman proximal method for convex nondifferentiable minimization . Math. Program , 85 : 241 – 258 .
   Web of Science ®Google Scholar
• Kiwiel , K. C. 2000 . Efficiency of proximal bundle methods . J. Optim. Theory Appl. , 104 : 589 – 603 .
   Web of Science ®Google Scholar
• Lemaréchal , C. An algorithm for minimizing convex functions . Proceedings IFIP ’74 Congress 17 . North-Holland, Amsterdam. Edited by: Rosenfeld , J. L. pp. 552 – 556 .
   Google Scholar
• Lemaréchal , C. 1975 . “ An extension of Davidon methods to nondifferentiable problems ” . In Nondifferentiable Optimization , Edited by: Balinski , M. and Wolfe , P. Vol. 3 , 145 – 173 . North-Holland, Amsterdam : Mathematical Programming Study .
   Google Scholar
• Lemaréchal , C. and Sagastizábal , C. A. 1997 . Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries . SIAM J. Optim. , 7 : 367 – 385 .
   Web of Science ®Google Scholar
• Lemaréchal , C. and Sagastizábal , C. A. 1997 . Variable metric bundle methods: from conceptual to implementable form . Math. Program , 76 : 393 – 410 .
   Web of Science ®Google Scholar
• Lemaréchal , C. , Nemirovskij , A. and Nesterov , Y. 1995 . New variants of bundle methods . Math. Program , 69 : 111 – 147 .
   Web of Science ®Google Scholar
• Lemaréchal , C. , Oustry , F. and Sagastizábal , C. A. 2000 . The 𝒰-Lagrangian of a convex function . Trans. Amer. Math. Soc. , 352 : 711 – 729 .
   Web of Science ®Google Scholar
• Mäkelä , M. 2002 . Survey of bundle methods for nonsmooth optimization . Optim. Methods Softw. , 17 : 1 – 29 .
   Web of Science ®Google Scholar
• Mäkelä , M. and Neittaanmäki , P. 1992 . Nonsmooth optimization: analysis and algorithms with applications to optimal control , World Scientific .
   Google Scholar
• Mangasarian , O. L. 1965 . Linear and nonlinear separation of patterns by linear programming . Oper. Res. , 13 : 444 – 452 .
   Web of Science ®Google Scholar
• Medhi , D. 1990 . Parallel bundle-based decomposition for large-scale structured mathematical programming problems . Ann. Oper. Res. , 22 : 101 – 127 .
   Google Scholar
• Megiddo , N. 1988 . On the complexity of polyhedral separability . Discrete Comput. Geom , 3 : 325 – 337 .
   Web of Science ®Google Scholar
• Mifflin , R. 1982 . A modification and an extension of Lemaréchal's algorithm for nonsmooth minimization , Vol. 17 , 77 – 90 . North-Holland, Amsterdam : Mathematical Programming Study .
   Google Scholar
• Mifflin , R. 1996 . A quasi-second-order proximal bundle algorithm . Math. Program , 73 : 51 – 72 .
   Web of Science ®Google Scholar
• Mifflin , R. and Sagastizábal , C. A. 2000 . On -theory for functions with primal-dual gradient structure . SIAM J. Optim. , 11 : 547 – 571 .
   Web of Science ®Google Scholar
• Mifflin , R. and Sagastizábal , C. A. 2004 . -smoothness and proximal point results for some nonconvex functions . Optim. Methods Softw. , 19 : 463 – 478 .
   Web of Science ®Google Scholar
• Mifflin , R. and Sagastizábal , C. A. 2005 . A -algorithm for convex minimization . Math. Program , 104 : 583 – 608 .
   Web of Science ®Google Scholar
• Mifflin , R. , Sun , D. and Qi , L. 1998 . Quasi-Newton bundle-type methods for nondifferentiable convex optimization . SIAM J. Optim. , 8 : 583 – 603 .
   Web of Science ®Google Scholar
• Mistakidis , E. and Stavroulakis , G. 1998 . “ Nonconvex optimization in mechanics. Smooth and nonsmooth algorithms, heuristics and engineering applications by the F.E.M. ” . In Nonconvex Optimization and its Applications , Vol. 21 , Kluwer Academic Publishers .
   Google Scholar
• Nesterov , Y. 2005 . Smooth minimization of non-smooth functions . Math. Program , 103 : 127 – 152 .
   Web of Science ®Google Scholar
• Orsenigo , C. and Vercellis , C. 2007 . Accurately learning from few examples with a polyhedral classifier . Comput. Optim. Appl. , 38 : 235 – 247 .
   Google Scholar
• Outrata , J. , Kočvara , M. and Zowe , J. 1998 . “ Nonsmooth approach to optimization problems with equilibrium constraints. Theory, applications and numerical results ” . In Nonconvex Optimization and its Applications , Vol. 28 , Kluwer Academic Publishers .
   Google Scholar
• Polak , E. , Royset , J. O. and Womersley , R. S. 2003 . Algorithms with adaptive smoothing for finite minimax problems . J. Optim. Theory Appl. , 119 : 459 – 484 .
   Web of Science ®Google Scholar
• Qi , L. 1994 . “ Second-order analysis of the Moreau-Yosida regularization of a convex function ” . In Tech. Rep. AMR 94/20 , University of New South Wales .
   Google Scholar
• Qi , L. and Chen , X. 1997 . A preconditioning proximal Newton method for nondifferentiable convex optimization . Math. Program , 76 : 411 – 429 .
   Web of Science ®Google Scholar
• Rauf , A. and Fukushima , M. 1998 . Globally convergent BFGS method for nonsmooth convex optimization . J. Optim. Theory Appl. , 104 : 539 – 558 .
   Google Scholar
• Rockafellar , R. 1976 . Monotone operators and the proximal point algorithm . SIAM J. Control Optim. , 14 : 877 – 898 .
   Web of Science ®Google Scholar
• Rosen , J. B. 1965 . Pattern separation by convex programming . J. Math. Anal. Appl. , 10 : 123 – 134 .
   Google Scholar
• Schölkopf , B. , Burges , C. J.C. and Smola , A. J. 1999 . Advances in kernel methods. Support vector learning , Cambridge, MA : MIT Press .
   Google Scholar
• Schramm , H. and Zowe , J. 1992 . A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis . SIAM J. Optim. , 1 : 121 – 152 .
   Google Scholar
• Shawe-Taylor , J. and Cristianini , N. 2004 . Kernel methods for pattern analysis , Cambridge University Press .
   Google Scholar
• Shor , N. 1985 . Minimization methods for non-differentiable functions , Berlin : Springer-Verlag .
   Google Scholar
• Sun , P. and Freund , R. M. 2004 . Computation of minimum-volume covering ellipsoids . Oper. Res. , 52 : 690 – 706 .
   Web of Science ®Google Scholar
• Tardella , F. 1999 . “ Piecewise concavity and discrete approaches to continuous minmax problems ” . In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems , Edited by: Pardalos , P. M. Kluwer Academic Publishers .
   Google Scholar
• Vandenberghe , L. and Boyd , S. 1996 . Semidefinite programming . SIAM Rev. , 38 : 49 – 95 .
   Web of Science ®Google Scholar
• L. Vandenberghe, S. Boyd, and B. Alkire, http://www.ee.ucla.edu/∼vandenbe/sp.html [accessed 12 September 2007]
   Google Scholar
• Vapnik , V. 1995 . The nature of the statistical learning theory , New York : Springer-Verlag .
   Google Scholar
• Wolfe , P. 1975 . A method of conjugate subgradients for minimizing nondifferentiable functions, Nondifferentiable Optimization Edited by: Balinski , M. L. and Wolfe , P. Vol. 3 , 145 – 173 . North-Holland, Amsterdam Mathematical Programming Study
   Google Scholar
• Yagiura , M. and Ibaraki , T. 2002 . “ Local search ” . In Handbook of Applied Optimization , Edited by: Pardalos , P. M. and Resende , M. G.C. 104 – 123 . Oxford University Press .
   Google Scholar