Non-monotone derivative-free algorithm for solving optimization models with linear constraints: extensions for solving n
- PDF / 2,973,246 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 115 Downloads / 215 Views
Non‑monotone derivative‑free algorithm for solving optimization models with linear constraints: extensions for solving nonlinearly constrained models via exact penalty methods Ubaldo M. García‑Palomares1,2 Received: 18 January 2020 / Accepted: 13 February 2020 © Sociedad de Estadística e Investigación Operativa 2020
Abstract This paper describes a non-monotone direct search method (NMDSM) that finds a stationary point of linearly constrained minimization problems. At each iteration the algorithm uses NMDSM techniques on the Euclidean space ℝn spanned by n variables carefully selected from the n + m variables formulated by the model under analysis. These variables are obtained by simple rules and are handled with pivot transformations frequently used in the solution of linear systems. A new weaker 0-order non smooth necessary condition is suggested, which transmute to other stationarity conditions, depending upon the kind of differentiability present in the system. Convergence with probability 1 is proved for non smooth functions. The algorithm is tested numerically on a set of small to medium size problems that have exhibited serious difficulties for their solution by other optimization techniques. The paper also considers possible extensions to non-linearly constrained problems via exact penalty function and a slightly modified algorithm satisfactorily solved a multi-batch multi-product plant that was modeled as a MINLP. Keywords Non monotone direct search method · 0-Order stationarity · Linear and non linear constraints · Exact penalty functions Mathematics Subject Classification 90-08
* Ubaldo M. García‑Palomares [email protected]; [email protected] 1
Dep. Procesos y Sistemas, Universidad Simón Bolívar, Caracas 1080, Venezuela
2
Information Technology Group, Atlantic, Universidad de Vigo, 36310 Vigo, Spain
13
Vol.:(0123456789)
U. M. García‑Palomares
1 Notation We will use a rather standard notation with the following peculiarities: The subindex i will always refer to the iteration number. All instances that change from iteration to iteration may be subscribed by i, but some times we dropped this index when it is clear from the context. • Lower Greek letters represent scalar values • Lower Roman letters stand for element in ℝn except • • • •
f (⋅) ∶ ℝn → ℝ , the objective function of an optimization model. gj (⋅) ∶ ℝn → ℝ, j = 1, … , r , nonlinear inequality constraints c(⋅) ∶ ℝn → ℝ+ , a non negative penalty function i, j, k, m, n, p, q, r, integers
• Superscripts are components and subscripts are different elements in ℝn
uT v is the internal product of 2 elements in ℝn uvT is an n × n matrix matrix f (x+𝜏i d)−f (x) • f 0 (x, d) = lim𝜏→0 is the directional derivative at x along d 𝜏i f (x+𝜏i d)−f (x) � is the generalized directional deriva f (x∗ , d∗ ) = lim𝜏→0,xi →x∗ ,di →d∗ 𝜏 i
tive • Upper Case Roman letters represent sets, except
• F(x;𝜌) = f (x) ∗ 𝜌c(x) , the aggregate function • I, the identity matrix • H = (I − 2uuT ) , the Householder matrix; uT u = 1 • N − B , the difference set:
Data Loading...
