Constrained Nonlinear Optimization

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization in Data Science

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher’s augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that … Read more

Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods

Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , ,

Augmented Lagrangian (AL) methods are a classical framework for constrained optimization, but for directly verifiable approximate KKT points, known first-order complexity bounds for standard inexact AL methods are suboptimal, while the best known proximal augmented Lagrangian (PAL) bounds retain an additional logarithmic factor. We consider linearly constrained convex composite problems with a smooth convex term … Read more

A new theorem of alternatives leading to sufficient conditions for the superiorization guarantee question of Dynamic String-Averaging in the inconsistent case

Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization

We study the Superiorization Methodology (SM) in the context of the General Dynamic String-Averaging (GDSA) method in the inconsistent case (that is, where the input operators don’t have a common fixed point) which primarily aims at achieving convex feasibility while simultaneously reducing an objective function. In many scientific and real-world problems modeled as constrained minimization … Read more

Adaptive Scenario Partitioning for Stochastic Bilevel Linear Programs

Categories Bilevel Optimization, Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

This paper develops an adaptive scenario partitioning approach for stochastic bilevel linear programs. The method extends the Adaptive Partitioning Method, originally designed for two-stage stochastic programs, to settings in which a leader makes a first-stage decision while anticipating scenario dependent optimal responses from a follower. The proposed approach solves a sequence of aggregated master problems … Read more

GPU-accelerated superiorization on constrained physical problems with SupPy

Categories Applications - OR and Management Sciences, Biomedical Applications, Constrained Nonlinear Optimization Tags , , , , ,

The superiorization method (SM) is situated between feasibility-seeking and constrained optimization. Instead of aiming at the minimum of a given objective function over a constraint set, it seeks a feasible point at which the objective function value is reduced — though not necessarily minimal — compared to that reached by the feasibility-seeking algorithm alone. This … Read more

Lower Bounds for Feasibility and Stationarity in First-Order Nonconvex Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

We study oracle-complexity lower bounds for first-order methods applied to smooth equality-constrained nonconvex optimization, separating two components of approximate KKT accuracy: feasibility and stationarity. Under iteration-wise Jacobian regularity, we prove a lower bound of order \(\Omega(\frac{L_c\Delta_c}{\sigma^2}+\log\log(\frac{\sigma^2}{L_c\epsilon}))\) to achieve \(\epsilon\)-feasibility. For stationarity, we construct a nonlinear equality-constrained hard instance whose multiplier-minimized stationarity residual reduces exactly to … Read more

A Fletcher’s Augmented Lagrangian-Based Stochastic First-Order Method for Nonconvex Equality-Constrained Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization

In this paper, we study nonconvex equality-constrained optimization problems in which only stochastic first-order approximations of the objective and constraint functions are available. Owing to the stochasticity in both objective and constraints, most existing stochastic first-order methods incur relatively high oracle complexity, particularly in terms of stochastic constraint function evaluations. To address this issue, we … Read more

On the existence of Lagrange multipliers in conic programming

Categories Constrained Nonlinear Optimization Tags ,

The existence of Lagrange multipliers at a solution of a nonlinear optimization problem constitutes one of the cornerstones of modern optimization theory, with many important consequences for guiding algorithmic procedures towards a solution, defining stopping criteria, performing stability analysis, and several other aspects. However, the proof of this result is often intricate, relying on non-trivial … Read more

Covering for Set-Valued Mappings in the Absence of Metric Regularity

Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

Covering properties build the foundation of stability and sensitivity analysis of solutions to a generalized equation and more specific optimization-related stationarity and equilibrium problems. It has been well-understood that metric regularity of the mapping defining the generalized equation is a key to furnish Lipschitzian stability of the solution of interest. With this work, we want … Read more

Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization

Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex problems, with step sizes that require either line search or knowledge of the Lipschitz constant of the gradient. We develop a novel step size strategy that does … Read more