Numerical Experiments with universal barrier functions for cones of Chebyshev systems

Based on previous explicit computations of universal barrier functions, we describe numerical experiments for solving certain classes of convex optimization problems. The comparison is given of the performance of the classical affine-scaling algorithm with similar algorithm based upon the universal barrier function Citation To appear in “Computational Optimization and Applications” Article Download View Numerical Experiments … Read more

Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms

Sparse PCA seeks approximate sparse “eigenvectors” whose projections capture the maximal variance of data. As a cardinality-constrained and non-convex optimization problem, it is NP-hard and yet it is encountered in a wide range of applied fields, from bio-informatics to finance. Recent progress has focused mainly on continuous approximation and convex relaxation of the hard cardinality … Read more

Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

A Tractable Approximation of Stochastic Programming via Robust Optimization

Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more

A Robust Optimization Framework for Analyzing Distribution Systems with Transshipment

This paper studies a distribution system consisting of multiple retail locations with transshipment operations among the retailers. Due to the difficulty in computing the optimal solution imposed by the transshipment operations and in estimating shortage cost from a practical perspective, we propose a robust optimization framework for analyzing the impact of transshipment operations on such … Read more

A Feasibility Pump for Mixed Integer Nonlinear Programs

We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration within … Read more

A local convergence property of primal-dual methods for nonlinear programming

We prove a new local convergence property of a primal-dual method for solving nonlinear optimization problem. Following a standard interior point approach, the complementarity conditions of the original primal-dual system are perturbed by a parameter which is driven to zero during the iterations. The sequence of iterates is generated by a linearization of the perturbed … Read more

An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more

Smooth minimization of two-stage stochastic linear programs

This note presents an application of the smooth optimization technique of Nesterov for solving two-stage stochastic linear programs. It is shown that the original O(1/e) bound of Nesterov on the number of main iterations required to obtain an e-optimal solution is retained. Citation Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, … Read more

Second-order convergence properties of trust-region methods using incomplete curvature information, with an application to multigrid optimization

Convergence properties of trust-region methods for unconstrained nonconvex optimization is considered in the case where information on the objective function’s local curvature is incomplete, in the sense that it may be restricted to a fixed set of “test directions” and may not be available at every iteration. It is shown that convergence to local “weak” … Read more