Nesterov's smoothing technique and minimizing differences of convex functions for hierarchical clustering

DOI10.1007/S11590-017-1183-0MaRDI QIDQ1749775zbMATH OpenOpenAlexFDO

Authors W. Geremew, S. Reynolds, T. Tran, Nguyen Mau Nam

Publication date 28 May 2018

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.04464, https://pdxscholar.library.pdx.edu/cgi/viewcontent.cgi?article=1172&context=mth_fac

zbMATH Keywords

DC programmingFenchel conjugatehierarchical clusteringNesterov's smoothing techniquesubgradient

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: A bilevel hierarchical clustering model is commonly used in designing optimal multicast networks. In this paper, we consider two different formulations of the bilevel hierarchical clustering problem, a discrete optimization problem which can be shown to be NP-hard. Our approach is to reformulate the problem as a continuous optimization problem by making some relaxations on the discreteness conditions. Then Nesterov's smoothing technique and a numerical algorithm for minimizing differences of convex functions called the DCA are applied to cope with the nonsmoothness and nonconvexity of the problem. Numerical examples are provided to illustrate our method.

Recommendations

• A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique
• Optimization based DC programming and DCA for hierarchical clustering
• Clustering via d. c. optimization.
• The hyperbolic smoothing clustering method
• A DC optimization approach for constrained clustering with _1-norm

Cites work

• A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
• A heuristic algorithm for solving the minimum sum-of-squares clustering problems
• A new efficient algorithm based on DC programming and DCA for clustering
• Convex Analysis
• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 3465097 (Why is no real title available?)
• Minimizing differences of convex functions with applications to facility location and clustering
• Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems
• On functions representable as a difference of convex functions
• Optimization based DC programming and DCA for hierarchical clustering
• Smooth minimization of non-smooth functions
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(10)

• A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique
• Minimax D-optimal designs for multivariate regression models with multi-factors
• The hyperbolic smoothing clustering method
• The boosted DC algorithm for linearly constrained DC programming
• Clustering and multifacility location with constraints via distance function penalty methods and DC programming
• Solving a continuous multifacility location problem by DC algorithms
• The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions
• A DC optimization approach for constrained clustering with _1-norm
• A boosted DC algorithm for non-differentiable DC components with non-monotone line search
• An inexact boosted difference of convex algorithm for nondifferentiable functions

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Nesterov's smoothing technique and minimizing differences of convex functions for hierarchical clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749775)