A bundle method for nonsmooth DC programming with application to chance-constrained problems
- PDF / 2,291,160 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 250 Views
A bundle method for nonsmooth DC programming with application to chance-constrained problems W. van Ackooij1 · S. Demassey2 · P. Javal1,2 W. de Oliveira2 · B. Swaminathan1
· H. Morais3
·
Received: 3 February 2020 / Accepted: 25 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This work considers nonsmooth and nonconvex optimization problems whose objective and constraint functions are defined by difference-of-convex (DC) functions. We consider an infeasible bundle method based on the so-called improvement functions to compute critical points for problems of this class. Our algorithm neither employs penalization techniques nor solves subproblems with linearized constraints. The approach, which encompasses bundle methods for nonlinearly-constrained convex programs, defines trial points as solutions of strongly convex quadratic programs. Different stationarity definitions are investigated, depending on the functions’ structures. The approach is assessed in a class of nonsmooth DC-constrained optimization problems modeling chance-constrained programs. Keywords DC programming · Nonsmooth optimization · Variational analysis · Chance constraints
B
P. Javal [email protected]
1
EDF R&D, Boulevard Gaspard Monge, Paris, France
2
MINES ParisTech, CMA – Centre de Mathématiques Appliquées, PSL – Research University, Sophia-Antipolis, France
3
INESC-ID, Department of Electrical and Computer Engineering, Instituto Superior Técnico-IST, Universidade de Lisboa, Lisbon, Portugal
123
W. van Ackooij et al.
1 Introduction In this work we are concerned with nonsmooth and nonconvex optimization problems of the form min f (x), with f (x) := f 1 (x) − f 2 (x) and
x∈X c c
X := {x ∈ X : c1 (x) − c2 (x) ≤ 0}
(1)
where X is a nonempty bounded polyhedron contained in an open set Ω ⊂ Rn , and the functions f 1 , f 2 , c1 , c2 : Ω → R are all convex but possibly nonsmooth. In this setting, there is no loss of generality in considering the scalar constraint function c(x) := c1 (x) − c2 (x): if the problem possesses m DC constraints c1,i (x) − c2,i (x) ≤ 0, i = 1, . . . , m, then we can represent these constraints as maxi=1,...,m {c1,i (x) − to the scalar function of (1) with c2,i (x)} ≤ 0, which is equivalent mDC decomposition c2,i (x); see for c1 (x) := maxi=1,...,m [c1,i (x) + mj=i c2, j (x)] and c2 (x) := i=1 instance [27, Prop. 4.1(ii)]. Note that the latter is a smooth function provided that all c2, j , j = 1, . . . , m, are smooth. Industrial applications fitting (1) include bilevel optimization problems originating from energy management [31], reformulation of mixed-binary problems [27], chance-constrained energy management problems [8], gas network management under uncertainty [12], and others [19,27]. The motivation of this work is chance-constrained optimization, that is, optimization problems having a probability constraint of the form P[x ∈ M(ξ )] ≥ p .
(2)
In this notation, M(ξ ) ⊂ Rn is a random set depending on the random vector ξ (in a given sample space
Data Loading...
