Partial Envelope for Optimization Problem with Nonconvex Constraints

Abstract

In this paper, we consider the nonlinear constrained optimization problem (NCP) with constraint set $\{x\in \mathcal{X}:c(x)=0\}$, where $\mathcal{X}$ is a closed convex subset of ${\mathbb{R}}^n$. Building upon the forward-backward envelope framework for optimization over $\mathcal{X}$, we propose a forward-backward semi-envelope (FBSE) approach for solving (NCP). In the proposed semi-envelope approach, we eliminate the constraint $x\in \mathcal{X}$ through a specifically designed envelope scheme while preserving the constraint $x\in \mathcal{M}:=\{x\in {\mathbb{R}}^n:c(x)=0\}$. We establish that the forward-backward semi-envelope for (NCP) is well-defined and locally Lipschitz smooth over a neighborhood of $\mathcal{M}$. Furthermore, we prove that (NCP) and its corresponding forward-backward semi-envelope have the same first-order stationary points within a neighborhood of $\mathcal{X}\cap \mathcal{M}$. Consequently, our proposed forward-backward semi-envelope approach enables direct application of optimization methods over $\mathcal{M}$ while inheriting their convergence properties for (NCP). Additionally, we develop an inexact projected gradient descent method for minimizing the forward-backward semi-envelope over $\mathcal{M}$ and establish its global convergence. Preliminary numerical experiments demonstrate the practical efficiency and potential of our proposed approach.

22 pages