Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization

The interior-point methodology is one of the most popular and effective derivative-based algorithm methodologies for solving inequality-constrained continuous optimization problems. Indeed, while there has been a long history of development of other types of algorithms—e.g., of the augmented-Lagrangian and sequential-quadratic-optimization varieties [16]—interior-point methods are arguably the most effective class of approaches for solving many constrained continuous optimization problems. In the setting of nonconvex optimization, which is the setting of interest in this paper, the effectiveness of interior-point methods is evidenced by the fact that the most popular software packages for solving such problems are based on interior-point methods. These include the packages Ipopt [19], Knitro [5], and LOQO [18]. This popularity withstands despite the fact that interior-point methods for solving nonconvex problems do not necessarily achieve the same optimal worst-case complexity properties that can be achieved in convex settings.

Despite its widespread success, little work has been done on extending the interior-point methodology to the stochastic regime. Here, we are focused on the setting in which constraint values and derivatives are tractable to compute, but objective values and derivatives are not. Furthermore, like in the setting of stochastic-gradient-based methods for solving unconstrained problems, our focus is to have an interior-point method that employs stochastic-gradient estimates (in place of exact objective gradients) and no objective function evaluations. Given the success of interior-point methods in the deterministic regime, there is ample motivation to explore their potential theoretical and practical behavior in such a stochastic regime. This is the main motivation for the work presented in this paper.

We contend that there are at least a few significant obstacles to the design and analysis of a stochastic interior-point method, which may be at least part of the reason that there has been little prior work on this topic. Firstly, interior-point methods often have a nested-loop structure wherein an inner loop is designed to solve (approximately) a so-called barrier subproblem for a fixed value of a barrier parameter and the outer loop involves decreasing the barrier parameter. Determining when to terminate the inner loop typically involves evaluating a measure of stationarity. However, in the aforementioned stochastic setting, evaluating such a measure is not tractable since objective-gradient evaluations are not tractable. Secondly, the barrier functions introduced in interior-point methods have corresponding gradient functions that are not Lipschitz continuous nor bounded. This presents major difficulties since for many stochastic-gradient-based methods, Lipschitz continuity and boundedness of the gradients are necessary features for ensuring convergence guarantees. Thirdly, interior-point methods regularly involve globalization mechanisms such as line searches or trust-region step-acceptance mechanisms that require exact function evaluations, but these are not tractable to perform in the aforementioned stochastic setting that is of interest here.

Our proposed algorithm framework (Algorithm 1 on page 1) is designed to solve nonlinearly constrained optimization problems of the form

where $A\in\mathbb{R}^{l\times n}$ (with $l<n$), $b\in\mathbb{R}^{l}$, and the functions $f$ and $c$ satisfy the following assumption with respect to the feasible region of problem (1), namely,

The elements of Assumption 2.1 pertaining to $f$ and $c$ are mostly common for the literature on smooth nonlinearly constrained optimization. The only exception is the assumption that there exists $x\in{\cal F}$ such that $c(x)<0$. This aspect of the assumption precludes the presence of nonlinear equality constraints (through two-sided inequalities). It is needed in our setting since our algorithm requires a feasible initial point that is strictly feasible with respect to the nonaffine constraints.

Assumption 2.1 does not require that the feasible region ${\cal F}$ is bounded, although our convergence analysis in §4 requires that the iterates remain within a set such that $c$ remains component-wise bounded below, and that the functions $f$, $c$, $\nabla f:\overline{\cal F}\to\mathbb{R}^{n}$, and $\nabla c_{i}:\overline{\cal F}\to\mathbb{R}^{n}$ for all $i\in[m]$ are Lipschitz continuous; see Assumption 4.1 on page 4.1. Our analysis could be extended to the setting in which the matrix $A$ does not have full row rank as long as the linear system $Ax=b$ is consistent. Our algorithm framework requires that the initial iterate is contained in ${\cal E}$ and that each step lies in the null space of $A$, which inductively implies that each iterate lies in ${\cal E}$. These requirements remain reasonable when $A$ has linearly dependent rows as long as a projection operator onto the null space of $A$ is available. Merely for ease of notation, we assume $A$ has full row rank.

In fact, our algorithm framework ensures that all iterates remain in the set

