A Solver for large-scale indefinite quadratic programs

Based on an active set strategy, a method for solving linearly constrained indefinite quadratic programs to solve the corresponding system of equations at each iteration is presented. The algorithm takes two descent directions to strictly decrease the value of objective function and obtains a suitable step to maintain feasibility. Computational results on a range of quadratic test problems are given.     

The indefinite zero-one quadratic problem

A method is described for transforming an indefinite 0–1 quadratic programming problem into an equivalent positive definite problem of precisely the same size. Several variations of the basic transformation are incorporated in a branch and bound algorithm. This technique is combined with a system of analytical bounds on the variables. Computational results on several hundred random test problems with up to 30 variables demonstrate that the (polynomial bounded) transformation together with the bounds are sufficient to solve many large indefinite problems.     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

An optimality criterion for global quadratic optimization

In this paper we prove a sufficient condition that a strong local minimizer of a bounded quadratic program is the unique global minimizer. This sufficient condition can be verified computationally by solving a linear and a convex quadratic program and can be used as a quality test for local minimizers found by standard indefinite quadratic programming routines.Part of this work was done while the author was at the University of Wisconsin-Madison.     

A computational comparison of some branch and bound methods for indefinite quadratic programs

The aim of this paper is to discuss different branch and bound methods for solving indefinite quadratic programs. In these methods the quadratic objective function is decomposed in a d.c. form and the relaxations are obtained by linearizing the concave part of the decomposition. In this light, various decomposition schemes have been considered and studied. The various branch and bound solution methods have been implemented and compared by means of a deep computational test.      

Active constraints,indefinite quadratic test problems,and complexity

The observation that at leasts constraints are active when the Hessian of the Lagrangian hass negative eigenvalues at a local minimizer is used to obtain two results: (i) a class of nearly concave quadratic minimization problem can be solved in polynomial time; (ii) a class of indefinite quadratic test problems can be constructed with a specified number of positive and negative eigenvalues and with a known global minimizer.The authors thank the reviewers for their constructive comments. The first author was supported by the National Science Foundation Grant DMS-85-20926 and by the Air Force Office of Scientific Research Grant AFOSR-ISSA-86-0091.     

Hidden convexity in some nonconvex quadratically constrained quadratic programming

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs. This author's work was partially supported by GIF, the German-Israeli Foundation for Scientific Research and Development and by the Binational Science Foundation. This author's work was partially supported by National Science Foundation Grants DMS-9201297 and DMS-9401871.     

Lipschitz continuity of the optimal value function and KKT solution set in indefinite quadratic programs

When all the involved data in indefinite quadratic programs change simultaneously,we show the locally Lipschtiz continuity of the KKT set of the quadratic programming problem firstly, then we establish the locally Lipschtiz continuity of the KKT solution set. Finally, the similar conclusion for the corresponding optimal value function is obtained.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints

In Floudas and Visweswaran (1990, 1993), a deterministic global optimization approach was proposed for solving certain classes of nonconvex optimization problems. An algorithm, GOP, was presented for the solution of the problem through a series ofprimal andrelaxed dual problems that provide valid upper and lower bounds respectively on the global solution. The algorithm was proved to have finite convergence to an -global optimum. In this paper, new theoretical properties are presented that help to enhance the computational performance of the GOP algorithm applied to problems of special structure. The effect of the new properties is illustrated through application of the GOP algorithm to a difficult indefinite quadratic problem, a multiperiod tankage quality problem that occurs frequently in the modeling of refinery processes, and a set of pooling/blending problems from the literature. In addition, extensive computational experience is reported for randomly generated concave and indefinite quadratic programming problems of different sizes. The results show that the properties help to make the algorithm computationally efficient for fairly large problems.     

Hidden conic quadratic representation of some nonconvex quadratic optimization problems

The problem of minimizing a quadratic objective function subject to one or two quadratic constraints is known to have a hidden convexity property, even when the quadratic forms are indefinite. The equivalent convex problem is a semidefinite one, and the equivalence is based on the celebrated S-lemma. In this paper, we show that when the quadratic forms are simultaneously diagonalizable (SD), it is possible to derive an equivalent convex problem, which is a conic quadratic (CQ) one, and as such is significantly more tractable than a semidefinite problem. The SD condition holds for free for many problems arising in applications, in particular, when deriving robust counterparts of quadratic, or conic quadratic, constraints affected by implementation error. The proof of the hidden CQ property is constructive and does not rely on the S-lemma. This fact may be significant in discovering hidden convexity in some nonquadratic problems.     

