We present a new feasible proximal gradient method for constrained optimization where both the objective and constraint functions are given by summation of a smooth, possibly nonconvex function and a convex simple function. The algorithm converts the original problem into a sequence of convex subproblems. Formulating those subproblems requires the evaluation of at most one gradient-value of the original objective and constraint functions. Either exact or approximate subproblems solutions can be computed efficiently in many cases. An important feature of the algorithm is the constraint level parameter. By carefully increasing this level for each subproblem, we provide a simple solution to overcome the challenge of bounding the Lagrangian multipliers and show that the algorithm follows a strictly feasible solution path till convergence to the stationary point. We develop a simple, proximal gradient descent type analysis, showing that the complexity bound of this new algorithm is comparable to gradient descent for the unconstrained setting which is new in the literature. Exploiting this new design and analysis technique, we extend our algorithms to some more challenging constrained optimization problems where (1) the objective is a stochastic or finite-sum function, and (2) structured nonsmooth functions replace smooth components of both objective and constraint functions. Complexity results for these problems also seem to be new in the literature. Finally, our method can also be applied to convex function constrained problems where we show complexities similar to the proximal gradient method.
]]>In this paper, we study the following constrained optimization problem min
where ψ i (x) is a composite function that sums up functions f i (x) and χ i (x). Here, f i , i = 0, 1, . . . , m, are smooth functions, χ 0 (x) is a proper, convex, lowersemicontinuous (lsc) function and χ i (x), i = 1, . . . , m, are convex continuous functions over the domain of χ 0 (i.e. dom χ 0 ). We consider that χ i , i = 0, . . . , m are 'simple' functions, namely, a feasible optimization problem of the form below min x∈R d
xa 0 2 + χ 0 (x) : xa i 2 + χ i (x) ≤ b i , i = 1, . . . , m.
(1.2) can be solved to efficiently obtain either an exact solution or an inexact solution of desired accuracy. Note that if χ i = 0, i = 1, . . . , m, then (1.2) becomes a proximal operator for function χ 0 on the intersection of balls. If we further assume χ 0 = 0, then (1.2) is a special type of quadratically constrained quadratic programming (QCQP) that can be solved efficiently because all the Hessians are identity matrices. In addition, we consider the case where constraints f i , i = 1, . . . , m, are structured nonsmooth functions which can be approximated by smooth functions (also called smoothable functions). Note that problem (1.1) covers a variety of convex and nonconvex function constrained optimization depending on the assumptions of f i , i = 0, . . . , m. Nonlinear optimization with function constraints is a classical topic in continuous optimization. While the earlier study focused on the asymptotic performance, recent work has put more emphasis on the complexity analysis of algorithms, mainly driven by the growing interest in large-scale optimization and machine learning. For most of our discussion on the complexity analysis, we generally require convergence to an -approximate KKT point (c.f. Definition 3). Penalty methods [9,25,33], including augmented Lagrangian methods [22][23][24]34], is one popular approach for constrained optimization. In [8], Cartis et al. presented an exact penalty method by minimizing a sequence of convex composition functions. When the penalty weight is bounded, this method solves O(1/ ) trust region subproblems. If the penalty weight is unbounded, the complexity is of O(1/ 2.5 ) to reach an -KKT point. In a subsequent work [9], the authors provided a target following method that achieves the complexity of O(1/ ), regardless of the growth of the penalty parameter. In [33], Wang et al. extended the penalty method for solving constrained problems where the objective takes the expectation form. Sequential quadratic programming (SQP) is another important approach for constrained optimization. Typically, SQP involves linearization of the constraints, quadratic approximation of the objective, and possibly some trust region constraint for the convergence guarantee [6,7]. The recent work [12] established a unified convergence analysis of SQP (GSQP) in more general settings where the feasibility and constraint qualification may or may not hold. Different from the standard SQP, the Moving Balls Approximation (MBA) method [1] follows a feasible solution path and transforms the initial problem into a diagonal QCQP. A subsequent work [3] presented a unified analysis of MBA and other variants of SQP methods. Under the assumption of Kurdyka-Łojasiewicz (KL) property, they establish the global convergence rates which depend on the Łojasiewicz exponent.
Despite much progress in prior works, there are some significant remaining issues. Specifically, most of the analysis is carried out for only smooth optimization and requires that the exact optimal solution of the convex subproblem is readily available. Unfortunately, both assumptions can be unrealistic in many large-scale applications. To overcome these issues, [4,25,26] presented some new proximal point algorithms that iteratively solve strongly convex proximal subproblems inexactly using first-order methods. A significant computational advantage is that first-order methods only need to compute a relatively easy proximal gradient mapping in each iteration. In particular, [4] proposed to solve the proximal point subproblem by a new first-order primal-dual method called ConEx. Under some strict feasibility assumption, they derived the total complexities of the overall algorithm for which the objective and constraints can be either stochastic or deterministic, and either nonsmooth or smooth. Notably, for nonconvex and smooth constrained problems, inexact proximal point [4] requires O(1/ 1.5 ) function/gradient evaluations. A similar complexity bound is obtained by the proximal point penalty method [25] when a feasible point is available. Nevertheless, at this point, it may be difficult to directly compare the efficiency of the proximal point with the earlier approach, given that very different oracles are employed in each method. The inexact proximal point method appears to be less efficient in terms of gradient and function value computations since first-order penalty method [9] and a variant of SQP [12] (where the surrogate is formed by first-order approximation) has an O(1/ ) complexity bound. Nevertheless, it might be more efficient if the corresponding proximal mapping is much easier to solve than the subproblems in penalty or SQP methods.
In this paper, we attempt to alleviate some of the aforementioned issues in solving nonconvex constrained optimization. Our main contribution is the development of a novel Level Constrained Proximal Gradient (LCPG) method for constrained optimization, based on the following key ideas.
First, we convert the original problem (1.1) into a sequence of simple convex subproblems of the form (1.2) for which an exact or an approximate solution can be computed efficiently. In particular, solving the subproblem requires at most one gradient and function value computation for f i , i = 0, . . . , m. This phenomenon is quite similar to simple single-loop methods even though LCPG method can be multi-loop since we allow for an inexact solution of (1.2) using some kind of iterative scheme.
Second, starting from a strictly feasible initial point and carefully controlling the feasibility levels of the subproblem constraints, we ensure that LCPG follows a strictly feasible solution path. This also allows us to deal with nonsmooth constraints where χ i is not necessarily 0 and further extends LCPG to the inexact case where the subproblem admits an approximate solution. Even though subtle, the level-control design is crucial in bounding the Lagrange multipliers under the well-known Mangasarian-Fromovitz constraint qualification (MFCQ) [4,27]. Subsequently, we also show asymptotic convergence of the LCPG method.
Third, we offer a new insight into the complexity analysis of LCPG as a gradient descent type method, which could be of independent interest. When the objective and constraints are nonconvex composite, we aim to find a first-order -KKT point (c.f. Definition 3) under the aforementioned MFCQ assumption. We can show that LCPG method converges in O(1/ ) iterations. Furthermore, each subproblem requires at most one function-value and gradient computation. The net outcome is that gradient complexity of our method is of O(1/ ). Notice that the number of iterations required by the proximal point method under MFCQ is also O(1/ ) (see [4,Theorem 5]). However, each iteration of this method requires O(1/ 0.5 ) gradient computation, and hence its total gradient complexity can be bounded by O(1/ 1.5 ). This is much worse than LCPG method. We compare with some significant lines of work in Table 1.
Exploiting the intrinsic connection between LCPG and proximal gradient (without function constraints), we extend LCPG to a variety of cases. (1) We can show a similar O(1/ ) gradient complexity for an inexact LCPG method for which the subproblem is solved to a pre-specified accuracy. If we assume χ i = 0, then the corresponding subproblem (1.2) (i.e. diagonal QCQP) can be efficiently solved by a customized interior point method in logarithmic time. In the more general setting when χ i = 0, we propose to solve (1.2) by the first-order method ConEx, which has very cheap iterations. (2) We also extend LCPG method to stochastic (LCSPG) and variance-reduced (LCSVRG) variants when f 0 is either stochastic or finite-sum function, respectively. LCSPG and LCSVRG require O(1/ 2 ) (similar to SGD [15]) and O( √ n/ ) (similar to SVRG [18]) stochastic gradients, respectively, where n is the number of components in the finite-sum objective. The complexity of variants of LCPG method for stochastic cases can also be seen in Table 2. (3) We consider the case when function f i , i = 0, 1, . . . , m are nondifferentiable but contain a smooth saddle structure (referred to as structured nonsmooth). We extend LCPG method for such nonsmooth nonconvex function constrained problem using Nesterov's smoothing scheme [29]. In this case, LCPG method requires O(1/ 2 ) gradients.
We show that the GD-type analysis of the LCPG method can be extended to the convex case. In particular, when the objective and constraint functions are convex, we show that LCPG method requires O(1/ ) gradient computations for smooth and composite constrained problems, and this complexity improves to O(log (1/ )) when the objective is smooth and strongly-convex. Furthermore, we develop the complexity of inexact variants of LCPG method by leveraging the analysis of gradient descent with inexact projection oracles [31]. Inexact LCPG method maintains the gradient complexity of O(1/ ) and O(log(1/ )) for convex and strongly convex problems, respectively. [12,25] requires an O( √ ) error on the complementary slackness and feasibility. Our measure requires 0feasibility error and O( )-complementary slackness error. * IQRC does not explicitly discuss the composite case. Their subproblem oracle can be upgraded to handle proximal cases relatively easily † Different methods have different costs for solving the subproblem. Some methods require explicit gradient computations for solving the subproblems and hence, are expected to be quite computationally costly. Some methods (including ours) have simple subproblems. See Remark 11 for a detailed discussion. Hence, comparing total computational complexity is not possible. We instead compare gradient complexities to provide a realistic estimate of the computational effort of each of these methods
Throughout our analysis, we require that the Lagrange multipliers for the convex subproblems of type (1.2) are bounded. This problem is addressed in different ways in arguably all works in the literature. In this paper, we show that under the assumption of MFCQ, Lagrange multipliers associated with the sequence of subproblems remain bounded by a quantity specified as B. Even then, the value of B cannot be estimated a priori. Fortunately, this bound is not needed in the implementation of our methods. However, it plays a role in complexity analysis. Hence, our comparison with the existing complexity literature (e.g., proximal point method of [4]) is valid when bound B on the sequence of Lagrange multipliers largely depends on the problem itself and not on the sequence of subproblems. One can easily see that such uniform bounds on Lagrange multipliers hold under the strong feasibility constraint qualification [4], a similar uniform Slater's condition [26] or for nonsmooth nonconvex relaxation in the application of sparsity constrained optimization [5]. The problem of comparing bounds B on Lagrange multipliers requires getting into specific applications, which is not the purpose of this paper. Hence, throughout our comparison with existing literature, we assume that bound B for different methods is of a similar order.
Comparison with MBA method Auslender et al. [1] provided a Moving Balls Approximation (MBA) method for smooth constrained problems, i.e. χ i (x), i = 0, . . . , m, are not present. They use Lipschitz continuity of constraint gradients along with MFCQ to
Table 2 Total number of stochastic gradient evaluations to obtain O ε, ε randomized KKT points in the finite sum problem
ensure that the subproblems satisfy Slater's conditions (see [1, Proposition 2.1(iii)]).
A similar result is also used in [35] where they provide a line-search version of MBA for functions satisfying certain KL properties. The MBA method was studied for semialgebraic functions in [3] where they used the KL-property of semi-algebraic functions.
The work [1] also provides the complexity guarantee for constrained programs with a smooth and strongly convex objective. Our results differ from the past studies in the following several aspects. First, we do not assume any KL property on the class of functions, hence making the method applicable to a wider class of problems. Second, we show complexity analysis for a variety of cases, e.g., stochastic, finite-sum, or structured nonsmooth cases. Note that complexity results are not known for the MBA type method even for the purely smooth problem. Third, we show complexity results for both convex and strongly convex cases which strictly subsumes the results in [1]. Fourth, it should be noted that [1] also considered the efficiency of solving subproblems. They proposed an accelerated gradient method that obtains O(1/ √ ) complexity for solving the dual of the QCQP subproblem. However, it is unclear what accuracy is enough for ensuring asymptotic convergence of the whole algorithm.
Comparison with generalized SQP The work [12] developed the first complexity analysis of the generalized SQP (GSQP) method by using a novel ghost penalty approach. Different from our feasible method, they consider a general setting where the feasibility and constraint qualification may or may not hold. They show that SQP-type methods have an O(1/ 2 ) complexity for reaching some -approximate generalized stationary point. Under an extended MFCQ condition, they established an improved complexity O(1/ ) for reaching the scaled-KKT point, which matches our complexity result under a similar MFCQ assumption. Notably, both their analysis and ours rely on MFCQ to show that the global upper bound (constant B) on the multipliers of the subproblems exists. However, to obtain the best O(1/ ) complexity, GSQP explicitly relies on the value of such unknown upper bound to determine the stepsize, which appears to be rather challenging in practical use. In contrast, our algorithm does not involve the constant B in the algorithm implementation; we only require the Lipschitz constants of the gradients, which is standard for gradient descent methods.
Outline This paper is organized as follows: Sect. 2 describes notations and assumptions.
It also provides various definitions used throughout the paper. Section 3 presents the LCPG method which uses exact solutions of subproblems. It also establishes asymptotic convergence and convergence rate results. Section 4.1 and Sect. 4.2 provides the LCSPG and LCSVRG method for stochastic and finite-sum problems, respectively. Section 5 shows the extension of LCPG for nonsmooth nonconvex function constraints. Section 6 introduces the inexact LCPG method and provides its complexity analysis when the subproblems are inexactly solved by an interior point method or first-order method. Finally, Sect. 7 extends LCPG method for convex optimization problems and establishes its complexity for both strongly convex and convex problems.
Notations. R n + stands for the non-negative orthant in R n . We use • to express the Euclidean norm. For a set X , we define X -= dist(0, X ) = inf x , x ∈ X . If X is a convex set then we denote its normal cone at x as N X (x). Furthermore, we denote the dual cone of the normal cone at x as N * X (x). Let e be a vector full of elements one. For simplicity, we denote
Assumption 1 (General) We assume that the optimal value of problem (1.1) is finite:
Furthermore, the objective and constraint functions have the following properties.
1: χ 0 is a proper, convex, and lower semi-continuous (lsc) function. Moreover, we assume that for all i = 1, . . . , m, the function
The Lagrangian function of problem (1.1) is denoted by
For functions ψ i , we denote its subdifferential as
where the sum is in the Minkowski sense. Note that this definition of the subdifferential for nonconvex functions was first proposed in [4]. Moreover, ∂ψ i = {∇ f i } when ψ i is a "purely" smooth nonconvex function and ∂ψ i = ∂χ i when ψ i is a nonsmooth convex function. Hence, it is a valid definition for the subdifferential of a nonconvex function. Below, we define the KKT condition using the above subdifferential.
x is feasible and there exists a vector
The values {λ i } are called Lagrange multipliers.
It is known that the KKT condition is necessary for optimality under the assumption of certain constraint qualifications (c.f. [2]). Our result will be based on a variant of the Mangasarian-Fromovitz constraint qualification, which is formally given below.
We say that a point x satisfies the Mangasarian-Fromovitz constraint qualification for (1.1) if there exists a vector z ∈ -N *
where
Proposition 1 (Necessary condition) Let x be a local optimal solution of Problem (1.1). If it satisfies MFCQ (2.3), then there is a vector λ ∈ R m + such that the KKT condition (1) holds.
Next, we introduce some optimality measures before formally presenting any algorithms. It is natural to characterize algorithm performance by measuring the error of satisfying the KKT condition. Towards this goal, we have the following definition.
We say that x is an type-I (approximate) KKT point if it is feasible (i.e. ψ(x) ≤ η), and there exists a vector λ ∈ R m + satisfying the following conditions:
Moreover, x is a randomized type-I KKT point if both x and λ are feasible randomized primal-dual solutions that satisfy
where the expectation is taken over the randomness of x and λ.
Besides the above definition, we invoke a second optimality measure which will help analyze the performance of a proximal algorithm (see, for example, [4]). Therein, it is arguably more convenient to approach the proximity of some nearly stationary points.
We say that x is a ( , ν) type-II KKT point if there exists an type-I KKT point x and x -x 2 ≤ ν. Similarly, x is a randomized ( , ν) type-II KKT point if x is a random vector and E[ x -x 2 ] ≤ ν.
We present the level constrained proximal gradient (LCPG) method in Algorithm 1. The main idea of this algorithm is to turn the original nonconvex problem into a sequence of relatively easier subproblems that involve some convex surrogate functions ψ k i (x) (0 ≤ i ≤ m) and variable constraint levels η k : min
Above, we take the surrogate function ψ k i (x) (0 ≤ i ≤ m) by partially linearizing ψ i (x) at x k and adding the proximal term L i 2 xx k 2 :
It should be noted that our algorithm may not be well-defined if it were to be initialized by an infeasible solution x 0 . Furthermore, we require the initial point to be strictly feasible with respect to the nonlinear constraints ψ(x) ≤ η. Therefore, we explicitly state this assumption below and assume it holds throughout the paper.
Assumption 2 (Strict feasibility) There exist a point x 0 ∈ dom χ 0 and a vector η 0 ∈ R m satisfying
With a strictly feasible solution, we assume that the constraint levels {η k } are incrementally updated and converge to the constraint levels for the original problem:
Algorithm 1 Level constrained proximal gradient method (LCPG)
1: Input: x 0 , η 0 ; 2: for k=0,1,2,...,K do 3: For i = 0, 1, . . . , m, set ψ k i (x) by (3.2); 4: Update x k+1 by solving (3.1); 5:
Choose δ k > 0 and update η k+1 by
2, . . . , m. (3.3) 6: end for 7: Output: x k+1 where k is a random index sampled from {0, 1, 2, ..., K }.
The following Lemma will be used many times throughout the rest of the paper.
123
Lemma 1 [Three-point inequality] Let g : R d → (-∞, ∞] be a proper lsc convex function and
then for any x ∈ R d , we have
Next, we present some important properties of the generated solutions in the following theorem.
Proposition 2 Suppose that Assumption 2 holds, then Algorithm 1 has the following properties.
1. The sequence x k is well-defined and is feasible for problem (1.1). {x k } satisfies the sufficient descent property:
Moreover, the sequence of objective values ψ 0 (x k ) is monotonically decreasing and lim k→∞ ψ 0 (x k ) exists. 2. There exists a vector λ k+1 ∈ R m + such that the KKT condition holds:
Proof Part 1). First, we show that {x k } is a well-defined sequence, namely, X k ∩dom χ 0 is a nonempty set where X k = x : ψ k i (x) ≤ η k i . This result clearly holds for k = 0 by Assumption 2. We show the general case (k > 0) by induction. Suppose that x k is well-defined, i.e., X k-1 ∩ dom χ 0 is nonempty. Then, by the definition of ψ k i , ψ k-1 i and the definition x k , we have x k ∈ dom χ 0 and
Here, the first inequality follows due to the smoothness of f i (x) which ensures for all x,
fact that η k i < η i , we have x k ∈ dom χ 0 ∩{x : ψ i (x) ≤ η i , i = 1, . . . , m}. Hence, the whole sequence {x k } remains feasible for the original problem. Now, let us apply Lemma 1 with g(x) = ∇ f 0 (x k ), x + χ 0 (x) + 1 X k (x), y = x k and γ = L 0 . Then, for any x ∈ dom χ 0 ∩X k , we have
Placing x = x k in the above relation, we have
(3.8)
Moreover, since f 0 (•) is Lipschitz smooth, we have that
Summing up the above two inequalities and using the definition ψ 0 = f 0 + χ 0 , we conclude (3.5). Hence, the sequence ψ 0 (x k ) is monotonically decreasing. The convergence of ψ 0 (x k ) follows from the lower boundedness assumption. Part 2). Note that (3.7) ensures the strict feasibility of x k w.r.t. the constraint set X k for the kth subproblem. Therefore, Slater's condition for (3.1) and the optimality of x k+1 imply that there must exist a vector λ k+1 ∈ R m + satisfying KKT condition (3.6). Hence, we complete the proof.
In order to show convergence to the KKT solutions, we need the following constraint qualifications.
Assumption 3 [Uniform MFCQ] All the feasible points of problem (1.1) satisfy MFCQ.
We state the main asymptotic convergence property of LCPG in the following theorem.
Theorem 1 Suppose that Assumption 3 holds, then we have the following conclusions.
1. The dual solutions {λ k+1 } are bounded from above. Namely, there exists a constant B > 0 such that sup 0≤k≤∞ λ k+1 < B.
(3.9)
Proof Part 1). First, we can immediately see that {x k } is a bounded sequence and hence the limit point exists. This result is from Assumption 1.3: and the feasibility of x k for problem (1.1) (c.f. Proposition 2, Part 1). Without loss of generality, we can assume lim k→∞ x k = x. For the sake of contradiction, suppose that λ k+1 is unbounded, then passing to a subsequence if necessary, we can assume λ k+1 → ∞ 123 for simplicity. Note that we also have lim k→0 x k+1x k 2 = 0 due to the sufficient descent property (3.5). From the KKT condition (3.6), we have
(3.10) Let X := i∈[m] {x : ψ i (x) ≤ η i } ∩ dom χ 0 be the feasible domain for problem (1.1). Due to the fact that x k ∈ X (Proposition 2), boundedness of X (Assumption 1.3:) and strong convexity of ψ k 0 , there exists l 0 ∈ R such that X ⊂ {x : ψ k 0 (x) < l 0 } for all k. Then, using (3.10) for all x ∈ dom χ 0 ∩{ψ k 0 (x) ≤ l 0 } and dividing both sides by λ k+1 , we have
Let us take k → ∞ on both sides of (3.11). Note that for all x ∈ dom χ 0 ∩{ψ k 0 (x) ≤ l 0 }, we have
where (3.12) is due to boundedness of ψ k 0 (x) on dom χ 0 ∩{ψ k 0 (x) ≤ l 0 } and boundedness of ψ k 0 (x k+1 ) since x k+1 ∈ X which is a bounded set. Moreover, (3.13) and (3.14) use the continuity of f i (x) and χ i (x), i ∈ [m]. Next, we consider the sequence {u k = λ k+1 / λ k+1 }. Since u k is a bounded sequence, it has a convergent subsequence. Let ū be a limit point of {u k } and the subsequence { j k } ⊆ {1, 2, ..., } such that lim k→∞ u j k = ū. Since the subsequence of a convergent sequence is also convergent, we pass to the subsequence j k in (3.11) and apply (3.12), (3.13) and (3.14), yielding
x) < l 0 } and using the stationarity condition for optimality of x, we have (3.16) where we dropped the constraint ψ k 0 (x) ≤ l 0 due to complementary slackness and the fact that ψ k 0 ( x) < l 0 .
Let B = {i : ūi > 0}, then we must have lim k→∞ λ
Based on complementary slackness, we have ψ
i for any i ∈ B for large enough k. Due to (3.14), we have the limit: ψ i ( x) = η i . Therefore, the ith constraint is active at x, i.e. i ∈ A( x). In view of (3.16), there exists subgradients
(3.17)
However, equation (3.17) contradicts the MFCQ assumption. This is because MFCQ guarantees the existence of z∈ -N *
where the first inequality follows since z ∈ -N dom χ 0 ( x) and v 0 ∈ N dom χ 0 ( x) implying that z, v 0 ≤ 0, the second inequality follow since ūi ≥ 0 and v i ∈ ∂ψ i ( x), and the last strict inequality follows due to uniform MFCQ (c.f. Assumption 3 and relation (2.3)) and ūi > 0 for at least one i ∈ B. This clearly leads to a contradiction. Hence, we conclude that {λ k+1 } is a bounded sequence and conclude the proof.
Part 2). Without loss of generality, we assume that x is the only limit point. Since {λ k+1 } is a bounded sequence, there exists a limit point λ. Passing to a subsequence if necessary, we have λ k+1 → λ.
From the optimality condition 0 ∈ ∂ x L k (x k+1 , λ k+1 ), for any x, we have
Let us take k → ∞ on both sides of (3.18). We note that lim k→∞ x k -
), and χ 0 ( x) ≤ lim inf k→∞ χ 0 (x k ) due to the lower semi-continuity of χ 0 (•). It then follows that
In other words, x is the minimizer of convex optimization problem min
In addition, using the complementary slackness, we have
due to the convergence lim k→∞ λ k+1 = λ, lim k→∞ η k = η, lim k→∞ χ(x k+1 ) = χ( x) and lim k→∞ x k+1x k = 0. Putting (3.20) and (3.21) together, we conclude that ( x, λ) satisfies the KKT condition.
To show the existence of a limit point x, we use Assumption 1.3: to ensure that the sequence x k remains in a bounded domain. For the sake of conciseness, we henceforth assume the existence of a limit point x and do not delve into the technical assumption used to ensure this condition. Moreover, it should be noted that the boundedness property can be obtained under other assumptions, e.g., assuming the compactness of sublevel set {x : ψ 0 (x) ≤ ψ 0 (x 0 )} and using the sufficient descent condition (3.5), we can immediately show the existence of x. However, it appears to be more challenging to show convergence via this approach when sufficient descent condition fails (e.g., in the forthcoming stochastic optimization).
In Theorem 1, we proved existence of a bound B on the dual multiplier. However, the size of that bound still remains unknown. Through Example 1 below, we observe that the limiting behaviour of the sequence λ k (which largely governs the size of B) is closely tied to the magnitude of the number c( x), where
Here, the inner max follows from the relation (2.3) and outer min tries to find the best possible z that ensures MFCQ. It is observed that if c( x) is a large positive number, then MFCQ is strongly satisfied and B is a reasonable bound. In contrast, if c( x) is close to 0, then B can get quite large.
Example 1 Consider a two dimensional optimization problem with SCAD constraint:
This function fits our framework with the smoothness parameter 1 θ-1 . Lets consider β = 1, θ = 5, the level η 1 = 3 and limit point x = (5, 0). Clearly, the constraint is active at x and h is 1 4 -smooth function. Then, ∂ψ( x) = {
} as per the definition. Then, one can see that uniform MFCQ is violated at the limit point x. Indeed,
implying c( x) = 0. Furthermore, no λ can be found satisfying the KKT condition
. Hence, as we get close to this limit point, bound on λ k will get arbitrarily large. Easy way to see this fact is to construct a subproblem at the limit point itself. After observing the feasible region for the subproblem at (5, 0), it is clear that it has only one feasible solution (5, 0) which gives rise to degeneracy. See Fig. 1 for more details. Figure 1a shows the well-behaved subproblem at an interior point while Fig. 1b show the degeneracy at the limit. However, as we change level η 1 to any value either above or below 3, we do not get any violation of MFCQ. It also gives nondegenerate feasible sets at limit point and λ k remains bounded for all k. See Fig. 2 below for more details. In particular, if η 1 = 2.5 < 3, then x = (3, 0) is the limit point. At this point, we have ∂ψ
Choosing the unit vector z = (z 1 , z 2 ) = (-1, 0), we obtain that point x satisfies MFCQ with c( x) = 0.5. Hence, even when the search point reaches the limit point x (i.e., → 0), the λ k still exists. (See, in particular, Fig. 2b whose subproblem at x has a nonempty interior).
The view of the above example, we see that the limiting behavior of λ k (and by implication the order of B) is closely related to the "strength" of the constraint qualification MFCQ at the limit point. In order to get an apriori bound B, we use a somewhat stronger yet verifiable constraint qualification called as strong feasibility which is a slight modification of the CQ proposed in [4, Assumption 3]. Fig. 2 The nonconvex constraint ψ 1 (x) ≤ η 1 where η 1 = 2.5. The dotted blue curves are subproblem constraint for two different points. Since the MFCQ is satisfied, the limiting subproblem constraint at (3, 0) is still a full dimensional set with nonempty interior Assumption 4 [Strong feasibility CQ] There exists x ∈ X := i∈[m] {x :
where
In view of Assumption 1.3:, we note that X is a bounded set. Hence, D X and (consequently) Assumption 4 are well-defined. See [4] for a connection between Assumption 4 and Assumption 3. Below, we show that strong feasibility CQ leads to a fixed apriori bound on λ k .
Lemma 2 Suppose Assumption 4 is satisfied. Then, λ k 1 ≤ B :=
where first inequality uses
x -x k 2 (follows due to L i -smoothness of f i ), and second inequality follows by Assumption 4 along with the fact that x k ∈ X (see Proposition 2).
In view of (3.24), we have strict feasibility of subproblem (3.1) for all k implying that λ k+1 exists. Hence, we have
Then, for all x ∈ dom χ 0 , we have
where equality follows from the complementary slackness of the KKT condition, and inequality is due to optimality of x k+1 . Using x = x in the above relation and combining with (3.24), we obtain
Finally, note that
where first inequality follows by (3.24) for i = 0 and ψ k 0 (x) ≥ ψ 0 (x), and second inequality follows by the definition of ψ * 0 and D X . Combining the above relation with (3.25), we get the result. Hence, we conclude the proof.
The discussion above implies that the value of B is intricately related to the constraint qualification. While uniform MFCQ is unverifiable and does not allow for a priori bounds on B, it is widely used in nonlinear programming to ensure the existence of such a bound [2]. As observed in Fig. 1b and Fig. 2b, the actual value of B depends on the closeness of the MFCQ violation at the limit point. This situation is rare, but the current assumptions do not eliminate that possibility. Problems of this nature are ill-conditioned, and to our knowledge, no algorithm can ensure bounds on the dual in such a situation. The existing literature deals with this issue in two ways: One track assumes existence of B (similar to Theorem 1) and performs the complexity or convergence analysis; A second track assumes a stronger constraint qualification that removes the ill-conditioned problems and shows more explicit bound on the dual (similar to Lemma 2. We perform our analysis for both cases. To conclude, we henceforth assume that the bound B is a constant and do not delve into the discussion on 123 related constraint qualification. To substantiate that the bound B is small, we perform detailed numerical experiments in Sect. 8.
Our main goal now is to develop some non-asymptotic convergence rates for Algorithm 1.
In Algorithm 1, for k = 1, 2, ..., we have
Proof Let L k be the Lagrangian function of subproblem (3.1):
Using (2.1) and (3.27), we have
Using the smoothness of f i (x), the optimality condition 0 ∈ ∂ x L k (x k+1 , λ k+1 ) and the triangle inequality, we obtain
Hence we conclude the proof.
In view of Lemma 3, we derive the complexity of LCPG to attain approximate KKT solutions in the following theorem.
Theorem 2 Let α k > 0 (k = 0, 1, .., K ) be a non-decreasing sequence and suppose that Assumption 3 holds, then there exists a constant B > 0 such that
where D =
Proof From the sufficient descent property (3.5), we have
where the second inequality uses the monotonicity of sequence ψ 0 (x k ). In view of Theorem 1 and Cauchy-Schwarz inequality, we have λ k+1 , L ≤ λ k+1 L ≤ B L . This relation and (3.26) implies
Combining the above inequality with (3.33) immediately yields (3.30).
Next, we bound the error of complementary slackness. We have
where the first inequality uses the triangle inequality, the second inequality uses complementary slackness and the Lipschitz smoothness of f i (•), and the last inequality follows from Cauchy-Schwartz inequality and boundedness of λ k+1 . Summing up (3.34) weighted by α k for k = 0, ..., K , we have
Combining the above result with (3.33) gives (3.31). Finally, the fact that x k+1 is a randomized K type-I KKT point for K defined in (3.32) is immediately follows from (3.30), (3.31) and Definition 3.
The following corollary shows that the output of Algorithm 1 is a randomized O(1/K ) KKT point under more specific parameter selection.
In Algorithm 1, suppose that all the assumptions of Theorem 2 hold. Set
. Moreover, for i ∈ [m] and k ≥ 0, we have
Plugging these values into (3.32) gives us the desired conclusion.
Remark 2 Corollary 1 shows that the gradient complexity of LCPG for smooth composite constrained problems is on a par with that of gradient descent for unconstrained optimization problems. To the best of our knowledge, this is the first complexity result for a constrained problem where the constraint functions can be nonsmooth and nonconvex. Note that the convergence rate involves the unknown bound B on the Lagrangian multipliers. The presence of such a constant is not new in nonlinear programming literature [1,8,9,12,13]. Fortunately, we can safely implement LCPG method since the step-size scheme does not rely on B. On the other hand, the bound B is often a problem-dependent quantity. E.g., in [4] authors show a class of problems for which an a priori bound B can be established, or [5] shows the exact value of B for a class of nonconvex relaxations of sparse optimization problems. In such cases, our comparisons are arguably fair. Hence, throughout the paper, we make comparative statements under the assumption that B largely depends on the problem.
The goal of this section is to extend our proposed framework to stochastic constrained optimization where the objective f 0 is an expectation function:
Here, F(x, ξ) is differentiable and ξ denotes a random variable following a certain distribution Ξ . Directly evaluating either the objective f 0 or its gradient can be computationally challenging due to the stochastic nature of the problem. To address this, we introduce the following additional assumptions.
The information of f 0 is available via a stochastic first-order oracle (SFO). Given any input x and a random sample ξ , SFO outputs a stochastic gradient
for some σ ∈ (0, ∞).
In Algorithm 2, we present a stochastic variant of LCPG for solving problem 1.1 with f 0 defined by (4.1). As observed in (4.2) and (4.3), the LCSPG method uses a minibatch of random samples to estimate the true gradient in each iteration. It should be noted that the value f 0 (x k ) is presented in (4.3) only for the ease of description, it is not required when solving (3.1).
Algorithm 2 Level constrained stochastic proximal gradient (LCSPG)
by (3.2); 6: Update x k+1 by (3.1) and update η k+1 by (3.3); 7: end forOutput: x k+1 where k is a random index sampled from {0, 1, 2, ..., K }.
Note that the proximal point method of [4] does not need to account for a stochastic nonconvex problem separately since they solve corresponding stochastic convex subproblems using a ConEx method developed in their work. On the contrary, LCSPG directly applies to stochastic nonconvex function constrained problems and convex subproblems are deterministic in nature. Hence, we need to develop asymptotic convergence and convergence rates for the LCSPG method separately.
Let
) denote the error of gradient estimation. We have
The following proposition summarizes some important properties of the generated solutions of LCSPG.
Moreover, there exists a vector λ k+1 ∈ R m + such that the KKT condition (3.6) (with ψ k 0 defined in (4.3)) holds. Proof By the KKT condition, x k+1 is the minimizer of L k (•, λ k+1 ). Therefore, we have
(4.5)
Placing x = x k in (4.5) and using (3.27), we have
where the second inequality is due to the complementary slackness λ k+1 i
) and Lipschitz smoothness of f 0 , we have
Above, the last inequality uses the fact -a 2 x 2 + bx ≤ b 2 2a for any x, b ∈ R, a > 0. Showing the existence of the KKT condition follows a similar argument of proving part 2, Proposition 2.
We prove a technical result in the following lemma which plays a crucial role in proving dual boundedness.
Proof We prove this result by contradiction. If the result does not hold then there exists > 0 and c > 0 such that
However, due to Chebyshev's inequality, we have P(
The above relation contradicts (4.8). Hence, we have lim k→∞ X k = 0 a.s.
In the following theorem, we present the main asymptotic property of LCSPG.
Theorem 3 Suppose that ∞ k=0 b -1 k < ∞, then we have that lim k→∞ x k+1x k = 0, a.s. Moreover, suppose that Assumption 3 holds, γ k < ∞, β k is lower bounded and 2γ k -β k -L 0 > 0, then we have that (1) sup k λ k < ∞ a.s., and (2) all the limit points of Algorithm 2 satisfy the KKT condition, a.s.
Proof First, we fix notations. Let (Ω, F, P) be the probability space defined over the sampling minibatches B 0 , B 1 , . . . ,. Let E k [•] be the expectation conditioned on the sub σ -algebra generating B 0 , B 1 , . . . , B k-1 . Applying it to (4.4) gives
In view of the super-martingale convergence theorem [30], we have that lim k→∞ ψ 0 (x k ) exists and is finite a.s., when
x s+1x s 2 for k ≥ 0 and C 0 = 0. We have
Applying the super-martingale convergence theorem [30] again we can show that the limit of ψ 0 (x k ) + C k exists a.s. Together with (4.9) and lower-boundedness of β k and 2γ k -β k -L 0 , we have that lim k→∞ x k+1x k 2 = 0, a.s. Next, we prove the boundedness of λ k . Let us consider the events
We just argued P(B) = 1. It is easy to see that if both conditions (i)
Hence, using Lemma 4, we have that lim k→∞ ζ k = 0 a.s. Due to the boundedness of ∇ f (x k ), we have that
We prove condition (ii) by contradiction. Suppose that our claim fails. We take an element ω ∈ U ∩ (A ∩ B) and then pass to a subsequence { j k } such that lim k→∞ λ j k (ω) = ∞. In the rest of the proof, we skip ω for brevity. Passing to another subsequence if necessary, let x be a limit point of {x j k }. By our presumption, x satisfies MFCQ. Moreover, the KKT condition implies that
Dividing both sides by λ j k +1 gives
where we denote
converges to 0. Therefore, taking k → ∞ on both sides of (4.11), we have
Analogous to the proof of Theorem 1, it is easy to show that x violates MFCQ, which however, contradicts Assumption 3. As a consequence of this argument, we have U ⊆ A c ∪ B c . Hence, we claim that the event sup k λ k < ∞ will happen a.s. and complete our proof of the boundedness condition. Next, we prove asymptotic convergence to KKT solutions. For any random element ω, let x(ω) be any limit point of {x k }. Passing to some subsequence if necessary, we assume that lim k→∞ x k = x and lim k→∞ λ k+1 = λ.
Moreover, we have
Combining the above two results, we have
Taking k → ∞ in the above relation and noting that almost surely we have lim k→∞ ζ k = 0 and lim k→∞ x kx k+1 = 0, then
Using an argument similar to the one in Theorem 1, we can show that x is almost surely a KKT point.
Our next goal is to develop the iteration complexity of Algorithm 2. To achieve this goal, we need to assume that the dual is uniformly bounded, namely, condition (3.9) holds for all the random events. While this condition is stronger than the almost sure boundedness of λ k+1 shown by Theorem 3, it is indeed satisfied in many scenarios, e.g., when strong feasibility (Assumption 4) holds or other scenarios described in [4,5]. We present the main complexity result in the following theorem.
Theorem 4 Suppose that condition (3.9) holds. Then, the sequence {(x k+1 , λ k+1 )} satisfies that
Proof First, appealing to (4.3), (2.1) and (3.27), we have
It follows that
In view of the above result and basic inequality (a + b) 2 ≤ 2a 2 + 2b 2 , we have
Let us denote an auxiliary sequence
Putting this relation and (4.15) together, we have
Summing up (4.17) over k = 0, 1, . . . , K weighted by α k leads to
Moreover, since {C k } is monotonically decreasing, we have
Combining the above two relations leads to our first result (4.13).
For the second part, note that (3.34) remains valid in the stochastic setting. Putting (3.34) and (4.16) together, we obtain
Multiplying both ends by α k and then summing up the resulting terms over k = 0, . . . , K gives (4.14).
We next obtain more specific convergence rate by choosing the parameters properly.
. Then x k+1 is a randomized type-I KKT point with
Proof Plugging in the value of γ k , α k , β k in the relation (4.13) and taking expectation over all the randomness, we have
Moreover, due to the random sampling of k, we have
Combining the above two results, we have
Second, plugging in the values of γ k , β k and δ k in (4.14), we have
It then follows from (4.18) and the definition of k that
This completes our proof.
In order to obtain some -error in satisfying the type I KKT condition, LCSPG requires a number of O(ε -2 ) calls to the SFO, which matches the complexity bound of stochastic gradient descent for unconstrained nonconvex optimization [15]. Moreover, due to minibatching, LCSPG obtains an even better O(ε -1 ) complexity in the number of evaluations of f i (x) and
We consider the finite sum problem:
where each F(x, ξ i ) is Lipschitz smooth with the parameter L 0 , i = 1, 2, . . . , n.
To further improve the convergence performance in this setting, we present a new variant of the stochastic gradient method by extending the stochastic variance reduced gradient descent to the constrained setting. We present the level constrained stochastic variance-reduced gradient descent (LCSVRG) in Algorithm 3, which extends the nonconvex variance reduced mirror descent (see [20]) to handle nonlinear constraint. Algorithm 3 can be viewed as a double-loop algorithm in which the outer loop computes the full gradient ∇ f (x k ) Algorithm 3 Level constrained stochastic variance-reduced gradient descent (LCSVRG) 1: Input: x 0 , x -1 , η 0 < η, T ; 2: for k = 0, 1, . . . , K do 3:
if k%T == 0 then 4:
Sample a mini-batch B k of size b uniformly at random and compute
(4.20)
7: end if 8: Set ψ k 0 (x) by (4.3) and set ψ k i (x) by (3.2) for i ∈ [m]; 9: Update x k+1 by (3.1) and update η k+1 by (3.3); 10: end for once every T iterations and the nested loop performs stochastic proximal gradient updates based on an unbiased estimator of the true gradient. In this view, we let k indicate the tth iteration at the r th epoch, for some values t and r . Then we use k and (r , t) interchangeably throughout the rest of this section. We keep the notation ζ k (or ζ (r , j) ) for expressing G k -∇ f (x k ) and note that ζ (r ,0) = 0.
Our next goal is to develop some iteration complexity results of LCSVRG. We skip the asymptotic analysis since it is similar to that of LCSPG. The following Lemma (see [20,Lemma 6.10]) presents a key insight of Algorithm 3 that the variance is controlled by the point distances. We provide proof for completeness.
In Algorithm 3, G k is an unbiased estimator of ∇ f 0 (x k ). Moreover, Let (r , t) correspond to k. If t > 0, then we have
Proof We prove the first part by induction. When k = 0, we have
Next, we estimate the variance of the stochastic gradient. Appealing to (4.20), we have
where the third equality uses the independence of B k and ζ k-1 , the first inequality uses the bound Var(x) ≤ E x 2 , and the second inequality uses the Lipschitz smoothness of F(•, ξ). Taking expectation over all the randomness generating B (r ,1) , B (r ,2) , . . . , B (r ,t) , we have
The next Lemma shows that the generated solutions satisfy a property of sufficient descent on expectation.
Assume that γ k = γ and (r ,0) ) -E ψ 0 (x (r ,t+1) ) , 0 ≤ t < T .
Proof In view of (3), at the jth iteration of the r th epoch, we have
. Summing up the above result over j = 0, 1, 2, ..., t (t < T ) and using Lemma 5, we have
Here we use -1 j=0 • = 0.
We present the main convergence property of Algorithm 3 in the next theorem.
Theorem 5 Suppose that condition (3.9) and assumptions of Lemma 6 hold, b ≥ 2T and K = r 0 T + j 0 for some r 0 , j 0 ≥ 0. Let {α k } be a non-decreasing sequence and {α (r , j) } be its equivalent form in (r , j) notations. Suppose that α (r , j) = α (r ,0) for j = 1, 2, ..., T -1. Then we have
Moreover, if we take T = √ n , b = 8T , γ = L 0 , β = L 0 /2, and α k = T k/T +1, and set δ k = η-η 0 (k+1)(k+2) . Then x k+1 is a randomized Type-I -KKT point with
Proof First, using Lemma 5 and the assumption that b ≥ 2T , for any t ≤ T -1 we have
Note that (4.15) still holds. Therefore, combining (4.15) and (4.25) leads to
It then follows from Lemma 6 that (r ,t+1) ) . (4.26)
Let K = r 0 T + j 0 . Summing up the above inequality weighted by α k and exchanging the notation α k ↔ α (r , j) , then we have
Above, the first inequality applies (4.26) and uses x (r ,T ) = x (r +1,0) while the second inequality uses the monotonicity of {ψ 0 (x k )} and an argument similar to (3.33).
The second part is similar to the argument of Theorem 4. Particularly, combining (3.34) and (4.21) gives
Consequently, using the above relation and an argument similar to show (3.33), we deduce
Therefore, we complete the proof of (4.22) and (4.23).
Using the provided parameter setting, we have
Remark 4 It is interesting to compare the performance of LCSVRG with the other two level constrained first-order methods in the finite sum setting (4.19). Similar to LCPG, LCSVRG runs for O(ε -1 ) iterations to compute Type-I -KKT point.
LCSVRG has an appealing feature that the number of stochastic gradient ∇ F(x, ξ) computed can be significantly reduced for a large value of n. Specifically, Algorithm 3 requires a full gradient ∇ f 0 (x) every T iterations, which contributes
√ nK . This is better than the O(nK ) stochastic gradients needed by LCPG. Moreover, it is better than the bound O(K 2 ) of LCSPG when K is at an order larger than Ω( √ n), which corresponds to a higher accuracy regime of 1 √ n . The complexities of all the proposed algorithms for getting some ε-KKT solutions are listed in Table 2.
Remark 5 While we mainly discuss the finite-sum objective (4. 19), it is possible to extend the variance reduction technique to handle the expectation-based objective (4.1) and improve the O(ε -2 ) bound of LCSPG to O(ε -3/2 ). To achieve this goal, we impose an additional assumption that F(x, ξ) is L 0 -Lipschitz smooth for each ξ in the support set. We choose to omit a detailed discussion on this particular extension, as the technical development for this can be readily derived from the arguments in Sec. 6.5.2. [21] and our previous analysis.
In this section, we consider the constrained problem (1.1) with nonsmooth objective and nonsmooth constraint functions. We assume that f i (i ∈ {0, 1, ..., m}) exhibits a difference-of-convex (DC) structure f i (x) := g i (x)-h i (x): 1) h i is an L h i -Lipschitzsmooth convex function and 2) g i is a structured nonsmooth convex function:
where A i ∈ R a i ×n is a linear mapping, Y i ⊂ R a i is a convex compact set and p i : Y i → R is a convex continuous function. In view of such a nonsmooth structure, we can not simply apply the LCPG method, as the crucial quadratic upper-bound on f i (x) does not hold in the nonsmooth cases. However, as pointed out by Nesterov [29], the nonsmooth convex function g i can be closely approximated by a smooth convex function. Let us denote y i := argmin y i ∈Y i y i , D Y i := max y i ∈Y i y iy i and define the approximation function
where β i > 0.
Given some properly chosen smoothing parameter β i , we propose to apply LCPG to solve the following smooth approximation problem:
Prior to the analysis of our algorithm, we need to develop some properties of the smooth function f
We first present a key Lemma which builds some important connection between the quadratic approximation of smooth function and Lipschitz smoothness. The proof is left in Appendix A.
for all x, y. Then, p(•) satisfies
In smooth approximation, it is shown in [29] that g
i is a Lipschitz smooth function and it approximates the function value of g i with some O(β i )-error:
∇g
Similar properties of f
i are developed in the following proposition.
We have the following properties about the approximation function f
1. Let βi ∈ [0, β i ], then we have f
(5.6)
)
(5.8)
Namely, for any x, y, we have ∇ f
(5.9)
On the other hand, using the boundedness of Y i , we have
Combining the above two results gives the desired inequality. Part 2. Since g
i and h i are both convex and smooth functions, we have
Summing up the above two inequalities and noting the definition of f
Similarly, using convexity of g β i i and smoothness of h i , we obtain that f β i i has a negative lower curvature -L h i . Part 3. The Lipschitz continuity (5.9) is an immediate consequence of part 2) and Lemma 7.
When βi = 0, Relation (5.6) reads f
Together with Assumption 2, it can be seen that x 0 is also strictly feasible for problem (5.1). This justifies that LCPG is well-defined for problem (5.1).
The Lipschitz constant of ∇ f
be derived in a different way. Since ∇g β i i and ∇h i are L β i g i and L h i Lipschitz continuous, respectively, we can show by triangle inequality that ∇ f
In contrast, by exploiting the asymmetry between lower and upper curvature, Proposition 4 derived a slightly sharper bound on the gradient Lipschitz constant.
Throughout this section, we choose specific β i to ensure
. Hence, we can define the additive approximation factor above as
(5.10)
Note that (5.4) provides an approximation error for function values, or the so-called zeroth-order oracle of function g i . However, convergence results for nonconvex optimization are generally given in terms of first-order stationarity measure, implying that we need approximation for first-order oracle for the function f i and consequently function g i . Below we discuss a widely used approximate subdifferential for convex functions and generalize it for nonsmooth nonconvex functions.
Definition 5 [ν-subdifferential] We say that a vector v ∈ R n is a ν-subgradient of the convex function p(•) at x if for any z, we have
The set of all ν-subgradients of p at x is called the ν-subdifferential, denoted by ∂ ν p(x). Moreover, we define ν subdifferential of nonconvex function f i as ∂ ν f i (x) := ∂ ν g i (x) + {-∇h i (x)} where the addition of sets is in Minkowski sense.
Finally, we define a generalization of type-I KKT convergence criterion for structured nonsmooth nonconvex function constrained optimization problem: Definition 6 We say that a point x is an ( , ν) type-III KKT point of (1.1) if there exists λ ≥ 0 satisfying the following conditions:
(5.13)
Moreover, we say that x is a randomized ( , ν) type-III KKT point of (1.1) if (5.11), (5.12) and (5.13) are satisfied in expectation.
The -subdifferential and the type-III KKT point are essential for associating smooth approximation with the original nonsmooth problem. We build some important properties in the following proposition.
Proposition 5 Let β i and ν satisfy (5.10).
where the first inequality follows from the first relation in (5.4), and the third inequality follows from second relation in (5.4). Noting the definition of ν-subgradient, we conclude the proof.
Part 2. It suffices to show the conversion of randomized Type-I KKT points to randomized Type-III KKT points. Suppose that x is a randomized Type-I -KKT point and we have λ
Using Proposition 4, we have
This implies
Summing up this inequality over i = 1, 2, 3, ..., m and taking expectation with all the randomness, we have the
Moreover, we have
Now, we are ready to discuss the convergence rate of LCPG for nonsmooth nonconvex function constrained optimization. Theorem 6 Assume that β i , ν satisfy (5.10) and set δ k = η-η 0 (k+1)(k+2) when running LCPG to solve problem (5.1).
Proof Our analysis resembles the proof of Theorem 2. Using a similar argument in (3.33), we have
(5.14)
Combining this result with Lemma 3 we obtain 15), we see that x k+1 is a Type-I -KKT point for
), we have
Using the definition of k and Proposition 5 we obtain the desired result.
LCPG requires the exact optimal solution of subproblem (3.1), which, however, poses a great challenge when the subproblem is difficult to solve. To alleviate such an issue, we consider an inexact variant of LCPG method for which the update of x k+1 only solves problem (3.1) approximately. This section is organized as follows. First, we present a general convergence property of inexact LCPG when the subproblem solutions satisfy certain approximation criterion. Next, we analyze the efficiency of inexact LCPG when the subproblems are handled by different external solvers. When the subproblem is a quadratically constrained quadratic program (QCQP), we propose an efficient interior point algorithm by exploiting the diagonal structure. When the subproblem has general proximal components, we propose to solve it by first-order methods. Particularly, we consider solving the subproblem by the constraint extrapolation (ConEx) method and develop the total iteration complexity of ConEx-based LCPG.
Throughout the rest of this section, we will denote the exact primal-dual solution of (3.1) as ( x k+1 , λ k+1 ). We use the following criterion for measuring the accuracy of subproblem solutions.
We say that a point x is an -solution of (3.1) if
The following theorem shows asymptotic convergence to stationarity for inexact LCPG method under mild assumptions. Since the proof is similar to the previous argument, we present the details in Appendix B for the sake of completeness. Note that the theorem applies to a general nonconvex problem and hence applies to convex problems as well.
Theorem 7 Suppose that Assumption 3 holds and let x k+1 be an k -solution of (3.1)
Then all the conclusions of Theorem 1 still hold. Then the dual sequence { λk } is uniformly bounded by a constant B > 0. Moreover, every limit point of inexact LCPG is a KKT point.
Under the inexactness condition in Definition 7, we establish the complexity of inexact LCPG in the following theorem.
)
(6.4)
In particular, using
Proof Using (3.8) with x k+1 replaced by x k+1 (the optimal solution of problem (3.1)) and adding f (x k ) + L 0 2 x kx k+1 2 on both sides, we have
where the second inequality follows from ψ k 0 (x k ) = ψ 0 (x k ) as well as x k+1 being an k -solution (see Definition 7) of subproblem (3.1), and the third inequality follows from the fact that ψ k 0 (x) ≥ ψ 0 (x) for all x ∈ dom χ 0 . Using Lemma 3 (again x k+1 is replaced by x k+1 ), noting that k satisfies the requirements of Theorem 7 implying that λ k ≤ B and using (6.6), we have
Similar to the argument of (3.34), we have
Multiplying (6.6), (6.7) and (6.8) by α k and summing over k = 0, 1, . . . , K give (6.1), (6.2) and (6.3). We derive a convergence rate based on the specified parameters. First, from relation (6.6), we note that ψ 0 (x k+1 ) ≤ ψ 0 (x k ) + k . Hence, we have by induction that
By setting
for all k ≥ 0 (note that k satisfies the requirement of Theorem 7), we have
Here, (i), (ii) follows from (6.9) and α k+1 -
and last inequality follows since
2 and (6.10) inside (6.4), we have (6.5). Hence, we conclude the proof.
Compared to the convergence result (3.31) for exact LCPG, we have to control the accumulated error in Δ for the inexact case (6.4). However, we need an even more stringent condition on the error to ensure asymptotic convergence. Specifically, we assume ε k to be smaller than the level increments δ k i to ensure that each subsequent subproblem is strictly feasible. As long as the subproblems are solved deterministically with sufficient accuracy, we can ensure such feasibility as well as the boundedness of the dual.
Note that the convergence analysis of the inexact method for the stochastic case will go through in a similar fashion. In particular, the subproblems of LCSPG are still deterministic in nature. Hence, a deterministic error can be easily incorporated into the analysis of the stochastic outer loop. In particular, Proposition 3 will have an additional k in the RHS. We can use k = min i∈[m] δ k i 2 to ensure the strict feasibility. Following the analysis in Theorem 4, we will get the additional term K k=0 α k k . Note that we have identical policies for α k in the above analysis and Corollary 2. Furthermore, since δ k used above and in Corollary 2 are the same, we have identical values of k as well. Following the above development, we can easily bound the additional K k=0 α k k term.
Our goal is to develop an efficient interior point algorithm to solve problem (3.1)
Without loss of generality, we express the subproblem as the following QCQP:
We assume that the initial solution x of such problem is strictly feasible, namely, there exists δ > 0 such that
Let e 1 = [1, 0, . . . , 0] T ∈ R d+1 . With a slight abuse of notation, we can formulate (6.11) as the following problem
Here we set artificial variables L m+1 = 1, a m+1 = 0 and b m+1 = 1 2 R 2 for some sufficiently large R. We explicitly add such a ball constraint to ensure bound on (η, x). Note that the bound R always exists since our domain is compact and the objective is Lipschitz continuous. Our goal is to apply the path-following method to solve (6.13). We denote
The key idea of the path-following algorithm is to approximately solve a sequence of penalized problems
with increased values of τ , and generate a sequence of strictly feasible solution u τ close to the central path-a trajectory composed of the minimizers u * τ = argmin u φ τ (u). We apply a standard path-following algorithm (See [28,Chapter 4]) for solving (6.13), and outline the overall procedure in Algorithm 4. This algorithm consists of two main steps:
1. Initialization: We seek a solution u 0 near the analytic center (i.e. minimizer of φ(u)). To this end, we solve a sequence of auxiliary problems φτ (u) = τ w T u + φ(u) where w = -∇φ( û). It can be readily seen that û is in the central path of this auxiliary problem with τ = 1. Performing a reverse path-following scheme ( decreasing rather than increasing τ ), we gradually converge to the analytic center. 2. Path-following: We solve a sequence of penalized problems with an increasing value of τ by a damped version of Newton's method, which ensures the solutions in the proximity of the central path.
Algorithm 4 Path-following Interior Point Method ( [28])
Phase Zero: Approximate analytic center 2: for i = 0, 1, . . . do 3:
Set u * = u i+1 and Break; 7:
end if 8: end for Phase One: Path-following scheme 9: Set u 0 = u * , τ 0 = max{τ : n(φ τ , u 0 ) ≤ κ}, s = √ υ γ ln 2υ τ 0 ε -1; 10: for i = 0, 1, . . . , s do 11:
12: Obtain u i+1 from calling Newton(φ τ i+1 , u i , τ i+1 , κ); 13: end for 14: Output: u s+1 .
Damped Newton method for solving the subproblem. 15: function Newton( f , v 0 , τ , ) 16:
for s = 0, 1, 2, . . . do 17:
if n( f , v s ) ≤ then Break; 18: end if 19:
end for 21: end function
First, we calculate the gradient and Hessian map of φ t (•):
where θ i = -gi (u) -1 , and
Note that computing the gradient ∇φ t (u) takes O(dm), hence the computation burden is from forming and solving the Newton systems. This is divided into two cases.
1. m < d. Then the Hessian is the sum of a low rank matrix and a diagonal matrix.
Based on the Sherman-Morrison-Woodbury formula, we have
Computing the product N T Γ -1 N takes O(m 2 d) while performing Cholesky factorization takes O(m 3 ). Therefore, the overall complexity of each Newton step is
In such case, we can directly compute N N T in O(md 2 ) and then perform Cholesky factorization ∇ 2 φ τ (x) = L L T in O(d 3 ), followed by two triangle systems. Hence the overall complexity of a Newton step is
Due to the above discussion, the cost of computing each Newton system is O min{d, m} • md . (6.17)
Before deriving the complexity of solving the subproblems, we require some additional assumptions. We assume that M = max x ∇g i (x) and max g 0 (x)min x g 0 (x) ≤ V . Note that these assumptions are easily satisfied if we assume functions in the original problem have bounded level sets.
According to [28, Theorem 4.5.1], the complexity of interior point methods depends not only on the time to follow the central path, but also on the time to arrive near the analytic center from an arbitrary initial point. Let us put it in the context of Algorithm 1. Despite the strict feasibility guarantee, we do not know whether x k is near the analytic center of each subproblem. It remains to show how to control the complexity of approximating the analytic center.
To measure the strict feasibility of the initial point, we use the Minkowsky function of the domain, which is defined by π x (y) = inf{t > 0 : x + t -1 (yx) ∈ D} for any given x in the interior of the domain. With the help of the Minkowsky function, we bound the distance between the initial point and the boundary in the following proposition.
Proposition 6 Let û = (g 0 ( η), x) where η = g 0 ( x) + δ. If u -û ≤ δ M+1 , then u is feasible for problem (6.13). Moreover, we have
where u * is defined in phase zero of Algorithm 4.
We have
Analogously, for i = 0, 1, . . . , m, we have
Using triangle inequality, we have gi (u) = g i (x) ≤ g i ( x) + δ=0. The last constraint in (6.13) is trivially satisfied for sufficiently large R. Therefore, u is a feasible point of (6.13).
Let t + = (M+1) û-u * (M+1) û-u * +δ , then from the above analysis, we know that the point
must be a feasible solution. Using the last constraint u ≤ R, we immediately obtain the bound (6.18).
Using [28,Theorem 4.5.1] and Proposition 6, we can derive the total complexity of solving the diagonal QCQP.
Theorem 9 Under the assumptions of Proposition 6, the total number of Newton steps to get an ε solution is
In the inexact LCPG method, assume that the subproblems are solved by Algorithm 4 and the returned solution satisfies the inexactness requirement in Theorem 8. Then, to get an O( , ) Type-II KKT point, the overall arithmetic cost of Algorithm 4 is
Proof According to Theorem 8, the total number of LCPG is K = O(1/ε). In the kth iteration of LCPG, we set the error criteria ν = O( 1 k 2 ) and ε = O( 1 k 2 ). Theorem 9 implies that the number of Newton steps is N k = O( √ m ln(k)). Therefore, the total number of Newton steps in LCPG is
Combining this result with (6.17) gives us the desired bound.
10 First, at the kth step of LCPG, we need log(k) iterations of interior point methods, of which the complexity order is equally contributed by the two phases of IPM. Specifically, we first require O(ln(k)) Newton steps to pull the iterates from near the boundary to the proximity of the central path, and then require O(ln(k)) to obtain an O(1/k 2 )-accurate solution. Second, it is interesting to consider the case when the constraint is far less than the feature dimensionality, namely, m d. We observe that the total computation O dm 2.5 K ln K is linear in dimensionality. Third, despite the simplicity, the basic barrier method offers a relatively stronger approximate solution than what is needed in Theorem 8, the feasibility of the solution path allows us to weaken the assumption to εk = 0. Nevertheless, besides our approach, it is possible to employ long-step and infeasible primal-dual interior point methods which may give a better empirical performance.
In this section, we use a previously proposed ConEx method [4] to solve the subproblem (3.1) when general proximal functions χ i are present. Then, we analyze the overall complexity of LCPG method with ConEx method as a subproblem solver. First, we formally state the extended version of problem (6.11) as follows: min x∈X φ 0 (x) := g 0 (x) + χ 0 (x) s.t. φ i (x) := g i (x) + χ i (x) ≤ 0, i = 1, . . . , m. (6.19) For the application of ConEx for the subproblem, we need access to a convex compact set X such that ∩ i dom χ i ⊆ X . Moreover, X is a "simple" set in the sense that it allows easy computation of the proximal operator of χ 0 (x) + i=1 w i χ i (x) for any given weights w i , i = 1, . . . , m. Such assumptions are not very restrictive as many machine learning and engineering problems explicitly seek the optimal solution from a bounded set. Under these assumptions, we apply ConEx to solve the subproblem (3.1) of LCPG. We now reproduce a simplified optimality guarantee of the ConEx method below without necessarily going into the details of the algorithm.
Theorem 10 [4] Let x be the output of ConEx after T iterations for problem (6.19). Assume that φ 0 is a strongly convex function and ( x, λ) is the optimal primal-dual solution. Moreover, Let B be a parameter of the ConEx method which satisfies B > λ . Then, the solution x satisfies
123
Even though ConEx can be applied to a wider variety of convex function constrained problems, it has two vital and intricate issues that need to be addressed in our context:
1. The solution path of ConEx can be arbitrarily infeasible in the early iterations, while the successive iterations make the solutions infeasibility smaller. Note that the approximation criterion in Definition 7 requires guarantees on the amount of infeasibility. This implies ConEx has to run a significant number of iterations before getting sufficiently close to the feasible set. 2. Since ConEx is a primal-dual method, its convergence guarantees depend on the optimal dual solution λ * . Moreover, a bound on the dual, B(> λ * ), is required to implement the algorithm to achieve an accelerated convergence rate of O(1/T
2 ) for strongly convex problems. From Theorem 10, it is clear that ConEx requires a bound B. This requirement naturally leads to two cases: (1) bound B can be estimated apriori, e.g., see Lemma 2; and (2) bound B is known to exist but cannot be estimated, e.g., see Theorem 1. Both cases have different convergence rates for the subproblem which leads to different overall computational complexity. Case 1: B can be estimated apriori. In this case, we do not need to estimate B k as in (6.20). Using the bound B, we can get accelerated convergence of ConEx in accordance with Theorem 10 which leads to better performance of the LCPG method. The corollary below formally states the total computational complexity of LCPG method for this case. Corollary 4 If an explicit value of B is known, the LCPG method with ConEx as subproblem solver obtains O( 1 K , 1 K ) type-II KKT point in O(K 2 ) computations. Proof According to Theorem 10, the required ConEx iterations for each subproblem can be bounded by
Since B is a constant, we have
. Hence, we conclude the proof. Case 2: B is known to exist but cannot be estimated. For the subproblem (3.1), we can easily find B k > λ k+1 by using the difference in levels of successive iterations. This bound is weak, especially in the limiting case as it does not take into account Proposition 7 For subproblem (3.1), we have
(6.20)
Proof By Slater's condition, we know that λ k+1 exists. Then, due to saddle point property of ( x k+1 , λ k+1 ), we have for all x ∈ X
where the equality follows by complementary slackness. Using x = x k in the above relation and noting that
where second inequality follows from λ k+1 ≥ 0 and δ k > 0 and last inequality follows due to the fact that λ k+1 1 ≥ λ k+1 . We can further upper bound the LHS of the above relation as follows
where the last inequality follows since x k+1 is feasible for the original problem (1.1).
Combining the above two relations, we obtain (6.20). Hence, we conclude the proof.
We now state the final computation complexity of LCPG withConEx which uses the bound in (6.20).
If an explicit value of B is not known, the LCPG method with ConEx as subproblem solver obtains O( 1 K , 1 K ) type-II KKT point in O(K 4 ) computations.
Proof Using Proposition 7, we can set B k :=
where i * := argmin i∈m η iη 0 i . Then, required ConEx iterations T k can be bounded by
Finally, in view of (6.9) and the fact that
) which is the overall computational complexity of LCPG method with ConEx as subproblem solver to obtain
Remark 11 [Gradient complexity vs. computational complexity] Note that evaluating the gradient of ψ k i (x) is relatively simple since it does not involve any new computation of ∇ f i (x). In that sense, the entire inner loop requires only one ∇ f i computation; hence the total gradient complexity of ∇ f i equals the total outer loops of inexact LCPG. On the other hand, inner loop computation does contribute to the problem's computational complexity. However, such iterations are expected to be very cheap given the ease of obtaining gradients for the QP subproblem (3.1) with identity hessian matrices.
where the last inequality uses the fact that -1 2 a + b 2 ≤ -1 2 a 2a, b ≤ - 1 2 a 2 + a b with a = xz + and b = z +x + . Finally, combining the above two results gives the desired inequality (7.1).
Using the above lemma, we provide the main convergence property of LCPG for convex optimization.
Lemma 9 Let x be feasible solution. Then, we have
where (i) follows from the definition of ψ k 0 , (ii) follows since x k+1 is an k solution of (3.1), (iii) follows by complementary slackness for the optimal primal-dual solution for (3.1) and (iv) follows from Lemma 8. In particular, we use g(x)
Finally, note that
Using the above two relations in (7.7), we obtain (7.6). Hence, we conclude the proof.
Let x * be an optimal solution of (1.1) and D := max{ xy : x, y ∈ dom χ 0 , ψ i (x) ≤ η i , ψ i (y) ≤ η i , for all i ∈ [m]}. Now, we show convergence rate guarantees.
Theorem 11 Consider general convex optimization problems with μ 0 = 0. Suppose Assumption 3 is satisfied and set δ k = (η-η 0 ) (k+1)(k+2) . Then we have
123
Proof From Lemma 9 with μ 0 = 0 for convex part and ψ(x * ) ≤ η, we have
Dividing both sides by L 0 + λ k+1 ,L 2 , we have
Note that the sequence { λ k+1 } is uniformly bounded above such that λ k+1 ≤ B for all k ≥ 0. Using this fact and the above relation, we have
Using δ k = η-η 0 (k+1)(k+2) and k = η-η 0 2(k+1)(k+2) , we have x k is strictly feasible solutions for (3.1) for all k. Hence, under Assumption 3, we can follow the steps of Theorem 1 to show uniform bound B on sequence { λ k }. Using these values in (7.9), we have
Due to the optimality of the exact solution x k+1 , we have
Combining these two relations, we get:
Effectively, inexact LCPG method is almost (up to an additive error of k ) a descent method. Using this relation recursively, we have
Using the above relation in (7.10), we have
Multiplying the above relation by k + 1 and summing from k = 0 to K -1, we have
After rearranging, this relation implies (7.8). Hence, we conclude the proof.
Consider strongly convex problems (μ 0 > 0) and suppose that Assumption 3 is satisfied. Set δ k = ρ k (1 -ρ)(η -η 0 ) where ρ = L 0 -μ 0 2(L 0 -aμ 0 ) , 2 k ≤ a(1 -ρ)ρ k η -η 0 and a ∈ (0, 1). Then we have
Moreover, if k = 0, we have
Proof Proceeding similar to the convex case, using Lemma 9, we obtain
Combining the above two results, we have
Let us denote
Multiplying both sides of the above inequality by
. Using these relations in (7.13), we have
Similar to the convex part, we also have
Using the above relation into (7.14), we have
Summing the above relation from k = 0 to K -1, we have
Note that
Combining the above two relations we obtain the desired result (7.11).
In this section, we conduct some preliminary studies to examine our theoretical results and the performance of the LCPG method. The experiments are run on CentOS with Intel Xeon (2.60 GHz) and 128 GB memory.
In the first experiment, we compare LCPG with some established open-source solvers such as CVXPY [11] and DCCP [32]. We consider the penalized Quadratically Constrained Quadratic Program (QCQP) described as follows, min
where each Q i (0 ≤ i ≤ m) is an n × n matrix, b 0 , b 1 , . . . , b m are n-dimensional real vectors, α is a positive weight on the ℓ 1 norm penalty, which helps to promote sparse solution. In the first setting, we consider a convex constrained problem where each Q i is a positive semidefinite matrix. We set Q i = V DV T where V is an n × n random sparse matrix with density 0.01, and its nonzero entries are uniformly distributed in [0, 1]. D is a diagonal matrix whose diagonal elements are uniformly distributed in between [0, 100]. We set b i = 10e +v, where e is a vector of ones and v ∈ N (0, I n×n ) is sampled from standard Gaussian distribution. We set c i = -10 to make x = 0 a strictly feasible initial solution. Furthermore, we add a ball constraint to ensure that the domain is a compact set. We set r = √ 20 and α = 1. We fix m = 10 and explore different dimensions n from the set {500, 1000, 2000, 3000, 4000}.
We solve Problem (8.1) by both CVXPY and LCPG. Both use the initial solution x = 0. For CVXPY, we use MOSEK as the internal solver due to its superior performance in quadratic optimization. In LCPG, for simplicity, we also solve the diagonal quadratic subproblem by MOSEK through CVXPY. Note that calling the external API repetitively for each LCPG subproblem only causes more overheads to run LCPG. Nonetheless, as we shall see, the standard IPM solvers can still fully leverage the diagonal structure and exhibit fast convergence.
In Table 3, we present the experiment results of the compared algorithms. The final objective, the norm of the dual solution (DNorm), and for LCPG, the maximum dual norm in the solution path (Max DNorm) are reported. All values represent the average of 5 independent runs. From the results, we observe that while LCPG does not outperform CVXPY for the small-size problem (n = 500), LCPG becomes increasingly favorable as the problem dimension increases. This justifies the empirical advantage of our proposed approach as we do not need to construct a full Hessian matrix. Moreover, interestingly, we observe that the dual solution norm { λ k } is increasing, reaching the maximum at the last iteration. This accounts for the equal values of DNorm and Max DNorm. Meanwhile, in all the cases, the dual remains bounded and the reported dual norm closely aligns with the solution returned by CVXPY. This result confirms our intuition that the dual bound is intricately tied to the nature of problems.
In the second setting of this experiment, we examine the performance of LCPG on nonconvex constrained optimization. Specifically, we express Q i as the difference of two matrices: Q i = P i -S i , where P i is generated in the same manner as Q i in the first setting, and S i = 10I n×n . Given the construction of the quadratic components, it is natural to view the function 1 2 x T Q i x + b T i x + c i as a difference of two convex quadratic functions: 1 2 x T P i x + b T i x + c i -1 2 x T S i x. Leveraging this decomposition, we apply the DC programming, and more specifically, the DCCP framework to solve and LCSVRG. We apply all these algorithms to a sparsity-induced finite-sum problem, wherein a nonconvex constraint is incorporated into the supervised learning framework to actively enforce a sparse solution. The optimization problem is as follows min where f i (x) is a smooth loss function associated with the ith sample, ψ 1 (x) is the difference between ℓ 1 -penalty and a convex smooth function g(x). Employing a difference-of-convex constraint is seen as a tighter relaxation of the cardinality constraint x 0 ≤ κ than the ℓ 1 relaxation. The appealing properties of difference-ofconvex penalties have been demonstrated in various studies [5,14,16,17,36,37].
In view of the concave structure of -g(x), there is a strong asymmetry between the lower and upper curvature of -g(x), namely, the following -L g 2 yx 2 -∇g(y) T (xy)g(y) ≤ -g(x) ≤ -g(y) -∇g(y) T (xy) (8.3) holds for certain L g > 0. Note that this is much stronger than the L g smoothness condition which adds an extra L g 2 yx 2 on the right-hand side of (8.3). Due to this feature, one can impose a tighter piece-wise linear surrogate function constraint β x 1g(x k ) -∇g(x k )(xx k ) ≤ η k 1 in the LCPG subproblem. It should be noted that our analysis is readily adaptable to accommodate this scenario since it is the smoothness, as opposed to concavity/convexity, that plays a central role in our convergence analysis and that remains valid. An empirical advantage of this approach is that we now have a tractable subproblem solvable in nearly linear time. See more discussion in [5].
Our experiment considers the task of binary classification with logistic loss, denoted by f i (x) = log(1 + exp(-b i (a T i x)), where a i ∈ R d , b i ∈ {1, -1}, 1 ≤ i ≤ n. We use the SCAD penalty g(x) = d j=1 h β,θ (x j ) where h β,θ (•) is defined in (3.22). We use the real-sim dataset from the LibSVM repository [10] and the covtype data from the UCI repository [19]. For the latter, we formulate a binary classification task by distinguishing class "3" from the other classes. We set β = 2, θ = 5, and η 1 = σ d, with σ ∈ {0.4, 0.6} for covtype and σ ∈ {0.1, 0.2} for real-sim dataset. For each algorithm, we use its theoretically suggested batch size and stepsize. for a fair comparison, we count n evaluations of the stochastic gradient as an effective pass over the dataset and plot the objective value over the number of effective passes. Figure 3 plots the convergence result of the compared algorithms. It can be readily seen that LCSPG performs better than LCPG in terms of the number of gradient samples, and LCSVRG achieves the best performance among the three algorithms. The empirical findings further confirm our theoretical complexity analysis.
In this work, we presented a new LCPG method for nonconvex function constrained optimization which can achieve gradient complexity of the same order as that of unconstrained nonconvex problems. The key ingredient in our algorithm design is the use of constraint levels to ensure the subproblem feasibility, which allows us to overcome a well-known difficulty in bounding the Lagrange multipliers in the presence of nonsmooth constraints. Moreover, a merit of our convergence analysis is its striking similarity with that of gradient descent methods for unconstrained problems. Therefore, we can easily extend our method to minimizing stochastic, finite-sum, and structured nonsmooth functions with nonconvex function constraints; many of the complexity results were not known before. Another important feature of our work is that the method can deal with complex scenarios where the subproblems are not exactly solvable. To the best of our knowledge, existing work on sequential convex optimization (SQP, MBA) only assumes the subproblems to be exactly solved. We provided a detailed complexity analysis of LCPG when the subproblems are inexactly solved by customized interior point method and first-order method. Finally, we clearly distinguished the notion of gradient complexity from that of computational complexity. In terms of gradient complexity, all of our proposed methods are state-of-the-art and easy to implement. Whether the computational complexity can be further improved for composite cases remains an open problem that we leave as a future direction.
Funding Open access funding provided by SCELC, Statewide California Electronic Library Consortium Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Let {δ n } n≥1 be a function of C ∞ -smooth, real-valued mollifier functions over R d where, for every n ≥ 1, we have: (i) δ n ≥ 0, (ii) δ n (τ )dτ = 1, and (iii) and δ n (τ ) = 0 for τ satisfying τ ≥ for all x, y. Note that p n is C ∞ -smooth. Hence, using Taylor's theorem, there exist ξ ∈ [x, y] such that p n (x)p n (y) -∇ p n (y), xy = 1 2 xy, ∇ 2 p n (ξ )(xy) + o( xy 2 ). Using this relation along with (A.1) and denoting v := yx, we have
Now, diving both sides of the above relation by v 2 , taking y → x which implies ξ → x and ∇ 2 p n (ξ ) → ∇ 2 p n (x), we have
for all v and x. The above relation is equivalent to the fact that ∇ 2 p n (x) ≤ max{L, μ} for all x. From here, for any x, y, we have ∇ p n (x) -∇ p n (y) = 1 t=0 ∇ 2 p(y + t(xy))(xy)dt ≤ 1 t=0 ∇ 2 p(y + t(xy))(xy) dt ≤ 1 t=0 ∇ 2 p(y + t(xy)) xy dt ≤ max{L, μ} xy . Now, taking n → ∞ and noting that ∇ p n (x) → ∇ p(x) for all x, we have (5.3). Hence, we conclude the proof.
First of all, using the definition of k and the fact that ψ k i (x k+1 ) ≤ η k i + k for all i ∈ [m], we have
Hence x k is strictly feasible solution of (3.1). Due to Slater condition, there exists a pair of optimal primal and dual solutions, which we denote by xk+1 and λ k+1 . We first prove the following lemma. Our argument will be based on the following key result. Proof Using optimality of x k+1 , strong convexity of ψ k 0 , feasibility of x k for the subproblem (3.1) and ψ k 0 (x k+1 ) ≤ ψ k 0 ( x k+1 ) + k , we have,
Since k is summable, we have that x kx k+1 2 is summable. This implies x kx k+1 → 0. Since k → 0 and x k+1 is a unique optimal solution of (3.1), we have x k+1x k+1 → 0. Then, using Cauchy-Schwarz inequality, we have x k+1 -x k ≤ x k+1x k+1 + x k+1x k and hence, x k+1x k → 0. Hence, we conclude the proof. Now, we show boundedness of λk+1 . Assume, for the sake of contradiction, that λk+1 is unbounded. Let x be a limit point of {x k }. Passing to a subsequence if necessary, we have x k → x. Using Lemma 10, we have x k+1 → x and x k+1 → x. Then, we have
Note that the above relation is comparable to (3.10) up to an error term of k . Following the arguments in the proof of Theorem 1 (Part 1, (3.10) onwards) and noting that k is summable, we conclude that { λk+1 } is bounded. Now, we prove limit point of {x k } is a KKT point. Since L k (x k+1 , λk+1 ) ≤ L k ( x k+1 , λk+1 ) + k , we rewrite (3.18) as
Let x be a limit point of sequence {x k }. Since λk+1 is bounded, we assume limit point λ. Without loss of generality, we have x k → x and λk+1 → λ. Then, in view of Lemma 10, we have lim k→∞ x k+1 → x and lim k→∞ x k+1 → x. Taking limit k → ∞ in (B.2), we have ∇ f 0 ( x) + m i=1 λi ∇ f i ( x), xx + χ 0 ( x) -χ 0 (x) + λ, χ ( x) -χ(x) ≤ 0.
Note that the above equation matches with (3.19) exactly. From here, we follow the proof of Theorem 1 (Part 2, (3.19) onwards) to conclude first-order stationarity of
This assumption is used to ensure the limit point of a certain sequence in the analysis. There are other conditions that can ensure the existence of a limit point as we will discuss in Remark 1.