GNCGCP - Graduated NonConvexity and Graduated Concavity Procedure
In this paper we propose the Graduated NonConvexity and Graduated Concavity Procedure (GNCGCP) as a general optimization framework to approximately solve the combinatorial optimization problems on the set of partial permutation matrices. GNCGCP comprises two sub-procedures, graduated nonconvexity (GNC) which realizes a convex relaxation and graduated concavity (GC) which realizes a concave relaxation. It is proved that GNCGCP realizes exactly a type of convex-concave relaxation procedure (CCRP), but with a much simpler formulation without needing convex or concave relaxation in an explicit way. Actually, GNCGCP involves only the gradient of the objective function and is therefore very easy to use in practical applications. Two typical NP-hard problems, (sub)graph matching and quadratic assignment problem (QAP), are employed to demonstrate its simplicity and state-of-the-art performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationGraph MatchingSimilar Papers 제목 키워드 기반
A Weighted Common Subgraph Matching Algorithm
We propose a weighted common subgraph (WCS) matching algorithm to find the most similar subgraphs in two labeled weighted graphs. WCS matching, as a natural generalization of the equal-sized graph matching or subgraph ma…
Combinatorial OptimizationGraph MatchingExplicit and Implicit Graduated Optimization in Deep Neural Networks
Graduated optimization is a global optimization technique that is used to minimize a multimodal nonconvex function by smoothing the objective function with noise and gradually refining the solution. This paper experiment…
global-optimizationimage-classificationImage ClassificationSchedulingConvergence Properties of Score-Based Models for Linear Inverse Problems Using Graduated Optimisation
The incorporation of generative models as regularisers within variational formulations for inverse problems has proven effective across numerous image reconstruction tasks. However, the resulting optimisation problem is …
Image ReconstructionLearning Gradually Non-convex Image Priors Using Score Matching
In this paper, we propose a unified framework of denoising score-based models in the context of graduated non-convex energy minimization. We show that for sufficiently large noise variance, the associated negative log de…
DenoisingUsing Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization
The graduated optimization approach is a method for finding global optimal solutions for nonconvex functions by using a function smoothing operation with stochastic noise. We show that stochastic noise in stochastic grad…
image-classificationImage ClassificationScheduling