In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an … Read more
In this work we are interested in nonlinear symmetric cone problems (NSCPs), which contain as special cases nonlinear semidefinite programming, nonlinear second order cone programming and the classical nonlinear programming problems. We explore the possibility of reformulating NSCPs as common nonlinear programs (NLPs), with the aid of squared slack variables. Through this connection, we show … Read more
Using the T-algebra machinery we show that the only strictly convex homogeneous cones in R^n with n >= 3 are the 2-cones, also known as Lorentz cones or second order cones. In particular, this shows that the p-cones are not homogeneous when p is not 2, 1 < p <\infty and n >= 3, thus … Read more
The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current LP solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known … Read more
Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set $K$. The idea consists of approximating from above the indicator function of $K$ with a sequence of polynomials of increasing degree $d$, so that the integrals of these polynomials generate a convergence sequence of upper bounds … Read more
Radiation therapy is considered to be one of important treatment protocols for cancers. Radiation therapy employs several beams of ionizing radiation to kill cancer tumors, but such irradiation also causes damage to normal tissues. Therefore, a treatment plan should satisfy dose-volume constraints (DVCs). Intensity-modulated radiotherapy treatment (IMRT) enables to control the beam intensities and gives … Read more
We propose simple polynomial-time algorithms for two linear conic feasibility problems. For a matrix $A\in \R^{m\times n}$, the {\em kernel problem} requires a positive vector in the kernel of $A$, and the {\em image problem} requires a positive vector in the image of $A^\T$. Both algorithms iterate between simple first order steps and rescaling steps. … Read more
We deal with a recently proposed method of Chubanov [1] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov’s method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [1]. The … Read more
The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The … Read more
We show how random projections can be used to solve large-scale dense linear programs approximately. This is a new application of techniques which are now fairly well known in probabilistic algorithms, but have never yet been systematically applied to the fundamental class of Linear Programming. We develop the necessary theoretical framework, and show that this … Read more