nonconvex quadratic programming with box constraints is a fundamental NP-hard global optimization problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove sev...
详细信息
nonconvex quadratic programming with box constraints is a fundamental NP-hard global optimization problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterize their extreme points and vertices, show their invariance under certain a. ne transformations, and show that various linear inequalities induce facets. We also show that the sets are closely related to the Boolean quadric polytope, a fundamental polytope in the field of polyhedral combinatorics. Finally, we give a classification of valid inequalities and show that this yields a finite recursive procedure to check the validity of any proposed inequality.
作者：
YE, YYUNIV IOWA
DEPT MANAGEMENT SCIIOWA CITYIA 52242 USA
We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex - indefinite or negative definite - quadraticprogramming (QP) problems. Although the nonconvex QP with a poly...
详细信息
We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex - indefinite or negative definite - quadraticprogramming (QP) problems. Although the nonconvex QP with a polytope constraint is a "hard" problem, we show that the problem with an ellipsoidal constraint is "easy". When the "hard" QP is solved by successively solving the "easy" QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.
nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combine...
详细信息
nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature-finite branching based on the first-order KKT conditions and polyhedralsemidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.
We present effective linear programming based computational techniques for solving nonconvexquadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadri...
详细信息
We present effective linear programming based computational techniques for solving nonconvexquadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvatal-Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvexquadratic programs with linear constraints.
In this paper, we consider the socalled k-coloring problem in general ***, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadrati...
详细信息
In this paper, we consider the socalled k-coloring problem in general ***, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic 0-1 programming and its relaxed rpoblem, k-coloring problem is converted into a class of (continuous) nonconvexquadratic programs, and several theoretic results are also introduced. Thirdly, linear programming approximate algorithm is quoted and verified for this class of nonconvexquadratic programs. Finally,examining problems which are used to test the algorithm are constructed and sufficient computation experiments are reported.
In general it is very difficult to determine a true local minimizer in nonconvex quadratic programming. The main problems arise if we have so-called weakly active constraints. We discuss an efficient method for checki...
详细信息
In general it is very difficult to determine a true local minimizer in nonconvex quadratic programming. The main problems arise if we have so-called weakly active constraints. We discuss an efficient method for checking the local optimality or determining a direction of descent.
To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approa...
详细信息
To globally solve a nonconvex quadratic programming problem, this paper presents an accelerating linearizing algorithm based on the framework of the branch-and-bound method. By utilizing a new linear relaxation approach, the initial quadraticprogramming problem is reduced to a sequence of linear relaxation programming problems, which is used to obtain a lower bound of the optimal value of this problem. Then, by using the deleting operation of the investigated regions, we can improve the convergent speed of the proposed algorithm. The proposed algorithm is proved to be convergent, and some experiments are reported to show higher feasibility and efficiency of the proposed algorithm.
We consider the solution of nonconvexquadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology...
详细信息
We consider the solution of nonconvexquadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with cutting planes and conic constraints. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a variety of different nonconvexquadratic problems.
Battery energy storage systems (BESS) are increasingly crucial in balancing electricity production and consumption in modern power grids, due to their decreasing capital cost, flexibility, and short response time. How...
详细信息
Battery energy storage systems (BESS) are increasingly crucial in balancing electricity production and consumption in modern power grids, due to their decreasing capital cost, flexibility, and short response time. However, existing BESS optimization models often have complex, non-linear, and non-convex objectives and constraints. We recently proposed a voltage-current arbitrage model (VIAM) for BESS control using a linear approximation of the open circuit voltage and battery status dependency function. This model, called the linearly constrained exponential optimization model, has an effective algorithm, but it's unclear if its solutions are globally optimal. Moreover, using a linearized function in the VIAM can lead to profit loss. This paper presents a new reformulation of the VIAM as a biconvex optimization problem, which can be reduced to convex optimization under certain conditions, allowing for effective location of global optimal solutions. We also propose a new approximation scheme for the original non-linear function using piece-wise linear and quadratic functions, leading to a quadratically constrained biconvex optimization model. We developed a novel sequential dynamic linear/quadratic approximation algorithm for this model and conducted preliminary experiments to demonstrate its efficacy and efficiency.
暂无评论