Complex Quadratic Optimization and Semidefinite Programming

In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson. We first develop a closed-form formula to compute the probability of … Read more

Reduction Tests for the Prize-Collecting Steiner Problem

The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more

A GRASP algorithm for the multi-objective knapsack problem

In this article, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, … Read more

Note: A Graph-Theoretical Approach to Level of Repair Analysis

Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize … Read more

Approximate fixed-rank closures of set covering problems

We show that for any fixed rank, the closure of a set covering problem (and related problems) can be approximated in polynomial time — we can epsilon-approximate any linear program over the closure in polynomial time. Citation CORC report TR-2003-01, Computational Optimization Research Center, Columbia University Article Download View Approximate fixed-rank closures of set covering … Read more

Faster approximation algorithms for packing and covering problems

We adapt a method due to Nesterov so as to obtain an algorithm for solving block-angular fractional packing or covering problems to relative tolerance epsilon, while using a number of iterations that grows polynomially in the size of the problem and whose dependency on epsilon is proportional to 1/epsilon. Citation CORC report TR-2004-09, Computational Optimization … Read more

SENSITIVITY ANALYSIS IN CONVEX QUADRATIC OPTIMIZATION: INVARIANT SUPPORT SET INTERVAL

In sensitivity analysis one wants to know how the problem and the optimal solutions change under the variation of the input data. We consider the case when variation happens in the right hand side of the constraints and/or in the linear term of the objective function. We are interested to find the range of the … Read more

Performance of CONDOR, a Parallel, Constrained extension of Powell’s UOBYQA algorithm. Experimental results and comparison with the DFO algorithm.

This paper presents an algorithmic extension of Powell’s UOBYQA algorithm (”Unconstrained Optimization BY Quadratical Approximation”). We start by summarizing the original algorithm of Powell and by presenting it in a more comprehensible form. Thereafter, we report comparative numerical results between UOBYQA, DFO and a parallel, constrained extension of UOBYQA that will be called in the … Read more

Robust Profit Opportunities in Risky Financial Portfolios

For risky financial securities with given expected return vector and covariance matrix, we propose the concept of a robust profit opportunity in single and multiple period settings. We show that the problem of finding the “most robust” profit opportunity can be solved as a convex quadratic programming problem, and investigate its relation to the Sharpe … Read more

Adjustable Robust Optimization Models for Nonlinear Multi-Period Optimization

We study multi-period nonlinear optimization problems whose parameters are uncertain. We assume that uncertain parameters are revealed in stages and model them using the adjustable robust optimization approach. For problems with polytopic uncertainty, we show that quasi-convexity of the optimal value function of certain subproblems is sufficient for the reducibility of the resulting robust optimization … Read more