Alexandre Belloni For a conic linear system of the form Ax \in K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K, and highlights the role of … Read more
In this paper we explore properties of a family of probability density functions, called norm-induced densities, defined as $$f_t(x) = \left\{ \begin{array}{ll} \displaystyle \frac{ e^{-t\|x\|^p}dx}{\int_K e^{-t\|y\|^p}dy}, & x \in K \\ 0, & x \notin K,\\ \end{array}\right. $$ where $K$ is a $n$-dimensional convex set that contains the origin, parameters $t > 0$ and $p … Read more
We study the second-order feasibility cone F = { y : \| My \| \le g^Ty } for given data (M,g). We construct a new representation for this cone and its dual based on the spectral decomposition of the matrix M^TM – gg^T. This representation is used to efficiently solve the problem of projecting an … Read more
The classical perceptron algorithm is an elementary row-action/relaxation algorithm for solving a homogeneous linear inequality system Ax > 0. A natural condition measure associated with this algorithm is the Euclidean width t of the cone of feasible solutions, and the iteration complexity of the perceptron algorithm is bounded by 1/t^2, see Rosenblatt 1962. Dunagan and … Read more
We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has … Read more
Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the … Read more
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