We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more
We consider the computational complexity of optimizing various classes of continuous functions over a simplex, hypercube or sphere. These relatively simple optimization problems have many applications. We review known approximation results as well as negative (inapproximability) results from the recent literature. Citation CentER Discussion paper 2006-85 Tilburg University THe Netherlands Article Download View The complexity … Read more
Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2006). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In … Read more
We consider the fundamental problem of computing an optimal portfolio based on a quadratic mean-variance model of the objective function and a given polyhedral representation of the constraints. The main departure from the classical quadratic programming formulation is the inclusion in the objective function of piecewise linear, separable functions representing the transaction costs. We handle … Read more
The n-step mixed integer rounding (MIR) functions are used to generate n-step MIR inequalities for (mixed) integer programming problems (Kianfar and Fathi, 2006). We show that these functions are sources for generating extreme valid inequalities (facets) for group problems. We first prove the n-step MIR function, for any positive integer n, generates two-slope facets for … Read more
We study in this paper a Markov Decision Problem (MDP) with continuous state space and discrete decision variables. We propose an extension of the Q-learning algorithm introduced to solve this problem by Watkins in 1989 for completely discrete MDPs. Our algorithm relies on stochastic approximation and functional estimation, and uses kernels to locally update the … Read more
We present a new primal-dual algorithm for convex quadratic multicriteria optimization. The algorithm is able to adaptively refine the approximation to the set of efficient points by way of a warm-start interior-point scalarization approach. Results of this algorithm when applied on a three-criteria real-world power plant optimization problem are reported, thereby illustrating the feasibility of … Read more
The notion of soft thresholding plays a central role in problems from various areas of applied mathematics, in which the ideal solution is known to possess a sparse decomposition in some orthonormal basis. Using convex-analytical tools, we extend this notion to that of proximal thresholding and investigate its properties, providing in particular several characterizations of … Read more
A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both … Read more
In this paper, we study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP). This set is a generalization of the traditional 0-1 knapsack polytope and the 0-1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its … Read more