PaperlayerView exact revision on arXiv

Source-linked AI summary

Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization

Mahyar Fazlyab, Santiago Paternain, Victor M. Preciado, Alejandro Ribeiro

arXiv:1608.07544v1math.OC

TL;DR

Time-varying convex optimization requires tracking an optimum that moves as objectives and constraints change, whereas snapshot-based methods can incur tracking error. The paper proposes a log-barrier prediction-correction dynamical system combining temporal prediction with continuous-time Newton correction. Under suitable conditions, it converges globally and exponentially with vanishing tracking error, and is demonstrated in sparse least squares and collision-free robot navigation.

  • Problem

    Snapshot-based optimization can incur steady-state tracking errors because the optimal solution drifts while each sampled problem is being solved.

  • Method

    The method uses log-barrier penalty functions and a continuous-time dynamical system combining prediction of temporal drift with Newton-based correction.

  • Results

    The dynamical system globally asymptotically converges to the time-varying optimal solution with exponentially vanishing tracking error under stated conditions.

  • Takeaways & Limitations

    The approach applies to time-varying convex optimization and is illustrated in sparsity-promoting least squares and collision-free robot navigation.

Abstract

from arXiv · show

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 paper addresses time-varying convex optimization by designing a prediction-correction dynamical system that tracks drifting optima with asymptotically vanishing error. Under stated regularity and convexity assumptions, the method converges globally and exponentially, with applications in sparse least squares and robot navigation.

  • Problem setting: The problem class uses smooth convex time-varying objectives, level-set inequality constraints, and affine equality constraints.The assumptions include uniform strong convexity, Slater’s condition, and linearly independent equality-constraint vectors.
  • Method: The proposed continuous-time system combines a prediction term using temporal variation with a Newton-based correction term.The framework is developed for unconstrained, affine-constrained, and more general time-varying constrained problems.
  • Applications: The paper illustrates the method in sparsity-promoting least squares and collision-free robot navigation, including tracking a moving target.The least-squares experiment examines time-varying barrier parameters and prediction for accelerating conventional interior-point methods.
  • Motivation: Sampling time-varying problems and solving each snapshot independently can create a steady-state tracking error because the optimum drifts between iterations.The gap depends on both available computation and the rate at which the optimal argument changes.
  • Method: The prediction term is obtained by differentiating the optimality condition, while the correction term pushes the state toward the instantaneous optimum.For the unconstrained case, the Newton correction has the form −α∇xxf0(x(t), t)^−1∇xf0(x(t), t).
  • Convergence: Under strong convexity, the unconstrained dynamical system converges exponentially to a point satisfying the first-order optimality condition.A forward-Euler discretization has error of order O(τ) when the vector field is uniformly Lipschitz in x.

B. Equality-Constrained Time-Varying Convex Optimization

The equality-constrained method combines prediction of time variation with Newton-like correction in primal-dual dynamics. Under bounded inverse-Hessian conditions, it converges exponentially while preserving feasibility from feasible initialization.

  • Method: The method augments the time-varying objective with equality-constraint multipliers and tracks the primal-dual optimum through a condensed KKT system.The aggregate state is z = [x^T, ν^T]^T, with the optimal pair characterized by ∇_zL = 0.
  • Method: The prediction term differentiates the KKT gradient over time, while the correction term applies a Newton-like update to the Lagrangian gradient.Both terms use the inverse Hessian of the Lagrangian.
  • Convergence: The resulting dynamical system converges exponentially to the time-varying optimal solution under the stated assumptions.The convergence proposition applies to the solution of the primal-dual dynamics.
  • Conditions: A uniformly bounded inverse Hessian is required both for the convergence bound and to avoid arbitrarily small discretization step sizes.The bound controls the convergence rate in the primal variable and limits the growth of the continuous-time velocity.
  • Feasibility: Feasibility errors vanish exponentially, and an initially feasible trajectory remains feasible for all future time.The infeasibility measure is ||A(t)x(t)−b(t)||_2.

