Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization

• URL: http://arxiv.org/abs/2007.10525v1
• Date: Mon, 20 Jul 2020 23:04:26 GMT
• Title: Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization
• Authors: Albert Berahas, Frank E. Curtis, Daniel P. Robinson, Baoyu Zhou
• Abstract summary: 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.
• Score: 10.017195276758454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sequential quadratic optimization algorithms are proposed for solving smooth nonlinear optimization problems with equality constraints. The main focus is an algorithm proposed for the case when the constraint functions are deterministic, and constraint function and derivative values can be computed explicitly, but the objective function is stochastic. It is assumed in this setting that it is intractable to compute objective function and derivative values explicitly, although one can compute stochastic function and gradient estimates. As a starting point for this stochastic setting, an algorithm is proposed for the deterministic setting that is modeled after a state-of-the-art line-search SQP algorithm, but uses a stepsize selection scheme based on Lipschitz constants (or adaptively estimated Lipschitz constants) in place of the line search. This sets the stage for the proposed algorithm for the stochastic setting, for which it is assumed that line searches would be intractable. Under reasonable assumptions, convergence (resp.,~convergence in expectation) from remote starting points is proved for the proposed deterministic (resp.,~stochastic) algorithm. The results of numerical experiments demonstrate the practical performance of our proposed techniques.

Related papers

• 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)
• Single-Loop Deterministic and Stochastic Interior-Point Algorithms for Nonlinearly Constrained Optimization [16.356481969865175]
  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.
  arXiv  Detail & Related papers  (2024-08-29T00:50:35Z)
• 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)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm. Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• 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)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians [17.9230793188835]
  We consider the problem of solving nonlinear optimization programs with objective and deterministic equality. We propose a sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. The proposed algorithm is the first SQP that allows a line search procedure and the first line search procedure.
  arXiv  Detail & Related papers  (2021-02-10T08:40:55Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.