\(NP\)-hardness of linear multiplicative programming and related problems

DOI10.1007/BF00121658zbMath0868.90111OpenAlexW2078340238MaRDI QIDQ2564608

Yanyan Li

Publication date: 15 January 1997

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00121658

zbMATH Keywords

linear inequality constraintslinear fractional programminglinear multiplicative programmingNP-hardnessmulti-ratio programming

Mathematics Subject Classification ID

Nonlinear programming (90C30) Fractional programming (90C32)

Related Items

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, Solving a class of generalized fractional programming problems using the feasibility of linear programs, Regional division and reduction algorithm for minimizing the sum of linear fractional functions, A new Lagrangian-Benders approach for a concave cost supply chain network design problem, Theoretical and computational results about optimality-based domain reductions, A fifth bibliography of fractional programming^*, Incorporating monitoring technology and on-site inspections into an \(n\)-person inspection game, A simplicial branch and bound duality-bounds algorithm to linear multiplicative programming, Robust Network Design with Uncertain Outsourcing Cost, A FPTAS for a class of linear multiplicative problems, An outcome-space finite algorithm for solving linear multiplicative programming, Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations, Data separation via a finite number of discriminant functions: a global optimization approach, Minimizing a linear multiplicative-type function under network flow constraints, Multiplicative programming problems: Analysis and efficient point search heuristic, Intersection Disjunctions for Reverse Convex Sets, A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity, Global optimization algorithm for solving linear multiplicative programming problems, Global algorithm for solving linear multiplicative programming problems, Globally minimizing the sum of a convex-concave fraction and a convex function based on wave-curve bounds, An FPTAS for optimizing a class of low-rank functions over a polytope, A survey of hidden convex optimization, A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, Convexity conditions and the Legendre-fenchel transform for the product of finitely many positive definite quadratic forms, Minimizing the sum of linear fractional functions over the cone of positive semidefinite matrices: approximation and applications, An Output-Space Based Branch-and-Bound Algorithm for Sum-of-Linear-Ratios Problem, An efficient spatial branch-and-bound algorithm using an adaptive branching rule for linear multiplicative programming, On the complexity and approximation of the maximum expected value all-or-nothing subset, Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems, An FPTAS for minimizing the product of two non-negative linear cost functions, A new deterministic global computing algorithm for solving a kind of linear fractional programming, A practical but rigorous approach to sum-of-ratios optimization in geometric applications, A new technique to derive tight convex underestimators (sometimes envelopes), Globally minimizing a class of linear multiplicative forms via simplicial branch-and-bound, An exact method for solving the integer sum of linear ratios problem, Unnamed Item, Range division and linearization algorithm for a class of linear ratios optimization problems, An effective computational algorithm for the global solution of a class of linear fractional programming, Global minimization for generalized polynomial fractional program, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Perron vector optimization applied to search engines, A global optimization approach for solving generalized nonlinear multiplicative programming problem, A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension, Solving a class of multiplicative programs with 0-1 knapsack constraints, A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Efficient local search procedures for quadratic fractional programming problems, An outcome space algorithm for minimizing a class of linear ratio optimization problems, An efficient global optimization algorithm for maximizing the sum of two generalized Rayleigh quotients, An objective space cut and bound algorithm for convex multiplicative programmes, Linear decomposition approach for a class of nonconvex programming problems, An extension of branch-and-bound algorithm for solving sum-of-nonlinear-ratios problem, A convexity theorem for multiplicative functions, A deterministic method for solving the sum of linear ratios problem, Approximation of linear fractional-multiplicative problems, Convexity conditions of Kantorovich function and related semi-infinite linear matrix inequalities, Duality for linear multiplicative programs, Robust metaheuristic algorithm for redundancy optimization in large-scale complex systems, Outer space branch and bound algorithm for solving linear multiplicative programming problems, Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes, Decomposition for adjustable robust linear optimization subject to uncertainty polytope, Global optimization algorithm for a generalized linear multiplicative programming, On reoptimizing multi-class classifiers, Minimizing the sum of a linear and a linear fractional function applying conic quadratic representation: continuous and discrete problems, A nonisolated optimal solution of general linear multiplicative programming problems, Complexity results for some global optimization problems, Global Optimization of Linear Multiplicative Programming Using Univariate Search, A Linear-Time Algorithm for Globally Maximizing the Sum of a Generalized Rayleigh Quotient and a Quadratic Form on the Unit Sphere, Solving generalized convex multiobjective programming problems by a normal direction method, Fast Algorithms for Rank-1 Bimatrix Games, Outcome-space cutting-plane algorithm for linear multiplicative programming, Optimizing over Pareto set of semistrictly quasiconcave vector maximization and application to stochastic portfolio selection, Global optimization method for linear multiplicative programming, An outcome-space-based branch-and-bound algorithm for a class of sum-of-fractions problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a class of quadratic programs
• Quadratic programming with one negative eigenvalue is NP-hard
• Parametric simplex algorithms for solving a special class of nonconvex minimization problems
• A global optimization approach for solving the convex multiplicative programming problem
• A parametric successive underestimation method for convex multiplicative programming problems
• Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
• Linear multiplicative programming
• Optimization on low rank nonconvex structures
• Generalized linear multiplicative and fractional programming
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• An efficient solution method for rank two quasiconcave minimization problems