A regularized smoothing method for fully parameterized convex problems with applications to convex and nonconvex two-sta
- PDF / 999,285 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 22 Downloads / 213 Views
Series B
A regularized smoothing method for fully parameterized convex problems with applications to convex and nonconvex two-stage stochastic programming Pedro Borges1 · Claudia Sagastizábal2
· Mikhail Solodov1
Received: 5 January 2020 / Accepted: 13 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be convex. One motivating application of interest is two-stage (possibly nonconvex) stochastic programming. We show that our approach, being computationally implementable, provides locally bounded upper bounds for the subdifferential of the value function of qualified convex problems. As a by-product of our development, we also recover that in the given setting the value function is locally Lipschitz continuous. Numerical experiments are presented for two-stage convex stochastic programming problems, comparing the approach with the bundle method for nonsmooth optimization. Keywords Smoothing techniques · Interior penalty solutions · Tikhonov regularization · Nonconvex stochastic programming · Two-stage stochastic programming · Lipschitz continuity of value functions Mathematics Subject Classification 90C15 · 65K05 · 90C25 · 65K10 · 46N10
B
Claudia Sagastizábal [email protected] Pedro Borges [email protected] Mikhail Solodov [email protected]
1
Instituto de Matemática Pura e Aplicada, Rio de Janeiro, RJ, Brazil
2
IMECC/UNICAMP, Campinas, São Paulo, Brazil
123
P. Borges et al.
1 Introduction and motivation This work focuses on developing computationally implementable smoothing methods for a family of parametric convex programming problems, noting that all the functions are differentiable but the parametric dependence can be arbitrary. As one motivating application, the approach provides approximations to (possibly nonconvex) stochastic programs, as long as they exhibit certain structure suitable to our theory. The setting can be illustrated by the following abstract stochastic programming problem formulation: min f 0 (x) := R[F(x, ξ(ω))], x∈X
(1)
where R is a risk measure [15, Chap. 6], and F(x, ξ ) is a real-valued function of the decision variables x ∈ X ⊂ Rnx . The random vector ξ(ω) has known probability distribution, with finite support described by scenarios ξs and probabilities ps ∈ (0, 1) for s = 1, . . . S. We start with an example when problem (1) is convex. Consider a two-stage stochastic linear program ⎧ ⎪ ⎨ ⎪ ⎩
min c x + s.t. x ∈ X
S s=1
ps Qs (x)
⎧ ⎨ min qs y for Qs (x) := s.t. W y = h s − Ts x ⎩ y ≥ 0,
(2)
where the involved vectors
Data Loading...
