We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more
We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the … Read more
This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more
The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more
We study homogeneous convex cones. We first characterize the extreme rays of such cones in the context of their primal construction (due to Vinberg) and also in the context of their dual construction (due to Rothaus). Then, using these results, we prove that every homogeneous cone is facially exposed. We provide an alternative proof of … Read more
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
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
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
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
The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying dimensions) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard discrete optimization problem; even the restricted version … Read more