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
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
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
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 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
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
We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-Łojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local generalized Hölder smoothness property. … Read more
Direct search is one of the most popular derivative-free optimization paradigms, that relies on exploring the variable space using polling directions. To analyze and implement direct search, one typically relies on positive spanning sets. This concept is somewhat decorrelated from interpolation-based sets used in model-based algorithms, another class of derivative-free optimization methods. This discrepancy is … Read more
In this study, we model the supervised feature selection problem using a novel approach: convex bi-objective optimization. Traditional methods have addressed this problem by maximizing relevance to class labels and minimizing redundancy among features. Recently, Wang et al. [30] formulated this problem as a single-objective convex optimization, yielding only a unique solution. Unlike that, we … Read more
In this work we develop and analyze a semi-smooth Newton method for the general non- linear conic programming problem. In particular, we study the problem with a generalized simplicial cone, i.e., the image of a symmetric cone under a linear mapping. We generalize Robinson’s normal equations to a conic setting, yielding what we call the … Read more