C. General Time-Varying Convex Optimization

The general method handles time-varying inequality constraints using a logarithmic barrier, an enlarged feasible domain, and prediction-correction dynamics. Increasing the barrier parameter and vanishing the slack yield asymptotic convergence to the original optimum.

  • Barrier formulation: Logarithmic barrier functions convert the inequality-constrained problem into a smooth convex optimization problem over the strict interior of the feasible set.The barrier parameter c is positive and weights the logarithmic penalty.
  • Barrier formulation: A nonnegative slack variable enlarges the feasible domain so arbitrary initial states can be admitted while maintaining valid barrier arguments.Choosing s(0) larger than the initial constraint values places any x(0) in the enlarged domain.
  • Prediction-correction dynamics: The dynamics combines a Newton-like correction with prediction terms accounting for changes in the barrier objective, slack, barrier parameter, and constraints.The gradient derivative includes ∇_xxΦ ẋ, ∇_xsΦ ṡ, ∇_xcΦ ċ, and ∇_xtΦ.
  • Convergence: Starting inside the enlarged domain, the trajectory remains there for all t ≥ 0 and converges exponentially to the approximate barrier optimum.The invariance result requires x(0) ∈ bD(0), while the convergence result allows arbitrary x(0) under its stated initialization conditions.
  • Convergence: The approximation error vanishes when the slack decays exponentially and the barrier parameter diverges, provided optimal dual variables do not escape exponentially fast.A convenient barrier schedule is c(t) = c(0) exp(γ_c t), with positive γ_c and c(0).
  • Convergence: The continuous-time method therefore converges asymptotically to the original optimal solution from arbitrary initial conditions under the stated assumptions.The result extends to equality constraints using a Lagrangian, provided its inverse Hessian is uniformly bounded.
  • Acceleration: For a time-invariant problem, an increasing time-dependent barrier parameter creates a continuous path converging to the constrained optimum instead of discontinuous barrier-parameter jumps.The paper proposes this as a less computationally expensive alternative for accelerating standard interior-point methods.

D. Online Implementation

The online implementation addresses imperfect prediction information by replacing the exact time derivative with a bounded estimate. With sufficient correction gain, the dynamics reaches and remains in a finite-time neighborhood of the approximate optimum.

  • Approximate prediction: Online implementation uses an estimate of the prediction derivative because the required time-variation terms may be limited or noisy.The estimate is assumed to satisfy a known error bound η.
  • Robust convergence: If the nominal correction coefficient satisfies α_0 > η, the resulting dynamics converges in finite time to an ε-neighborhood of the approximate optimum.The neighborhood is defined through the norm of the barrier-objective gradient.

IV. NUMERICAL EXPERIMENTS

The paper evaluates the proposed framework through synthetic and practical numerical examples, including inequality-constrained optimization, large-scale sparse least squares, and robot navigation.

  • Numerical examples: The numerical section contains three examples covering a synthetic inequality-constrained problem and two practical applications.The applications are a large-scale ℓ1-regularized least-squares problem and a robot-navigation problem.

A. Time-Varying Quadratic Programming

