A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.

M. Dyer, R. Kannan, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.
Original languageEnglish
Pages (from-to)207-229
JournalMathematical Programming
Issue number147
DOIs
Publication statusPublished - 2014

Fingerprint

Stochastic programming
Stochastic Programming
Convex optimization
Randomized Algorithms
Convex Optimization
Concave function
Evaluation Function
Convex Sets
Function evaluation
Polynomial function
Approximation Scheme
Polyhedron
Smoothing
Smoothness
Objective function
Polynomial approximation
Polynomial
Evaluation
Model
Polynomials

Cite this

@article{2fdb271c1ce1492ca27554bd5dd8a507,
title = "A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.",
abstract = "We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.",
author = "M. Dyer and R. Kannan and L. Stougie",
year = "2014",
doi = "10.1007/s10107-013-0718-0",
language = "English",
pages = "207--229",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "147",

}

A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming. / Dyer, M.; Kannan, R.; Stougie, L.

In: Mathematical Programming, No. 147, 2014, p. 207-229.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.

AU - Dyer, M.

AU - Kannan, R.

AU - Stougie, L.

PY - 2014

Y1 - 2014

N2 - We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.

AB - We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.

U2 - 10.1007/s10107-013-0718-0

DO - 10.1007/s10107-013-0718-0

M3 - Article

SP - 207

EP - 229

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 147

ER -