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
In many applications in statistics, finance, and insurance/reinsurance, one seeks a solution of finding a covariance matrix satisfying a large number of given linear equality and inequality constraints in a way that it deviates the least from a given symmetric matrix. The difficulty in finding an efficient method for solving this problem is due to … 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
Euclidean Jordan-algebra is a commonly used tool in designing interior point algorithms for symmetric cone programs. T-algebra, on the other hand, has rarely been used in symmetric cone programming. In this paper, we use both algebraic characterizations of symmetric cones to extend the target-following framework of linear programming to symmetric cone programming. Within this framework, … 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
The problem of approximately factoring a real or complex multivariate polynomial $f$ seeks minimal perturbations $\Delta f$ to the coefficients of the input polynomial $f$ so that the deformed polynomial $f + \Delta f$ has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomials that has non-trivial factors. (see … 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
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more
In the context of simulating the frictional contact dynamics of large systems of rigid bodies, this paper reviews a novel method for solving large cone complementarity problems by means of a fixed-point iteration algorithm. The method is an extension of the Gauss-Seidel and Gauss-Jacobimethods with overrelaxation for symmetric convex linear complementarity problems. Convergent under fairly … Read more
Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more