The paper evaluates its time-varying interior-point dynamics on a quadratic program and an accelerated ℓ1-regularized least-squares problem. The simulations illustrate tracking with vanishing slack and compare convergence using relative duality-gap iterations.

  • Time-Varying Quadratic Programming: The quadratic simulation starts infeasible but uses a time-dependent slack variable to enlarge the feasible set before enforcing the original constraint.The initial condition is x(0) = (−2, 0)⊤, with s(0) = 2.
  • Time-Varying Quadratic Programming: The quadratic-program experiment uses c(t) = 10e^t, s(t) = 2e^−5t, Euler’s method with step size τ = 0.1, and t ∈ [0, 2π].These choices satisfy the stated conditions of Theorem 1.
  • Time-Varying Quadratic Programming: The state initially violates f1(x, t) ≤ 0 but converges exponentially fast to the feasible set as the slack variable vanishes exponentially.Figures 1 and 2 plot the tracking trajectory, optimal trajectory, constraint function, and slack variable.
  • Sparsity-Promoting Least Squares: The least-squares experiment generates a sparse vector with 10 entries of value ±1, Gaussian measurements, Gaussian noise, and λ = 2.The measurement matrix has dimensions 256 × 1024, and the noise covariance is 0.01 I_256.
  • Sparsity-Promoting Least Squares: At the stopping criterion η/g(ν) ≤ 10^−4, SNIPM requires 42 iterations while the accelerated ANIPM requires 17 iterations.The paper reports ANIPM as comparable to TNIPM because TNIPM updates the barrier parameter but omits the prediction term.

C. Robot Navigation

The robot-navigation problem seeks a collision-free trajectory to a desired configuration inside a workspace containing spherical obstacles. The formulation uses local workspaces and projected goals to maintain feasibility while driving the robot toward its destination.

  • Problem Setup: The navigation task requires x_c(t) ∈ F for all t ≥ 0 and lim_t→∞ x_c(t) = x_d.The robot center of mass must remain in free space while converging to the final desired configuration.
  • Local Workspace: The local workspace contains points closer in power distance to the robot than to any obstacle and forms a polytope with hyperplane boundaries.The power distance is defined relative to obstacle disks, and the local workspace is represented in Fig. 4.
  • Collision-Free Constraints: The collision-free local workspace is described by linear inequalities a_i(x_c)^⊤x − b_i(x_c) ≤ 0 for i = 1 . . . m.Its coefficients depend on the robot center of mass.
  • Projected-Goal Control: A projected-goal controller uses the orthogonal projection of x_d onto the collision-free local workspace and converges under a separation condition between obstacles.The required condition is that obstacle-center distances exceed r_i + r_j + 2r.

1) Interior-Point Method to Estimate the Projected Goal:

The proposed estimator casts the projected goal as a time-varying convex optimization problem and solves it with the prediction-correction interior-point dynamics. The resulting estimator remains feasible and supports collision-free navigation, including tracking of a moving target.

  • Interior-Point Estimator: The projected goal x⋆ is formulated as the solution of a convex optimization problem constrained by a_i(x_c)^⊤x − b_i(x_c) ≤ 0.The constraints define the collision-free local workspace.
  • Interior-Point Estimator: Because the constraint coefficients depend on x_c, the projected-goal problem has an implicit time dependence through the robot trajectory.The estimator is initialized at the robot’s initial position and follows the ODE in (20).
  • Estimator Guarantees: The estimator x̂(t) remains feasible at all times and converges exponentially to the projection of x_d onto the collision-free local workspace.Feasibility follows from Lemma 3 and a feasible initial condition.
  • Fixed-Goal Experiment: In a square workspace with 8 circular obstacles, simulations use four initial conditions to show trajectories of the estimator and robot center of mass.The robot has radius one, and Fig. 4 displays the corresponding trajectories.
  • Moving-Target Experiment: For a moving target on a radius-15 circumference with period T = 2×10^3 s, the robot tracks the target while avoiding circular obstacles.The paper notes that the earlier technique provides no theoretical guarantees for this moving-target scenario.
  • Conclusion: The paper concludes that its method tracks time-varying optimal solutions with vanishing error and applies to sparse least squares and collision-free robot navigation.The method combines a Newton correction term with a prediction term for time variation.

APPENDIX

