Scaling, proximity, and optimization of integrally convex functions
From MaRDI portal
Publication:2414902
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.
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
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 1789203 (Why is no real title available?)
- A capacity scaling algorithm for M-convex submodular flow
- A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks
- Bimonotone linear inequalities and sublattices of \(\mathbb R^n\)
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- Complexity and algorithms for nonlinear optimization problems
- Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
- Convex separable optimization is not much harder than linear optimization
- Coordinatewise domain scaling algorithm for M-convex function minimization
- Discrete Convex Analysis
- Discrete L-convex function minimization based on continuous relaxation
- Discrete convex analysis
- Discrete fixed point analysis and its applications
- Discrete fixed point theorem reconsidered
- Discrete midpoint convexity
- Discrete modeling of economic equilibrium problems
- Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- 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
- Network flows. Theory, algorithms, and applications.
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- Notes on L-/M-convex functions and the separation theorems
- On the solutions of discrete nonlinear complementarity and related problems
- Proximity theorems of discrete convex functions
- Recent developments in discrete convex analysis
- Solving discrete systems of nonlinear equations
- \(L\)-convexity on graph structures
Cited in
(12)- Scaling and proximity properties of integrally convex functions
- Integrality of subgradients and biconjugates of integrally convex functions
- On basic operations related to network induction of discrete convex functions
- Discrete 2-convex functions
- Projection and convolution operations for integrally convex functions
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- Directed discrete midpoint convexity
- Discrete midpoint convexity
- Optimal scaling for p-norms and componentwise distance to singularity
- scientific article; zbMATH DE number 2086911 (Why is no real title available?)
- A survey of fundamental operations on discrete convex functions of various kinds
- Recent progress on integrally convex functions
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)
