A new penalty function algorithm for convex quadratic programming

In this paper, we develop an exterior point algorithm for convex quadratic programming using a penalty function approach. Each iteration in the algorithm consists of a single Newton step followed by a reduction in the value of the penalty parameter. The points generated by the algorithm follow an exterior path that we define. Convergence of the algorithm is established. The proposed algorithm was motivated by the work of Al-Sultan and Murty on nearest point problems, a special quadratic program. A preliminary implementation of the algorithm produced encouraging results. In particular, the algorithm requires a small and almost constant number of iterations to solve the small to medium size problems tested.     

An exterior point polynomial-time algorithm for convex quadratic programming

In this paper an exterior point polynomial time algorithm for convex quadratic programming problems is proposed. We convert a convex quadratic program into an unconstrained convex program problem with a self-concordant objective function. We show that, only with duality, the Path-following method is valid. The computational complexity analysis of the algorithm is given.     

An effective branch-and-bound algorithm for convex quadratic integer programming

We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.     

An extension of Karmarkar's projective algorithm for convex quadratic programming

We present an extension of Karmarkar's linear programming algorithm for solving a more general group of optimization problems: convex quadratic programs. This extension is based on the iterated application of the objective augmentation and the projective transformation, followed by optimization over an inscribing ellipsoid centered at the current solution. It creates a sequence of interior feasible points that converge to the optimal feasible solution in O(Ln) iterations; each iteration can be computed in O(Ln ³) arithmetic operations, wheren is the number of variables andL is the number of bits in the input. In this paper, we emphasize its convergence property, practical efficiency, and relation to the ellipsoid method.     

A weighted gram-schmidt method for convex quadratic programming

Range-space methods for convex quadratic programming improve in efficiency as the number of constraints active at the solution decreases. In this paper we describe a range-space method based upon updating a weighted Gram-Schmidt factorization of the constraints in the active set. The updating methods described are applicable to both primal and dual quadratic programming algorithms that use an active-set strategy. Many quadratic programming problems include simple bounds on all the variables as well as general linear constraints. A feature of the proposed method is that it is able to exploit the structure of simple bound constraints. This allows the method to retain efficiency when the number ofgeneral constraints active at the solution is small. Furthermore, the efficiency of the method improves as the number of active bound constraints increases. This research was supported by the U.S. Department of Energy Contract DE-AC03-76SF00326, PA No. DE-AT03-76ER72018; National Science Foundation Grants MCS-7926009 and ECS-8012974; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-79-C-0110. The work of Nicholas Gould was supported by the Science and Engineering Research Council of Great Britain.     

A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions

This paper presents a theoretical result on convergence of a primal affine-scaling method for convex quadratic programs. It is shown that, as long as the stepsize is less than a threshold value which depends on the input data only, Ye and Tse's interior ellipsoid algorithm for convex quadratic programming is globally convergent without nondegeneracy assumptions. In addition, its local convergence rate is at least linear and the dual iterates have an ergodically convergent property.Research supported in part by the NSF under grant DDM-8721709.     

A decomposition algorithm for quadratic programming

A decomposition algorithm using Lemke's method is proposed for the solution of quadratic programming problems having possibly unbounded feasible regions. The feasible region for each master program is a generalized simplex of minimal size. This property is maintained by a dropping procedure which does not affect the finiteness of the convergence. The details of the matrix transformations associated with an efficient implementation of the algorithm are given. Encouraging preliminary computational experience is presented.     

A quadratic programming algorithm

By using conjugate directions a method for solving convex quadratic programming problems is developed. The algorithm generates a sequence of feasible solutions and terminates after a finite number of iterations. Extensions of the algorithm for nonconvex and large structured quadratic programming problems are discussed.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041 and in part by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A 8189 and E 5582.     

A new algorithm for quadratic programming

We present a new finite algorithm for quadratic programming. Our algorithm is based on the solution procedures of linear programming (pivoting, Bland's rule, Hungarian Methods, criss-cross method), however this method does not require the enlargement of the basic tableau as Frank-Wolfe method does. It can be considered as a feasible point active-set method. We solve linear equation systems in oder to reach an active constraint set (complementary solutions) and we solve a feasibility problem in order to check that optimality can be reached on this active set or to improve the actual solution. This algorithm is a straightforward generalization of Klafszky's and Terlaky's Hungarian Method. It has nearly the same structure as Ritter's algorithm (which is based on conjugate directions), but it does not use conjugate directions.     

A semidefinite programming method for integer convex quadratic minimization

We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice \({\mathbf{Z}}^n\). We present a simple semidefinite programming (SDP) relaxation for obtaining a nontrivial lower bound on the optimal value of the problem. By interpreting the solution to the SDP relaxation probabilistically, we obtain a randomized algorithm for finding good suboptimal solutions, and thus an upper bound on the optimal value. The effectiveness of the method is shown for numerical problem instances of various sizes.     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

A clique algorithm for standard quadratic programming

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a StQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problem in an associated graph. Such a clique problem, which does not seem to have been studied before, is then solved with an exact and a heuristic algorithm. Some computational experience shows that our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

A parallel descent algorithm for convex programming

In this paper, we propose a parallel decomposition algorithm for solving a class of convex optimization problems, which is broad enough to contain ordinary convex programming problems with a strongly convex objective function. The algorithm is a variant of the trust region method applied to the Fenchel dual of the given problem. We prove global convergence of the algorithm and report some computational experience with the proposed algorithm on the Connection Machine Model CM-5.