An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint

DOI10.1016/0377-2217(86)90304-8MaRDI QIDQ1069860zbMATH OpenOpenAlexFDO

Authors K. M. Mjelde

Publication date 1986

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(86)90304-8

zbMATH Keywords

incremental algorithmparametrical algorithmratio of a concave function to a convex functionresource allocationsingle convex constraint function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Sensitivity, stability, parametric optimization (90C31) Fractional programming (90C32)

Review text

A problem of the maximization of the ratio of a concave function to a convex function is considered, subject to an upper bound on a single convex constraint function; all these functions are assumed to be differentiable. An incremental algorithm is defined, which solves the problem parametrically for different values of the constraint function by the solution of a set of ordinary first order differential equations. If K is the number of variables in the problem and B(K) is an upper bound - dependent of K - of the time needed to evaluate any function value or any first or second order derivative, the complexity of the algorithm is of the order \(O[(B(K)K+K)a]\), where a is the number of integration steps applied in the solution of the differential equations. In particular, a cost-effectiveness resource allocation problem with separable functions is solved numerically in a time of the order O[Ka] if B(K) is independent of K; an example of such a problem is given with analytically solvable differential equations.

Recommendations

• An algorithm for generalized fractional programs
• An efficient algorithm for solving convex-convex quadratic fractional programs
• Fractional Programming
• On Maximizing a Sum of Ratios
• Publication:3200903

Cites work

• Allocation of resources according to a fractional objective
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Einzelschrittverfahren zur Lösung konvexer und dual‐konvexer Minimierungsprobleme
• Fractional programming
• scientific article; zbMATH DE number 3848997 (Why is no real title available?)
• scientific article; zbMATH DE number 3807359 (Why is no real title available?)
• scientific article; zbMATH DE number 3308846 (Why is no real title available?)
• scientific article; zbMATH DE number 3417267 (Why is no real title available?)
• On Nonlinear Fractional Programming
• Parallelism in Comparison Problems

Cited in

(3)

• Minisymposium 2 : Optimierung
• A Fourth bibliography of fractional programming
• An efficient algorithm for solving convex-convex quadratic fractional programs

This page was built for publication: An incremental and parametrical algorithm for convex-concave fractional programming with a single constraint

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