Scaling, proximity, and optimization of integrally convex functions
From MaRDI portal
Publication:2414902
DOI10.1007/S10107-018-1234-ZzbMATH Open1421.90129arXiv1703.10705OpenAlexW2963240754MaRDI QIDQ2414902FDOQ2414902
Akihisa Tamura, Fabio Tardella, Kazuo Murota, Satoko Moriguchi
Publication date: 17 May 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: In discrete convex analysis, the scaling and proximity properties for the class of L-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of variables, we show here that the scaling property only holds when , while a proximity theorem can be established for any , but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.
Full work available at URL: https://arxiv.org/abs/1703.10705
Recommendations
- Scaling and proximity properties of integrally convex functions
- Approximating optimization problems over convex functions
- Proximal determination of convex functions
- Nonlinear rescaling and proximal-like methods in convex optimization
- Publication:4733687
- Optimal algorithms for integrating convex functions
- Optimization of Schur-convex functions
- scientific article; zbMATH DE number 554968
- Publication:4715190
- On approximate solutions in vector optimization problems via scalarization
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Discrete Convex Analysis
- Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Discrete fixed point analysis and its applications
- Title not available (Why is that?)
- Recent Developments in Discrete Convex Analysis
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- Discrete fixed point theorem reconsidered
- Convex separable optimization is not much harder than linear optimization
- Discrete convex analysis
- Complexity and algorithms for nonlinear optimization problems
- Notes on L-/M-convex functions and the separation theorems
- On the Solutions of Discrete Nonlinear Complementarity and Related Problems
- Solving discrete systems of nonlinear equations
- Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Title not available (Why is that?)
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- M-Convex Function Minimization by Continuous Relaxation Approach: Proximity Theorem and Algorithm
- L-CONVEXITY ON GRAPH STRUCTURES
- Discrete modeling of economic equilibrium problems
- Discrete L-convex function minimization based on continuous relaxation
- Coordinatewise domain scaling algorithm for M-convex function minimization
- A capacity scaling algorithm for M-convex submodular flow
- Proximity theorems of discrete convex functions
- Discrete Midpoint Convexity
Cited In (11)
- Projection and convolution operations for integrally convex functions
- Integrality of subgradients and biconjugates of integrally convex functions
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- Directed discrete midpoint convexity
- Recent progress on integrally convex functions
- On basic operations related to network induction of discrete convex functions
- Optimal scaling for p-norms and componentwise distance to singularity
- A survey of fundamental operations on discrete convex functions of various kinds
- Discrete 2-convex functions
- Discrete Midpoint Convexity
- Title not available (Why is that?)
This page was built for publication: Scaling, proximity, and optimization of integrally convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414902)
