Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs

The author (1992, 1993) earlier studied the equivalence of a class of 0–1 quadratic programs and their relaxed problems. Thus, a class of combinatorial optimization problems can be solved by solving a class of nonconvex quadratic programs. In this paper, a necessary and sufficient condition for local minima of this class of nonconvex quadratic programs is given; this will be the foundation for study of algorithms.Research supported by Huo Yingdong Educational Foundation '93.     

Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound

We consider a recent branch-and-bound algorithm of the authors for nonconvex quadratic programming. The algorithm is characterized by its use of semidefinite relaxations within a finite branching scheme. In this paper, we specialize the algorithm to the box-constrained case and study its implementation, which is shown to be a state-of-the-art method for globally solving box-constrained nonconvex quadratic programs. S. Burer was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

Global optimization of a class of nonconvex quadratically constrained quadratic programming problems

In this paper we study a class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.     

A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations

Existing global optimization techniques for nonconvex quadratic programming (QP) branch by recursively partitioning the convex feasible set and thus generate an infinite number of branch-and-bound nodes. An open question of theoretical interest is how to develop a finite branch-and-bound algorithm for nonconvex QP. One idea, which guarantees a finite number of branching decisions, is to enforce the first-order Karush-Kuhn-Tucker (KKT) conditions through branching. In addition, such an approach naturally yields linear programming (LP) relaxations at each node. However, the LP relaxations are unbounded, a fact that precludes their use. In this paper, we propose and study semidefinite programming relaxations, which are bounded and hence suitable for use with finite KKT-branching. Computational results demonstrate the practical effectiveness of the method, with a particular highlight being that only a small number of nodes are required. This author was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (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.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

A relaxation method for nonconvex quadratically constrained quadratic programs

We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch and bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.This research was supported in part by National Science Foundation Grant DDM-91-14489.     

A necessary and sufficient condition of existence of positive solutions for nonlinear singular differential systems

In this paper, by means of monotone iterative technique, a necessary and sufficient condition of the existence of positive solution for a class of nonlinear singular differential system is established, the results of the existence and uniqueness of the positive solution and the iterative sequence of solution are given. In the end, two classes extending boundary value differential systems are discussed and some further results are obtained.     

A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs

We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be second-order cone representable. The usefulness of these new relaxations is demonstrated both theoretically and computationally.     

On lower bounds for a class of quadratic 0, 1 programs

We present a new method of obtaining lower bounds for a class of quadratic 0, 1 programs that includes the quadratic assignment problem. The method generates a monotonic sequence of lower bounds and may be interpreted as a Lagrangean dual ascent procedure. We report on a computational comparison of our bounds with earlier work in [2] based on subgradient techniques.     

Local saddle point and a class of convexification methods for nonconvex optimization problems

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.     

A necessary and sufficient condition of positive solutions for nonlinear singular differential systems with four-point boundary conditions

In this paper, we concert with the existence of positive solution for the following nonlinear singular differential system with four-point boundary conditions

     

Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions

We develop convergent decomposition branch and bound algorithms for solving a class of bilinear programming problems. As an application of the proposed method, we apply it to quadratic programs with a few negative eigenvalues, and to a class of mixed integer programming problems.This paper was completed during the stay of the first author at LMI-INSA Rouen, CNRS URA 1378, France.     

An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds

This paper gives an O(n) algorithm for a singly constrained convex quadratic program using binary search to solve the Kuhn-Tucker system. Computational results indicate that a randomized version of this algorithm runs in expected linear time and is suitable for practical applications. For the nonconvex case an-approximate algorithm is proposed which is based on convex and piecewise linear approximations of the objective function.     

On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs

We discuss the convergence of cutting plane algorithms for a class of nonconvex programs called the Generalized Lattice Point Problems (GLPP). A set of sufficient conditions which guarantee finite convergence are presented. Although these conditions are usually difficult to enforce in a practical implementation, they do illustrate the various factors that must be involved in a convergent rudimentary cutting plane algorithm. A striking example of nonconvergence (in which no subsequence converges to a feasible solution, even when seemingly strong cutting planes are used), is presented to show the effect of neglecting one such factor. We give an application of our analysis to problems with multiple choice constraints and finally discuss a modification of cutting plane algorithms so as to make finite convergence more readily implementable.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

A nonconvex ADMM for a class of sparse inverse semidefinite quadratic programming problems

ABSTRACT

In this paper, we consider a class of sparse inverse semidefinite quadratic programming problems, in which a nonconvex alternating direction method of multiplier is investigated. Under mild conditions, we establish convergence results of our algorithm and the corresponding non-ergodic iteration-complexity is also considered under the assumption that the potential function satisfies the famous Kurdyka–?ojasiewicz property. Numerical results show that our algorithm is suitable to solve the given sparse inverse semidefinite quadratic programming problems.     

Zero duality gap for a class of nonconvex optimization problems

By an equivalent transformation using thepth power of the objective function and the constraint, a saddle point can be generated for a general class of nonconvex optimization problems. Zero duality gap is thus guaranteed when the primal-dual method is applied to the constructed equivalent form.The author very much appreciates the comments from Prof. Douglas J. White.     

广义系统能控性的两个充要条件

能控性判定问题是现代控制论研究的重要课题,它是系统分析和设计的理论基础.本文给出了广义系统能控性的两个充要条件,该些结果也为判定广义系统的能控性提供了一些实用方法,最后给出了一个例子.     

DC programming techniques for solving a class of nonlinear bilevel programs

We propose a method for finding a global solution of a class of nonlinear bilevel programs, in which the objective function in the first level is a DC function, and the second level consists of finding a Karush-Kuhn-Tucker point of a quadratic programming problem. This method is a combination of the local algorithm DCA in DC programming with a branch and bound scheme well known in discrete and global optimization. Computational results on a class of quadratic bilevel programs are reported.     

On the convergence of two branch-and-bound algorithms for nonconvex programming problems

This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.The author would like to thank Professor R. M. Soland for his helpful comments concerning this paper.