Abstract
Motivated by robotic trajectory optimization problems, we consider the Augmented Lagrangian (AL) approach to constrained optimization. We first propose an alternative augmentation of the Lagrangian to handle the inequality case (not based on slack variables) and a corresponding "central" update of the dual parameters. We prove certain properties of this update: roughly, in the case of Linear Programs (LPs) and when the "constraint activity" does not change between iterations, the Karush-Kuhn-Tucker (KKT) conditions hold after just one iteration. This gives essential insight on when the method is efficient in practice. We then present our main contribution, which are consistent any-time (non-central) updates of the dual parameters (i.e., updating the dual parameters when we are not currently at an extremum of the Lagrangian). Similar to the primal-dual Newton method, this leads to an algorithm that parallelly updates the primal and dual solutions, not distinguishing between an outer loop to adapt the dual parameters and an inner loop to minimize the Lagrangian. We again prove certain properties of this anytime update: roughly, in the case of LPs and when constraint activities would not change, the dual solution converges after one iteration. Again, this gives essential insight in the caveats of the method: if constraint activities change the method may destabilize. We propose simple smoothing, step-size adaptation and regularization mechanisms to counteract this effect and guarantee monotone convergence. Finally, we evaluate the proposed method on random LPs as well as on standard robot trajectory optimization problems, confirming our motivation and intuition that our approach performs well if the problem structure implies moderate stability of constraint activity.
Introduction
Constrained optimization is fundamental to robotics, where tasks such as trajectory planning require balancing objective targets with physical constraints like collision avoidance and joint limits. Traditionally, these problems are solved using Interior Point (Log-Barrier) methods or Augmented Lagrangian (AL) methods.
While Log-Barriers are widely used, they often suffer from ill-conditioning as they approach the solution. Standard AL methods avoid this but typically rely on a computationally expensive nested-loop structure: an inner loop to minimize the Lagrangian and an outer loop to update dual parameters. Furthermore, handling inequality constraints in AL usually necessitates the introduction of slack variables, which increases the problem's dimensionality. This paper introduces a streamlined AL framework designed to overcome these limitations by exploiting the inherent structure of robotic optimization problems.
Methodology
Slack-Free Augmentation
The proposed method introduces a modified Lagrangian that handles inequalities without slack variables. Instead, it applies a squared penalty specifically to "active" constraints—those currently violated or near violation. This approach maintains a lower problem dimensionality and avoids the warping of the optimization landscape (Hessian) common in Log-Barrier methods, allowing standard Newton methods to remain effective near constraints.
Any-Time (Non-Central) Updates
The core innovation is the AnyAula algorithm. In traditional AL, dual parameters are updated only after the inner minimization is complete. AnyAula performs "any-time" updates, adjusting dual parameters simultaneously with primal variables. By solving a bounded quadratic program at each step, the algorithm ensures dual parameters remain consistent with the current gradient, effectively merging the inner and outer loops into a single, high-speed process.
Evaluation
The framework was evaluated on two distinct benchmarks: synthetic random Linear Programs (LPs) and a high-dimensional robotic trajectory optimization task.
Random Linear Programs
Testing on random LPs (dimensions $n=20$ to $n=500$) provided insights into how the algorithm handles unstable constraint activity. As shown in Figure 1, AnyAula is significantly more efficient than standard AL (Aula) and Log-Barrier methods for small-to-medium dimensions. However, in very high-dimensional random settings where constraint activity becomes "chattery" or unstable, the any-time update loses its performance edge.
Robotic Trajectory Optimization
In a realistic 5,000-dimensional robot arm simulation (25 degrees of freedom over 200 time slices), AnyAula demonstrated superior performance. It required approximately 48 function evaluations to converge, compared to 64 for standard AL and 60 for Log-Barriers. Notably, Log-Barrier methods failed to find reasonable solutions in this complex task, while the proposed AL approach converged to high-quality, feasible paths.
Discussion and Conclusion
The success of AnyAula in robotics stems from the relative stability of constraint activity in physical trajectories; the set of active constraints (e.g., proximity to an obstacle) rarely changes abruptly between iterations. This stability allows the "one-iteration" property of the dual update to be fully exploited.
While the method is highly effective for structured problems, it can destabilize if constraint activity is chaotic. Future work will explore applying these any-time update principles to other penalty functions, such as shifted barriers, to further enhance robustness and convergence speed in diverse optimization landscapes.
Summary updated