A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more

Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

On the Volumetric Path

We consider the logarithmic and the volumetric barrier functions used in interior point methods. In the case of the logarithmic barrier function, the analytic center of a level set is the point at which the central path intersects that level set. We prove that this also holds for the volumetric path. For the central path, … Read more

Convex approximations in stochastic programming by semidefinite programming

The following question arises in stochastic programming: how can one approximate a noisy convex function with a convex quadratic function that is optimal in some sense. Using several approaches for constructing convex approximations we present some optimization models yielding convex quadratic regressions that are optimal approximations in $L_1$, $L_\infty$ and $L_2$ norm. Extensive numerical experiments … Read more

On the computational complexity of gap-free duals for semidefinite programming

We consider the complexity of gap-free duals in semidefinite programming. Using the theory of homogeneous cones we provide a new representation of Ramana’s gap-free dual and show that the new formulation has a much better complexity than originally proved by Ramana. Citation COR@L Technical Report, Lehigh University Article Download View On the computational complexity of … Read more

A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with (\sqrt{n}\log{\frac{{\rm Tr}(X^0S^0)}{\epsilon}})$ iteration complexity

In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … Read more

A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ “sharp” turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension … Read more

Controlling the dose distribution with gEUD-type constraints within the convex IMRT optimization framework

Radiation therapy is an important modality in treating various cancers. Various treatment planning and delivery technologies have emerged to support Intensity Modulated Radiation Therapy (IMRT), creating significant opportunities to advance this type of treatment. We investigate the possibility of including the dose prescription, specified by the DVH, within the convex optimization framework for inverse IMRT … Read more

The continuous d-step conjecture for polytopes

The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more

Exact duality for optimization over symmetric cones

We present a strong duality theory for optimization problems over symmetric cones without assuming any constraint qualification. We show important complexity implications of the result to semidefinite and second order conic optimization. The result is an application of Borwein and Wolkowicz’s facial reduction procedure to express the minimal cone. We use Pataki’s simplified analysis and … Read more