# Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

Baiwei Guo, Yuning Jiang, Maryam Kamgarpour, Giancarlo Ferrari-Trecate This
work was supported by the Swiss National Science Foundation under the NCCR
Automation (grant agreement 51NF40_80545).Baiwei Guo and Giancarlo Ferrari-
Trecate are with the DECODE group, Institute of Mechanical Engineering, EPFL,
Switzerland. email: {baiwei.guo<EMAIL_ADDRESS>Jiang is with the Predict group, IGM, EPFL, Switzerland. email:
<EMAIL_ADDRESS>Kamgarpour is with the Systems Control And
Multiagent Optimization Research (sycamore) labs at IGM, EPFL,
<EMAIL_ADDRESS>
###### Abstract

We address black-box convex optimization problems, where the objective and
constraint functions are not explicitly known but can be sampled within the
feasible set. The challenge is thus to generate a sequence of feasible points
converging towards an optimal solution. By leveraging the knowledge of the
smoothness properties of the objective and constraint functions, we propose a
novel zeroth-order method, SZO-QQ, that iteratively computes quadratic
approximations of the constraint functions, constructs local feasible sets and
optimizes over them. We prove convergence of the sequence of the objective
values generated at each iteration to the minimum. Through experiments, we
show that our method can achieve faster convergence compared with state-of-
the-art zeroth-order approaches to convex optimization.

##  I Introduction

Applications ranging from energy resources operation [1], machine learning [2]
and trajectory optimization [3] to optimal control tuning [4] often require
solving complex optimization problems where the fulfillment of the hard
constraints is essential. In case the modelling of the objective and
constraint functions is not available or the given data from safe system
operation is not sufficient for modelling, zeroth-order optimization methods
can be used to derive the optimum without violation of constraints. The
methods of this category only rely on the possibility of sampling the unknown
objective and constraint functions evaluated at a set of chosen points [5].
The decision variables are then iteratively updated using the collected
evaluations.

Classical techniques for zeroth-order unconstrained optimization can be
classified as direct-search-based (where a set of points around the current
point is searched for a lower value of the objective function) and model-based
(where a local model of the objective function around the current point is
built and used for local optimization) [6, Chapter 9]. Examples for these two
categories are, respectively, pattern search methods [7] and trust region
methods [8]. For constrained problems, a common approach is to include in the
cost barrier functions penalizing constraint violations so as to cast the
constrained optimization problem into an unconstrained one [9, 10]. By
adopting log barrier functions to penalize the proximity towards the boundary
of the feasible set, Extremum Seeking methods estimate the gradient of the new
objective function by adding sinusoidal perturbations to the decision
variables [11]. However, most penalty-based methods lack a mechanism to tune
the penalty coefficients for ensuring feasible sampling.

To guarantee feasible sampling with a high probability, [12] proposes an
iterative algorithm, called SafeOpt, that expands the estimated feasible set
by modeling the constraints as Gaussian processes. However, the computational
complexity of this algorithm scales exponentially with the number of the
decision variables. To address this issue, a gradient-descent penalty-based
approach, called s0-LBM, is proposed in [13]. This method exploits the
constraint functions’ smoothness to calculate the step size of the descent.
Although this method can address non-convex problems and comes with a worst-
case complexity that is polynomial in problem dimension, it might converge
slowly, even for convex problems. The reason is that as the iterates approach
the boundary of the feasible set, the log-barrier function and its derivative
become very large, leading to very conservative local feasible sets that
result in slow progress of the iterates. The work [14] addresses the zeroth-
order optimization of convex objectives subject to unknown polytopic
constraints. It ensures sampling feasibility by estimating the polytope
iteratively and constructing confidence bounds for the estimates. While the
optimization algorithm in [14] enjoys faster convergence than [13], the
approach is not readily generalizable to nonlinear constraints.

Contributions: In this work, we aim to solve convex optimization problems
based on Lipschitz and smoothness constants instead of the exact knowledge of
the objective and constraint functions. To achieve fast convergence, we
approximate the constraint functions with known quadratic functions (in
contrast to the affine approximation used in [12, 13]) and tackle the
optimization problem by solving a series of known Quadratically Constrained
Quadratic Programs (QCQP). Our main contributions are summarized as follows:

  1. 1.

a method to construct local feasible sets, which is less conservative than
those in [12, 13] when the subproblem solutions are close to the boundary of
the original feasible set. To this purpose we use local quadratic
approximations of the constraints based on the knowledge of the Lipschitz
constants of the constraints’ gradients;

  2. 2.

a zeroth-order optimization algorithm where sampling feasibility is guaranteed
and the objective function values provably converge to the minimum;

  3. 3.

numerical examples comparing the speed of convergence of our method with
state-of-the-art alternative approaches as well as an application of the
proposed algorithm to an optimal control problem.

Notations: We use $e_{i}\in\mathbb{R}^{d}$ to define the $i$-th standard basis
of vector space $\mathbb{R}^{d}$. Given a vector $x\in\mathbb{R}^{d}$ and a
scalar $\epsilon>0$, we write $x=[x^{(1)},\ldots,x^{(d)}]^{\top}$ and
$\mathcal{B}_{\epsilon}(x)=\\{y:\|y-x\|\leq\epsilon\\}$, where $\|\cdot\|$ is
the 2-norm. We define $\mathbb{Z}_{i}^{j}=\\{i,i+1,\ldots,j\\}$.

##  II Problem Formulation

We address the constrained convex optimization problem

$\min_{x\in\mathbb{R}^{d}}\;\;f_{0}(x)\quad\text{subject to}\;\;x\in\Omega,$
(1)

where $\Omega:=\\{x\in\mathbb{R}^{d}:f_{i}(x)\leq 0,i\in\mathbb{Z}_{1}^{m}\\}$
is the feasible set. We consider the setting where the convex functions
$f_{i}:\mathbb{R}^{d}\to\mathbb{R}$, $i\in\mathbb{Z}^{n}_{1}$, are not
explicitly known but they can be queried within $\Omega$. We further assume,
without loss of generality, the convex objective function $f_{0}(x)$ is
explicitly known and linear. Indeed, when the convex function $f_{0}(x)$ in
(1) is not known but can be queried, the problem in (1) can be written as

$\displaystyle\min_{(x,\gamma)\in\mathbb{R}^{d+1}}$ $\displaystyle\gamma$
$\displaystyle\mathrm{subject\;to}$ $\displaystyle f_{0}(x)-\gamma\leq 0,$
$\displaystyle f_{i}(x)\leq 0,\quad i\in\mathbb{Z}_{1}^{m},$

where the objective function is now known and linear.

We also consider the following assumptions on the smoothness of the objective
and constraint functions and the availability of a strictly feasible point.

###### Assumption 1

The functions $f_{i}(x)$, $i\in\mathbb{Z}_{0}^{m}$ are continuously
differentiable and satisfy for any $x_{1}$, $x_{2}\in\mathbb{R}^{d}$,

$\displaystyle|f_{i}(x_{1})-f_{i}(x_{2})|$ $\displaystyle\leq
L_{i}\|x_{1}-x_{2}\|,$ (2) $\displaystyle\|\nabla f_{i}(x_{1})-\nabla
f_{i}(x_{2})\|$ $\displaystyle\leq M_{i}\|x_{1}-x_{2}\|.$

In the following, we use the notation $L_{\max}:=\max_{i\geq 1}L_{i}$,
$M_{\max}:=\max_{i\geq 1}M_{i}$,
$L_{i,\text{inf}}:=\inf\\{L:\|f_{i}(x_{1})-f_{i}(x_{2})\|\leq
L\|x_{1}-x_{2}\|,\forall x_{1},x_{2}\in\Omega\\}$ and
$M_{i,\text{inf}}:=\inf\\{M:\|\nabla f_{i}(x_{1})-\nabla f_{i}(x_{2})\|\leq
M\|x_{1}-x_{2}\|,\forall x_{1},x_{2}\in\Omega\\}$.

###### Remark 1

The bounds in (2) are utilized in several works on zeroth-order optimization,
e.g., [15, 16]. As it will be clear in the sequel, these bounds allow one to
estimate the error of local approximations of the unknown functions and their
derivatives. Moreover, our method does not require to precisely know
$L_{i,\text{inf}}$ and $M_{i,\text{inf}}$, but only upper bounds to their
values, see Remark 4.

###### Assumption 2

There exists a known strictly feasible point $x_{0}$, i.e., $f_{i}(x_{0})<0$
for all $i\in\mathbb{Z}_{1}^{m}$.

###### Remark 2

The existence of a strictly feasible point is called Slater’s Condition and
commonly assumed in several optimization methods [17]. Moreover, several works
on safe learning [12, 14] assume that a strictly feasible point is given to
initialize the algorithm. This is necessary for designing an algorithm whose
iterates remain feasible since the constraint functions are unknown a priori.
Practically, this assumption holds in several applications. For example, in
any robot mission planning, the robot is placed initially at a safe point and
needs to gradually explore the neighboring regions while ensuring feasibility
of its trajectory. Similarly, in the optimization of manufacturing processes,
often an initial set of (suboptimal) design parameters that satisfy the
problem constraints are known [18].

###### Assumption 3

There exists $\beta\in\mathbb{R}$ such that the sublevel set
$\mathcal{P}_{\beta}=\\{x\in\Omega:f_{0}(x)\leq\beta\\}$ is bounded and
includes the initial feasible point $x_{0}$.

The above assumption ensures the iterates remain bounded and have a convergent
subsequence (due to compactness of $\mathcal{P}_{\beta}$) as will be shown in
Theorem 2.

Based on the aforementioned assumptions and properties, in the next section we
design an algorithm that iteratively optimizes $f_{0}(x)$ over local safe sets
constructed by exploiting Assumption 1 on smoothness.

##  III The Proposed Zeroth-Order Algorithm

Here, we propose an approach to construct local feasible sets around a given
feasible point using function queries. To do so, we first recall properties of
a gradient estimator constructed through finite differences.

The gradients of the unknown functions $\\{f_{i}\\}_{i=1}^{m}$ can be
approximated through finite differences as

${\nabla}^{\nu}f_{i}\left(x\right):=\sum_{j=1}^{d}\frac{f_{i}\left(x+\nu
e_{j}\right)-f_{i}\left(x\right)}{\nu}e_{j}$ (3)

with $\nu>0$. The estimation error is denoted as

$\Delta^{\nu}_{i}(x):={\nabla}^{\nu}f_{i}\left(x\right)-\nabla f_{i}(x).$

From (2), we have the following result.

######  Lemma 1 ([19], Theorem 3.2)

Under Assumption 1, the gradient estimation error at $x\in\mathbb{R}^{d}$ can
be bounded as

$\left\|\Delta^{\nu}_{i}(x)\right\|_{2}\leq\alpha_{i}\nu,\text{ with
}\alpha_{i}=\frac{\sqrt{d}M_{i}}{2}.$ (4)

###  III-A Local feasible set construction

Based on the estimated gradient and the error bound above, we build a local
feasible set around a feasible point $x_{0}$.

###### Theorem 1

For any strictly feasible point $x_{0}$, let
$l^{*}=\min_{i=1,\dots,m}-f_{i}(x_{0})/L_{\mathrm{max}}\text{ and
}\nu^{*}=2l^{*}/\sqrt{d}$. Define

$\displaystyle\mathcal{S}^{\circ}_{i}(x_{0}):=$
$\displaystyle\big{\\{}x:f_{i}(x_{0})+{\nabla}^{\nu^{*}}f_{i}\left(x_{0}\right)^{\top}(x-x_{0})+$
(5) $\displaystyle\qquad\qquad\qquad\quad 2M_{i}\|x-x_{0}\|^{2}\leq
0\big{\\}}.$

Under Assumption 1, the set
$\mathcal{S}^{\circ}(x_{0}):=\bigcap^{m}_{i=1}\mathcal{S}^{\circ}_{i}(x_{0})$
satisfies $\mathcal{S}^{\circ}(x_{0})\subset\Omega$.

Proof. We first partition $\mathcal{S}^{\circ}_{i}(x_{0})$ as

$\mathcal{S}^{\circ}_{i}(x_{0})=\left(\mathcal{S}^{\circ}_{i}(x_{0})\bigcap\mathcal{B}_{l^{*}}(x_{0})\right)\bigcup\left(\mathcal{S}^{\circ}_{i}(x_{0})\setminus\mathcal{B}_{l^{*}}(x_{0})\right)$

and notice that
$\mathcal{S}^{\circ}_{i}(x_{0})\bigcap\mathcal{B}_{l^{*}}(x_{0})\subseteq\Omega$.
Then, it only remains to check that
$\mathcal{S}^{\circ}_{i}(x_{0})\setminus\mathcal{B}_{l^{*}}(x_{0})\subseteq\Omega.$

For $x\in\mathcal{S}^{\circ}_{i}(x_{0})\setminus B_{l^{*}}(x_{0})$, we have
$\frac{\sqrt{d}\nu^{*}}{2}=l^{*}\leq\|x-x_{0}\|.$ By the mean value theorem,
for any $i$ there exists $\theta_{i}\in[0,1]$ such that

$\displaystyle f_{i}(x)=$ $\displaystyle f_{i}(x_{0})+\nabla
f_{i}\left(x_{0}+\theta_{i}(x-x_{0})\right)^{\top}(x-x_{0})$ (6)
$\displaystyle=$ $\displaystyle f_{i}(x_{0})+\nabla
f_{i}\left(x_{0}\right)^{\top}(x-x_{0})+$ $\displaystyle\left(\nabla
f_{i}\left(x_{0}+\theta_{i}(x-x_{0})\right)-\nabla
f_{i}\left(x_{0}\right)\right)^{\top}(x-x_{0})$ $\displaystyle\leq$
$\displaystyle
f_{i}(x_{0})+{\nabla}^{\nu^{*}}f_{i}\left(x_{0}\right)^{\top}(x-x_{0})$
$\displaystyle+\frac{\sqrt{d}\nu^{*}M_{i}}{2}\|x-x_{0}\|+M_{i}\|x-x_{0}\|^{2}$
$\displaystyle\leq$ $\displaystyle
f_{i}(x_{0})+{\nabla}^{\nu^{*}}f_{i}\left(x_{0}\right)^{\top}(x-x_{0})+2M_{i}\|x-x_{0}\|^{2}$
$\displaystyle\leq$ $\displaystyle 0,$

where the first inequality is due to Assumption 1 while the second can be
derived according to the definition of $\nu^{*}$ in Theorem 1. Hence,
$\mathcal{S}^{\circ}_{i}(x_{0})\setminus\mathcal{B}_{l^{*}}(x_{0})\subseteq\Omega.$
Since $\mathcal{S}^{\circ}_{i}(x_{0})\subseteq\Omega,\forall i$, then
$\mathcal{S}^{\circ}(x_{0})\subseteq\Omega$. $\blacksquare$

By construction, we see that if $x_{0}$ is strictly feasible, then it belongs
to $\mathcal{S}^{\circ}(x_{0})$. Moreover, the set
$\mathcal{S}^{\circ}(x_{0})$ is convex since
$\mathcal{S}^{\circ}(x_{0})=\cap^{m}_{i=1}\mathcal{S}^{\circ}_{i}(x_{0})$ and,
for any $i$, $\mathcal{S}^{\circ}_{i}(x_{0})$ is a $d$-dimensional ball. In
the sequel, we call $\mathcal{S}^{\circ}(x_{0})$ a local feasible set around
$x_{0}$.

###### Remark 3

The works [13, 12] consider an alternative approximation of the functions and
a local feasible set

$\mathcal{C}(x_{0}):=\bigcap^{m}_{i=1}\left\\{x:\|x-x_{0}\|\leq-\frac{f_{i}(x_{0})}{L_{\max}}\right\\}.$

We see that $\mathcal{C}(x_{0})=\\{x:F^{L}_{i}(x)\leq 0,\forall i\\}$ where
$F^{L}_{i}(x):=f_{i}(x_{0})+L_{\max}\|x-x_{0}\|$. In contrast,
$\mathcal{S}^{\circ}(x_{0})=\\{x:F^{M}_{i}(x)\leq 0,\forall i\\}$ where
$F^{M}_{i}(x):=f_{i}(x_{0})+{\nabla}^{\nu^{*}}f_{i}\left(x_{0}\right)^{\top}(x-x_{0})+2M_{i}\|x-x_{0}\|^{2}$.
One can easily verify that $F^{M}_{i}(x)<F^{L}_{i}(x)$ when $\|x-x_{0}\|$ is
sufficiently small. If $x_{0}$ is close to the boundary of the feasible set,
the distance $\|x-x_{0}\|$ is small for any $x\in\mathcal{C}(x_{0})$ and thus
$\mathcal{C}(x_{0})\subset\mathcal{S}^{\circ}(x_{0})$ due to
$F^{M}_{i}(x)<F^{L}_{i}(x)$. We illustrate this point in Example 1. The above
analysis reveals why $\mathcal{S}^{\circ}(x_{0})$ can be less conservative
than $\mathcal{C}(x_{0})$, which constitutes the main reason for which our
method can achieve faster convergence than [13].

###### Example 1

Consider the optimization problem (1) with $d=1$, $m=2$, $f_{0}(x)=3x$,
$f_{1}(x)=x^{2}-x-0.75$ and $x_{0}=1.49$, which is close to the boundary of
the feasible set $[-1,1.5]$. We let ${L_{\max}}=3.01$ and ${M_{\max}}=3$, then
$\mathcal{T}(x_{0})=[1.4836,1.4964]\subset\mathcal{S}^{\circ}(x_{0})=[1.1502,1.4998]$.

###  III-B The proposed algorithm

The proposed method to solve problem (1) is summarized in Algorithm 1. The
main idea is to start from the strictly feasible initial point $x_{0}$ and
iteratively solve (∗) in Algorithm 1, which is a convex Quadratically
Constrained Quadratic Program (QCQP), until the distance $\|x_{k+1}-x_{k}\|$
is smaller than a given threshold $\xi>0$ (see Line 6-8). By using the penalty
term $\mu\|x-x_{k}\|^{2}$ in (∗), we can guarantee that the increment
$\|x_{k+1}-x_{k}\|$ diminishes and Algorithm 1 terminates as shown later in
Theorem 2.

Algorithm 1 Safe Zeroth-Order Sequential QCQP (SZO-QQ)

Input: $\mu>0$, $\xi>0$, initial feasible point $x_{0}\in\Omega$
Output: $\tilde{x}$

1:Choose $M_{i}>M_{i,\text{inf}}$, for $i\in\mathbb{Z}^{m}_{1}$

2:$k\leftarrow 0,\textsc{TER}=0$

3:while $\textsc{TER}=0$ do

4: Compute $\mathcal{S}(x_{k})$ based on (5) and (7).

5:
$x_{k+1}=\operatorname*{arg\,min}_{x\in\mathcal{S}(x_{k})}f_{0}(x)+\mu\|x-x_{k}\|^{2}\quad\quad\hypertarget{starstar}{(*)}$

6: if $\|x_{k+1}-x_{k}\|\leq\xi$ then

7: $\tilde{x}\leftarrow x_{k+1}$, $\textsc{TER}\leftarrow 1$

8: end if

9: $k\leftarrow k+1$

10:end while

The construction of $\mathcal{S}(x_{k})$ is based on Theorem 1. We let
$\mathcal{S}(x_{k})=\bigcap^{m}_{i=1}\mathcal{S}_{i}(x_{k})$ where
$M_{i}>M_{i,\mathrm{inf}}$,

$l_{k}^{*}=\min_{i}\frac{-f_{i}(x_{k})}{L_{\max}},\quad\nu_{k}^{*}=\min\\{\frac{2l_{k}^{*}}{\sqrt{d}},\frac{1}{k}\\}.$
(7)

and

$\displaystyle\mathcal{S}_{i}(x_{k}):=$
$\displaystyle\big{\\{}x:f_{i}(x_{0})+{\nabla}^{\nu_{k}^{*}}f_{i}\left(x_{0}\right)^{\top}(x-x_{0})+$
(8) $\displaystyle\qquad\qquad\qquad\quad 2M_{i}\|x-x_{0}\|^{2}\leq
0\big{\\}}.$

By requiring $M_{i}>M_{i,\mathrm{inf}}$, we guarantee that $\forall k$,
$x_{k}$ is strictly feasible (see the proof of Theorem 1). Thanks to (7), we
can ensure that the gradient approximation error goes to 0, which is essential
for the convergence analysis in Theorem 2.

###### Remark 4

To run Algorithm 1, we need to set $L_{i}>L_{i,\mathrm{inf}}$ and
$M_{i}>M_{i,\mathrm{inf}}$ for $i\geq 1$. Here, we discuss the effect of
under/overestimating $L_{i,\mathrm{inf}}$ and $M_{i,\mathrm{inf}}$. If
$L_{i}<L_{i,\mathrm{inf}}$ or $M_{i}<M_{i,\mathrm{inf}}$, the set
$\mathcal{S}(x_{k})$ built according to (7) and (8) might not be feasible.
Consequently, when infeasible samples happen, one can increase $L_{i}$ and
$M_{i}$ for $i\geq 1$ by a certain factor. At the same time, one should avoid
too large a value for $M_{i}$, since if $M_{i}\gg M_{i,\mathrm{inf}}$, the
approximation used to construct $\mathcal{S}(x_{i})$ can be very conservative
and thus the convergence of Algorithm 1 can become much slower.

Algorithm 1 is similar to Sequential QCQP (SQCQP) [20], where at each
iteration quadratic proxies for both the objective and constraint functions
are built based on the local gradient vectors and Hessian matrices.
Applications of SQCQP to optimal control have received increasing attention
[21, 22], due to the development of efficient solvers for QCQP subproblems
[23]. Different from SQCQP [20], Algorithm 1, which we also call SZO-QQ in the
remainders, can guarantee feasible sampling and does not require line search,
which is costly due to the required generation of extra examples. Due to the
lack of line search, Algorithm 1’s convergence cannot be proved by simply
following the arguments in [20].

##  IV Theoretical Convergence Analysis

In this section, we first consider the sequence $\\{x_{k}\\}_{k\geq 1}$
generated by Algorithm 1 without the termination condition. We show that under
mild assumptions, the sequence $\\{f_{0}(x_{k})\\}_{k\geq 1}$ converges to the
minimum objective value of (1). Then, we discuss the choice of the termination
condition and the required number of iterations for the algorithm to stop.

###  IV-A Objective value converging to minimum

We let $\xi=0$, which is to say the termination condition
$\|x_{k+1}-x_{k}\|\leq\xi$ in Algorithm 1 is omitted. We characterize the
limit of the sequence $\\{f_{0}(x_{k})\\}_{k\geq 1}$ generated by the
algorithm in the following theorem.

###### Theorem 2

Under Assumption 1-3, if $\xi=0$, the sequence $\\{x_{k}\\}_{k\geq 1}$ in
Algorithm 1 has the following properties:

  * 1.

the sequence $\\{f_{0}(x_{k})\\}_{k\geq 1}$ is non-increasing;

  * 2.

the sequence $\\{x_{k}\\}_{k\geq 1}$ has at least one accumulation point
$x_{c}$111Theorem 2 does not imply that $\\{x_{k}\\}_{k\geq 1}$ is convergent.
For this property to hold, a sufficient condition is
$\sum^{\infty}_{k=0}\|x_{k}-x_{k+1}\|<\infty$. However, in the proof of
Theorem 2, we have only been able to show a weaker condition, namely,
$\sum^{\infty}_{k=0}\|x_{k}-x_{k+1}\|^{2}<\infty$.;

  * 3.

for any accumulation point $x_{c}$ of the sequence,
$\lim_{k\rightarrow\infty}f_{0}(x_{k})=f_{0}(x_{c})>-\infty$.

The proof of Theorem 2, provided in Appendix -A, leverages the optimality of
the solution to the subproblem (∗) in Algorithm 1, the boundedness of the
sublevel set $\mathcal{P}_{\beta}$ required by Assumption 3 and the continuity
of $f_{0}(x)$.

In view of point 3 of Theorem 2, to show that $\\{f_{0}(x_{k})\\}_{k\geq 1}$
converges to the minimum objective value of (1), we need to show there exists
an accumulation point $x_{c}$ of $\\{x_{k}\\}_{k\geq 1}$ that is the optimum
of (1). We now address the optimality of any accumulation point $x_{c}$ in
Theorem 3 below.

###### Assumption 4

There exists an accumulation point $x_{c}$ such that $\nabla f_{i}(x_{c})\neq
0,\forall i\in\mathcal{A}(x_{c})$, where
$\mathcal{A}(x_{c}):=\\{i:f_{i}(x_{c})=0\\}$

###### Remark 5

For proving the convergence of Interior Point Methods [6, Theorem 19.1], one
often assumes the Linear Independence Constraint Qualification (LICQ),
requiring that vectors $\nabla f_{i}(x_{c})\text{ for }i\in\mathcal{A}(x_{c})$
are linearly independent. Note that Assumption 4 is weaker than LICQ because
if there exists $i_{0}\in\mathcal{A}(x_{c})$ such that $\nabla
f_{i_{0}}(x_{c})=0$ then the vectors $\nabla f_{i}(x_{c})\text{ for
}i\in\mathcal{A}(x_{c})$ cannot be linearly independent.

###### Theorem 3

Under Assumptions 1-4, any accumulation point $x_{c}$ is an optimizer of
problem (1).

The complete proof of Theorem 3 can be found in Appendix -D. Below, we provide
an outline of it, which is based on the following optimality conditions for
the constrained optimization problem (1) as stated below.

######  Definition 1 ([24])

A pair $(x,\lambda)$ with $x\in\Omega$ and $\lambda\in\mathbb{R}^{m}_{\geq 0}$
is a $\eta-$approximate KKT (also written as $\eta-$KKT) point with $\eta>0$
of Problem (1) if it fulfills

$\displaystyle\|\nabla f_{0}(x)+\sum^{m}_{i=1}\lambda^{(i)}\nabla f_{i}(x)\|$
$\displaystyle\leq\eta,$ (9) $\displaystyle|\lambda^{(i)}f_{i}(x)|$
$\displaystyle\leq\eta,\quad i\in\mathbb{Z}^{m}_{1}.$

If $(x^{*},\lambda^{*})$ with $x^{*}\in\Omega$ and
$\lambda^{*}\in\mathbb{R}^{m}_{\geq 0}$ fulfills (9) with $\eta=0$, we say
that it is a KKT point.

We notice that due to Slater’s Condition, $x^{*}$ is a minimizer of (1) if and
only if there exists $\lambda^{*}\in\mathbb{R}^{d}_{\geq 0}$ such that
$(x^{*},\lambda^{*})$ is a KKT point of (1).

Sketch of the proof of Theorem 3:  Let $x_{c}$ be an accumulation point of
$\\{x_{k}\\}_{k\geq 1}$ such that $\nabla f_{i}(x_{c})\neq 0,\forall
i\in\mathcal{A}(x_{c})$ (see Assumption 4). Since $x_{k}$ is feasible for any
$k$ and $\Omega$, the point $x_{c}$ belongs to $\Omega$. If $\nabla
f_{0}(x_{c})=0$, then with $\lambda_{c}=0$, the pair $(x_{c},\lambda_{c})$ is
a KKT point and thus $x_{c}$ is a minimizer. Now, we consider $\nabla
f_{0}(x_{c})\neq 0$. It follows that that the active set
$\mathcal{A}(x_{c})=\\{i:f_{i}(x_{c})=0\\}$ is not empty (see Lemma 2 in
Appendix -B for the rigorous statement). We can then show the optimality of
$x_{c}$ through contradiction as follows.

We assume $x_{c}$ is not a minimizer and let $x_{s}\in\Omega$ be such that
$f_{0}(x_{s})<f_{0}(x_{c})$. We denote the line segment between $x_{c}$ and
$x_{s}$ as $x(t):=x_{c}+t(x_{s}-x_{c}),t\in[0,1]$. By utilizing Lemma 2 in
Appendix -B, we can find $\bar{t}\in(0,1)$ such that any $0<t_{p}<\bar{t}$
verifies $x(t_{p})$ belonging to the interior of $\mathcal{S}(x_{c})$ and
$f_{0}(x(t_{p}))+\mu\|x(t_{p})-x_{c}\|^{2}<f_{0}(x_{c})$. For this $t_{p}$ and
any $\tau>0$, there exists $k_{p}>0$ verifying $\|x_{k_{p}}-x_{c}\|\leq\tau$
and $x(t_{p})\in\mathcal{S}(x_{k_{p}})$ (see Lemma 3 in Appendix -C for the
rigorous statement). By letting $\tau$ be sufficiently small, we have
$f_{0}(x(t_{p}))+\mu\|x(t_{p})-x_{k_{p}}\|^{2}<f_{0}(x_{c})$. Since
$x_{k_{p}+1}=\operatorname*{arg\,min}_{x\in\mathcal{S}(x_{k_{p}})}f_{0}(x)+\mu\|x-x_{k_{p}}\|^{2}$,
we have $f_{0}(x_{k_{p}+1})+\mu\|x_{k_{p}+1}-x_{k_{p}}\|^{2}\leq
f_{0}(x(t_{p}))+\mu\|x(t_{p})-x_{k_{p}}\|^{2}<f_{0}(x_{c})$, which contradicts
the monotonicity shown in point 1 of Theorem 2. Thus, $x_{c}$ is a minimizer
of (1).

###  IV-B Computational complexity analysis

The result in Theorem 3 is asymptotic, but in practice only finitely many
iterations can be computed. Algorithm 1 adopts the termination condition
$\|x_{k+1}-x_{k}\|<\xi$ for $\xi>0$. The motivation for this particular
stopping criteria is as follows. With this condition, we expect that the KKT
point of the inner optimization problem (∗) in Algorithm 1 fulfills the
approximate KKT conditions of the original problem, namely (9). To see this
point, for $k=K-1$ we consider the KKT point of the subproblem $(*)$,
$(x_{K},\lambda_{K})$. If the error term $\|x_{K}-x_{K-1}\|$ is small, one can
show that the left-hand-side terms in (9) evaluated at
$(x,\lambda)=(x_{K},\lambda_{K})$ are also small.

Our next goal is to address whether the termination condition
$\|x_{k+1}-x_{k}\|<\xi$ is triggered in a finite number of iterations. And if
yes, how many iterations are needed.

###### Theorem 4

Under Assumption 1-4, the increment $\|x_{k+1}-x_{k}\|$ converges to 0 as
$k\rightarrow\infty$. Moreover, $K:=\inf\\{k:\|x_{k+1}-x_{k}\|\leq\xi\\}$
satisfies

$K\leq\overline{K}=\frac{f_{0}(x_{0})-\inf\\{f_{0}(x):x\in\Omega\\}}{\mu\xi^{2}}.$
(10)

Hence, Algorithm 1 terminates within $\overline{K}$ iterations.

Proof. Since
$x_{k+1}=\operatorname*{arg\,min}f_{0}(x_{k})+\mu\|x-x_{k}\|^{2}$, we know
that $f_{0}(x_{k})-f_{0}(x_{k+1})\geq\mu\|x_{k}-x_{k+1}\|^{2}$. Then, we have

$\displaystyle f_{0}(x_{0})-\inf\\{f_{0}(x):x\in\Omega\\}$ $\displaystyle\geq
f_{0}(x_{0})-f_{0}(x_{k})$ (11)
$\displaystyle\geq\sum^{k-1}_{i=0}\|x_{i}-x_{i+1}\|^{2}$

for any $k$, where the first inequality is due to the monotonicity of
$\\{f_{0}(x_{k})\\}_{k\geq 1}$ (see Theorem 2) and the second one is derived
through a telescoping sum. Since, due to (11), the sum
$\sum^{k}_{i=0}\|x_{i}-x_{i+1}\|^{2}$ converges, the increment
$\|x_{k}-x_{k+1}\|^{2}$ goes to $0$ as $k\rightarrow\infty$. Since for $k<K$,
$f_{0}(x_{k})-f_{0}(x_{k+1})\geq\mu\xi^{2}$, we have that
$f_{0}(x_{0})-f_{0}(x_{K})\geq K\mu\xi^{2}$. Hence, (10) holds. $\blacksquare$

##  V Numerical Results

In this section, we present numerical experiments to test the performance of
the SZO-QQ algorithm222All the numerical experiments have been executed on a
PC with an Intel Core i9 processor..

###  V-A Solving an unknown convex QCQP

To test SZO-QQ and compare it with existing zeroth-order methods, we consider
the following convex QCQP,

$\displaystyle\min_{x\in\mathbb{R}^{2}}$ $\displaystyle\quad
f_{0}(x)=0.1\times(x^{(1)})^{2}+x^{(2)}$ subject to $\displaystyle\quad
f_{1}(x)=-x^{(1)}\leq 0,$ $\displaystyle\quad f_{2}(x)=x^{(2)}-1\leq 0,$
$\displaystyle\quad f_{3}(x)=(x^{(1)})^{2}-x^{(2)}\leq 0.$

We assume that the functions $f_{i}(x),i=1,2,3,$ are unknown but their values
can be measured and a strictly feasible initial point
$x_{0}=\begin{bmatrix}0.9&0.9\end{bmatrix}^{\top}$ is given. The unique
optimum $\begin{bmatrix}0&0\end{bmatrix}^{\top}$ is not strictly feasible.
Testing on this example allows us to see whether Algorithm 1 stays safe and
whether the convergence is fast when the iterates are close to the feasible
region boundary.

We run SZO-QQ and compare its result with that of s0-LBM[13], Extremum Seeking
[11] and SafeOptSwarm 333SafeOptSwarm is a variant of SafeOpt (introduced in
Section I). The former adds heuristics to make SafeOpt in [12] more tractable
for slightly higher dimensions. [25]. Except Algorithm 1, s0-LBM and
SafeOptSwarm are provably safe for a high probability during exploration. Only
SZO-QQ and s0-LBM require Assumption 1. For these two methods, by trial and
error (see Remark 4), we adopt $L_{i}=5$ and $M_{i}=3$ for any $i\geq 1$. The
penalty coefficient $\mu$ of Algorithm 1 in (∗) is set to be $0.001$. Both
s0-LBM and Extremum Seeking are log-barrier-based and we use the reformulated
unconstrained problem $\min_{x}f_{\mathrm{log}}(x,\mu_{\log})$, where
$f_{\mathrm{log}}(x,\mu_{\log}):=f_{0}(x)-\mu_{\mathrm{log}}\sum^{4}_{i=1}\log(-f_{i}(x))$,
and $\mu_{\log}=0.001$.

Figure 1: Objective value as a function of computation time.

In Fig. 1, we show how the objective function values decrease with the
computation time. During the experiments, none of the implementations violates
the constraints. Regarding the convergence to the minimum, we see that s0-LBM
is the fastest in the first 1.5 seconds, which is due to the low complexity of
each iteration. However, SZO-QQ achieves a better solution afterwards. In the
first 6 seconds, Algorithm 1 already shows a clear trend of convergence to the
optimum, which is consistent with Theorem 2.

s0-LBM slows down when the iterates are close to the boundary of the feasible
set (see Remark 3 and Example 1). Meanwhile, the slow convergence of Extremum
Seeking is due to its small learning rate. The concept of learning rate is
analogous to the step size in gradient descent. If the learning rate is large,
the iterates might be brought too close to the boundary of the feasible set
and then the perturbation added by this method (most visible in Fig. 1 between
$5$ sec and $6$ sec) would lead to the violation of the constraints. These
considerations constitute the main dilemma in parameter tuning for Extremum
Seeking. In contrast, the exploration of the unknown functions in SafeOptSwarm
is based on Gaussian Process (GP) regression models instead of local
perturbations. Since SafeOptSwarm does not exploit the convexity of the
problem, it maintains a safe set and tries to expand it for finding the global
minimum. This is why many samples are close to the boundary of the feasible
set even though they are far away from the optimum. This phenomenon is also
observed in [26]. These samples along with the computational complexity of GP
regression are the main reason of the slow convergence with SafeOptSwarm.

Moreover, we also run s0-LBM and Extremum Seeking with different penalty
coefficients $\mu_{\mathrm{log}}$ to check whether the slow convergence is due
to improper tuning. We see that with larger $\mu_{\mathrm{log}}$ the
performances of the log-barrier-based methods deteriorates. This is probably
because the optimum of the unconstrained problem $f_{\log}(x,\mu_{\log})$
deviates more from the optimum $(0,0)$ as $\mu_{\mathrm{log}}$ increases. With
smaller $\mu_{\mathrm{log}}$, the Extremum Seeking method leads to constraint
violation while the performance of s0-LBM barely changes.

###  V-B Open-loop optimal control with unmodelled disturbance

This section shows an application of SZO-QQ for solving constrained optimal
control problem. We consider a non-linear system with dynamics
$x_{k+1}=Ax_{k}+Bu_{k}+\delta(x_{k})\begin{bmatrix}1&0\end{bmatrix}^{\top}$,
where $x_{k}=[x^{(1)}_{k}\;x^{(2)}_{k}]^{\top}\in\mathbb{R}^{2}$ for $k\geq
0$, $x_{0}=\begin{bmatrix}1&1\end{bmatrix}^{\top},$ the matrices

$A=\begin{bmatrix}1.1&1\\\ -0.5&1.1\end{bmatrix},B=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$

are known but the disturbance $\delta(x):=0.1*(x^{(2)})^{2}$ is unmodelled. We
aim to design the input $u_{k}$ for $i=$ $0,\ldots,5,$ to minimize the cost
$\mathcal{F}(\\{x_{k}\\}_{0\leq k\leq 5},\\{u_{k}\\}_{0\leq k\leq
5}):=\sum^{5}_{k=0}\left(x_{k+1}^{\top}Qx_{k+1}+u_{k}^{\top}Ru_{k}\right)$
where $Q=0.5\,\mathbf{I}_{2}$ and $R=2\,\mathbf{I}_{2}$ with identity matrix
$\mathbf{I}_{2}\in\mathbb{R}^{2\times 2}$ while enforcing
$\|x_{k}\|_{\infty}\leq 0.7$ and $\|u_{k}\|_{\infty}\leq 1.5$ for $k\geq 1$.
Since we assume all the states are measured, we can evaluate the objective and
constraints. This constrained optimal control problem represents a class of
problems where a gap exists between the assumed and true models and safety
(i.e., system trajectory verifying the constraints) is essential. These
problems, called Safe Learning Control Problem (SLCP), are surveyed in [27].
In this example, we assume to have a feasible sequence of inputs
$\\{u_{k}\\}_{0\leq k\leq 5}$ (as in Assumption 2) that leads to a safe
trajectory and results in a cost of 6.81. Different from the settings in the
model-based methods [28, 29] for SLCP, we don’t assume that the safe
trajectory is sufficient for identifying the disturbance $\delta(x)$ with
small error bounds. If the error bounds are huge, the robust control problems
formulated in [28, 29] may become infeasible.

If we only take into account the nominal model (i.e., neglect the nonlinear
disturbance $\delta(x)$), the optimal control problem is a Quadratic Program.
The minimal cost is 5.78 but the input sequence fails to satisfy the output
constraints.

We consider applying SZO-QQ to sample only feasible trajectories and derive a
feasible solution that achieves a low cost. To this aim, we utilize the known
feasible input sequence as the initial solution. By setting $L_{i}=M_{i}=20$
for $i\geq 1$, $\mu=10^{-4}$ and $\xi=10^{-4}$, we implement Algorithm 1 to
further decrease the cost resulting from the initial trajectory and derive
within 57 seconds of computation an input sequence that satisfies all the
constraints and achieves a cost of 5.96. This result is the same as that
derived through assuming the disturbance $\delta(\cdot)$ is known and applying
the nonlinear programming solver IPOPT [30], which is consistent with Theorem
3 on the convergence to a KKT point. Moreover, if we set $\xi=3*10^{-3}$, we
derive, within 12 seconds, an input sequence that achieves a cost of 6.00,
which shows that one may greatly reduce the computational time without ending
up with a much larger cost.

Observe that the problem studied is not convex due to the disturbance. A
detailed analysis of the performance of SZO-QQ for solving non-convex problems
is left for future work.

##  VI Conclusions

For safe black-box convex optimization problems, we proposed a method, SZO-QQ,
using samples of the objective and constraint functions to iteratively
optimize over local feasible sets. Each iteration of our algorithm involves a
QCQP subproblem, which can be solved efficiently. We showed that one of the
accumulation points of the iterates is a minimizer. From the numerical
experiments, we see our method can be faster than existing ones including
s0-LBM, SafeOptSwarm and Extremum Seeking. The fast convergence of the
algorithm motivates several directions of research, including the
characterization of the suboptimality for the solution returned by the
algorithm, the theoretical analysis of SZO-QQ when applied to non-convex
problems and the study of its performance when samples of the cost function
and the constraints are noisy.

###  -A Proof of Theorem 2

Given any $k$, we have $x_{k}\in\mathcal{S}(x_{k})$ and
$x_{k+1}=\operatorname*{arg\,min}_{x\in\mathcal{S}(x_{k})}f_{0}(x)+\mu\|x-x_{k}\|^{2}$.
Thus,

$\displaystyle f_{0}(x_{k+1})+\mu\|x_{k+1}-x_{k}\|^{2}$ $\displaystyle\leq$
$\displaystyle f_{0}(x_{k})+\mu\|x_{k}-x_{k}\|^{2}=f_{0}(x_{k}).$

Then for $k\geq 0$, $f_{0}(x_{k})\leq f_{0}(x_{0})<\beta$ (see Assumption 3).

Now we know $\\{x_{k}\\}_{k\geq 1}$ is within the set $\mathcal{P}_{\beta}$.
Due to the continuity of the functions $f_{i}(x)$ for $i\in\mathbb{Z}^{m}_{0}$
and the boundedness of the set $\mathcal{P}_{\beta}$, the set
$\mathcal{P}_{\beta}$ is compact. Hence, $\\{x_{k}\\}_{k\geq 1}$ has at least
an accumulation point $x_{c}$.

Since $f_{0}(x)$ is continuous and $\Omega$ is closed,
$\inf_{x\in\Omega}f_{0}(x)$ $>-\infty$ and the non-increasing sequence
$(f_{0}(x_{k}))_{k\geq 1}$ converges to $\inf_{k}f_{0}(x_{k})$. Considering
that $x_{c}$ is the limit point of a subsequence, we have
$f_{0}(x_{c})\geq\inf_{k}f_{0}(x_{k})$. Due to the fact that, for any $k$,
$f_{0}(x_{c})\leq f_{0}(x_{k})$, we have
$f_{0}(x_{c})\leq\inf_{k}f_{0}(x_{k})$. Thus $\\{f_{0}(x_{k})\\}_{k\geq 1}$
converges to $f_{0}(x_{c})$.

###  -B Statement and proof of Lemma 2

###### Lemma 2

If $x_{c}$ is an accumulation point of the sequence $\\{x_{k}\\}_{k\geq 1}$
and $\nabla f_{0}(x_{c})\neq 0$, the set $\mathcal{A}(x_{c})$ is nonempty.

Proof. We prove the lemma by contradiction. We assume $f_{i}(x_{c})<0$ for all
$i$ and let $(x_{k_{j}})_{j}$ be the subsequence converging to $x_{c}$.

The first claim to prove is that for some $r_{c}>0$ there exists $j_{c}$ such
that, for any $j>j_{c}$,
$\mathcal{B}_{r_{c}}(x_{c})\subset\mathcal{S}(x_{k_{j}})$. To see this, we let
$j_{c}$ be such that for any $j\geq j_{c}$ and any $i$,

$\displaystyle f_{i}(x_{k_{j}})$ $\displaystyle<\frac{1}{2}f_{i}(x_{c}),$ (12)
$\displaystyle 2L_{\max}\|x_{c}-x_{k_{j}}\|+4M_{\max}\|x_{c}-x_{k_{j}}\|^{2}$
$\displaystyle<-\frac{1}{4}f_{i}(x_{c}).$

Since $\nu_{k_{j}}$ converges to 0,
${\nabla}^{\nu^{*}_{k_{j}}}f_{i}\left(x_{k_{j}}\right)$ converges to
${\nabla}f_{i}\left(x_{k_{j}}\right)$. Thus, without loss of generality, we
can assume, for any $j\geq j_{c}$,
$\|{\nabla}^{\nu^{*}_{k_{j}}}f_{i}\left(x_{k_{j}}\right)\|\leq 2L_{\max}$. We
also let $r_{c}>0$ be such that

$2L_{\max}r_{c}+4M_{\max}r_{c}^{2}<-\frac{1}{4}f_{i}(x_{c}).$

Then, for any $x^{\prime}_{c}\in\mathcal{B}_{r_{c}}(x_{c})$ and $j\geq j_{c}$
we have

$\displaystyle
f_{i}(x_{k_{j}})+{\nabla}^{\nu^{*}_{k_{j}}}f_{i}\left(x_{k_{j}}\right)(x^{\prime}_{c}-x_{k_{j}})+2M_{i}\|x^{\prime}_{c}-x_{k_{j}}\|^{2}$
$\displaystyle<$
$\displaystyle-\frac{1}{2}f_{i}(x_{c})+2L_{\max}\|x^{\prime}_{c}-x_{k_{j}}\|+2M_{\max}\|x^{\prime}_{c}-x_{k_{j}}\|^{2}$
$\displaystyle<$
$\displaystyle-\frac{1}{2}f_{i}(x_{c})+2L_{\max}\|x_{c}-x_{k_{j}}\|+4M_{\max}\|x_{c}-x_{k_{j}}\|^{2}+$
$\displaystyle\text{
}2L_{\max}\|x_{c}-x^{\prime}_{c}\|+4M_{\max}\|x_{c}-x^{\prime}_{c}\|^{2}$
$\displaystyle<$
$\displaystyle-\frac{1}{2}f_{i}(x_{c})+\frac{1}{4}f_{i}(x_{c})+\frac{1}{4}f_{i}(x_{c})=0,$

where the second inequality is due to the triangle inequality while the third
is derived using (12). This means for any $j\geq j_{c}$ we have
$\mathcal{B}_{r_{c}}(x_{c})\subset S(x_{k_{j}})$.

The second claim is that in $\mathcal{B}_{r_{c}}(x_{c})$ we can find $x$ such
that $f_{0}(x)+\mu\|x-x_{c}\|^{2}<f_{0}(x_{c})$. To see this we let
$x=x_{c}-t\nabla f_{0}(x_{c})$, where $t\in\mathbb{R}_{\geq 0}$ is a
parameter. From (6), we have that

$\displaystyle f_{0}(x)$ $\displaystyle\leq f_{0}(x_{c})+\nabla
f_{0}(x_{c})^{\top}(x-x_{c})+M_{0}\|x-x_{c}\|^{2}$
$\displaystyle=f_{0}(x_{c})-t\|\nabla{f}_{0}(x_{c})\|^{2}+t^{2}M_{0}\|\nabla{f}_{0}(x_{c})\|^{2}.$

Hence, for $t<\min\\{(M_{0}+\mu)^{-1},r_{c}/|\nabla f_{0}(x_{c})|\\}$, we have

$f_{0}(x)+\mu\|x-x_{c}\|^{2}<f_{0}(x_{c}).$

Therefore, there exists $j_{c}\geq 1$ such that, for any $j\geq j_{c}$,
$f_{0}(x)+\mu\|x-x_{k_{j}}\|^{2}<f_{0}(x_{c}).$ Since $x\in S(x_{k_{j}})$, we
have

$\displaystyle f_{0}(x_{k_{j}+1})+\mu\|x_{k_{j}+1}-x_{k_{j}}\|^{2}$
$\displaystyle\leq$ $\displaystyle
f_{0}(x)+\mu\|x-x_{k_{j}}\|^{2}\,<\,f_{0}(x_{c}).$

which leads to the fact that $f_{0}(x_{k_{j}+1})<f_{0}(x_{c})$ and

$\underset{k\rightarrow\infty}{\lim}f_{0}(x_{k})<f_{0}(x_{c}),$

This result contradicts Theorem 2. Thus, $\mathcal{A}(x_{c})$ is not empty.
$\blacksquare$

###  -C Statement and proof of Lemma 3

###### Lemma 3

If $x_{c}$ is not an optimum, $\nabla f_{0}(x_{c})\neq 0$ and Assumption 4 is
verified, the following properties hold:

  * •

There exists $x_{s}\in\Omega$ such that $f_{0}(x_{s})<f_{0}(x_{c})$ and
$\nabla f_{i}(x_{c})^{\top}(x_{s}-x_{c})<0$, $\forall i\in\mathcal{A}(x_{c})$;

  * •

Define $x(t):=x_{c}+t(x_{s}-x_{c}),t\in[0,1]$ where $x_{s}$ was given above.
Then, there exists $\bar{t}\leq 1$ such that, for $0<t<\bar{t}$,
$f_{0}(x(t))+\mu\|x(t)-x_{c}\|^{2}<f_{0}(x_{c})$;

  * •

There exists $0<t_{p}<\bar{t}$ such that, for any $\tau>0$ and
$k_{0}\in\mathbb{Z}_{\geq 1}$, we can find $k_{p}>k_{0}$ satisfying
$\|x_{k_{p}}-x_{c}\|\leq\tau$ and $x(t_{p})\in\mathcal{S}(x_{k_{p}})$.

Proof. Convexity of $\Omega$ along with Assumption 2 on strict feasibility
leads to the following property.

###### Property 1

For any $x\in\Omega$ and any $r>0$, there exists an interior point of $\Omega$
in $\mathcal{B}_{r}(x)$, i.e., there exists $x^{\prime}\in\mathcal{B}_{r}(x)$
and $r^{\prime}>0$ such that
$\mathcal{B}_{r^{\prime}}(x^{\prime})\subset\Omega$.

If $x_{c}$ is not a minimizer, we let $x_{s}\in\Omega$ be such that
$f_{0}(x_{s})<f_{0}(x_{c})$. According to Property 1 and the assumption that
$\nabla f_{i}(x_{c})\neq 0$ for $i\in\mathcal{A}(x_{c})$, we can find an
interior point $x^{\prime}_{s}$ in the neighborhood of $x_{s}$ such that
$f_{0}(x^{\prime}_{s})<f_{0}(x_{c})$ and another point
$x^{\prime\prime}_{s}\in\Omega$ in the neighborhood of $x^{\prime}_{s}$ such
that $f_{0}(x^{\prime\prime}_{s})<f_{0}(x_{c})$ and $-\nabla
f_{i}(x_{c})^{\top}(x^{\prime\prime}_{s}-x_{c})\neq 0,\forall
i\in\mathcal{A}(x_{c})$. Since
$x(t):=tx_{c}+(1-t)x^{\prime\prime}_{s}\in\Omega$ for $0<t<1$, there exists
$g(t)$ such that

$\displaystyle\lim_{t\rightarrow\infty}\frac{g(t)}{t}$ $\displaystyle=0,$
$\displaystyle f_{i}(x(t))$ $\displaystyle=f_{i}(x_{c})+\nabla
f_{i}(x_{c})^{\top}(x^{\prime\prime}_{s}-x_{c})t+g(t)\leq 0.$

Therefore, $-\nabla f_{i}(x_{c})^{\top}(x^{\prime\prime}_{s}-x_{c})>0,\forall
i\in\mathcal{A}(x_{c})$.

Due to convexity, $f_{0}(x_{s})\geq f_{0}(x_{c})+\nabla
f_{0}(x_{c})^{\top}(x_{s}-x_{c})$, which leads to the fact that $\nabla
f_{0}(x_{c})^{\top}(x_{s}-x_{c})<0$ and there exists a constant $\sigma<0$
such that $\nabla f_{0}(x_{c})^{\top}(x(t)-x_{c})=t\sigma$. Since
$f_{0}(x(t))\leq f_{0}(x_{c})+t\sigma+t^{2}M_{0}\|x_{s}-x_{c}\|^{2}$, we let
$\bar{t}=-\sigma/((M_{0}+\mu)\|x_{s}-x_{c}\|^{2})$ and have, for
$0<t<\bar{t}$, $f_{0}(x(t))+\mu\|x(t)-x_{c}\|^{2}<f_{0}(x_{c})$.

To check the feasibility of $x(t)$ with respect to $\mathcal{S}_{i}(x_{k})$
for $i\in\mathcal{A}(x_{c})$, we first notice that

$\mathcal{S}_{i}(x_{k})=\mathcal{B}_{r^{k}_{i}(x_{k})}(O^{k}_{i}(x_{k})),\text{where
for a strictly feasible }x,$ $O^{k}_{i}(x):=x-\frac{\nabla
f^{\nu^{*}_{k}}_{i}(x)}{2M_{i}}\text{,
}\left(r^{k}_{i}(x)\right)^{2}:=-\frac{f_{i}(x)}{M_{i}}+\frac{\|\nabla
f_{i}^{\nu^{*}_{k}}(x)\|^{2}}{4M_{i}^{2}}.$

Furthermore, for $x_{c}$, we define

$O_{i}(x_{c}):=x_{c}-\frac{\nabla f_{i}(x_{c})}{2M_{i}}\text{,
}\left(r_{i}(x_{c})\right)^{2}:=-\frac{f_{i}(x_{c})}{M_{i}}+\frac{\|\nabla
f_{i}(x_{c})\|^{2}}{4M_{i}^{2}}.$

With
$\bar{\bar{t}}_{i}:=\operatorname*{arg\,min}_{t\in\mathbb{R}^{d}}\|O_{i}(x_{c})-x(t)\|$,
by considering that

$\|O_{i}(x_{c})-x_{c}+x_{c}-x(\bar{\bar{t}}_{i})\|=\|\frac{\nabla
f_{i}(x_{c})}{2M_{i}}+\bar{\bar{t}}_{i}(x_{s}-x_{c})\|$

and the fact that $\|O_{i}(x_{c})-x(\bar{\bar{t}}_{i})\|\leq r_{i}(x_{c})$, we
know

$(r_{i}(x_{c}))^{2}+\|\bar{\bar{t}}_{i}(x_{s}-x_{c})\|^{2}+\frac{\bar{\bar{t}}_{i}\nabla
f_{i}(x_{c})^{\top}(x_{s}-x_{c})}{2M_{i}}\leq(r_{i}(x_{c}))^{2}.$

Since $-\nabla f_{i}(x_{c})(x_{s}-x_{c})>0$, we have $\bar{\bar{t}}_{i}>0$.
Then for any $0<\tilde{t}_{i}\leq\min\\{\bar{\bar{t}}_{i},\bar{t},1\\}$, we
have $\|O_{i}(x_{c})-x(\tilde{t}_{i})\|<r_{i}(x_{c})$ and thus
$x(\tilde{t}_{i})$ is an interior point in
$\mathcal{B}_{r_{i}(x_{c})}(O_{i}(x_{c})),\forall i\in\mathcal{A}(x_{c})$.
Consequently, we can find $t_{p}\leq\bar{t}$ such that $x(t_{p})$ is an
interior point in the ball $\mathcal{B}_{r_{i}(x_{c})}(O_{i}(x_{c})),\forall
i\in\mathcal{A}(x_{c}),$ and $f_{0}(x(t_{p}))<f_{0}(x_{c})$.

We let $\\{x_{k_{j}}\\}_{j\geq 1}$ be the subsequence of $\\{x_{k}\\}_{k\geq
1}$ that converges to $x_{c}$. Since $\nu^{*}_{k_{j}}$ converges to 0,
$O^{k_{j}}_{i}(x_{k_{j}})$ converges to $O_{i}(x_{c})$ and
$r^{k_{j}}_{i}(x_{k_{j}})$ converges to $r_{i}(x_{c})$ for any
$i\in\mathcal{A}(x_{c})$. Because $x(t_{p})$ is an interior point of
$\mathcal{B}_{r_{i}(x_{c})}(O_{i}(x_{c})),\forall i\in\mathcal{A}(x_{c}),$ we
know that for any $j_{0}$ there exists $j>j_{0}$ such that $x_{k_{j}}$ is
arbitrarily close to $x_{c}$ and $x(t_{p})\in\mathcal{S}(x_{k_{j}})$. Thus,
for any $k_{0}$ and $\tau$ there exists $k_{p}>k_{0}$ such that
$\|x_{k_{p}}-x_{c}\|\leq\tau$ and $x(t_{p})\in\mathcal{S}(x_{k_{p}})$.
$\blacksquare$

###  -D Proof of Theorem 3

We let $x_{c}$ be an accumulation point of $\\{x_{k}\\}_{k\geq 1}$ such that
$\nabla f_{i}(x_{c})\neq 0,\forall i\in\mathcal{A}(x_{c})$ (see Assumption 4).
If $\nabla f_{0}(x_{c})=0$, then with $\lambda_{c}=0$, the pair
$(x_{c},\lambda_{c})$ is a KKT point and thus $x_{c}$ is minimizer. In the
following, we assume $\nabla f_{0}(x_{c})\neq 0$.

From Lemma 2, we know

$\nabla f_{0}(x_{c})\neq 0,\;\mathcal{A}(x_{c})\neq\emptyset,\;\text{and
}\nabla f_{i}(x_{c})\neq 0\text{ for }i\in\mathcal{A}(x_{c}).$

Then, we prove the optimality of $x_{c}$ by contradiction. By assuming $x_{c}$
is not an optimum, we know the three points in Lemma 3 hold. Therefore, for
any $\tau>0$ and $k_{0}\in\mathbb{Z}_{\geq 1}$ there exist $k_{p}>k_{0}$ and
$x^{\prime}\in\mathcal{S}(x_{k_{p}})$ verifying $\|x_{k_{p}}-x_{c}\|\leq\tau$
and $f_{0}(x^{\prime})+\mu\|x^{\prime}-x_{c}\|^{2}<f_{0}(x_{c})$. By letting
$\tau$ be sufficiently small, we have $k_{p}$ and
$x^{\prime}\in\mathcal{S}(x_{k_{p}})$ verifying

$\mu\|x_{c}-x_{k_{p}}\|^{2}<\frac{1}{2}\left(f_{0}(x_{c})-f_{0}(x(t_{p}))-\mu\|x(t_{p})-x_{c}\|^{2}\right),$

and $f_{0}(x^{\prime})+\mu\|x^{\prime}-x_{c}\|^{2}<f_{0}(x_{c}).$ Therefore,
we have

$\displaystyle f_{0}(x^{\prime})+\mu\|x^{\prime}-x_{k_{p}}\|^{2}$
$\displaystyle\leq$ $\displaystyle
f_{0}(x^{\prime})+\mu\|x^{\prime}-x_{c}\|^{2}+\mu\|x_{c}-x_{k_{p}}\|^{2}$
$\displaystyle<$
$\displaystyle\frac{1}{2}f_{0}(x_{c})+\frac{1}{2}\left(f_{0}(x^{\prime})+\mu\|x(t_{p})-x_{c}\|^{2}\right)$
$\displaystyle<$ $\displaystyle f_{0}(x_{c}).$

Therefore, we have

$\displaystyle f_{0}(x_{k_{p}+1})+\mu\|x_{k_{p}+1}-x_{k_{p}}\|^{2}$
$\displaystyle\leq$ $\displaystyle
f_{0}(x^{\prime})+\mu\|x^{\prime}-x_{k_{p}}\|^{2}\;<\;f_{0}(x_{c}),$

which contradicts the monotonicity properties shown in Theorem 2. Now, we have
shown that $x_{c}$ is optimum.

For any accumulation point $x_{c}$, no matter whether $\nabla f_{i}(x_{c})\neq
0,\forall i\in\mathcal{A}(x_{c})$ holds, we know
$f_{0}(x_{c})=\lim_{k\rightarrow\infty}f_{0}(x_{k})$ due to Theorem 2. Thus,
any accumulation point $x_{c}$ is a minimizer of (1).

## References

  * [1] Z. Chu, N. Zhang, and F. Teng, “Frequency-constrained resilient scheduling of microgrid: a distributionally robust approach,” IEEE Transactions on Smart Grid, vol. 12, no. 6, pp. 4914–4925, 2021.
  * [2] Y. Chen, A. Orvieto, and A. Lucchi, “An accelerated DFO algorithm for finite-sum convex functions,” in Proceedings of the 37th International Conference on Machine Learning, vol. 119 of Proceedings of Machine Learning Research, pp. 1681–1690, 13–18 Jul 2020.
  * [3] Z. Manchester and S. Kuindersma, “Derivative-free trajectory optimization with unscented dynamic programming,” in 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 3642–3647, IEEE, 2016.
  * [4] W. Xu, C. N. Jones, B. Svetozarevic, C. R. Laughman, and A. Chakrabarty, “VABO: Violation-aware Bayesian Optimization for Closed-Loop Control Performance Optimization with unmodeled constraints,” in 2022 American Control Conference (ACC), pp. 5288–5293, IEEE, 2022.
  * [5] I. Bajaj, A. Arora, and M. Hasan, Black-Box Optimization: Methods and Applications, pp. 35–65.  Springer, 2021.
  * [6] J. Nocedal and S. J. Wright, Numerical optimization.  Spinger, 2006.
  * [7] R. M. Lewis and V. Torczon, “Pattern search methods for linearly constrained minimization,” SIAM Journal on Optimization, vol. 10, no. 3, pp. 917–941, 2000.
  * [8] A. R. Conn, N. I. Gould, and P. L. Toint, Trust region methods.  SIAM, 2000.
  * [9] R. M. Lewis and V. Torczon, “A globally convergent augmented lagrangian pattern search algorithm for optimization with general constraints and simple bounds,” SIAM Journal on Optimization, vol. 12, no. 4, pp. 1075–1089, 2002\.
  * [10] C. Audet and J. E. Dennis Jr, “A progressive barrier for derivative-free nonlinear programming,” SIAM Journal on optimization, vol. 20, no. 1, pp. 445–472, 2009.
  * [11] D. B. Arnold, M. Negrete-Pincetic, M. D. Sankur, D. M. Auslander, and D. S. Callaway, “Model-free optimal control of var resources in distribution systems: An extremum seeking approach,” IEEE Transactions on Power Systems, vol. 31, no. 5, pp. 3583–3593, 2015.
  * [12] Y. Sui, A. Gotovos, J. Burdick, and A. Krause, “Safe exploration for optimization with gaussian processes,” in International Conference on Machine Learning, pp. 997–1005, PMLR, 2015.
  * [13] I. Usmanova, A. Krause, and M. Kamgarpour, “Log barriers for safe non-convex black-box optimization,” arXiv preprint arXiv:1912.09478, 2019.
  * [14] I. Usmanova, A. Krause, and M. Kamgarpour, “Safe convex learning under uncertain constraints,” in The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2106–2114, PMLR, 2019.
  * [15] A. Wibisono, M. J. Wainwright, M. Jordan, and J. C. Duchi, “Finite sample convergence rates of zero-order stochastic optimization methods,” Advances in Neural Information Processing Systems, vol. 25, 2012.
  * [16] A. R. Conn, K. Scheinberg, and L. N. Vicente, Introduction to derivative-free optimization.  SIAM, 2009.
  * [17] S. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization.  Cambridge university press, 2004.
  * [18] A. Rupenyan, M. Khosravi, and J. Lygeros, “Performance-based trajectory optimization for path following control using bayesian optimization,” in 2021 60th IEEE Conference on Decision and Control (CDC), pp. 2116–2121, IEEE, 2021.
  * [19] A. S. Berahas, L. Cao, K. Choromanski, and K. Scheinberg, “A theoretical and empirical comparison of gradient approximations in derivative-free optimization,” Foundations of Computational Mathematics, pp. 1–54, 2021\.
  * [20] M. V. Solodov, “On the sequential quadratically constrained quadratic programming methods,” Mathematics of Operations Research, vol. 29, no. 1, pp. 64–79, 2004.
  * [21] F. Messerer and M. Diehl, “Determining the exact local convergence rate of sequential convex programming,” in 2020 European Control Conference (ECC), pp. 1280–1285, IEEE, 2020.
  * [22] F. Messerer, K. Baumgärtner, and M. Diehl, “Survey of sequential convex programming and generalized gauss-newton methods,” ESAIM. Proceedings and Surveys, vol. 71, p. 64, 2021.
  * [23] G. Frison, J. Frey, F. Messerer, A. Zanelli, and M. Diehl, “Introducing the quadratically-constrained quadratic programming framework in hpipm,” in 2022 European Control Conference (ECC), pp. 447–453, IEEE, 2022.
  * [24] J. Dutta, K. Deb, R. Tulshyan, and R. Arora, “Approximate kkt points and a proximity measure for termination,” Journal of Global Optimization, vol. 56, no. 4, pp. 1463–1499, 2013.
  * [25] F. Berkenkamp, A. P. Schoellig, and A. Krause, “Safe controller optimization for quadrotors with gaussian processes,” in 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 491–496, IEEE, 2016.
  * [26] M. Turchetta, F. Berkenkamp, and A. Krause, “Safe exploration for interactive machine learning,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [27] L. Brunke, M. Greeff, A. W. Hall, Z. Yuan, S. Zhou, J. Panerati, and A. P. Schoellig, “Safe learning in robotics: From learning-based control to safe reinforcement learning,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 5, pp. 411–444, 2022.
  * [28] D. D. Fan, A.-a. Agha-mohammadi, and E. A. Theodorou, “Deep learning tubes for tube mpc,” in Proceedings of Robotics: Science and Systems XVI, 2020.
  * [29] L. Hewing, J. Kabzan, and M. N. Zeilinger, “Cautious model predictive control using gaussian process regression,” IEEE Transactions on Control Systems Technology, vol. 28, no. 6, pp. 2736–2743, 2019.
  * [30] A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical programming, vol. 106, no. 1, pp. 25–57, 2006.