Symmetry Points of Convex Set: Basic Properties and Computational Complexity

Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x – y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. … Read more

Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In … Read more

Mean-risk objectives in stochastic programming

Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criteria. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk criterion, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various … Read more

On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems

In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case where this system is defined by a Gaussian random matrix and characterise the exact decay rates of the distribution tails, improve the existing moment estimates, … Read more


We study the limiting properties of the affine-scaling directions for linear programming problems. The worst-case angle between the affine-scaling directions and the objective function vector provides an interesting measure that has been very helpful in convergence analyses and in understanding the behaviour of various interior-point algorithms. We establish new relations between this measure and some … Read more

Streaming Cache Placement Problems: Complexity and Algorithms

Virtual private networks (VPN) are often used to distribute live content, such as video or audio streams, from a single source to a large number of destinations. Streaming caches or splitters are deployed in these multicast networks to allow content distribution without overloading the network. In this paper, we consider two combinatorial optimization problems that … Read more

The Inverse Optimal Value Problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost coefficients, determine a cost-coefficient vector such that the corresponding optimal objective value of the linear program is closest to the given value. The above problem, referred here as the inverse optimal value … Read more

Condition and complexity measures for infeasibility certificates of systems of linear inequalities and their sensitivity analysis

We begin with a study of the infeasibility measures for linear programming problems. For this purpose, we consider feasibility problems in Karmarkar’s standard form. Our main focus is on the complexity measures which can be used to bound the amount of computational effort required to solve systems of linear inequalities and related problems in certain … Read more

Complexity of Convex Optimization using Geometry-based Measures and a Reference Point

Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more

Warm start strategies in interior-point methods for linear programming

We study the situation in which, having solved a linear program with an interior-point method, we are presented with a new problem instance whose data is slightly perturbed from the original. We describe strategies for recovering a “warm-start” point for the perturbed problem instance from the iterates of the original problem instance. We obtain worst-case … Read more