Observe that this set is guaranteed to be nonempty under Assumption 2.1. In each iteration, our framework involves the computation of a search direction that, for a given barrier parameter $\mu\in\mathbb{R}_{>0}$, aims to reduce the value of the objective augmented with the logarithmic barrier function defined with respect to the inequality-constraint functions of (1), namely, the function $\phi(\cdot,\mu):{\cal C}_{<0}\to\mathbb{R}$ defined by

Going forward, we refer to this as the barrier-augmented objective function. Observe that if $x^{\mu}$ is a local solution of the problem to minimize $\phi(\cdot,\mu)$ over ${\cal F}_{<0}={\cal E}\cap{\cal C}_{<0}$, then there exists a Lagrange multiplier vector $y^{\mu}\in\mathbb{R}^{l}$ such that, along with $z_{i}^{\mu}:=-\mu(c_{i}(x^{\mu}))^{-1}$ for all $i\in[m]$, one finds that

Any tuple $(x^{\mu},y^{\mu},z^{\mu})$ satisfying this system is referred to as a stationary point for the problem to minimize $\phi(\cdot,\mu)$ over ${\cal F}_{<0}$. This system should be compared to the Karush-Kuhn-Tucker (KKT) conditions for problem (1); in particular, under a constraint qualification—such as the Mangasarian-Fromovitz constraint qualification (MFCQ) [13]—if $x$ is a local solution of problem (1), then there exists $y\in\mathbb{R}^{l}$ and $z\in\mathbb{R}^{m}$ such that the following system of KKT conditions is satisfied:

Any tuple $(x,y,z)$ satisfying this system is referred to as a stationary point (or KKT point) for problem (1). As is generally the case for an interior-point method, our algorithm framework aims to find such a KKT point by taking steps to reduce the barrier-augmented objective function for a diminishing sequence of barrier parameters—a procedure that can be motivated by the fact that the stationarity conditions for the minimization of $\phi(\cdot,\mu)$ over ${\cal F}_{<0}$ tend toward those of (1).

Our algorithm framework is stated as Algorithm 1 on page 1. The framework presumes that it is given an initial neighborhood parameter $\theta_{0}\in\mathbb{R}_{>0}$ and an initial iterate $x_{1}\in{\cal E}\cap{\cal N}(\theta_{0})$, where for all $\theta\in\mathbb{R}_{>0}$ we define

Observe that the existence of such $\theta_{0}$ and $x_{1}$ is guaranteed under Assumption 2.1. Moreover, the steps of Algorithm 1 ensure that, for a prescribed, monotonically decreasing sequence $\{\theta_{k}\}\subset\mathbb{R}_{>0}$ with $\theta_{1}<\theta_{0}$, one finds $x_{k}\in{\cal E}\cap{\cal N}(\theta_{k-1})$ for all $k\in\mathbb{N}$. Hence, to describe the main steps of the algorithm for each $k\in\mathbb{N}$, we may presume that for all $k\in\mathbb{N}$ the algorithm has an iterate $x_{k}\in{\cal E}\cap{\cal N}(\theta_{k-1})$.

Following [7], Algorithm 1 also employs a prescribed, monotonically decreasing sequence of barrier parameters $\{\mu_{k}\}\subset\mathbb{R}_{>0}$ such that $\{\mu_{k}/\theta_{k-1}\}$ is a constant sequence. Other inputs required by Algorithm 1 in the deterministic setting are $\eta\in(\theta_{0}/\mu_{1},1)$, $\underline{\eta}\in(\theta_{0},\infty)$, $\underline{\zeta}\in\mathbb{R}_{>0}$, $\overline{\zeta}\in\mathbb{R}_{>0}$ with $\underline{\zeta}\leq\overline{\zeta}$, and $\zeta\in(0,1)$, each of which influences the search direction computation. Given these inputs along with $k\in\mathbb{N}$ and $x_{k}\in{\cal E}\cap{\cal N}(\theta_{k-1})$, the computation proceeds as follows. Firstly, a set of indices of constraints that are nearly active with respect to $x_{k}$ is identified as

