The knowledge of sparsity information plays an important role in efficient determination of sparse Jacobian matrices. In a recent work, we have proposed sparsity-exploiting substitution techniques to determine Jacobian matrices. In this paper, we take a closer look at the underlying combinatorial problem. We propose a column ordering heuristic to augment the “usable sparsity” in … Read more
We present large-scale optimization techniques to model the energy function that underlies the folding process of proteins. Linear Programming is used to identify parameters in the energy function model, the objective being that the model predict the structure of known proteins correctly. Such trained functions can then be used either for {\em ab-initio} prediction or … Read more
The goal of this paper is to organize some of the mathematical and algorithmic aspects of the recently proposed space-mapping technique for continuous optimization with expensive function evaluations. First, we consider the mapping from the fine space to the coarse space when the models are vector-valued functions and when the space-mapping (nonlinear) least-squares residual is … Read more
In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters. The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, … Read more
Recently,Tseng extended a class of merit functions for the nonlinear complementarity problem to semidefinite complementarity problem (SDCP), showing some properties under suitable assumptions. Yamashita and Fukushima also presented other properties. In this paper, we propose a new class of merit functions for the SDCP, and prove some of those properties, under weaker hypothesis. Particularly, we … Read more
This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more
Automatic differentiation (AD) automatically transforms programs which calculate elementary functions into programs which calculate the gradients of these functions. Unlike other differentiation techniques, AD allows one to calculate the gradient of any function at the cost of at most 5 values of the function (in terms of time). Interval constraint programming (ICP) is a part … Read more
The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and … Read more
We present a primal-dual interior-point algorithm of line-search type for nonlinear programs, which uses a new decomposition scheme of sequential quadratic programming. The algorithm can circumvent the convergence difficulties of some existing interior-point methods. Global convergence properties are derived without assuming regularity conditions. The penalty parameter rho in the merit function is updated automatically such … Read more
In this note we present an improved approximation algorithm for the (uncapacitated) metric facility location problem. This algorithm uses the idea of cost scaling, the greedy algorithm of \cite{JMS}, and the greedy augmentation procedure of \cite{CG,GK}. CitationWorking Paper, MIT and the University of IowaArticleDownload View PDF