Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization

• URL: http://arxiv.org/abs/2408.16186v1
• Date: Thu, 29 Aug 2024 00:50:35 GMT
• Title: Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization
• Authors: Frank E. Curtis, Xin Jiang, Qi Wang,
• Abstract summary: An interior-point algorithm is proposed, analyzed, and tested for solving objectively constrained continuous optimization problems. The algorithm is intended for the setting when-gradient, estimates are available and employed in place gradients, and when no objective function values are employed.
• Score: 16.356481969865175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An interior-point algorithm framework is proposed, analyzed, and tested for solving nonlinearly constrained continuous optimization problems. The main setting of interest is when the objective and constraint functions may be nonlinear and/or nonconvex, and when constraint values and derivatives are tractable to compute, but objective function values and derivatives can only be estimated. The algorithm is intended primarily for a setting that is similar for stochastic-gradient methods for unconstrained optimization, namely, the setting when stochastic-gradient estimates are available and employed in place of gradients of the objective, and when no objective function values (nor estimates of them) are employed. This is achieved by the interior-point framework having a single-loop structure rather than the nested-loop structure that is typical of contemporary interior-point methods. For completeness, convergence guarantees for the framework are provided both for deterministic and stochastic settings. Numerical experiments show that the algorithm yields good performance on a large set of test problems.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• A Stochastic-Gradient-based Interior-Point Algorithm for Solving Smooth Bound-Constrained Optimization Problems [12.29270365918848]
  The proposed algorithm is based on the subject-point unique constraints from other interior-point methods. It is shown that with a careful balance between the projection, step-size and sequence sequences, the proposed algorithm convergence guarantees in both numerical and deterministic settings.
  arXiv  Detail & Related papers  (2023-04-28T15:30:43Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
  It is assumed that constraint function values and derivatives are available, but only programming approximations of the objective function and its associated derivatives can be computed. A high-probability bound on the iteration complexity of the algorithm to approximate first-order stationarity is derived.
  arXiv  Detail & Related papers  (2023-01-01T21:46:50Z)
• Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming [17.9230793188835]
  We study nonlinear optimization problems with objective and deterministic equality and inequality constraints. We propose an active-set sequentialAdaptive programming algorithm, using a differentiable exact augmented Lagrangian as the merit function. The algorithm adaptively selects the parameters of augmented Lagrangian and performs line search to decide the stepsize.
  arXiv  Detail & Related papers  (2021-09-23T17:12:17Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• A Stochastic Sequential Quadratic Optimization Algorithm for Nonlinear Equality Constrained Optimization with Rank-Deficient Jacobians [11.03311584463036]
  A sequential quadratic optimization algorithm is proposed for solving smooth nonlinear equality constrained optimization problems. Results of numerical experiments demonstrate that the algorithm offers superior performance when compared to popular alternatives.
  arXiv  Detail & Related papers  (2021-06-24T13:46:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization [10.017195276758454]
  It is assumed in this setting that it is intractable to compute objective function and derivative values explicitly. An algorithm is proposed for the deterministic setting that is modeled after a state-of-the-art line-search SQP algorithm. The results of numerical experiments demonstrate the practical performance of our proposed techniques.
  arXiv  Detail & Related papers  (2020-07-20T23:04:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.