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
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 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
We give an elementary proof of optimality conditions for linear programming. The proof is direct, built on a straightforward classical perturbation of the constraints, and does not require either the use of Farkas’ lemma or the use of the simplex method. Citation Technical Report TRITA-MAT-2008-OS6, Department of Mathematics, Royal Institute of Technology (KTH), SE-100 44 … Read more
The space of linear programs (LP) can be partitioned into a finite number of sets, each corresponding to a basis. This partition is thus called the basis partition. The closed-form solution on the space of LP can be determined with the basis partition if we can characterize the basis partition. A differential equation on the … Read more
Linear programming is arguably one of the most basic forms of optimization. Its theory and algorithms can not only be applied to linear optimization problems but also to relaxations of nonlinear problems and branch-and-bound methods for mixed-integer and global optimization problems. Recent research shows that against intuition bad condition numbers frequently occur in linear programming. … Read more
In this paper, we analyze the limiting behavior of the weighted least squares problem $\min_{x\in\Re^n}\sum_{i=1}^p\|D_i(A_ix-b_i)\|^2$, where each $D_i$ is a positive definite diagonal matrix. We consider the situation where the magnitude of the weights are drastically different block-wisely so that $\max(D_1)\geq\min(D_1) \gg \max(D_2) \geq \min(D_2) \gg \max(D_3) \geq \ldots \gg \max(D_{p-1}) \geq \min(D_{p-1}) \gg \max(D_p)$. … Read more
We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more
By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more