We formalize an algorithm for solving the L1-norm best-fit hyperplane problem derived using first principles and geometric insights about L1 projection and L1 regression. The procedure follows from a new proof of global optimality and relies on the solution of a small number of linear programs. The procedure is implemented for validation and testing. This … Read more
In this paper we develop and analyze an efficient algorithm which solves seven related optimization problems simultaneously, in relative scale. Each iteration of our method is very cheap, with main work spent on matrix-vector multiplication. We prove that if a certain sequence generated by the algorithm remains bounded, then the method must terminate in $O(1/\delta)$ … Read more
It has recently been shown (Burer, 2006) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs (CPPs), i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are necessarily NP-hard. A basic tractable relaxation … Read more
Based on extensive computational evidence (hundreds of thousands of randomly generated problems) the second author conjectured that $\bar{\kappa}(\zeta)=1$, which is a factor of $\sqrt{2n}$ better than that has been proved, and which would yield an $O(\sqrt{n})$ iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that $\bar{\kappa}(\zeta)$ is in the … Read more
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim., 16(4):1110–1136, 2006). We introduce a kernel function in the algorithm. For $p\in[0,1)$, the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, … Read more
In this paper we study linear optimization problems with multi-dimensional linear positive second-order stochastic dominance constraints. By using the polyhedral properties of the second- order linear dominance condition we present a cutting-surface algorithm, and show its finite convergence. The cut generation problem is a difference of convex functions (DC) optimization problem. We exploit the polyhedral … Read more
This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom … Read more
In this paper we derive new upper bounds for the densities of measurable sets in R^n which avoid a finite set of prescribed distances. The new bounds come from the solution of a linear programming problem. We apply this method to obtain new upper bounds for measurable sets which avoid the unit distance in dimensions … Read more
In this paper we present an infeasible interior-point algorithm for solving linear optimization problems. This algorithm is obtained by modifying the search direction in the algorithm [C. Roos, A full-Newton step ${O}(n)$ infeasible interior-point algorithm for linear optimization, 16(4) 2006, 1110-1136.]. The analysis of our algorithm is much simpler than that of the Roos’s algorithm … Read more
We provide a closed-form solution to the problem of computing the sharpest static-arbitrage upper bound on the price of a European basket option, given the prices of vanilla call options in the underlying securities. Unlike previous approaches to this problem, our solution technique is entirely based on linear programming. This also allows us to obtain … Read more