In this paper we present optimization algorithms for image restoration based on the total variation (TV) minimization framework of L. Rudin, S. Osher and E. Fatemi (ROF). Our approach formulates TV minimization as a second-order cone program which is then solved by interior-point algorithms that are efficient both in practice (using nested dissection and domain … Read more
It is known that predictor-corrector methods in a large neighborhood of the central path are among the most efficient interior point methods (IPMs) for linear optimization (LO) problems. The best iteration bound based on the classical logarithmic barrier function is $O\left(n\log{\frac{n}{\epsilon}}\right)$. In this paper we propose a family of self-regular proximity based predictor-corrector (SR-PC) IPM … Read more
Sensitivity analysis is one of the most nteresting and preoccupying areas in optimization. Many attempts are made to investigate the problem’s behavior when the input data changes. Usually variation occurs in the right hand side of the constraints and/or the objective function coefficients. Degeneracy of optimal solutions causes considerable difficulties in sensitivity analysis. In this … Read more
Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x – y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. … Read more
We present a new approach to estimate the risk-neutral probability density function (pdf) of the future prices of an underlying asset from the prices of options written on the asset. The estimation is carried out in the space of cubic spline functions, yielding appropriate smoothness. The resulting optimization problem, used to invert the data and … Read more
Conic optimization is the problem of optimizing a linear function over an intersection of an affine linear manifold with the Cartesian product of convex cones. However, many real world conic models involves an intersection rather than the product of two or more cones. It is easy to deal with an intersection of one or more … Read more
We discuss computational enhancements for the low-rank semidefinite programming algorithm, including the extension to block semidefinite programs, an exact linesearch procedure, and a dynamic rank reduction scheme. A truncated Newton method is also introduced, and several preconditioning strategies are proposed. Numerical experiments illustrating these enhancements are provided. CitationManuscript, Department of Mangagement Sciences, University of Iowa, … Read more
We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification … Read more
We consider two notions for the representations of convex cones: $G$-representation and lifted-$G$-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones … Read more
We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more