{'fraction_non_alphanumeric': 0.05643666323377961, 'fraction_numerical': 0.014443872296601441, 'mean_word_length': 4.431548035239826, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization

In this paper, we develop an interior-point method for solving a class of convex optimization problems with time-varying objective and constraint functions. Using log-barrier penalty functions, we propose a continuous-time dynamical system for tracking the (time-varying) optimal solution with an asymptotically vanishing error. This dynamical system is composed of two terms: (i) a correction term consisting of a continuous-time version of Newton's method, and (ii) a prediction term able to track the drift of the optimal solution by taking into account the time-varying nature of the objective and constraint functions. Using appropriately chosen time-varying slack and barrier parameters, we ensure that the solution to this dynamical system globally asymptotically converges to the optimal solution at an exponential rate. We illustrate the applicability of the proposed method in two practical applications: a sparsity promoting least squares problem and a collision-free robot navigation problem.


I. INTRODUCTION
The interplay between optimization and control theory is rich and fruitful, resulting in a plethora of efficient computational tools to solve fundamental control problems [1]- [7]. Dynamical systems theory provides an array of mathematical tools to analyze the behavior of iterative algorithms proposed to solve standard optimization problems [8], [9]. In this direction, control theory can be used to guarantee the convergence of iterative algorithms to accurate solutions, as well as to analyze the impact of numerical errors and computational delays. Control tools have been extensively exploited in the context of stationary (i.e., time-invariant) optimization problems, in which both the objective function and constraints do not depend on time [1]- [7]. In many practical settings, however, we find optimization problems in which the objective function and/or the constraints depend explicitly on time [10]- [17]. In particular, time-varying optimization problems appear in, for example, the estimation of the path of a stochastic process [10], signal detection with adaptive filters [11], tracking of moving targets [12], and various problems in autonomous systems [13], [14], computer networks [15], and learning [16], [17].
In time-varying optimization problems, the optimal solution is a function of time; therefore, solving the optimization problem is equivalent to tracking the optimal solution as it varies over time. A natural approach to addressing this problem is to sample the objective and constraint functions at particular times and to solve the corresponding sequence of (time-invariant) optimization problems using standard iterative algorithms (e.g., gradient or Newton's method [18], [19]). However, this approach ignores the dynamic aspect of the problem, since each iteration tends to converge towards the optimal point of the sampled time-invariant problem, while the solution of the time-varying case is drifting away over time. Therefore, this approach is likely to induce a steady-state optimality gap (i.e., a tracking error) whose magnitude depends on the time-varying aspects of the problem. This phenomenon has been previously observed in gradient descent algorithms for unconstrained optimization [20], as well as in constrained optimization problems that arise in distributed robotics [21], sequential estimation [10], distributed optimization [22], and neural networks [23].
In this paper, we consider time-varying smooth convex optimization problems characterized by (i) a convex time-varying objective function, and (ii) constraints that are expressed as level sets of time-varying convex functions and affine equalities. To track the time-varying optimal solution of the problem without a tracking error, we propose a continuous-time dynamical system whose state is globally asymptotically driven to the optimal solution at an exponential rate (under certain technical conditions). In particular, we develop a predictioncorrection interior-point method that utilizes information about time variations of the optimization problem in order to predict and correct the drift in the optimal solution, resulting in an asymptotically vanishing optimality gap.
The paper is structured as follows. In Section II, we formally state the problem under consideration and introduce some regularity assumptions needed in our derivations. We then consider the particular case of time-varying optimization problems without constraints, as well as affine constraints only (Section III). In both cases, we propose to track the optimal solution using a dynamical system composed of two terms: (i) a 'prediction' term that uses information about time variations of the optimization problem, and (ii) a 'correction' term based on a continuous-time version of Newton's method. In Section III-C, we propose a dynamical system able to track the solution of time-varying optimization problems with inequality constraints. In this case, we incorporate a logarithmic barrier function with an appropriately chosen time-varying barrier parameter, as well as a time-varying slack variable used to guarantee global convergence. We show that the proposed dynamical system converges at an exponential rate to the time-varying optimal point for any initial condition (Theorem 1), under mild assumptions. These assumptions correspond to standard requirements to prove convergence of interior-point methods and differentiability of the objective and constraints with respect to time. To illustrate our results, we perform numerical evaluations in a quadratic problem (Section IV-A) and consider two practical applications. The first application is a time-invariant 1 regularized least squares problem in which we show that the use of a time-varying barrier parameter along with a prediction term speeds up the convergence of conventional interior-point methods (Section IV-B). The second application involves the navigation of a robot in an environment with circular obstacles (Section IV-C). We further consider situations in which the robot is charged with the task of tracking a moving target (Section IV-C2). We close with concluding remarks (Section V).
Notation. Let R, R + , and R ++ be the set of real, nonnegative, and strictly positive numbers. The set {1, . . . , n} is denoted by [n]. We denote by I n the n-dimensional identity matrix. We denote by S n the space of n-by-n symmetric matrices. The gradient of a function f (x, t) : II. PROBLEM STATEMENT This paper considers a class of convex optimization programs where both the objective and the constraint functions are indexed by continuous time. Formally, consider a variable x ∈ R n and let t ∈ R ++ be a continuous time index. We then define a time-varying (TV) objective function f 0 : R n × R + → R taking values f 0 (x, t); we also define p timevarying inequality constraint functions f i : R n × R + → R taking values f i (x, t) for i ∈ [p]; and q time-varying affine equality constraint functions f i : . For any given time t > 0, the objective function and the constraints define an optimization problem whose optimal argument x * (t) is defined as: A naive approach to solving (1) is to sample the problem at particular times, say 0 ≤ t 0 < t 1 < · · · , and solve the corresponding sequence of (time-invariant) optimization problems. In particular, for each k ∈ Z + , one could estimate x (t k ) by assuming the objective and constraints are time-invariant on the time interval [t k , t k+1 ) and run standard iterative algorithms (such as interior-point methods [19], [27]). However, this naive implementation is likely to induce steady-state tracking errors.
In particular, the sub-optimality of the solution computed at t k+1 depends on the number of iterations allowed by our computational capabilities during the time interval t ∈ [t k , t k+1 ), as well as how fast the optimal argument has drifted away from x (t k ) during this interval.
Our goal is to develop an alternative approach to solving the TV optimization problem with a vanishing tracking error by leveraging information about the temporal variation of the objective and the constraints. More precisely, we propose a continuous-time dynamical systemẋ(t) = h(x(t), t) whose solution x(t) satisfies x(t) − x (t) → 0 as t → ∞ (i.e., it tracks the optimal solution with asymptotically vanishing error). To facilitate the exposition, we first address TV optimization problems without constraints (Section III-A), and then extend the framework to problems with TV constraints (Section III-B and III-C). In order to make the contributions of the paper more precise, we list below the assumptions that we impose on the optimization problem (1).

Assumption 1 (Convexity)
The objective function f 0 (x, t) and the constraint functions f i (x, t), i ∈ [p] are twice continuously differentiable with respect to x and continuously differentiable with respect to t for all t ≥ 0. Furthermore, Assumption 2 (Strong Convexity) The objective function is uniformly strongly convex, i.e., there exists a positive constant m such that for all times t ≥ 0, the inequality ∇ xx f 0 (x, t) mI n holds.

Assumption 3 (Slater's condition)
The interior of the feasible region is nonempty for all t ≥ 0, i.e., there exits Assumption 4 The number of equality constraints is less than the dimension of the optimization space, i.e., q < n. Moreover, the vectors a i (t), i ∈ [q] are linearly independent for all t ≥ 0. This implies that rank(A(t)) = q for all t ≥ 0.
The uniform strong convexity of the objective function implies that the optimal trajectory x (t) is unique for all t ≥ 0. From Assumption 3, the optimal solution x (t) in (1) at each t ≥ 0 can be characterized using the Karush-Kuhn-Tucker (KKT) conditions [18,Chapter 5]. Finally, Assumption 4 ensures that the system of equations is consistent and has infinitely many solutions at each t ≥ 0. It is worth remarking that we do not make any assumption about asymptotic vanishing time variations in the objective and the constraints, namely, the partial derivates of these functions with respect to time are not assumed to converge to zero. However, we will assume that the optimal solution of the TV optimization problem does not grow exponentially as a function of time. We will explicitly impose this assumption in Section III-C.

III. PREDICTION-CORRECTION METHODS FOR TIME-VARYING OPTIMIZATION
In this section, we consider the TV optimization problem in (1) without inequality constraints. In particular, we consider two versions of this problem: (i) the unconstrained case (Section III-A), and (ii) the case with linear equality constraints (Section III-B). We show that, in both cases, it is possible to track the optimal trajectory x (t) with an exponentially vanishing error. The algorithms developed here will be leveraged in Section III-C to derive a predictioncorrection interior-point method to tracking the solution of (1) when inequality constraints are also considered.

A. Unconstrained Time-Varying Convex optimization
Consider the following unconstrained version of (1): Under sufficient regularity conditions, we could implement a sequence of Newton steps on the function f 0 (x, t) that would rapidly converge to x (t). In the limit of infinitesimal steps, the sequence of Newton's iterations results in the following continuous-time dynamical system: where α > 0 is a constant. The trajectory x(t) generated by (3) would approach a neighborhood around x (t), but it does not track exactly to x (t), since the solution is itself changing over time. To overcome this limitation, observe that-with sufficient regularity-the optimal argument x (t) in (2) satisfies the first-order optimality condition ∇ x f 0 (x (t), t) = 0.
Since this latter condition is true for all times t ≥ 0, the time derivative of this condition should also be null, from where we obtain , where∇ x f 0 denotes the total derivative of ∇ x f 0 with respect to time, while ∇ xt f 0 denotes the partial derivative of the gradient ∇ x f 0 with respect to time. Solving (4) forẋ (t) yields the dynamical systeṁ If the optimal solution x (t) is known at some point in time, the system in (5) can be used to track the evolution of x (t), since (5) guarantees that the optimality ∇ x f 0 (x (t), t) = 0 is satisfied for all times t. If we do not have access to x (t) at any point in time, we propose to combine the dynamics in (3) and (5) to build the following dynamical system: The dynamics in (6) contains two terms: , t) that attempts to track the changes in the objective function [cf. (5) pushes' x(t) towards the optimum. In the next proposition, we show that the dynamical system in (6) converges exponentially to the optimal trajectory x (t).
Proposition 1 Let x (t) be defined as in (2) and x(t) be the solution of (6), where the objective function is m-strongly convex (Assumption 2). Then, the following inequality holds: Proof: See Appendix A.
Proposition 1 confirms that the solution of (6) tends exponentially to a point that satisfies the first-order optimality condition ∇ x f 0 (x (t), t) = 0. For algorithmic implementation, we can discretize the continuous-time dynamics (6) using, for example, Euler's forward method with a constant step size τ [28, Chap. 1]. If the vector field in the right-hand side of (6) is uniformly Lipschitz in x, then the discretization error would be of the order O(τ ) [28, Chap. 1]. Alternatively, one could use line search to generate adaptive step sizes that guarantee a strict reduction in the suboptimality in each iteration [29].

B. Equality-Constrained Time-Varying Convex Optimization
We consider now a version of (1) in which we incorporate equality constraints: where the matrix A(t) : R + → R q×n and vector b(t) : R + → R q define a TV equality constraint. In order to design a dynamical system to track x (t) in (7), we introduce a Lagrange multiplier ν ∈ R q and define the Lagrangian associated with the optimization problem in (7) as From the Lagrangian in (8), we define the TV dual function G(ν, t) := min x∈R n L(x, ν, t) and the optimal dual argument as ν * (t) := argmax ν∈R q G(ν, t). By virtue of Assumptions 2 and 4, the optimal primal-dual pair (x (t), ν (t)) is unique for each time t ≥ 0. Furthermore, we know this optimal pair must satisfy the following KKT conditions: We define the aggregate variable z := [x , ν ] ∈ R n+q and the optimal primal-dual solution z (t) := [x (t) , ν (t) ] so as to rewrite (9) in the condensed form 0 = ∇ z L(x (t), ν (t), t). Since this latter equation must hold for all t ≥ 0, we can take the time derivative of this gradient, which results in a prediction term of the form , similar to the one in (5). We combine this prediction term with a Newton-like correction term of the form −α∇ −1 zz L(z(t), t)∇ z L(z(t), t) to propose the following dynamical system: In the following proposition, we prove that the state of this dynamical system converges exponentially to the optimal solution x (t) of (7).
Proposition 2 confirms that the state of the dynamical system in (10) converges exponentially to the optimal solution x (t) of (7). Notice also that this dynamical system can have any arbitrary initial condition; in other words, the state of the system is globally asymptotically driven to the TV optimal solution x (t) at an exponential rate. In fact, asymptotic feasibility is achieved, since the term , which quantifies the infeasibility, vanishes exponentially, according to (11). Moreover, we show below that, if the dynamical system in (10) starts from a feasible point z(0), it will remain feasible for all t > 0. To prove this, notice that the solution of the dynamical system in (10) This implies that, if the solution is initially feasible (i.e., Remark 1 In contrast to the unconstrained problem considered in Subsection III-A, where the objective function f 0 (x, t) is strongly convex in the primal variable x ∈ R n , the Lagrangian function of the problem with equality constraints, i.e., L(x, ν, t), is no longer strongly convex in the primal-dual variable z = [x ν ] ∈ R n+q .

Remark 2
The assumption ∇ −1 zz L(z, t) 2 ≤ M in Proposition 2 allows to quantify the convergence rate in the domain of the primal variable x [cf. (12)]. The latter assumption is also of practical importance for the following reason: ifż(t) in (10) grew arbitrarily large, then the discretization of (10) would require arbitrarily small step sizes.
In the next subsection, we propose a solution to the most general time-varying optimization problem, where both equality and inequality constraints are considered.

C. General Time-Varying Convex Optimization
In this subsection, we return to our original optimization problem in (1), considering both equality and inequality constraints. In light of the analysis in Subsection III-B, we can always eliminate the equality constraints in (1) by Lagrangian relaxation. Therefore, we ignore equality constraints for now, without losing generality, and will remark on the addition of equality constraints at the end of this subsection. Under Assumptions 1 and 3, the necessary and sufficient KKT conditions [18,Chapter 5] for optimality of x (t) in (1) at each t ≥ 0 read as, In what follows, we use barrier functions [18,Chapter 11] to incorporate the inequality constraints into the objective function. First, we consider the following convex optimization problem, which is equivalent to (1), without equality constraints: where , where c > 0 is an arbitrary constant called the barrier parameter 1 . Therefore, we can approximate (14) by the following smooth convex optimization problem: where c(t) is a time-dependent positive barrier parameter and the domain of the objective function is the open set Our goal is to design a dynamical system able to track the optimal solution of (15). As we show below, this would require the initial condition of this dynamical system to lie inside the initial domain D(0), i.e., x(0) ∈ D(0). To circumvent this requirement, we include a nonnegative time-dependent slack variable s(t) in the optimization problem (15), and solve for the approximate optimal trajectory defined by where Notice that for any x(0) ∈ R n , we can choose s(0) > max i f i ((x(0), 0)) so that x(0) ∈ D(0), i.e., the initial condition lies in the 'enlarged' feasible set D(0). In the next lemma, we characterize the approximation error in terms of c(t), s(t), and the optimal dual variables in (13).
Lemma 1 Let x (t) and x (t) be defined as in (14) and (16), respectively. Then, under Assumptions 1 and 3, the following inequality holds for all t ≥ 0, Proof: See Appendix C.
The above lemma suggests that, if s(t) and c(t) are chosen such that the right-hand side of (17) converges to zero, the approximate solution x (t) converges to the optimal solution x (t) in (14). In what follows, we design a dynamical system whose solution globally asymptotically converges to x (t). Let us define Φ(x, c, s, t) as, Then, the optimal solution x (t) in (16) satisfies the optimality condition ∇ x Φ( x (t), c(t), s(t), t) = 0 n for all t ≥ 0. Given the time evolution of x(t), s(t), and c(t), we can use the chain rule to compute the time derivative of the gradient ∇ x Φ(x, s, c, t), as follows: Our goal is to design the dynamics of x(t), as well as the time evolution of c(t) and s(t), such that the gradient ∇ x Φ vanishes exponentially. In particular, based on the results in Section III, we propose the following dynamical system: The first term inside the bracket in the right-hand side corresponds to a Newton-like term, which is similar to the correction term in (6). The remaining terms in (20) play a role similar to the prediction term in (6), since they account for time variations in Φ(x, c, s, t) through s(t), c(t), and {f i (x, t)} i=p i=0 . Notice that it is important for the dynamics in (20) to render a solution x(t) such that the argument of the logarithmic barrier functions in (18) remains positive, i.e., we must have that x(t) ∈ D(t) for all t ≥ 0. The next lemma states that this is, indeed, the case. In the following lemma, we prove that the solution to (20) converges exponentially to the approximate solution x (t) in (16), for all initial conditions x(0) ∈ R n . Lemma 2 Let x (t) be defined in (16) and x(t) be the solution of (20) for x(0) ∈ R n , s(0) > max i f i ((x(0), 0)), and c(0) > 0. Then, under Assumptions 1, 2, and 3, the following inequality holds, Proof: See Appendix E.
Next, we need to establish the convergence of the approximate solution x (t) in (16) to the optimal solution x (t) in (14). Intuitively, we need the barrier parameter c(t) to asymptotically go to infinity and the slack variable s(t) to asymptotically vanish so that the approximation error vanishes, according to (17). For this to be true, we need to make the following assumption about the optimal dual variables defined in (13).
The above assumption excludes the possibility for the optimal dual variables to escape to infinity exponentially fast. By virtue of Assumption 5, the approximation error in (17) vanishes asymptotically if the slack variable s(t) goes to zero exponentially fast and the barrier parameter c(t) diverges to infinity. The next theorem states the main result of this subsection.
Theorem 1 Consider the optimization problem in (14) and the objective function in (18). Let x(t) be the solution of (20) with initial conditions x(0) ∈ R n , c(0) > 0, and According to Theorem 1, the continuous-time dynamics in (20) yields a solution that asymptotically converges to the optimal solution in (14) from arbitrary initial conditions. Some remarks are in order.

Remark 3 (Barrier Parameter) The barrier parameter c(t)
is required to be positive, monotonically increasing, asymptotically converging to infinity, and bounded in finite time. A convenient choice is c(t) = c(0) exp(γ c t) for γ c , c(0) > 0.
Remark 4 (Adding Equality Constraints) As mentioned at the beginning of Section III-C, we ignored equality constraints in our analysis. In order to account for equality constraints, we define the Lagrangian function as L(x, ν, c, (18), and consider the aggregate vector of decision variables z = [x ν ] ∈ R n+q . If we replace Φ by L in (20) and x with z, we would obtain a dynamical system that solves the optimization problem in (1), where both equality and inequality constraints are considered. However, we need the inverse Hessian inverse in ∇ −1 zz L to be uniformly bounded, i.e., there must exist an M > 0 such that Therefore, using the same arguments as in Proposition 2, the result in Theorem 1 also holds, i.e., lim t→∞ z(t) − z (t) 2 = 0.

Remark 5 (Accelerating Standard Interior-Point Method)
As a particular application of our results, we consider the following time-invariant convex optimization problem, Using barrier functions, we define and the corresponding central path where } is the interior of the feasible set. It follows from Lemma 1 that lim c→∞ x (c)−x = 0. In the standard implementation of the interior-point method [18,Chapter 11], the optimization problem (23) is solved sequentially for a positive growing sequence (c k ) ∞ k=1 , each starting from the optimal solution of the previous optimization problem. The resulting sequence (x (c k )) ∞ k=1 converges to the optimal point x as c k → ∞. For each fixed c k , x (c k ) can be found, for instance, using the following Newton-like dynamics: According to Theorem 1, we have that lim t→∞ x k (t) − x (c k ) = 0. Thus, by choosing the initial points as x k (0) = lim t→∞ x k−1 (t), we can build a continuous path that converges to x in (21). As a less computationally expensive alternative, we propose to consider an increasing time-dependent barrier parameter c = c(t), in lieu of discontinuous jumps. In this case, the problem in (23) renders a time-varying optimization. Hence, the continuous dynamics (20) using the barrier function in (22) yields a solution x(t) satisfying lim t→∞ x(t)−x 2 = 0 when lim t→∞ c(t) = ∞. We will numerically illustrate the performance of this approach in Subsection IV-B.
Remark 6 (Second-Order Implementation) Logarithmic barrier functions present a singularity at the origin that may induce numerical instability in the discrete-time implementation of the dynamical system (20). To avoid this issue, we replace the first-order dynamics in (20) by the following second-order dynamics [15]: where γ > 0 is an arbitrary constant. Intuitively, the gradient function is passed through a first-order low-pass filter (the second ODE in (25)) whose output is then fed into the main dynamics. The resulting dynamics tends to reduce numerical instability induced by discretization. It was shown in [15] that V = 1 2 ∇ x Φ ∇ x Φ + 1 2 y y is a Lyapunov function for (25), proving that lim t→∞ ∇ x Φ = 0.

D. Online Implementation
The dynamical system proposed in (20) includes the prediction term ∇ xt Φ(x, t), whose computation involves finding the terms In an online setting, we might only have access to limited or noisy information about these terms. More precisely, assume that we have access to an estimate of ∇ xt Φ denoted by ∇ xt Φ that satisfies the bound for some known η > 0. In this setting, we consider the following dynamics: where we define a state-dependent α = α(x) as follows: where α 0 satisfies α 0 > η, and ε > 0 is an arbitrary constant. The next theorem states that the solution of (27) converges to an ε-neighborhood of the approximate optimal solution x (t), defined in (16), in finite time and will stay there forever.
Proof: See Appendix F.

IV. NUMERICAL EXPERIMENTS
In this section, we provide three numerical examples to illustrate the time-varying optimization framework herein proposed. In Subsection IV-A, we solve a synthetic optimization problem to illustrate the effectiveness of the prediction-correction interior-point method in solving inequality-constrained problems. In Subsection IV-B, we use the accelerated interior-point method discussed in Remark 5 to solve a large-scale 1 -regularized least-squares problem. In Subsection IV-C, we solve a navigation problem to drive a disk-shaped robot towards a (potentially moving) desired location x d without colliding with obstacles in the environment.

A. Time-Varying Quadratic Programming
Consider the following TV quadratic optimization problem: x (t) := argmin 1 2 (x 1 + sin(t)) 2 + 3 2 (x 2 + cos(t)) 2 , In the following simulation, we show how to track x (t) using the continuous-time dynamics in (20). In order to illustrate the usage of the time-dependent slack variable s(t), we choose the initial condition x(0) = (−2, 0) , which is infeasible at t = 0.
As discussed in Subsection III-C, we include the slack variable 0 1 2 Fig. 1: Plot of the coordinates of the optimal trajectory x (t), defined in (29), and the tracking trajectory x(t).
to enlarge the feasible set. In this example, the augmented objective function in (18) takes the form: In our simulations, we consider the following timedependent barrier parameter and slack variable: c(t) = 10e t and s(t) = 2e −5t . The initial value of the slack variable is s(0) = 2; hence, x(0) is initially feasible with respect to the enlarged feasible set. Using these particular values, all the conditions of Theorem 1 are satisfied. We numerically solve the ODE in (20) for the time interval t ∈ [0, 2π] using Euler's forward method with step size τ = 0.1. In Fig. 1, we plot the trajectory of the resulting solution x(t) = (x 1 (t), x 2 (t)) along with the optimal solution x (t) = (x 1 (t), x 2 (t)) defined in (29). In Fig. 2 we plot the time evolution of the constraint function f 1 (x, t) := x 2 (t) − x 1 (t) − cos(t), as well as the slack variable s(t). Notice how, at t = 0, the state x(t) violates the constraint f 1 (x, t) ≤ 0. However, x(t) converges to the feasible set exponentially fast as the slack variable s(t) vanishes exponentially.

B. 1 -Regularized Least Squares
In this subsection, we illustrate how to use the accelerated interior-point method (described in Remark 5) to solve the following 1 -regularized least-squares problem: where A ∈ R m×n and b ∈ R m are given, and λ > 0 is a regularizer which is commonly used to prevent overfitting whenever m < n. Since the objective function in (30) is not differentiable, we analyze the following (differentiable) equivalent convex program [30]: In the following numerical experiment, we generate a sparse vector x ∈ R 2048 with 10 entries of value ±1, and all other entries equal to zero. The entries of the measurement matrix A ∈ R 256×1024 are independently generated according to the standard normal density. The measured vector b ∈ R 256 is generated by b = Ax + v where v is a contaminating noise drawn from the Gaussian distribution N (0 256 , 0.01 I 256 ). The regularizer parameter is chosen to be λ = 2. For these numerical values, we solve (31) using three methods: (i) the Standard Newton Interior-Point Method (SNIPM) [18,Chapter 11] where the central points x (c) are computed using Newton's method with the sequence c k = 10 × 5 k , k = 0, 1, . . . ; (ii) the Accelerated Newton Interior-Point Method (ANIPM), described in Remark 5, where the barrier parameter is equal to c(t) = 10e t ; and (iii) the Truncated Newton Interior-Point Method (TNIPM), described in [30], where a preconditioned conjugate gradient method was proposed to compute the Newton step, and the barrier parameter is updated at each iteration. For all these three methods, we use a backtracking line search to adaptively select the step size. To assess the progress of the algorithms, we use the following quantity (as proposed in [30]), Here, g(ν) is the dual function of the constrained problem akin to (30): and ν ∈ R m is the dual vector associated with the constraint z = Ax − b. The quantity in (32) is an upper bound of the relative duality gap [p − g(ν)]/g(ν), where p = Ax (λ)−b 2 2 +λ x (λ) 1 is the primal optimal value (see [30] for more details). Fig. 3 illustrates the evolution of η/g(ν) against the iteration number for these three algorithms. For the stopping criterion, we choose η/g(ν) ≤ 10 −4 . In our simulations, the SNIPM takes 42 iterations, while the ANIPM proposed in Remark 5 takes 17 iterations. Notice that the performance of our accelerated method is comparable to TNIPM, since in the latter method the barrier parameter is also updated at each iteration, but the prediction term is not included.

C. Robot Navigation
In this subsection, we solve the navigation problem of driving a disk-shaped robot of radius r > 0 to a given configuration x d without colliding with obstacles in the environment. More precisely, let us consider a closed and convex workspace W ⊂ R n of possible configurations that the robot can take. Assume that the workspace is populated with m nonintersecting spherical obstacles, where the center and radius of the i-th obstacle are denoted by x i ∈ W and r i > 0, respectively. We define the free space, denoted by F, as the set of configurations in the workspace in which the robot does not collide with any of the obstacles. More formally, where B(x, r) is the n-dimensional open ball centered at x with radius r, and B(x, r) represents its closure. Let us denote the center of mass of the robot by x c . Given a final desired configuration x d ∈ F, the navigation problem under consideration consists of finding a trajectory of x c such that x c (t) ∈ F for all t ≥ 0, and lim t→∞ x c (t) = x d . In [31], the authors proposed a solution to this problem using the idea of projected goal, as described below. This idea consists of continuously computing the projection of the destination x d onto a neighborhood around the center of mass of the robot in which there are no obstacles. Denote this projection byx d -yet to be properly defined-then, the control laẇ x c = − (x c −x d ) ensures convergence of the center of mass of the robot to the desired configuration while avoiding the obstacles [31]. As we describe below, this technique can be interpreted as the solution of a TV convex optimization problem. To formulate this problem, we first need to provide some definitions.
We define first the notion of power distance between a point x and a disk B(x i , r i ) as P(x, B(x i , r i )) = x − x i 2 2 − r 2 i , [32]. We define the so-called local workspace around x c as i.e., the set of points in W that are closer (in power distance) to the robot than to any of the obstacles. The local workspace defines a polytope whose boundaries are hyperplanes, such as the polygon marked with a thick light blue line in Fig. 4 (see [31,Eq. (6)] for an explicit expression of these hyperplanes). Furthermore, the collision-free local workspace around x c is defined as [31]: where, Assuming that the robot follows the integrator dynamicsẋ c = u(x c ), the controller proposed in [31] is given bẏ where K > 0 is the gain of the controller and x is the orthogonal projection of the desired configuration x d onto the collision-free local workspace LF(x c ). Under the assumption that the distance between the center of any two obstacles i and j is larger than r i + r j + 2r, it can be shown that the controller law in (36) solves the navigation problem ( [31,Theorem 1]). In what follows, we cast the navigation problem as a TV convex optimization program that can be solved using the tools developed in this paper. 1) Interior-Point Method to Estimate the Projected Goal: We now show that the prediction-correction interior-point method developed in Section III can be used to efficiently build an estimatorx of the projection of x d onto the set LF(x c ), which we denote by x . First, observe that x can be defined as the solution of the following convex optimization problem, x := argmin x∈R n 1 2 x Observe that since a i (x c ) and b i (x c ) depend on the position of the center of mass of the robot, the above optimization problem has an implicit dependence on time through x c . We estimate the projected goal x as the solution to the ODE in (20) with initial condition x(0) = x c (0), i.e., the initial position of the robot, and the following objective function: In Appendix G, we derive explicit expressions for all the terms involved in this ODE.
Next, we consider the control law (36), with the difference that we use an estimate of the projected goal instead of the projected goal itself, i.e., we consider the closed loop dynamicṡ where the estimatorx(t) is the solution to the ODE in (20) with initial conditionx(0) = x c (0). An important feature of x(t) is that it is feasible at all times, i.e.,x(t) ∈ LF(x c ). This follows from Lemma 3 and the fact that the initial condition is assumed to be feasible, i.e., the robot is initially located in the free space. Moreover, the estimatorx(t) converges exponentially to the projection of x d onto the collision-free local workspace, denoted by x .
To evaluate the performance of the proposed controller and optimizer, we consider a square workspace W = [−20, 20] 2 containing 8 circular obstacles (black circles in Fig. 4). In Fig. 4, we also depict the trajectories followed by a discshaped robot of radius equal to one (blue circle) for four different initial conditions. The green and blue lines represent, respectively, the trajectories of the estimatesx(t) of the projected goal onto the collision-free local workspace, and the trajectories of the center of mass of the robot x c (t) for 4 different initial conditions. The blue circle represents a particular configuration of the robot, where the local workspace LW(x) (resp., the collision-free local workspace LF(x c )) is the polygon enclosed within light blue lines (resp., the polygon filled in solid purple). For these particular realizations, we have set α = 5 in (20), and K = 0.01 in (38). Finally, the barrier parameter in (18) is chosen to be c(t) = e 0.001t . In Fig. 4, we observe how the robot succeeds in converging to the desired destination. Collision avoidance is ensured due to the fact that the estimate of the projected goalx remains always in the collision-free local workspace LF(x c ).
2) Moving Targets: In our final experiment, we consider a similar navigation problem, but in this case the disk-shaped robot must track a moving target, i.e., x d (t) : R + → W. In this scenario, no theoretical guarantees are provided by the technique proposed in [31]; however, we demonstrate how our approach can be used to track a moving target.
In our experiment, we consider a moving target x d (t) following a circumference of radius 15, centered at the origin, and moving periodically with a period T = 2 × 10 3 s. Observe that the target trajectory (red line in Fig. 5) is allowed to intersect the circular obstacles (e.g., obstacles are on the ground, and the target is flying). To track this target, we use the controller (38) wherex is the solution to the ODE in (20) with the following barrier function: where a i (x c ) = x i − x c and b i (x c ) are given by (35). The parameter selection for our simulation is K = 0.05, α = 30, and c(t) = 100e αt with α = 0.001. In Fig. 5, we depict the trajectory followed by the disk-shaped robot (blue circle) over time. As we can observe, the robot succeeds in tracking the moving target while avoiding the circular obstacles.

V. CONCLUSIONS
In this paper, we have developed a prediction-correction interior-point method for solving convex optimization problems with time-varying objective and/or constraint functions. Using log-barrier penalty functions, we have proposed a continuous-time dynamical system for tracking the solution of the time-varying problem. This dynamical system contains both a correction term, which is a continuous-time implementation of Newton's method, as well as a prediction term that takes into account the time-varying nature of the objective and constraint functions. Under reasonable assumptions, our method globally asymptotically converges to the time-varying optimal solution of the original problem with a vanishing tracking error. We have illustrated the applicability of the proposed method in two practical applications: a sparsity promoting least squares problem and a collision-free robot navigation problem.
Finally, it follows from m-strong convexity of Φ that Combining the last two inequalities gives the desired inequality. The proof is complete.

F. Proof of Theorem 2
We first define the following Lyapunov function, which is positive everywhere and is zero along the approximate optimal trajectory, i.e., V ( x (t), s(t), c(t), t) = 0, t ≥ 0. The time derivative of the Lyapunov function along the trajectories of (27) iṡ When ∇ x Φ 2 ≥ ε, we have that α = α0 ∇xΦ 2 and, therefore, V is given bẏ Using the Assumption ∇ xt Φ − ∇ xt Φ 2 ≤ η, we obtain the inequalityV