共查询到20条相似文献,搜索用时 15 毫秒
1.
K. C. Kiwiel 《Journal of Optimization Theory and Applications》2008,136(3):445-458
We study several variations of the Bitran–Hax variable fixing method for the continuous quadratic knapsack problem. We close
the gaps in the convergence analysis of several existing methods and provide more efficient versions. We report encouraging
computational results for large-scale problems. 相似文献
2.
Krzysztof C. Kiwiel 《Mathematical Programming》2008,112(2):473-491
We give several linear time algorithms for the continuous quadratic knapsack problem. In addition, we report cycling and wrong-convergence
examples in a number of existing algorithms, and give encouraging computational results for large-scale problems.
相似文献
3.
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem 总被引:1,自引:0,他引:1
In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x
t
Qx+c
t
x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this,
we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x
i
2=x
i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable
vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first
one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved.
We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods
to several other exact solution methods. Furthermore, we report computational results for the max-cut problem. 相似文献
4.
In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss–cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush–Kuhn–Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems. 相似文献
5.
Yanjin Wang 《Numerical Functional Analysis & Optimization》2013,34(11):1283-1293
This article proposes a class of infeasible interior point algorithms for convex quadratic programming, and analyzes its complexity. It is shown that this algorithm has the polynomial complexity. Its best complexity is O(nL). 相似文献
7.
R. Goldbach 《Applied Mathematics and Optimization》1999,39(1):121-142
We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems,
which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation
and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic
constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present.
We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical
results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered
in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since
many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular,
we do not assume boundedness of the feasible set as required in related methods.
Accepted 7 May 1997 相似文献
8.
We introduce a new algorithm for the continuous bounded quadratic knapsack problem. This algorithm is motivated by the geometry of the problem, is based on the iterative solution of a series of simple projection problems, and is easy to understand and implement. In practice, the method compares favorably to other well-known algorithms (some of which have superior worst-case complexity) on problem sizes up ton = 4000. 相似文献
9.
The constrained optimization problem with a quadratic cost functional and two quadratic equality constraints has been studied by Bar-on and Grasse, with positive-definite matrix in the objective. In this note, we shall relax the matrix in the objective to be positive semidefinite. A necessary and sufficient condition to characterize a local optimal solution to be global is established. Also, a perturbation scheme is proposed to solve this generalized problem. 相似文献
10.
一种新的可分凸二次规划的不可行内点算法 总被引:3,自引:0,他引:3
本文对可分凸二次规划提出了一个新的不可行内点算法 ,证明了该算法是一个多项式时间算法 ,并将迭代复杂性界降至O(nL) . 相似文献
11.
A dual l
p-norm perturbation approach is introduced for solving convex quadratic programming problems. The feasible region of the Lagrangian dual program is approximated by a proper subset that is defined by a single smooth convex constraint involving the l
p-norm of a vector measure of constraint violation. It is shown that the perturbed dual program becomes the dual program as p and, under some standard conditions, the optimal solution of the perturbed dual program converges to a dual optimal solution. A closed-form formula that converts an optimal solution of the perturbed dual program into a feasible solution of the primal convex quadratic program is also provided. Such primal feasible solutions converge to an optimal primal solution as p. The proposed approach generalizes the previously proposed primal perturbation approach with an entropic barrier function. Its theory specializes easily for linear programming. 相似文献
12.
We present an optimal piecewise-linear approximation method for the objective function of separable convex quadratic programs. The method provides guidelines on how many grid points to use and how to position them for a piecewise-linear approximation if the error induced by the approximation is to be bounded a priori.Corresponding author. 相似文献
13.
对框式凸二次规划问题提出了一种非精确不可行内点算法 ,该算法使用的迭代方向仅需要达到一个相对的精度 .在初始点位于中心线的某邻域内的假设下 ,证明了算法的全局收敛性 相似文献
14.
The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time. 相似文献
15.
16.
Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems. 相似文献
17.
Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints 总被引:4,自引:0,他引:4
N. V. Thoai 《Journal of Optimization Theory and Applications》2000,107(2):331-354
The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported. 相似文献
18.
19.
不等式约束二次规划的一新算法 总被引:3,自引:0,他引:3
文献[1]提出了一般等式约束非线性规划问题一种求解途径.文献[2]应用这一途径给出了等式约束二次规划问题的一种算法,本文在文献[1]和[2]的基础上对不等式约束二次规划问题提出了一种新算法. 相似文献
20.
Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers. 相似文献