A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization

DOI10.1007/S10898-017-0571-4MaRDI QIDQ1704920zbMATH OpenOpenAlexFDO

Authors Christoph Buchheim, M. De Santis, F. Rinaldi, Long Trieu

Publication date 13 March 2018

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05914

zbMATH Keywords

global optimizationmixed-integer programmingmean-risk optimization

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Applications of mathematical programming (90C90) Integer programming (90C10)

Abstract: We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. We address this class of convex mixed-integer minimization problems by designing a branch-and-bound algorithm, where at each node, the continuous relaxation is solved by a non-monotone Frank-Wolfe type algorithm with away-steps. Experimental results on portfolio optimization problems show that our approach can outperform the MISOCP solver of CPLEX 12.6 for instances where a linear risk-weighting function is considered.

Recommendations

• A branch and bound algorithm for solving mean-risk-skewness portfolio models
• Integer programming approaches in mean-risk models
• An exact solution approach for portfolio optimization problems under stochastic and integer constraints
• Polymatroids and mean-risk minimization in discrete optimization
• A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs

Cites work

• scientific article; zbMATH DE number 46303 (Why is no real title available?)
• A Nonmonotone Line Search Technique for Newton’s Method
• A feasible active set method with reoptimization for convex quadratic mixed-integer programming
• A new method for mean-variance portfolio optimization with cardinality constraints
• A truncated Newton method with non-monotone line search for unconstrained optimization
• Benchmarking optimization software with performance profiles.
• Convergence Rates for Conditional Gradient Sequences Generated by Implicit Step Length Rules
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Lagrangean decomposition for mean-variance combinatorial optimization
• New analysis and results for the Frank-Wolfe method
• Nonmonotone globalization techniques for the Barzilai-Borwein gradient method
• Optimal Inequalities in Probability Theory: A Convex Optimization Approach
• Polymatroids and mean-risk minimization in discrete optimization
• Some comments on Wolfe's ‘away step’
• The convergence of equilibrium algorithms with non-monotone line search technique.
• Validation of subgradient optimization

Cited in

(3)

• An oracle-based framework for robust combinatorial optimization
• Robust combinatorial optimization under convex and discrete cost uncertainty
• On the exactness of the \(\varepsilon\)-constraint method for biobjective nonlinear integer programming

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704920)