Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming. Article Download View An Extension of Chubanov's Polynomial-Time Linear Programming Algorithm to Second-Order Cone Programming
This document briefly describes our freely distributed Maple library {\sc spectra}, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required. Article Download View SPECTRA – a Maple … Read more
The extended second order cones were introduced by S. Z. Németh and G. Zhang in [S. Z. Németh and G. Zhang. Extended Lorentz cones and variational inequalities on cylinders. J. Optim. Theory Appl., 168(3):756-768, 2016] for solving mixed complementarity problems and variational inequalities on cylinders. R. Sznajder in [R. Sznajder. The Lyapunov rank of extended … Read more
We focus on efficient preconditioning techniques for sequences of KKT linear systems arising from the interior point solution of large convex quadratic programming problems. Constraint Preconditioners (CPs), though very effective in accelerating Krylov methods in the solution of KKT systems, have a very high computational cost in some instances, because their factorization may be the … Read more
This paper considers the relaxed Peaceman-Rachford (PR) splitting method for fi nding an approximate solution of a monotone inclusion whose underlying operator consists of the sum of two maximal strongly monotone operators. Using general results obtained in the setting of a non-Euclidean hybrid proximal extragradient framework, convergence of the iterates, as well as pointwise and ergodic … Read more
We present a linear-time approximation algorithm for minimum subset sum, which has better worst-case approximation factor (6/5) than previous linear-time algorithms for this problem. We also present a generalization of the scheme used to derive the algorithm, which can be used to obtain algorithms with approximation ratios of (k+1)/k. In addition, we present a family … Read more
We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $\Omega(\sqrt{\sfrac{n}{\log n}})$ many integer variables. By known reductions, this result extends to the traveling salesman polytope. This lower bound has various implications regarding the existence of small mixed-integer mathematical … Read more
When generating cutting-planes for mixed-integer programs from multiple rows of the simplex tableau, the usual approach has been to relax the integrality of the non-basic variables, compute an intersection cut, then strengthen the cut coefficients corresponding to integral non-basic variables using the so-called trivial lifting procedure. Although of polynomial-time complexity in theory, this lifting procedure … Read more
In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an $\epsilon$-optimal solution with a low complexity than SG method. In particular, we first … Read more
In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving … Read more