In this paper we analyze the limiting behavior of infeasible weighted central paths in semidefinite programming under the assumption that a strictly complementary solution exists. We show that the paths associated with the “square root” symmetrization of the weighted centrality condition are analytic functions of the barrier parameter $\mu$ even at $\mu=0$ if and only … Read more
In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more
Let $N(\epsilon,\delta)$ be the number of samples needed when solving a stochastic program such that the objective function evaluated at the sample optimizer is within $\epsilon$ of the true optimum with probability $1-\delta$. Previous results are of the form $N(\epsilon,\delta)=O(\epsilon^{-2}\log \delta^{-1})$. However, a smooth objective function is often locally quadratic at an interior optimum. For … Read more
Computational Convex Analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of Computational Convex Analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is … Read more
Production theory needs generalizations so that it can incorporate broader class of production functions. A generalized Hotelling’s lemma and a generalized Shephard’s lemma in economic theory, which are established in virtue of nonsmooth analysis under the assumption of upper semicontinuity on production functions. Continuity of factor inputs with respect to a change of the factor … Read more
We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\’asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and … Read more
Lovasz and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions are revisited and a new, block-diagonal hierarchy is proposed. It has the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. It is applied … Read more
We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: [D. Cvetkovic, M. Cangalovic and V. Kovacevic-Vucic. Semidefinite Programming Methods for the Symmetric Traveling Salesman … Read more
The Libopt environment is both a methodology and a set of tools that can be used for testing, comparing, and profiling solvers on problems belonging to various collections. These collections can be heterogeneous in the sense that their problems can have common features that differ from one collection to the other. Libopt brings a unified … Read more
In this paper we present a robust optimization approach to portfolio management under uncertainty that (i) builds upon the well-established Lognormal model for stock prices while addressing its limitations, and (ii) incorporates the imperfect knowledge on the true distribution of the continuously compounded rates of return, i.e., the increments of the logarithm of the stock … Read more