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

A Starting-Point Strategy for Nonlinear Interior Methods

This paper presents a strategy for choosing the initial point, slacks and multipliers in interior methods for nonlinear programming. It consists of first computing a Newton-like step to estimate the magnitude of these three variables and then shifting the slacks and multipliers so that they are sufficiently positive. The new strategy has the option of … Read more

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is $\min_{x\in\Delta} x’Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One … Read more

On Conically Ordered Convex Programs

In this paper we study a special class of convex optimization problems called {\em conically ordered convex programs}\/ (COCP), where the feasible region is given as the level set of a vector-valued nonlinear mapping, expressed as a nonnegative combination of convex functions. The nonnegativity of the vectors is defined using a pre-described conic ordering. The … Read more

The Complexity of Self-Regular Proximity Based Infeasible IPMs

Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting perties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to … Read more

A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity … Read more

Conic systems and sublinear mappings: equivalent approaches

It is known that linear conic systems are a special case of set-valued sublinear mappings. Hence the latter subsumes the former. In this note we observe that linear conic systems also contain set-valued sublinear mappings as a special case. Consequently, the former also subsumes the latter. Citation Operations Research Letters 32 (2004) pp. 463–467.

Global optimization of rational functions: a semidefinite programming approach

We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, or the (partial) closure of such a set (constrained case). We show that in the univariate case ($n=1$), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced … Read more

Characterizations of error bounds for lower semicontinuous functions on metric spaces

By using a variational method based on Ekeland’s principle, we give characterizations of the existence of so-called global and local error bounds, for lower semicontinuous functions defined on complete metric spaces. We thus provide a systematic and synthetic approach to the subject, emphasizing the special case of convex functions defined on arbitrary Banach spaces, and … Read more

LMI approximations for cones of positive semidefinite forms

An interesting recent trend in optimization is the application of semidefinite programming techniques to new classes of optimization problems. In particular, this trend has been successful in showing that under suitable circumstances, polynomial optimization problems can be approximated via a sequence of semidefinite programs. Similar ideas apply to conic optimization over the cone of copositive … Read more