Observe that since $x_{k}\in{\cal N}(\theta_{k-1})$ it follows that $c_{i}(x_{k})\leq-\theta_{k-1}$ for all $i\in[m]$, and, since the facts that $\eta\in(\theta_{0}/\mu_{1},1)$ and $\{\mu_{k}/\theta_{k-1}\}$ is a constant sequence together ensure $-\eta\mu_{k}<-\theta_{k-1}$, it follows that $-\eta\mu_{k}<c_{i}(x_{k})\leq-\theta_{k-1}$ for all $i\in{\cal A}_{k}$. Secondly, a vector $q_{k}\in\mathbb{R}^{n}$ is computed, the value of which is distinct between the deterministic and stochastic settings. In particular, the framework employs

where in the stochastic setting the vector $g_{k}$ is a stochastic estimate of $\nabla f(x_{k})$. Third, with $P:=I-A^{T}(AA^{T})^{-1}A$ denoting the orthogonal projection matrix onto the null space of $A$, a search direction $d_{k}\in\mathbb{R}^{n}$ is computed such that

In the deterministic setting, all that is required of the search direction $d_{k}$ is that it satisfies (5). For the stochastic setting, we introduce in our analysis a particular strategy for computing the search direction that implies that (5) holds along with other useful properties for our analysis for that setting.

Let us now discuss (5) in detail. Firstly, condition (5a) requires that the search direction satisfies $d_{k}\in\operatorname{Null}(A)$, i.e., it lies in the null space of $A$, which, since $x_{k}\in{\cal E}$, ensures that the subsequent iterate will also lie in ${\cal E}$. Secondly, conditions (5b) and (5c) require that the norm of the search direction $d_{k}$ is proportional to the norm of $Pq_{k}=(I-A^{T}(AA^{T})^{-1}A)q_{k}$, i.e., the norm of the projection of $q_{k}$ onto $\operatorname{Null}(A)$. Thus, conditions (5b) and (5c) require that the norm of the search direction is proportional to that of a projected gradient (estimate), which is a common type of requirement for a search direction in an algorithm for minimizing a smooth objective function over an affine set. Thirdly, condition (5d) requires that $d_{k}$ makes an angle with $Pq_{k}$ that is sufficiently obtuse. Again, this is a common type of requirement; e.g., in the deterministic setting, it ensures that any nonzero $d_{k}$ is a direction of sufficient descent with respect to the barrier-augmented objective function. Together, conditions (5a)–(5d) define a nonempty set and computing a search direction to satisfy these conditions is straightforward; e.g., one can compute the projection of $-q_{k}$ onto $\operatorname{Null}(A)$ and scale the resulting direction, if needed, to satisfy (5b)–(5c). However, it remains finally to consider condition (5e). Unfortunately, this is a requirement that is not always satisfiable along with the other conditions, namely, (5a)–(5d). That said, we contend that all of (5) can be satisfied as long as (a) the constraints are not degenerate in some sense and (b) the initial barrier parameter $\mu_{1}$ is sufficiently large relative to $\theta_{0}$. Denoting the conical hull of nearly active constraint gradients as

condition (5e) requires that $d_{k}$ lies sufficiently within the interior of the polar cone of ${\cal P}_{k}$, i.e., $\operatorname{int}({\cal P}_{k}^{\circ})$. Hence, to satisfy (5), there needs to exist a direction sufficiently within this interior that also satisfies (5a)–(5d). For our purposes now, let us simply introduce Assumption 3.1 below, which implicitly means that Algorithm 1 is being applied to a problem such that a search direction satisfying (5) always exists. We defer until §5 a more detailed discussion Assumption 3.1, where in particular we provide (a) example problems for which the assumption can be shown to hold or cannot be shown to hold, (b) further explanation about why the assumption can be viewed as a type of nondegeneracy assumption and an assumption about $\mu_{1}/\theta_{0}$ being sufficient large (which is reminiscient of a requirement in Corollary 3.8 and Lemma 3.15 in [7] for the bound-constrained setting), and (c) a procedure for computing $d_{k}$ to satisfy (5) when such a direction exists.

Upon computation of the search direction, Algorithm 1 chooses a step size $\alpha_{k}\in\mathbb{R}_{>0}$. For simplicity, our analyses for the deterministic and stochastic settings consider conservative rules for selecting the step sizes that each depend on the barrier- and neighborhood-parameter sequences, $\{\mu_{k}\}$ and $\{\theta_{k}\}$. We conjecture that it would be possible to generalize our algorithm and analyses to allow more flexibility in the step-size selection rules, as is done in [7]. However, for our purposes here, we present conservative strategies that are sufficient for proving convergence.

