Semidefinite optimization, a spectral approach

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

A primal affine-scaling algorithm for constrained convex programs

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

Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers

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

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

A New Self-Dual Embedding Method for Convex Programming

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

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

On the Primal-Dual Geometry of Level Sets in Linear and Conic Optimization

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). CitationMIT Operations Research Center Working PaperArticleDownload View PDF

An Attractor-Repeller Approach to Floorplanning

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

A conic formulation for hBcnorm optimization

In this paper, we formulate the $l_p$-norm optimization problem as a conic optimization problem, derive its standard duality properties and show it can be solved in polynomial time. We first define an ad hoc closed convex cone, study its properties and derive its dual. This allows us to express the standard $l_p$-norm optimization primal problem … Read more

Improving complexity of structured convex optimization problems using self-concordant barriers

The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using to the theory of self-concordant functions developed in [2]. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of … Read more