In this work, we give a tight estimate of the rate of convergence for the Halpern-Iteration for approximating a fixed point of a nonexpansive mapping in a Hilbert space. Specifically, we prove that the norm of the residuals is upper bounded by the distance of the initial iterate to the closest fixed point divided by … Read more
This work is about active set identification strategies aimed at accelerating block-coordinate descent methods (BCDM) applied to large-scale problems. We start by devising an identification function tailored for bound-constrained composite minimization together with an associated version of the BCDM, called Active BCDM, that is also globally convergent. The identification function gives rise to an efficient … Read more
This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a … Read more
Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an “inspect” phase to existing algorithms that helps escape from non-global stationary points. The inspection samples a set of points in a … Read more
We consider optimal control problems for gas flow in pipeline networks. The equations of motion are taken to be represented by a first-order system of hyperbolic semilinear equations derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a network and introduce a tailored time discretization thereof. In order … Read more
In a recent paper, it was shown that, for the smooth unconstrained optimization problem, worst-case evaluation complexity $O(\epsilon^{-(p+1)/p})$ may be obtained by means of algorithms that employ sequential approximate minimizations of p-th order Taylor models plus (p + 1)-th order regularization terms. The aforementioned result, which assumes Lipschitz continuity of the p-th partial derivatives, generalizes … Read more
Distributed optimization algorithms are essential for training machine learning models on very large-scale datasets. However, they often suffer from communication bottlenecks. Confronting this issue, a communication-efficient primal-dual coordinate ascent framework (CoCoA) and its improved variant CoCoA+ have been proposed, achieving a convergence rate of $\mathcal{O}(1/t)$ for solving empirical risk minimization problems with Lipschitz continuous losses. … Read more
In this paper we extend a lemma due to Yuan from several aspects. A new proof of Yuan’s lemma is given. A rank-one decomposition of positive semidefinite matrix is further developed. With the extended rank-one de- composition results, we generalize the Yuan’s lemma to general quadratic function systems, interval quadratic function systems and quadratic matrix … Read more
A probabilistic framework for large classes of binary integer programming problems is constructed. The approach is given by a mean field annealing scheme where the annealing phase is substituted by the solution of a dual problem that gives a lower (upper) bound for the original minimization (maximization) integer task. This bound has an information theoretic … Read more
We present DFO-GN, a derivative-free version of the Gauss-Newton method for solving nonlinear least-squares problems. As is common in derivative-free optimization, DFO-GN uses interpolation of function values to build a model of the objective, which is then used within a trust-region framework to give a globally-convergent algorithm requiring $O(\epsilon^{-2})$ iterations to reach approximate first-order criticality … Read more