Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

Categories Linear, Cone and Semidefinite Programming Tags , , , ,

The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274–1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more

Existence and stability results based on asymptotic analysis for semidefinite linear complementarity problems

Categories Semi-definite Programming Tags , ,

This work is devoted to the study of existence and stability results of semidefinite linear complementarity problems (SDLCP). Our approach consists of approximating the variational inequality formulation of the SDLCP by a sequence of suitable chosen variational inequalities. This provides particular estimates for the asymptotic cone of the solution set of the SDLCP. We thus … Read more

Linear complementarity problems over symmetric cones: Characterization of Qb-transformations and existence results

Categories Linear, Cone and Semidefinite Programming Tags , , , ,

This paper is devoted to the study of the {symmetric cone linear complementarity problem} (SCLCP). In this context, our aim is to characterize the class Q_b in terms of larger classes, such as Q and R_0. For this, we introduce the class F and García’s transformations. We studied them for concrete particular instances (such as … Read more

Parallel algebraic multilevel Schwarz preconditioners for a class of elliptic PDE systems

Categories Systems governed by Differential Equations Optimization Tags , , , ,

We present algebraic multilevel preconditioners for linear systems arising from the discretization of systems of coupled elliptic partial differential equations (PDEs). These preconditioners are based on modifications of Schwarz methods and of the smoothed aggregation technique, where the coarsening strategy and the restriction and prolongation operators are defined using a point-based approach with a primary … Read more

Simultaneous Pursuit of Out-of-Sample Performance and Sparsity in Index Tracking Portfolios

Categories Applications - OR and Management Sciences, Finance and Economics Tags , , , , ,

Index tracking is a passive investment strategy in which an investor purchases a set of assets to mimic a market index. The tracking error, the difference between the performances of the index and the portfolio, may be minimized by buying all the assets contained in the index. However, this strategy results in a considerable amount … Read more

A preconditioning framework for sequences of diagonally modified linear systems arising in optimization

Categories Nonlinear Optimization Tags , , ,

We propose a framework for building preconditioners for sequences of linear systems of the form $(A+\Delta_k) x_k=b_k$, where $A$ is symmetric positive semidefinite and $\Delta_k$ is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region … Read more

The Gram dimension of a graph

Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , , ,

The Gram dimension $\gd(G)$ of a graph is the smallest integer $k \ge 1$ such that, for every assignment of unit vectors to the nodes of the graph, there exists another assignment of unit vectors lying in $\oR^k$, having the same inner products on the edges of the graph. The class of graphs satisfying $\gd(G) … Read more

The Lagrange method and SAO with bounds on the dual variables

Categories Constrained Nonlinear Optimization

We consider the general nonlinear programming problem with equality and inequality constraints when the variables x are confined to a compact set. We regard the Lagrange multipliers as dual variables lambda, those of the inequalities being nonnegative. For each lambda, we let phi(lambda) be the least value of the Lagrange function, which occurs at x=x(lambda), … Read more

About error bounds in metric spaces

Categories Nonsmooth Optimization

The paper presents a general primal space classification scheme of necessary and sufficient criteria for the error bound property incorporating the existing conditions. Several primal space derivative-like objects – slopes – are used to characterize the error bound property of extended-real-valued functions on metric sapces. CitationPublished in D. Klatte et al. (eds.), Operations Research Proceedings … Read more

Some remarks on stability of generalized equations

Categories Nonsmooth Optimization Tags , , ,

The paper concerns the computation of the graphical derivative and the regular (Frechet) coderivative of the solution map to a class of generalized equations, where the multi-valued term amounts to the regular normal cone to a (possibly nonconvex) set given by C2 inequalities. Instead of the Linear Independence qualification condition, standardly used in this context, … Read more