When is the linear image of a closed convex cone closed? We present very simple, and intuitive necessary conditions, which 1) unify, and generalize seemingly disparate, classical sufficient conditions: polyhedrality of the cone, and “Slater” type conditions; 2) are necessary and sufficient, when the dual cone belongs to a class, that we call nice cones. … 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 provide a sufficient condition on a class of compact basic semialgebraic sets K for their convex hull to have a lifted semidefinite representation (SDr). This lifted SDr is explicitly expressed in terms of the polynomials that define K. Examples are provided. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we … Read more
In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more
We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more
Three primal-dual interior-point algorithms for homogeneous cone programming are presented. They are a short-step algorithm, a large-update algorithm, and a predictor-corrector algorithm. These algorithms are described and analyzed based on a characterization of homogeneous cone via T-algebra. The analysis show that the algorithms have polynomial iteration complexity. Citation Division of Mathematical Sciences, Nanyang Technological University, … Read more
It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more
The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more
We present an interior proximal point method with Bregman distance, whose Bregman function is separable and the zone is the interior of the positive orthant, for solving the quasiconvex optimization problem under nonnegative constraints. We establish the well-definedness of the sequence generated by our algorithm and we prove convergence to a solution point when the … Read more
We show the linear convergence of a simple first-order algorithm for the minimum-volume enclosing ellipsoid problem and its dual, the D-optimal design problem of statistics. Computational tests confirm the attractive features of this method. Citation Optimization Methods and Software 23 (2008), 5–19. Article Download View Linear convergence of a modified Frank-Wolfe algorithm for computing minimum … Read more