Fejer processes with diminishing disturbances and decomposition of constrained nondifferentiable optimization problems

Categories Convex and Nonsmooth Optimization Tags ,

Iterative processes based on Fejer mappings with diminishing problem-specific shifts in the arguments are considered. Such structure allows fine-tuning of Fejer processes by directing them toward selected subsets of attracting sets. Use of various Fejer operators provides ample opportunities for decomposition and parallel computations. Subgradient projection algorithms with sequential and simultaneous projections on segmented constraints … Read more

Robust Portfolio Optimization with Derivative Insurance Guarantees

Categories Finance and Economics, Robust Optimization Tags , , ,

Robust portfolio optimization finds the worst-case portfolio return given that the asset returns are realized within a prescribed uncertainty set. If the uncertainty set is not too large, the resulting portfolio performs well under normal market conditions. However, its performance may substantially degrade in the presence of market crashes, that is, if the asset returns … Read more

Hybrid MPI/OpenMP parallel support vector machine training

Categories Data-Mining, Parallel Algorithms, Quadratic Programming Tags , , ,

Support Vector Machines are a powerful machine learning technology, but the training process involves a dense quadratic optimization problem and is computationally challenging. A parallel implementation of Support Vector Machine training has been developed, using a combination of MPI and OpenMP. Using an interior point method for the optimization and a reformulation that avoids the … Read more

Theta Bodies for Polynomial Ideals

Categories Approximation Algorithms, Semi-definite Programming Tags , ,

Inspired by a question of Lov\’asz, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal, called theta bodies of the ideal. For the stable set problem in a graph, the first theta body in this hierarchy is exactly Lov{\’a}sz’s theta body of the graph. … Read more

Solving multi-objective network flow problems with an interior point method

Categories Linear Programming, Multi-Criteria Optimization, Network Optimization Tags , , ,

In this paper we present a primal-dual interior-point algorithm to solve a class of multi-objective network flow problems. More precisely, our algorithm is an extension of the single-objective primal-dual infeasible and inexact interior point method for multi-objective linear network flow problems. A comparison with standard interior point methods is provided and experimental results on bi-objective … Read more

OSPF Routing with Optimal Oblivious Performance Ratio Under Polyhedral Demand Uncertainty

Categories Network Optimization, Robust Optimization, Telecommunications Tags , , , , , ,

We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and the performance of each routing is assessed on … Read more

Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion

Categories Semi-definite Programming Tags , , ,

A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two … Read more

A Line Search Exact Penalty Method Using Steering Rules

Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , ,

Line search algorithms for nonlinear programming must include safeguards to enjoy global convergence properties. This paper describes an exact penalization approach that extends the class of problems that can be solved with line search SQP methods. In the new algorithm, the penalty parameter is adjusted at every iteration to ensure sufficient progress in linear feasibility … Read more

Approximate Level Method

Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

In this paper we propose and analyze a variant of the level method [4], which is an algorithm for minimizing nonsmooth convex functions. The main work per iteration is spent on 1) minimizing a piecewise-linear model of the objective function and on 2) projecting onto the intersection of the feasible region and a polyhedron arising … Read more

Simultaneously solving seven optimization problems in relative scale

Categories Linear Programming, Nonsmooth Optimization, Statistics Tags , , , , , , , , , , , , , ,

In this paper we develop and analyze an efficient algorithm which solves seven related optimization problems simultaneously, in relative scale. Each iteration of our method is very cheap, with main work spent on matrix-vector multiplication. We prove that if a certain sequence generated by the algorithm remains bounded, then the method must terminate in $O(1/\delta)$ … Read more