We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation – transforming the original problem into a constrained problem in a higher dimensional space – to define a sequence of suitable quadratic penalty subproblems with increasing penalty … Read more
We consider forms on the Euclidean unit sphere. We obtain obtain a simple and complete characterization of all points that satisfies the standard second-order necessary condition of optimality. It is stated solely in terms of the value of (i) f, (ii) the norm of its gradient, and (iii) the first two smallest eigenvalues of its … Read more
LSP(n), the largest small polygon with n vertices, is the polygon of unit diameter that has maximal area A(n). It is known that for all odd values n≥3, LSP(n) is the regular n-polygon; however, this statement is not valid for even values of n. Finding the polygon LSP(n) and A(n) for even values n≥6 has … Read more
Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest … Read more
We study representation of solutions and certificates to quadratic and cubic optimization problems. Specifically, we focus on minimizing a cubic function over a polyhedron and also minimizing a linear function over quadratic constraints. We show when there exist rational feasible solutions (and if we can detect them) and when we can prove feasibility of sublevel … Read more
This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose … Read more
In this paper we present the nonconvex exterior-point optimization solver (NExOS)—a novel first-order algorithm tailored to constrained nonconvex learning problems. We consider the problem of minimizing a convex function over nonconvex constraints, where the projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including … Read more
We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more
Recently, Neumaier and Azmi gave a comprehensive convergence theory for a generic algorithm for bound constrained optimization problems with a continuously differentiable objective function. The algorithm combines an active set strategy with a gradient-free line search CLS along a piecewise linear search path defined by directions chosen to reduce zigzagging. This paper describes LMBOPT, an … Read more
A trust-region algorithm using inexact function and derivatives values is introduced for solving unconstrained smooth optimization problems. This algorithm uses high-order Taylor models and allows the search of strong approximate minimizers of arbitrary order. The evaluation complexity of finding a $q$-th approximate minimizer using this algorithm is then shown, under standard conditions, to be $\mathcal{O}\big(\min_{j\in\{1,\ldots,q\}}\epsilon_j^{-(q+1)}\big)$ … Read more