Yinyu Ye In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large scale linear programs (LP). Traditional IPMs typically use Newton’s method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton’s method, IPM is … Read more
We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more
This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We … Read more
In this paper we consider the minimization of a continuous function that is potentially not differentiable or not twice differentiable on the boundary of the feasible region. By exploiting an interior point technique, we present first- and second-order optimality conditions for this problem that reduces to classical ones when the derivative on the boundary is … Read more
The paper answers several open questions of the alternating direction method of multipliers (ADMM) and the block coordinate descent (BCD) method that are now wildly used to solve large scale convex optimization problems in many fields. For ADMM, it is still lack of theoretical understanding of the algorithm when the objective function is not separable … Read more
The alternating direction method of multipliers (ADMM) is now widely used in many fields, and its convergence was proved when two blocks of variables are alternatively updated. It is strongly desirable and practically valuable to extend ADMM directly to the case of a multi-block convex minimization problem where its objective function is the sum of … Read more
We propose a first order interior point algorithm for a class of non-Lipschitz and nonconvex minimization problems with box constraints, which arise from applications in variable selection and regularized optimization. The objective functions of these problems are continuously differentiable typically at interior points of the feasible set. Our algorithm is easy to implement and the … Read more
We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when comparing to … Read more
Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the … Read more
We focus on a permutation betting market under parimutuel call auction model where traders bet on the final ranking of n candidates. We present a Proportional Betting mechanism for this market. Our mechanism allows the traders to bet on any subset of the n x n ‘candidate-rank’ pairs, and rewards them proportionally to the number … Read more