The minima of indefinite binary quadratic forms

The study of the minima of indefinite binary quadratic forms has a long history and the classical results concerning the determination of such minima are stated in terms of the continued fraction expansion of the roots. These results are recast in geometric terms. Using this, and well-known geometric properties of the modular group, some necessary and sufficient conditions for a certain class of quadratic forms to have positive unattained minima are obtained.     

General fractional variational problem depending on indefinite integrals

In this report, we consider two kind of general fractional variational problem depending on indefinite integrals include unconstrained problem and isoperimetric problem. These problems can have multiple dependent variables, multiorder fractional derivatives, multiorder integral derivatives and boundary conditions. For both problems, we obtain the Euler-Lagrange type necessary conditions which must be satisfied for the given functional to be extremum. Also, we apply the Rayleigh-Ritz method for solving the unconstrained general fractional variational problem depending on indefinite integrals. By this method, the given problem is reduced to the problem for solving a system of algebraic equations using shifted Legendre polynomials basis functions. An approximate solution for this problem is obtained by solving the system. We discuss the analytic convergence of this method and finally by some examples will be showing the accurately and applicability for this technique.     

Construction of Jacobi forms associated to indefinite quadratic forms

Vignéras constructs non-holomorphic theta functions according to indefinite quadratic forms with arbitrary signature. We use Vignéras’ theta functions to create examples of non-holomorphic Jacobi forms associated to indefinite theta series by two different methods.     

Class numbers of indefinite binary quadratic forms

We determine the asymptotic average sizes of the class numbers of indefinite binary quadratic forms when ordered by the sizes of their corresponding fundamental units. The proofs make use of the Selberg trace formula.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Approximation algorithms for indefinite complex quadratic maximization problems

In this paper,we consider the following indefinite complex quadratic maximization problem: maximize zHQz,subject to zk ∈ C and zkm = 1,k = 1,...,n,where Q is a Hermitian matrix with trQ = 0,z ∈ Cn is the decision vector,and m 3.An (1/log n) approximation algorithm is presented for such problem.Furthermore,we consider the above problem where the objective matrix Q is in bilinear form,in which case a 0.7118 cos mπ 2approximation algorithm can be constructed.In the context of quadratic optimization,various extensions and connections of the model are discussed.     

A finite algorithm for solving general quadratic problems

Here we propose a global optimization method for general, i.e. indefinite quadratic problems, which consist of maximizing a non-concave quadratic function over a polyhedron inn-dimensional Euclidean space. This algorithm is shown to be finite and exact in non-degenerate situations. The key procedure uses copositivity arguments to ensure escaping from inefficient local solutions. A similar approach is used to generate an improving feasible point, if the starting point is not the global solution, irrespective of whether or not this is a local solution. Also, definiteness properties of the quadratic objective function are irrelevant for this procedure. To increase efficiency of these methods, we employ pseudoconvexity arguments. Pseudoconvexity is related to copositivity in a way which might be helpful to check this property efficiently even beyond the scope of the cases considered here.     

BDD-based optimization for the quadratic stable set problem

The quadratic stable set problem (QSSP) is a natural extension of the well-known maximum stable set problem. The QSSP is NP-hard and can be formulated as a binary quadratic program, which makes it an interesting case study to be tackled from different optimization paradigms. In this paper, we propose a novel representation for the QSSP through binary decision diagrams (BDDs) and adapt a hybrid optimization approach which integrates BDDs and mixed-integer programming (MIP) for solving the QSSP. The exact framework highlights the modeling flexibility offered through decision diagrams to handle nonlinear problems. In addition, the hybrid approach leverages two different representations by exploring, in a complementary way, the solution space with BDD and MIP technologies. Machine learning then becomes a valuable component within the method to guide the search mechanisms. In the numerical experiments, the hybrid approach shows to be superior, by at least one order of magnitude, than two leading commercial MIP solvers with quadratic programming capabilities and a semidefinite-based branch-and-bound solver.