The algorithm’s last major step in the $k$th iteration is to compute a positive real number $\gamma_{k}\in\mathbb{R}_{>0}$ such that the line segment $[x_{k},x_{k}+\gamma_{k}\alpha_{k}d_{k}]$ is contained in the neighborhood ${\cal N}(\theta_{k})$. The subsequent iterate is then set as $x_{k+1}\leftarrow x_{k}+\gamma_{k}\alpha_{k}d_{k}$. As mentioned at the beginning of this section, from the facts that the $k$th iterate has $x_{k}\in{\cal E}\cap{\cal N}(\theta_{k-1})$, the $k$th search direction satisfies (5a), and the choice of $\gamma_{k}$ ensures that $x_{k}+\gamma_{k}\alpha_{k}d_{k}\in{\cal N}(\theta_{k})$, it follows that $x_{k+1}\in{\cal E}\cap{\cal N}(\theta_{k})$. For the sake of formality, we state the following lemma that has been proved.

We prove theoretical convergence guarantees for Algorithm 1 in both deterministic and stochastic settings. For both settings, we make the following additional, standard type of assumption beyond Assumptions 2.1 and 3.1.

Under Assumption 4.1, with $\{\kappa_{c_{i}}\}_{i\in[m]}\subset\mathbb{R}_{>0}$ defined in the assumption, we introduce ${\cal C}_{[-\kappa_{c},0)}:=\{x\in\mathbb{R}^{n}:c_{i}(x)\in[-\kappa_{c_{i}},0)\ \text{for all}\ i\in[m]\}$ along with the shifted barrier-augmented objective function $\tilde{\phi}:{\cal C}_{[-\kappa_{c},0)}\times\mathbb{R}_{>0}\to\mathbb{R}$ defined by

Important properties of the shifted barrier-augmented objective function are that (a) it is bounded below by $f_{\inf}:=\inf_{x\in{\cal F}_{<0}}f(x)\in\mathbb{R}$ whose existence follows under Assumption 2.1 and (b) it shares the same gradient function with respect to its first argument as that of the (unshifted) barrier-augmented objective function; i.e., for all $(x,\mu)\in{\cal C}_{[-\kappa_{c},0)}\times\mathbb{R}_{>0}$, one finds that

where $\nabla_{x}$ denotes the gradient operator with respect to a function’s first argument. These follow since for any $i\in[m]$ and $\delta\in(0,\kappa_{c_{i}}]$ one has $-\log(\delta/\kappa_{c_{i}})\geq 0$ and $-\log(\delta/\kappa_{c_{i}})=-\log(\delta)+\log(\kappa_{c_{i}})$, so $(x,\mu)\in{\cal C}_{[-\kappa_{c_{i}},0)}\times\mathbb{R}_{>0}$ implies

In addition, the shifted barrier-augmented objective function is monotonically increasing in its second argument in the sense that for any $x\in{\cal C}_{[-\kappa_{c},0)}$ one finds that $\tilde{\phi}(x,\mu)<\tilde{\phi}(x,\bar{\mu})$ for any $(\mu,\bar{\mu})\in\mathbb{R}_{>0}\times\mathbb{R}_{>0}$ with $\mu<\bar{\mu}$. These properties make the function $\tilde{\phi}$ useful for our analysis. Indeed, even though the algorithm is not aware of the constants $\{\kappa_{c_{i}}\}_{i\in[m]}$ in Assumption 4.1, we shall show that it follows from the former property above that it computes steps that lead to (expected) decrease in the shifted barrier-augmented objective function $\tilde{\phi}$. Also, with the latter property above, decreases in the barrier parameter also lead to decreases in $\tilde{\phi}$.

Our first result is useful for both the deterministic and stochastic settings. It shows that, for any $\theta\in\mathbb{R}_{>0}$, the gradient of the shifted barrier-augmented objective function with respect to its first argument is Lipschitz over line segments in ${\cal N}(\theta)$ with a Lipschitz constant that depends on $\theta$. This is a critical property, especially since this function is not globally Lipschitz over ${\cal F}_{<0}\supset{\cal N}(\theta)$. The proof follows standard techniques for such a result; we provide it for completeness.