A Feasible-Direction-Type Method for Nonconvex Optimization with Infeasible Starts

Abstract

We develop an infeasible-start extension of the Topkis–Veinott feasible-direction method for nonconvex composite optimization. At each main iteration, a strongly convex local model is used to obtain objective descent while limiting increases in constraint violation. A separate feasibility-reduction step is invoked when feasibility improvement is needed. Under a feasibility-reduction condition, we establish the standard first-order rate for reducing the Fritz John residual and constraint violation. We then verify that both proximal-gradient and regularized Gauss–Newton methods applied to minimizing the squared constraint-violation function satisfy the required feasibility-reduction property under a Polyak–Łojasiewicz condition. Numerical experiments compare the reduction methods, including an experimental prox-linear variant, and compare the scalar-regularized and curvature-enhanced subproblem formulations.