A prediction-correction inexact alternating direction method for convex nonlinear second-order cone programming with linear constraints

Yaling Zhang, Hongwei LiuJournal of Inequalities and Applications 2020 · DOI

Abstract

Convex nonlinear second-order cone programming (CNSOCP) with linear constraints is a fundamental problem in optimization with wide-ranging applications in engineering and robotics. This paper presents a prediction-correction inexact alternating direction method (PCIADM) designed for problems with a separate structure. A key advantage of the proposed method is that it does not require the convex objective function to be Lipschitz continuous, requiring only that it satisfies a specific inequality. We provide a proof of global convergence and demonstrate the method's efficiency through numerical experiments on random SOCP problems and a three-fingered grasping force optimization simulation.

Introduction

Second-order cone programming (SOCP) is a generalization of linear and quadratic programming that allows for constraints on the Euclidean norm of vector variables. When the objective function is nonlinear, the problem becomes a Convex Nonlinear Second-Order Cone Program (CNSOCP). While standard solvers like Interior Point Methods (IPM) and Sequential Quadratic Programming (SQP) are highly effective for reaching high-precision solutions, they often involve computationally expensive sub-problems, such as calculating and inverting Hessian matrices.

In many real-time applications, such as robotic grasping or signal processing, moderate precision is sufficient, but speed is critical. This paper introduces the PCIADM, a first-order method that simplifies the computational burden per iteration while maintaining robust convergence properties.

Methodology

The PCIADM framework is built upon the principles of the Alternating Direction Method of Multipliers (ADMM) but introduces several modifications to handle the complexities of CNSOCP.

1. Problem Reformulation

The original problem is transformed into a "separate structure" by introducing an auxiliary variable $x = y$. This allows the algorithm to decouple the nonlinear objective function from the second-order cone constraints.

2. Prediction-Correction Scheme

Rather than solving the nonlinear sub-problems exactly—which is often the bottleneck in traditional ADMM—the PCIADM utilizes an inexact update. A "prediction" step is performed using a gradient-based update, followed by a "correction" step. This approach ensures that the algorithm progresses toward the optimum without the overhead of exact minimization at every step.

A major difficulty in SOCP is handling the intersection of linear constraints ($Ax=b$) and the cone ($K$). PCIADM circumvents this by requiring projections only onto the second-order cone itself, which has a simple closed-form solution. Furthermore, to accommodate objective functions that are not Lipschitz continuous, we implement an Armijo-style line search to dynamically determine the step size, ensuring stability across a wider range of problem types.

Numerical Experiments

The performance of PCIADM was evaluated against SQP-type methods and the SeDuMi solver across two primary benchmarks.

Random CNSOCP Problems

We tested the algorithm on 15 randomly generated problems (P01–P15) with dimensions up to $m=290, n=580$. The results indicated that while PCIADM requires more iterations to converge compared to SQP, its total CPU time is significantly lower—often by a factor of 5 to 10. This is due to the "cheap" nature of its iterations, which avoid second-order derivative calculations.

Robotic Grasping Force Optimization

The method was extended to convex nonlinear circular cone programming to solve a three-fingered grasping force optimization problem. In a simulation involving 4,000 runs, PCIADM achieved an average CPU time of 0.0521 seconds, compared to 0.1967 seconds for the SeDuMi solver. This nearly 4x speedup highlights the method's suitability for real-time control tasks.

Conclusion

The Prediction-Correction Inexact Alternating Direction Method offers a computationally efficient alternative for solving CNSOCP problems. By relaxing the requirement for Lipschitz continuity and simplifying the projection steps, the method achieves significant speedups in medium-accuracy regimes. Future work will explore extending this framework to more complex structures, such as semidefinite programming (SDP) with nonlinear objectives.

Summary updated

Abstract

Abstract The convex nonlinear second-order cone programming with linear constraints is equivalent to a separate structure convex programming. A prediction-correction inexact alternating direction method is proposed for the separate structure convex programming. In the proposed method, the convex objective function is not required to be Lipschitz continuous and only needs satisfy an inequality. The global convergence result is given. Numerical results demonstrate that our method is efficient for some random second-order cone programming problems in lower accuracy. In addition, our method can be extended to the convex nonlinear circular cone programming with linear constraints. We also give the simulation results of the three-fingered grasping force optimization problems.
BibTeX
@article{zhang2020prediction,
  author = {Yaling Zhang and Hongwei Liu},
  title = {{A prediction-correction inexact alternating direction method for convex nonlinear second-order cone programming with linear constraints}},
  journal = {Journal of Inequalities and Applications},
  year = {2020},
  doi = {10.1186/s13660-020-2285-2},
}
Figure