Direct search based on probabilistic feasible descent for bound and linearly constrained problems

Direct search is a methodology for derivative-free optimization whose iterations are characterized by evaluating the objective function using a set of polling directions. In deterministic direct search applied to smooth objectives, these directions must somehow conform to the geometry of the feasible region, and typically consist of positive generators of approximate tangent cones (which then renders the corresponding methods globally convergent in the linearly constrained case). One knows however from the unconstrained case that randomly generating the polling directions leads to better complexity bounds as well as to gains in numerical efficiency, and it becomes then natural to consider random generation also in the presence of constraints. In this paper, we study a class of direct-search methods based on sufficient decrease for solving smooth linearly constrained problems where the polling directions are randomly generated (in approximate tangent cones). The random polling directions must satisfy probabilistic feasible descent, a concept which reduces to probabilistic descent in the absence of constraints. Such a property is instrumental in establishing almost-sure global convergence and worst-case complexity bounds with overwhelming probability. Numerical results show that the randomization of the polling directions can be beneficial over standard approaches with deterministic guarantees, as it is suggested by the respective worst-case complexity bounds.

1. When developing the convergence theory in the deterministic case, mostly in [27], then in [23], the authors have considered a formulation only involving linear inequality constraints. In [25], they have suggested to include linear equality constraints by adding to the positive generators of the approximate normal cone the transposed rows of A and their negatives, which in turn implies that the tangent cone lies in the null space of A. In this paper, we take an equivalent approach by explicitly considering the iterates in \({{\,\mathrm{null}\,}}(A)\). Not only does this allow a more direct application of the theory in [23, 27], but it also renders the consideration of the particular cases (only bounds or only linear equalities) simpler.

2. \(V^c_k\) corresponds to the coordinate vectors in \(T_k\) for which their negatives do not belong to \(V_k\), and hence the corresponding variables must be subject to bound constraints. Since there only are \(n_b\) bound constraints, one has \(0 \le |V_k^c| \le n_b\).

Authors and Affiliations

1. IRIT, University of Toulouse, 2 rue Charles Camichel, B.P. 7122, 31071, Toulouse Cedex 7, France

   S. Gratton

2. Wisconsin Institute for Discovery, University of Wisconsin-Madison, 330 N Orchard Street, Madison, WI, 53715, USA

   C. W. Royer

3. CMUC, Department of Mathematics, University of Coimbra, 3001-501, Coimbra, Portugal

   L. N. Vicente

4. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, China

   Z. Zhang

Corresponding author

Correspondence to C. W. Royer.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Support for C. W. Royer was partially provided by Université Toulouse III Paul Sabatier under a doctoral grant. Support for L. N. Vicente was partially provided by FCT under Grants UID/MAT/00324/2013 and P2020 SAICTPAC/0011/2015. Support for Z. Zhang was provided by the Hong Kong Polytechnic University under the Start-up Grant 1-ZVHT.

A Deterministic computation of positive cone generators

Provided a certain linear independence condition is satisfied, the positive generators of the approximate tangent cone can be computed as follows (see [25, Proposition 5.2]).

Proposition A.1

Let \(x \in \mathcal {F}\), \(\alpha > 0\), and assume that the set of generators of \(N(x,\alpha )\) has the form \(\left[ \, W_e\ \, -\!W_e\ \; W_i \,\right] \). Let B be a basis for the null space of \(W_e^\top \), and suppose that \(W_i^\top B = Q^\top \) has full row rank. If R is a right inverse for \(Q^\top \) and N is a matrix whose columns form a basis for the null space of \(Q^\top \), then the set

positively generates \(T(x,\alpha )\).

Note that the number of vectors in Y is then \(n_R+2(n_B-n_R)=2n_B - n_R\), where \(n_B\) is the rank of B and \(n_R\) is that of Q (equal to number of columns of R). Since \(n_B < {\tilde{n}}\), we have that \(|Y| \le 2 {\tilde{n}}\).

In the case where \(W_i^\top B\) is not full row rank, one could consider all subsets of columns of \(W_i\) of largest size that yield full row rank matrices, obtain the corresponding positive generators by Proposition A.1, and then take the union of all these sets [34]. Due to the combinatorial nature of this technique, we adopted a different approach, following the lines of [22, 25] where an algorithm originating from computational geometry called the double description method [16] was applied. We implemented this algorithm to compute a set of extreme rays (or positive generators) for a polyhedral cone of the form \(\{ {\tilde{d}} \in \mathbb {R}^{{\tilde{n}}}: B {\tilde{d}} = 0, C {\tilde{d}} \ge 0 \}\), where we assume that \({{\,\mathrm{rank}\,}}(B) < {\tilde{n}}\), and applied it to the approximate tangent cone. In our experiments, the three variants detected degeneracy (and thus invoked the double description method) in less than 2% of the iterations on average.

