First-order methods of smooth convex optimization with inexact oracle

We introduce the notion of inexact first-order oracle and analyze the behavior of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau–Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast gradient methods, and study in particular their dependence on the accuracy of the oracle and the desired accuracy of the objective function. We observe that the superiority of fast gradient methods over the classical ones is no longer absolute when an inexact oracle is used. We prove that, contrary to simple gradient schemes, fast gradient methods must necessarily suffer from error accumulation. Finally, we show that the notion of inexact oracle allows the application of first-order methods of smooth convex optimization to solve non-smooth or weakly smooth convex problems.     

Self-concordant functions for optimization on smooth manifolds

This paper discusses self-concordant functions on smooth manifolds. In Euclidean space, such functions are utilized extensively as barrier functions in interior-point methods for polynomial time optimization algorithms. Here, the self-concordant function is carefully defined on a differential manifold in such a way that the properties of self-concordant functions in Euclidean space are preserved. A Newton decrement is defined and analyzed for this class of functions. Based on this, a damped Newton algorithm is proposed for the optimization of self-concordant functions. Under reasonable technical assumptions such as geodesic completeness of the manifold, this algorithm is guaranteed to fall in any given small neighborhood of the optimal solution in a finite number of steps. The existence and uniqueness of the optimal solution is also proved in this paper. Hence, the optimal solution is a global one. Furthermore, it ensures a quadratic convergence within a neighborhood of the minimal point. This neighborhood can be specified in terms of the Newton decrement. The computational complexity bound of the proposed approach is also given explicitly. This complexity bound is shown to be of the order where is the desired precision. Some interesting optimization problems are given to illustrate the proposed concept and algorithm. A part of the materials has been presented at 2004 Conference on Decision and Control     

Global one-dimensional optimization using smooth auxiliary functions

In this paper new global optimization algorithms are proposed for solving problems where the objective function is univariate and has Lipschitzean first derivatives. To solve this problem, smooth auxiliary functions, which are adaptively improved during the course of the search, are constructed. Three new algorithms are introduced: the first used the exact a priori known Lipschitz constant for derivatives; the second, when this constant is unknown, estimates it during the course of the search and finally, the last method uses neither the exact global Lipschitz constant nor its estimate but instead adaptively estimates the local Lipschitz constants in different sectors of the search region during the course of optimization. Convergence conditions of the methods are investigated from a general viewpoint and some numerical results are also given. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Nonlinear coordinate representations of smooth optimization problems

Nonlinear coordinate representations of smooth optimization problems are investigated from the point of view of variable metric algorithms. In other words, nonlinear coordinate systems, in the sense of differential geometry, are studied by taking into consideration the structure of smooth optimization problems and variable metric methods.Both the unconstrained and constrained cases are discussed. The present approach is based on the fact that the nonlinear coordinate transformation of an optimization problem can be replaced by a suitable Riemannian metric belonging to the Euclidean metric class. In the case of equality and inequality constraints, these questions are related closely to the right inverses of full-rank matrices; therefore, their characterization is a starting point of the present analysis. The main results concern a new subclass of nonlinear transformations in connection with the common supply of coordinates to two Riemannian manifolds, one immersed in the other one. This situation corresponds to the differentiable manifold structure of nonlinear optimization problems and improves the insight into the theoretical background of variable metric algorithms. For a wide class of variable metric methods, a convergence theorem in invariant form (not depending on coordinate representations) is proved. Finally, a problem of convexification by nonlinear coordinate transformations and image representations is studied.This research was supported by the Hungarian National Research Foundation, Grant Nos. OTKA-2568 and OTKA-2116, and by the Project Trasporti of the Italian National Research Council (CNR).     

Descentwise inexact proximal algorithms for smooth optimization

The proximal method is a standard regularization approach in optimization. Practical implementations of this algorithm require (i)?an algorithm to compute the proximal point, (ii)?a rule to stop this algorithm, (iii)?an update formula for the proximal parameter. In this work we focus on?(ii), when smoothness is present??so that Newton-like methods can be used for?(i): we aim at giving adequate stopping rules to reach overall efficiency of the method. Roughly speaking, usual rules consist in stopping inner iterations when the current iterate is close to the proximal point. By contrast, we use the standard paradigm of numerical optimization: the basis for our stopping test is a ??sufficient?? decrease of the objective function, namely a fraction of the ideal decrease. We establish convergence of the algorithm thus obtained and we illustrate it on some ill-conditioned problems. The experiments show that combining the proposed inexact proximal scheme with a standard smooth optimization algorithm improves the numerical behaviour of the latter for those ill-conditioned problems.     

