This paper presents a branch-and-bound algorithm for nonconvex quadratic programming, which is based on solving semidefinite relaxations at each node of the enumeration tree. The method is motivated by a recent branch-and-cut approach for the box-constrained case that employs linear relaxations of the first-order KKT conditions. We discuss certain limitations of linear relaxations when handling … Read more
We describe a Jordan-algebraic version of results related to convexity of images of quadratic mappings as well as related results on exactness of symmetric relaxations of certain classes of nonconvex optimization problems. The exactness of relaxations is proved based on rank estimates. Our approach provides a unifying viewpoint on a large number of classical results … Read more
Suppose x and s lie in the interiors of a cone K and its dual K^* respectively. We seek dual ellipsoidal norms such that the product of the radii of the largest inscribed balls centered at x and s and incribed in K and K^* respectively is maximized. Here the balls are defined using the … Read more
We present a full-Newton step infeasible interior-point algorithm. It is shown that at most $O(n)$ (inner) iterations suffice to reduce the duality gap and the residuals by the factor $\frac1{e}$. The bound coincides with the best known bound for infeasible interior-point algorithms. It is conjectured that further investigation will improve the above bound to $O(\sqrt{n})$. … Read more
We analyze the problem of finding a point strictly interior to a bounded, fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the LP, SDP and SOCP cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number … Read more
Primal-dual Interior-Point Methods (IPMs) have shown their ability in solving large classes of optimization problems efficiently. Feasible IPMs require a strictly feasible starting point to generate the iterates that converge to an optimal solution. The self-dual embedding model provides an elegant solution to this problem with the cost of slightly increasing the size of the … Read more
For a locally optimal solution to the nonlinear semidefinite programming problem, under Robinson’s constraint qualification, the following conditions are proved to be equivalent: the strong second order sufficient condition and constraint nondegeneracy; the nonsingularity of Clarke’s Jacobian of the Karush-Kuhn-Tucker system; the strong regularity of the Karush-Kuhn-Tucker point; and others. Citation Technical Report, Department of … Read more
We investigate ill-posed semidefinite programming problems for which Slater’s constraint qualifications fail, and propose a new reliable termination criterium dealing with such problems. This criterium is scale-independent and provides verified forward error bounds for the true optimal value, where all rounding errors due to floating point arithmetic are taken into account. It is based on … Read more
We propose minimum volume ellipsoids (MVE) clustering as an alternate clustering technique to k-means clustering for Gaussian data points and explore its value and practicality. MVE clustering allocates data points into clusters that minimizes the total volumes of each cluster’s covering ellipsoids. Motivations for this approach include its scale-invariance, its ability to handle asymmetric and … Read more
We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has … Read more