B Proof of Proposition 7.1

Proof

To simplify the notation, we omit the index k in the proof. By our convention about \({{\,\mathrm{cm}\,}}_T(V, -{\tilde{G}})\) when \(P_T[{\tilde{G}}]=0\), we only need to consider the situation where \(P_T[{\tilde{G}}]\) is nonzero.

Define the event

and let \(\bar{\mathcal {E}}\) denote its complementary event. We observe that

for each \(\kappa \). Indeed, when \(\mathcal {E}\) happens, we have

and (B.1) is consequently true; when \(\bar{\mathcal {E}}\) happens, then by the orthogonal decomposition

we know that \(\Vert P_{T^c}[{\tilde{G}}]\Vert /\Vert P_{T}[{\tilde{G}}]\Vert \ge 1/\sqrt{2}\), and hence

which gives us (B.2). Since the events on the right-hand sides of (B.1) and (B.2) are mutually exclusive, the two inclusions lead us to

Then it suffices to show the existence of \(\kappa \in (0,1)\) and \(p \in (p_0,1)\) that fulfill simultaneously

because \({\mathbf {1}}_{\mathcal {E}} + {\mathbf {1}}_{\bar{\mathcal {E}}}=1\). If \(\mathbb {P}(\mathcal {E}) = 0\), then (B.3) holds trivially regardless of \(\kappa \) or p. Similar things can be said about \(\bar{\mathcal {E}}\) and (B.4). Therefore, we assume that both \(\mathcal {E}\) and \(\mathcal {{\bar{E}}}\) are of positive probabilities. Then, noticing that \(\mathcal {E}\in \sigma \) (\(\mathcal {E}\) only depends on the past iterations), we have

where \(\sigma \cap \mathcal {E}\) is the trace \(\sigma \)-algebra [35] of \(\mathcal {E}\) in \(\sigma \), namely \(\sigma \cap \mathcal {E} = \left\{ \mathcal {A} \cap \mathcal {E} \mathrel : \mathcal {A} \in \sigma \right\} \), and \(\sigma \cap \bar{\mathcal {E}}\) is that of \(\bar{\mathcal {E}}\). Hence it remains to prove that

Let us examine \({{\,\mathrm{cm}\,}}_S(U^s, -{\tilde{G}})\) whenever \(\mathcal {E}\) happens (which necessarily means that S is nonzero). Since \(\mathcal {E}\) depends only on the past iterations, while \(U^s\) is essentially a set of \(r_s\) (recall (7.1)) i.i.d. directions from the uniform distribution on the unit sphere in \(\mathbb {R}^s\) with \(s=\dim (S) \le {\tilde{n}}\), one can employ the theory of [19, Appendix B] to justify the existence of \(p_s > p_0\) and \(\tau > 0\) that are independent of \({\tilde{n}}\) or s (solely depending on \(\theta \) and \(\gamma \)) and satisfy

Now consider \({{\,\mathrm{cm}\,}}_{T^c}(U^c, -{\tilde{G}})\) under the occurrence of \(\bar{\mathcal {E}}\) (in that case, \(T^c\) is nonzero and \(V^c\) is nonempty). Let \(D^*\) be a direction in \(V^c\) that achieves

Then by the fact that \(U^c\) is a uniform random subset of \(V^c\) and \( |U^c| = \lceil p_c |V^c| \rceil \), we have

Let

where \(\lambda (\cdot )\) is defined as in (3.2) and \({\mathbf {T}}\) denotes all possible occurrences for the approximate tangent cone. Then \(\kappa _c > 0\) and \({{\,\mathrm{cm}\,}}_{T^c} (V^c, -{\tilde{G}}) \ge \kappa _c\). Hence (B.8) implies

Finally, set

Then \(\kappa \in (0,1)\), \(p \in (p_0, 1)\), and they fulfill (B.5) and (B.6) according to (B.7) and (B.9). Moreover, \(\kappa \) depends on the geometry of T, and consequently depends on m, n, and \(m_{\mathcal {I}}\), while p depends solely on \(\theta \), \(\gamma \), and \(p_c\). The proof is then completed. \(\square \)

C List of CUTEst problems

The complete list of our test problems, with the associated dimensions and number of constraints, is provided in Tables 1, 2, 3 and 4.

Reprints and permissions