Optimization and Control (math.OC)

Abstract: Motivated by the conspicuous use of momentum based algorithms in deep learning, we study a nonsmooth nonconvex stochastic heavy ball method and show its convergence. Our approach relies on semialgebraic assumptions, commonly met in practical situations, which allow to combine a conservative calculus with nonsmooth ODE methods. In particular, we can justify the use of subgradient sampling in practical implementations that employ backpropagation or implicit differentiation. Additionally, we provide general conditions for the sample distribution to ensure the convergence of the objective function. As for the stochastic subgradient method, our analysis highlights that subgradient sampling can make the stochastic heavy ball method converge to artificial critical points. We address this concern showing that these artifacts are almost surely avoided when initializations are randomized.

Abstract: This paper presents IML FISTA, a multilevel inertial and inexact forward-backward algorithm, based on the use of the Moreau envelope to build efficient and useful coarse corrections. Such construction is provided for a broad class of composite optimization problems with proximable functions. This approach is supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We evaluate our approach on several image reconstruction problems and we show that it considerably accelerates the convergence of classical methods such as FISTA, for large-scale images.

Abstract: In this paper, we deal with a minimum time problem in presence of a time delay $\tau.$ The value function of the considered optimal control problem is no longer defined in a subset of $\mathbb{R}^{n}$, as it happens in the undelayed case, but its domain is a subset of the Banach space $C([-\tau,0];\mathbb{R}^{n})$. For the undelayed minimum time problem, it is known that the value function associated with it is semiconcave in a subset of the reachable set and is a viscosity solution of a suitable Hamilton-Jacobi-Belmann equation. The Hamilton-Jacobi theory for optimal control problems involving time delays has been developed by several authors. Here, we are rather interested in investigating the regularity properties of the minimum time functional. Extending classical arguments, we are able to prove that the minimum time functional is semiconcave in a suitable subset of the reachable set.

Abstract: In this note, we propose polynomial-time algorithms solving the Monge and Kantorovich formulations of the $\infty$-optimal transport problem in the discrete and finite setting. It is the first time, to the best of our knowledge, that efficient numerical methods for these problems have been proposed.

Abstract: Focusing on stochastic programming (SP) with covariate information, this paper proposes an empirical risk minimization (ERM) method embedded within a nonconvex piecewise affine decision rule (PADR), which aims to learn the direct mapping from features to optimal decisions. We establish the nonasymptotic consistency result of our PADR-based ERM model for unconstrained problems and asymptotic consistency result for constrained ones. To solve the nonconvex and nondifferentiable ERM problem, we develop an enhanced stochastic majorization-minimization algorithm and establish the asymptotic convergence to (composite strong) directional stationarity along with complexity analysis. We show that the proposed PADR-based ERM method applies to a broad class of nonconvex SP problems with theoretical consistency guarantees and computational tractability. Our numerical study demonstrates the superior performance of PADR-based ERM methods compared to state-of-the-art approaches under various settings, with significantly lower costs, less computation time, and robustness to feature dimensions and nonlinearity of the underlying dependency.

Abstract: In this paper, a class of semilinear fractional elliptic equations associated to the spectral fractional Dirichlet Laplace operator is considered. We establish the existence of optimal solutions as well as a minimum principle of Pontryagin type and the first order necessary optimality conditions of associated optimal control problems. Second order conditions for optimality are also obtained for $L^{\infty}$ and $L^2-$ local solutions under some structural assumptions.

Abstract: In a previous paper [R. Andreani, G. Haeser, L. M. Mito, H. Ram\'irez, T. P. Silveira. First- and second-order optimality conditions for second-order cone and semidefinite programming under a constant rank condition. Mathematical Programming, 2023. DOI: 10.1007/s10107-023-01942-8] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all faces of the underlying cone. This condition is independent of Robinson's condition and it implies a strong second-order necessary optimality condition which depends on a single Lagrange multiplier instead of the full set of Lagrange multipliers. In this paper we expand on this result in several directions, namely, we consider the larger class of $\mathcal{C}^2-$cone reducible constraints and we show that it is not necessary to consider all faces of the cone; instead a single specific face should be considered (which turns out to be weaker than Robinson's condition) in order for the first order necessary optimality condition to hold. This gives rise to a notion of facial reduction for nonlinear conic programming, that allows locally redefining the original problem only in terms of this specific face instead of the whole cone, providing a more robust formulation of the problem in which Robinson's condition holds. We were also able to prove the strong second-order necessary optimality condition in this context by considering only the subfaces of this particular face, which is a new result even in nonlinear programming.