Gradient-type penalty method with inertial effects for solving constrained convex optimization problems with smooth data

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.     

Nondifferentiable optimization via smooth approximation: General analytical approach

In this paper we present a method for nondifferentiable optimization, based on smoothed functionals which preserve such useful properties of the original function as convexity and continuous differentiability. We show that smoothed functionals are convenient for implementation on computers. We also show how some earlier results in nondifferentiable optimization based on smoothing-out of kink points can be fitted into the framework of smoothed functionals. We obtain polynomial approximations of any order from smoothed functionals with kernels given by Beta distributions. Applications of smoothed functionals to optimization of min-max and other problems are also discussed.     

A first-order interior-point method for linearly constrained smooth optimization

We propose a first-order interior-point method for linearly constrained smooth optimization that unifies and extends first-order affine-scaling method and replicator dynamics method for standard quadratic programming. Global convergence and, in the case of quadratic program, (sub)linear convergence rate and iterate convergence results are derived. Numerical experience on simplex constrained problems with 1000 variables is reported.     

Accelerated Bregman proximal gradient methods for relatively smooth convex optimization

Computational Optimization and Applications - We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex...     

Some theoretical limitations of second-order algorithms for smooth constrained optimization

In second-order algorithms, we investigate the relevance of the constant rank of the full set of active constraints in ensuring global convergence to a second-order stationary point under a constraint qualification. We show that second-order stationarity is not expected in the non-constant rank case if the growth of so-called tangent AKKT2 sequences is not controlled. Since no algorithm controls their growth, we argue that there is a theoretical limitation of algorithms in finding second-order stationary points without constant rank assumptions.     

On a class of hybrid methods for smooth constrained optimization

With reference to smooth nonlinearly constrained optimization problems, we consider combinations of locally superlinearly convergent methods with globally convergent ones. The aim of this paper is threefold: to give a survey on well-known as well as possible unknown hybrid optimization methods, based on a special construction principle; to present a general convergence result for the class of hybrid algorithms; and to derive further methods for this class with new convergence properties.The authors thank the anonymous referees for their useful suggestions.     

A second-order smooth penalty function algorithm for constrained optimization problems

This paper introduces a second-order differentiability smoothing technique to the classical l ₁ exact penalty function for constrained optimization problems(COP). Error estimations among the optimal objective values of the nonsmooth penalty problem, the smoothed penalty problem and the original optimization problem are obtained. Based on the smoothed problem, an algorithm for solving COP is proposed and some preliminary numerical results indicate that the algorithm is quite promising.     

On the optimization of direct methods for solving fredholm integral equations of the second kind with infinitely smooth kernels

We give a direct method, optimal inL ₂, for solving the Fredholm integral equation of the second kind with operators acting into the space of functions harmonic in a disk or into the space of functions that can be analytically extended to an infinite strip. The exact order of the error of this method is determined.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 12, pp. 1695–1701, December, 1993.     

A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for the SVM QP with n variables, this rule can be implemented in O(n) operations using Rockafellar’s notion of conformal realization. Thus, for SVM training, our method requires only O(n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel.     

Peano curves with smooth footprints

We construct Peano curves \(\gamma : [0,\infty ) \rightarrow \mathbb {R}^2\) whose “footprints” \(\gamma ([0,t])\), \(t>0\), have \(C^\infty \) boundaries and are tangent to a common continuous line field on the punctured plane \(\mathbb {R}^2 {\backslash }\{\gamma (0)\}\). Moreover, these boundaries can be taken \(C^\infty \)-close to any prescribed smooth family of nested smooth Jordan curves contracting to a point.     

Operators with smooth functional calculi

We introduce a class of (tuples of commuting) unbounded operators on a Banach space, admitting smooth functional calculi, which contains all operators of Helffer-Sjöstrand type and is closed under the action of smooth proper mappings. Moreover, the class is closed under tensor product of commuting operators. In general, and operator in this class has no resolvent in the usual sense, so the spectrum must be defined in terms of the functional calculus. We also consider invariant subspaces and spectral decompositions.     

Convergence of the (GOP) algorithm for a large class of smooth optimization problems

In this paper it is shown that the (GOP) algorithm is guaranteed to be convergent for a large class of smooth mathematical programming problems.     

Character sums with smooth numbers

We use the large sieve inequality for smooth numbers due to Drappeau et al. (Smooth-supported multiplicative functions in arithmetic progressions beyond the \(x^{1/2}\)-barrier, Preprint, 2017. arXiv:1704.04831), together with some other arguments, to improve their bounds on the frequency of pairs \((q,\chi )\) of moduli q and primitive characters \(\chi \) modulo q, for which the corresponding character sums with smooth numbers are large.