We discuss several generalizations of the classical Eckart and Young identity. We show that a natural extension of this identity holds for rectangular matrices defining conic systems of constraints, and for perturbations restricted to a particular block structure, such as those determined by a sparsity pattern. Our results extend and unify the classical Eckart and … Read more
Aperture-based inverse planning (ABIP) for intensity modulated radiation therapy (IMRT) treatment planning starts with external radiation fields (beams) that fully conform to the target(s) and then superimposes sub-fields called segments to achieve complex shaping of 3D dose distributions. The segments’ intensities are determined by solving a feasibility problem. The least-intensity feasible (LIF) solution, proposed and … Read more
The notion of relaxation is well understood for orthogonal projections onto convex sets. For general Bregman projections it was considered only for hyperplanes and the question of how to relax Bregman projections onto convex sets that are not linear (i.e., not hyperplanes or half-spaces) has remained open. A definition of underrelaxation of Bregman projections onto … Read more
The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in mathematics and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections. In this paper, the case where one of the constraints … Read more
In this paper we introduce a conic optimization formulation for inequality-constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for … Read more
We formulate a block-iterative algorithmic scheme for the solution of systems of linear inequalities and/or equations and analyze its convergence. This study provides as special cases proofs of convergence of (i) the recently proposed Component Averaging (CAV) method of Censor, Gordon and Gordon ({\it Parallel Computing}, 27:777–808, 2001), (ii) the recently proposed Block-Iterative CAV (BICAV) … Read more
We study nonsmooth unconstrained optimization problem, which includes sum of pairwise maxima of smooth functions. Minimum $l_1$-norm approximation is a particular case of this problem. Combining ideas Lagrange multipliers with smooth approximation of max-type function, we obtain a new kind of nonquadratic augmented Lagrangian. Our approach does not require artificial variables, and preserves sparse structure … Read more
In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in $\Re^n$ defined by a finite set of linear inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two … Read more
For a conic optimization problem: minimize cx subject to Ax=b, x \in C, we present a geometric relationship between the maximum norms of the level sets of the primal and the inscribed sizes of the level sets of the dual (or the other way around). Citation MIT Operations Research Center Working Paper Article Download View … Read more
We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the … Read more