The appendix establishes convergence properties by analyzing gradient and Hessian evolution along the continuous-time dynamics. Strong convexity, full-rank constraints, bounded Hessians, and mean-value arguments provide the required error bounds.

  • Gradient Analysis: Uniform strong convexity ensures that the Hessian inverse of f_0(x, t) exists and remains uniformly bounded.This property supports the gradient-based convergence analysis.
  • Gradient Analysis: The time derivative of the objective gradient decomposes into state evolution through the Hessian and explicit time variation through ∇_xt f_0(x(t), t).The decomposition is given in equation (39).
  • Gradient Analysis: The appendix treats the gradient dynamics as a first-order linear differential equation and combines its solution with Cauchy-Schwarz and mean-value arguments.The expansion is centered at the optimal point where ∇_x f_0(x⋆(t), t) = 0.
  • Primal-Dual Analysis: Strong convexity and the full-rank condition rank(A(t)) = q < n ensure invertibility of the Lagrangian Hessian.The inverse Hessian is then used to analyze the time evolution of the primal-dual gradient.
  • Primal-Dual Analysis: The primal-dual gradient evolution is expressed through the Hessian, state velocity, and explicit time derivative, yielding an integral solution and a bound.The proof then expands around the optimal point and applies the theorem assumptions.
  • Primal-Dual Analysis: Bounding the primal error by the primal-dual error completes the convergence proof.The relation is ∥x(t) − x⋆(t)∥_2 ≤ ∥z(t) − z⋆(t)∥_2.

C. Proof of Lemma 1

The proof establishes feasibility by defining constraint residuals and showing that the dynamics keep them nonnegative. Near the feasible-set boundary, each residual increases when α > 0, which preserves feasibility for all t ≥ 0.

  • Constraint residuals ψi(x, t) := s(t) − fi(x, t) are nonnegative exactly when x(t) remains feasible.The proof uses residual nonnegativity as the feasibility condition for every constraint and time.
  • The proof analyzes the gradient and second derivatives of the barrier dynamics as a residual ψj approaches zero.It multiplies the ODE by ψj and takes the boundary limit to characterize the residual’s time evolution.
  • α > 0 makes ψj strictly increasing at the feasible-set boundary, preventing residual nonnegativity from being violated.This boundary behavior ensures that all residuals remain nonnegative for every t ≥ 0.

E. Proof of Lemma 2

The proof uses strong convexity and a Lyapunov analysis to establish convergence toward the approximate optimal trajectory. The dynamics reach a prescribed error set in finite time and remain within it thereafter.

  • Strong convexity of f0(x, t), together with c(t) > 0, makes ∇xxΦ strongly convex and invertible on D(t).This guarantees that the inverse Hessian used in the dynamics exists and is bounded.
  • The closed-loop gradient dynamics satisfy ˙∇xΦ = −α∇xΦ, yielding exponential decay of the gradient norm.Specifically, ∥∇xΦ(x(t), s(t), c(t), t)∥2 ≤ e−αt∥∇xΦ(x(0), s(0), c(0), 0)∥2.
  • The Lyapunov function is positive away from the approximate optimal trajectory and equals zero along that trajectory.Its derivative is analyzed separately above and below the threshold ∥∇xΦ∥2 = ε.
  • The trajectory reaches St(ε) in finite time and remains there, while converging asymptotically to the smaller set St(ηε/α0).The latter set is contained in St(ε) because η < α0.

G. Expressions for the Numerical Examples

For the numerical examples, the paper derives explicit expressions for the gradient, Hessian, and time derivatives required by the dynamical system. These expressions include derivatives induced by the moving reference point and control law.

  • The example-specific ODE expressions include the augmented-objective gradient, its Hessian, and the time derivative of the barrier-function gradient.These quantities provide the differential terms needed to instantiate the dynamics numerically.
  • The time derivative of ai(xc) is obtained from ai(xc) = (xi − xc) and the control law for xc.The derivation substitutes the control-law expression for ˙xc.
  • The paper differentiates θi(xc) and bi(xc) to obtain the remaining time-derivative expressions used in the example dynamics.The resulting formulas use ˙θi and ˙xc from the previously defined equations.
Loading 1608.07544v1…