Search

A popular approach to minimizing a finite sum of smooth convex functions is stochastic gradient descent (SGD) and its variants. Fundamental research questions associated with SGD include (i) how to find a lower bound on the number of times that the gradient oracle of each individual function must be assessed in order to find an e-minimizer of the overall ob jective; (ii) how to design algorithms which guarantee finding an e-minimizer of the overall ob jective in expectation no more than a certain number of times (in terms of 1/\epsilon) that the gradient oracle of each function needs to be assessed (i.e., upper bound). If these two bounds are at the same order of magnitude, then the algorithms may be called optimal. Most existing results along this line of research typically assume that the functions in the ob jective share the same condition number. In this paper, the first model we study is the problem of minimizing the sum of finitely many strongly convex functions whose condition numbers are all different. We propose an SGD-based method for this model and show that it is optimal in gradient computations, up to a logarithmic factor. We then consider a constrained separate block optimization model and present lower and upper bounds for its gradient computation complexity. Next, we propose solving the Fenchel dual of the constrained block optimization model via generalized SSNM, which we introduce earlier, and show that it yields a lower iteration complexity than solving the original model by the ADMM-type approach. Finally, we extend the analysis to the general composite convex optimization model and obtain gradient-computation complexity results under certain conditions. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and a nonsmooth function, while the second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have weak convergence guarantees or need to solve lots of subproblems per iteration. Due to this, we propose hybrid algorithms for solving this problem in which we first compute approximate critical points and then check whether these points are approximate D-stationary points. Under suitable conditions, we prove that there exists a subsequence of iterates of which every accumulation point is a D-stationary point. Some preliminary numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Given a closed convex set A in a Banach space X, motivated by the continuity and Fréchet differentiability of A introduced, respectively, in [D. Gale and V. Klee, Math. Scand., 7 (1959), pp. 379-391] and [X. Y. Zheng, SIAM J. Optim., 30 (2020), pp. 490-512], this paper considers the Cp-differentiability, subdifferentiability, and G\^ateaux differentiability of A. Using the technique of variational analysis, it is proved that A is Cp-differentiable (resp., subdifferentiable or G\^ateaux differentiable) if and only if for every continuous convex function f : X → R with infx∈A f(x) > infx∈X f(x) the corresponding constrained optimization problem PA(f) is 2/p-order-well-posed solvable (resp., generalized well-posed solvable or weak well-posed solvable). It is also proved that if the conjugate function f* of a continuous convex function f on X is Cp-differentiable on dom(f*), then for every closed convex set A in X with infx∈A f(x) > -∞ the corresponding optimization problem PA(f) is 2/p-order-well-posed solvable. As a byproduct, every constrained convex optimization problem with a strongly convex quadratic objective function is proved to be globally second-order-well-posed solvable. Our main results are new even in the case of finite dimensional spaces. [ABSTRACT FROM AUTHOR]

In a recent paper we studied an equation (called the "simple equation'') introduced by one of us in 1963 for an approximate correlation function associated with the ground state of an interacting Bose gas. Solving the equation yields a relation between the density ρ of the gas and the energy per particle. Our construction of solutions gave a well-defined function ρ(e) for the density as a function of the energy e. We had conjectured that ρ(e) is a strictly monotone increasing function, so that it can be inverted to yield the strictly monotone increasing function e(ρ). We had also conjectured that ρ e(ρ) is convex as a function of ρ. We prove both conjectures here for small densities, the context in which they have the most physical relevance, and the monotonicity also for large densities. Both conjectures are grounded in the underlying physics, and their proof provides further mathematical evidence for the validity of the assumptions underlying the derivation of the simple equation, at least for low or high densities, if not intermediate densities, although the equation gives surprisingly good predictions for all densities ρ. Another problem left open in our previous paper was whether the simple equation could be used to compute accurate predictions of observables other than the energy. Here, we provide a recipe for computing predictions for any one- or two-particle observables for the ground state of the Bose gas. We focus on the condensate fraction and the momentum distribution, and show that they have the same low density asymptotic behavior as that predicted for the Bose gas. Along with the computation of the low density energy of the simple equation in our previous paper, this shows that the simple equation reproduces the known and conjectured properties of the Bose gas at low densities. [ABSTRACT FROM AUTHOR]

Low rank recovery problems have been a subject of intense study in recent years. While the rank function is useful for regularization it is difficult to optimize due to its nonconvexity and discontinuity. The standard remedy for this is to exchange the rank function for the convex nuclear norm, which is known to favor low rank solutions under certain conditions. On the downside the nuclear norm exhibits a shrinking bias that can severely distort the solution in the presence of noise, which motivates the use of stronger nonconvex alternatives. In this paper we study two such formulations. We characterize the critical points and give sufficient conditions for a low rank stationary point to be unique. Moreover, we derive conditions that ensure global optimality of the low rank stationary point and show that these hold under moderate noise levels. [ABSTRACT FROM AUTHOR]

The golden ratio primal-dual algorithm (GRPDA) is a new variant of the classical Arrow-Hurwicz method for solving structured convex optimization problems, in which the objective function consists of the sum of two closed proper convex functions, one of which involves a composition with a linear transform. The same as the Arrow-Hurwicz method and the popular primal-dual algorithm (PDA) of Chambolle and Pock, GRPDA is full-splitting in the sense that it does not rely on solving any subproblems or linear system of equations iteratively. Compared with PDA, an important feature of GRPDA is that it permits larger primal and dual stepsizes. However, the stepsize condition of GRPDA requires that the spectral norm of the linear transform is known, which can be difficult to obtain in some applications. Furthermore, constant stepsizes are usually overconservative in practice. In this paper, we propose a linesearch strategy for GRPDA, which not only does not require the spectral norm of the linear transform but also allows adaptive and potentially much larger stepsizes. Within each linesearch step, only the dual variable needs to be updated, and it is thus quite cheap and does not require any extra matrix-vector multiplications for many special yet important applications such as a regularized least-squares problem. Global iterate convergence and 0(1/N) ergodic convergence rate results, measured by the function value gap and constraint violations of an equivalent optimization problem, are established, where N denotes the iteration counter. When one of the component functions is strongly convex, faster O(l/N²) ergodic convergence rate results, quantified by the same measures, are established by adaptively choosing some algorithmic parameters. Moreover, when the subdifferential operators of the component functions are strongly metric subregular, a condition that is much weaker than strong convexity, we show that the iterates converge R-linearly to the unique solution. Numerical experiments on matrix game and LASSO problems illustrate the effectiveness of the proposed linesearch strategy. [ABSTRACT FROM AUTHOR]

This paper deals with error bound characterizations of the conical constraint qualification (CCQ) for convex inequality systems in a Banach space X. We establish necessary and sufficient conditions for a closed convex set S defined by a convex function g to have CCQ. These conditions are expressed in terms of the notion of error bound. Our results show that these characterizations hold in the following special cases: 1. g is the maximum of a finite number of differentiable convex functions. 2. S is closed convex and polyhedral. 3. The dimension of the subspace span(S) is less than 2 and g is positively homogeneous. We construct technical examples showing that these characterizations are limited to the three situations above. We introduce a new condition in terms of the gauge function which allows us to give an error bound characterization of convex nondifferentiable systems and to obtain as a direct consequence different characterizations of the concept of the strong conical hull intersection property for a finite collection of convex sets. [ABSTRACT FROM AUTHOR]

We analyze the maximal growth of trajectories of discrete-time linear switching system, i.e., controlled linear systems with the control set being an arbitrary compact set of matrices. This is done by applying the optimal convex Lyapunov function called the Barabanov norm, which provides a very refined analysis of trajectories. Until recently that notion remained rather theoretical apart from special cases. In 2015 N. Guglielmi and M. Zennaro [SIAM J. Matrix Anal. Appl., 36 (2015), pp. 634-655] showed that many systems possess at least one efficiently computed Barabanov norm. In this paper we classify all possible Barabanov norms and prove that, under mild assumptions, which can be verified algorithmically, those norms are unique and are either piecewise-linear or piecewise-quadratic. For some narrow classes of systems, there are more complicated Barabanov norms, but they can still be classified and constructed. Using those results we find all trajectories of the fastest growth. Examples and numerical results are provided. [ABSTRACT FROM AUTHOR]

This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [I. Ekren, et al., Ann. Probab., 42 (2014), pp. 204-236], which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions and reduces to the notion of stochastic viscosity solutions analyzed in [E. Bayraktar and M. Sirbu, Proc. Amer. Math. Soc., 140 (2012), pp. 3645-3654; SIAM J. Control Optim., 51 (2013), pp. 4274-4294]. Our main result takes advantage of this enlargement of the test functions and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [L. A. Caffarelli and X. Cabre, Amer. Math. Soc. Colloq. Publ., 43, AMS, Providence, RI, 1995], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [I. Ekren et al., Ann. Probab., 42 (2014), pp. 204-236]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution. [ABSTRACT FROM AUTHOR]

This paper provides a probabilistic proof of the comparison result for viscosity solutions of path-dependent semilinear PDEs. We consider the notion of viscosity solutions introduced in [I. Ekren, et al., Ann. Probab., 42 (2014), pp. 204-236], which considers as test functions all those smooth processes which are tangent in mean. When restricted to the Markovian case, this definition induces a larger set of test functions and reduces to the notion of stochastic viscosity solutions analyzed in [E. Bayraktar and M. Sirbu, Proc. Amer. Math. Soc., 140 (2012), pp. 3645-3654; SIAM J. Control Optim., 51 (2013), pp. 4274-4294]. Our main result takes advantage of this enlargement of the test functions and provides an easier proof of comparison. This is most remarkable in the context of the linear path-dependent heat equation. As a key ingredient for our methodology, we introduce a notion of punctual differentiation, similar to the corresponding concept in the standard viscosity solutions [L. A. Caffarelli and X. Cabre, Amer. Math. Soc. Colloq. Publ., 43, AMS, Providence, RI, 1995], and we prove that semimartingales are almost everywhere punctually differentiable. This smoothness result can be viewed as the counterpart of the Aleksandroff smoothness result for convex functions. A similar comparison result was established earlier in [I. Ekren et al., Ann. Probab., 42 (2014), pp. 204-236]. The result of this paper is more general and, more importantly, the arguments that we develop do not rely on any representation of the solution. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of single-ratio fractional minimization problems, in which the numerator of the objective is the sum of a nonsmooth nonconvex function and a smooth nonconvex function while the denominator is a nonsmooth convex function. In this work, we first derive its first-order necessary optimality condition, by using the first-order operators of the three functions involved. Then we develop first-order algorithms, namely, the proximity-gradientsubgradient algorithm (PGSA), PGSA with monotone line search (PGSA ML), and PGSA with nonmonotone line search (PGSA NL). It is shown that any accumulation point of the sequence generated by them is a critical point of the problem under mild assumptions. Moreover, we establish global convergence of the sequence generated by PGSA or PGSA ML and analyze its convergence rate, by further assuming the local Lipschitz continuity of the nonsmooth function in the numerator, the smoothness of the denominator, and the Kurdyka--Łojasiewicz (KL) property of the objective. The proposed algorithms are applied to the sparse generalized eigenvalue problem associated with a pair of symmetric positive semidefinite matrices, and the corresponding convergence results are obtained according to their general convergence theorems. We perform some preliminary numerical experiments to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Conditional gradient methods have attracted much attention in both machine learning and optimization communities recently. These simple methods can guarantee the generation of sparse solutions. In addition, without the computation of full gradients, they can handle huge-scale problems sometimes even with an exponentially increasing number of decision variables. This paper aims to significantly expand the application areas of these methods by presenting new conditional gradient methods for solving convex optimization problems with general affine and nonlinear constraints. More specifically, we first present a new constraint extrapolated condition gradient (Co-exCG) method that can achieve an O(l/e2) iteration complexity for both smooth and structured nonsmooth function constrained convex optimization. We further develop novel variants of CoexCG, namely constraint extrapolated and dual regularized conditional gradient (CoexDurCG) methods, that can achieve similar iteration complexity to CoexCG but allow adaptive selection for algorithmic parameters. We illustrate the effectiveness of these methods for solving an important class of radiation therapy treatment planning problems arising from the healthcare industry. To the best of our knowledge, all the algorithmic schemes and their complexity results are new in the area of projection-free methods. [ABSTRACT FROM AUTHOR]

We consider a class of optimization problems with Cartesian variational inequality (CVI) constraints, where the objective function is convex and the CVI is associated with a monotone mapping and a convex Cartesian product set. This mathematical formulation captures a wide range of optimization problems including those complicated by the presence of equilibrium constraints, complementarity constraints, or an inner-level large scale optimization problem. In particular, an important motivating application arises from the notion of efficiency estimation of equilibria in multiagent networks, e.g., communication networks and power systems. In the literature, the iteration complexity of the existing solution methods for optimization problems with CVI constraints appears to be unknown. To address this shortcoming, we develop a first-order method called averaging randomized block iteratively regularized gradient (aRB-IRG). The main contributions include the following: (i) In the case where the associated set of the CVI is bounded and the objective function is nondifferentiable and convex, we derive new nonasymptotic suboptimality and infeasibility convergence rate statements in an ergodic sense. We also obtain deterministic variants of the convergence rates when we suppress the randomized block-coordinate scheme. Importantly, this paper appears to be the first work to provide these rate guarantees for this class of problems. (ii) In the case where the CVI set is unbounded and the ob jective function is smooth and strongly convex, utilizing the properties of the Tikhonov trajectory, we establish the global convergence of aRB-IRG in an almost sure and a mean sense. We provide the numerical experiments for computing the best Nash equilibrium in a networked Cournot competition model. [ABSTRACT FROM AUTHOR]

In [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407-438], an inexact variant of stochastic dual dynamic programming (SDDP) called ISDDP was introduced which uses approximate (instead of exact with SDDP) primal dual solutions of the problems solved in the forward and backward passes of the method. That variant of SDDP was studied in [V. Guigues, SIAM J. Optim., 30 (2020), pp. 407-438] for linear and for differentiable nonlinear multistage stochastic programs (MSPs). In this paper, we extend ISDDP to nondifferentiable MSPs. We first provide formulas for inexact cuts for value functions of convex nondifferentiable optimization problems. We then combine these cuts with SDDP to describe ISDDP for nondifferentiable MSPs and analyze the convergence of the method. More precisely, for a problem with T stages, we show that for errors bounded from ab ove by\varepsilon, the limit superior and limit inferior of sequences of upper and lower bounds on the optimal value of the problem are at most at distance 3\varepsilonT to the optimal value and that for asymptotically vanishing errors ISDDP converges to an optimal policy. Finally, we present the results of encouraging numerical experiments on a multistage nondifferentiable stochastic convex program solved using exact SDDP and the proposed ISDDP. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high level, the method is an inexact proximal-point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions. In addition, a two-phase variant is proposed that significantly reduces the variance of the solutions returned by the algorithm. Finally, preliminary numerical experiments are also provided. [ABSTRACT FROM AUTHOR]

Moreau's seminal paper, introducing what is now called the Moreau envelope and the proximity operator (also known as the proximal mapping), appeared in 1962. The Moreau envelope of a given convex function provides a regularized version which has additional desirable properties such as differentiability and full domain. Forty years ago, Attouch proposed using the Moreau envelope for regularization. Since then, this branch of convex analysis has developed in many fruitful directions. In 1967, Bregman introduced what is nowadays known as the Bregman distance as a measure of discrepancy between two points, generalizing the square of the Euclidean distance. Proximity operators based on the Bregman distance have become a topic of significant research as they are useful in the algorithmic solution of optimization problems. More recently, in 2012, Kan and Song studied regularization aspects of the left Bregman-Moreau envelope even for nonconvex functions. In this paper, we complement previous works by analyzing the left and right Bregman-Moreau envelopes and by providing additional asymptotic results. Several examples are provided. [ABSTRACT FROM AUTHOR]

Structured optimization problems are ubiquitous in fields like data science and engineering. The goal in structured optimization is using a prescribed set of points, called atoms, to build up a solution that minimizes or maximizes a given function. In the present paper, we want to minimize a black-box function over the convex hull of a given set of atoms, a problem that can be used to model a number of real-world applications. We focus on problems whose solutions are sparse, i.e., solutions that can be obtained as a proper convex combination of just a few atoms in the set, and propose a suitable derivative-free inner approximation approach that nicely exploits the structure of the given problem. This enables us to properly handle the dimensionality issues usually connected with derivative-free algorithms, thus getting a method that scales well in terms of both the dimension of the problem and the number of atoms. We analyze global convergence to stationary points. Moreover, we show that, under suitable assumptions, the proposed algorithm identifies a specific subset of atoms with zero weight in the final solution after finitely many iterations. Finally, we report numerical results showing the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we develop convergence analysis of a modified line search method for objective functions whose value is computed with noise and whose gradient estimates are inexact and possibly random. The noise is assumed to be bounded in absolute value without any additional assumptions. We extend the framework based on stochastic methods from [C. Cartis and K. Scheinberg, Math. Program., 169 (2018), pp. 337-375] which was developed to provide analysis of a standard line search method with exact function values and random gradients to the case of noisy functions. We introduce two alternative conditions on the gradient which, when satisfied with some sufficiently large probability at each iteration, guarantees convergence properties of the line search method. We derive expected complexity bounds to reach a near optimal neighborhood for convex, strongly convex and nonconvex functions. The exact dependence of the convergence neighborhood on the noise is specified. [ABSTRACT FROM AUTHOR]

The bitemperature Euler model describes a crucial step of inertial confinement fusion (ICF) when the plasma is quasineutral while ionic and electronic temperatures remain distinct. The model is written as a first-order hyperbolic system in nonconservative form with partially dissipative source terms. We consider the polytropic case for both ions and electrons with different γ-law pressures. The system does not fulfill the Shizuta-Kawashima condition and, the physical entropy, which is a strictly convex function, does not provide a symmetrizer of the system. In this paper we exhibit a symmetrizer to apply the result on the local existence of smooth solutions in several space dimensions. In the one-dimensional case we establish energy and dissipation estimates leading to global existence for small perturbations of equilibrium states. [ABSTRACT FROM AUTHOR]

This paper deals with particular families of DC optimization problems involving suprema of convex functions. We show that the specific structure of this type of function allows us to cover a variety of problems in nonconvex programming. Necessary and sufficient optimality conditions for these families of DC optimization problems are established, where some of these structural features are conveniently exploited. More precisely, we derive necessary and sufficient conditions for (global and local) optimality in DC semi-infinite programming and DC cone-constrained optimization, under natural constraint qualifications. Finally, a penalty approach to DC abstract programming problems is developed in the last section. [ABSTRACT FROM AUTHOR]

In this paper, we study greedy variants of quasi-Newton methods. They are based on the updating formulas from a certain subclass of the Broyden family. In particular, this subclass includes the well-known DFP, BFGS, and SR1 updates. However, in contrast to the classical quasi-Newton methods, which use the difference of successive iterates for updating the Hessian approximations, our methods apply basis vectors, greedily selected so as to maximize a certain measure of progress. For greedy quasi-Newton methods, we establish an explicit nonasymptotic bound on their rate of local superlinear convergence, as applied to minimizing strongly convex and strongly self-concordant functions (and, in particular, to strongly convex functions with Lipschitz continuous Hessian). The established superlinear convergence rate contains a contraction factor, which depends on the square of the iteration counter. We also show that greedy quasi-Newton methods produce Hessian approximations whose deviation from the exact Hessians linearly converges to zero. [ABSTRACT FROM AUTHOR]

This paper generalizes the optimized gradient method (OGM) [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482], [D. Kim and J. A. Fessler, Math. Program., 159 (2016), pp. 81-107], [D. Kim and J. A. Fessler, J. Optim. Theory Appl., 172 (2017), pp. 187-205] that achieves the optimal worst-case cost function bound of first-order methods for smooth convex minimization [Y. Drori, J. Complexity, 39 (2017), pp. 1-16]. Specifically, this paper studies a generalized formulation of OGM and analyzes its worst-case rates in terms of both the function value and the norm of the function gradient. This paper also develops a new algorithm called OGM-OG that is in the generalized family of OGM and that has the best known analytical worst-case bound with rate O(1/N1.5) on the decrease of the gradient norm among fixed-step first-order methods. This paper also proves that Nesterov's fast gradient method [Y. Nesterov, Dokl. Akad. Nauk. USSR, 269 (1983), pp. 543-547], [Y. Nesterov, Math. Program., 103 (2005), pp. 127-152] has an O(1/N1.5) worst-case gradient norm rate but with constant larger than OGM-OG. The proof is based on the worst-case analysis called the Performance Estimation Problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482]. [ABSTRACT FROM AUTHOR]

This paper is meant to prove the consistency of the scenario approach à la Calafiore, Campi, and Garatti with convex constraints. Scenario convex problems are usually stated in two equivalent forms: first, as the minimum of a linear function over the intersection of a finite random sample of independent and identically distributed convex sets, or second, as the min-max of a finite random sample of independent and identically distributed convex functions. The paper shows that, under fairly general assumptions, as the size of the sample increases the minimum attained by the solution of a problem of the first kind converges almost surely to the minimum attained by a suitably defined "essential" robust problem (or diverges if such a robust problem is infeasible), and that the minimum attained by the solution of a scenario problem of the second kind converges almost surely to the minimum of the pointwise essential supremum taken over all the possible convex functions (or diverges if such essential supremum takes the only value +∞). In both cases, if the solution of the essential problem exists and is unique, the solution of the scenario problem converges to it almost surely. [ABSTRACT FROM AUTHOR]

This paper provides a new way of developing the fast iterative shrinkage/thresholding algorithm (FISTA) [A. Beck and M. Teboulle, SIAM J. Imaging Sci., 2 (2009), pp. 183{202] that is widely used for minimizing composite convex functions with a nonsmooth term such as the ℓ1 regularizer. In particular, this paper shows that FISTA corresponds to an optimized approach to accelerating the proximal gradient method with respect to a worst-case bound of the cost function. This paper then proposes a new algorithm that is derived by instead optimizing the step coefficients of the proximal gradient method with respect to a worst-case bound of the composite gradient mapping. The proof is based on the worst-case analysis called the performance estimation problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482]. [ABSTRACT FROM AUTHOR]

In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function f and a (possibly nonsmooth) proper closed convex function g. The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of convex optimization problems. It has also found numerous applications in machine learning. The proximal damped Newton (PDN) methods have been well studied in the literature for solving this problem that enjoy a nice iteration complexity. Given that at each iteration these methods typically require evaluating or accessing the Hessian of f and also need to solve a proximal Newton subproblem, the cost per iteration can be prohibitively high when applied to large-scale problems. Inspired by the recent success of block coordinate descent methods, we propose a randomized block proximal damped Newton (RBPDN) method for solving the CSC minimization. Compared to the PDN methods, the computational cost per iteration of RBPDN is usually significantly lower. The computational experiment on a class of regularized logistic regression problems demonstrate that RBPDN is indeed promising in solving large-scale CSC minimization problems. The convergence of RBPDN is also analyzed in the paper. In particular, we show that RBPDN is globally convergent when g is Lipschitz continuous. It is also shown that RBPDN enjoys a local linear convergence. Moreover, we establish a global linear rate of convergence for a class of g including the case where g is smooth (but not necessarily self-concordant) and ∇g is Lipschitz continuous in a certain level set of f + g. As a consequence, we obtain a global linear rate of convergence for the classical damped Newton methods [Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, Boston, 2004; Y. Zhang and L. Xiao, preprint, arXiv:1501.00263, 2015] and the PDN [Q. Tran-Dinh, A. Kyrillidis, and V. Cevher, J. Mach. Learn. Res., 16 (2015), pp. 371-416] for such g, which was previously unknown in the literature. Moreover, this result can be used to sharpen the existing iteration complexity of these methods. [ABSTRACT FROM AUTHOR]

In this paper, we consider the general nonoblivious stochastic optimization where the underlying stochasticity may change during the optimization procedure and depends on the point at which the function is evaluated. We develop Stochastic Frank-Wolfe++ (SFW++), an efficient variant of the conditional gradient method for minimizing a smooth nonconvex function subject to a convex body constraint. We show that SFW++ converges to an ε-first order stationary point by using O(1/ε³) stochastic gradients. Once further structures are present, SFW++'s theoretical guarantees, in terms of the convergence rate and quality of its solution, improve. In particular, for minimizing a convex function, SFW++ achieves an ε-approximate optimum while using O(1/ε²) stochastic gradients. It is known that this rate is optimal in terms of stochastic gradient evaluations. Similarly, for maximizing a monotone continuous DR-submodular function, a slightly different form of SFW++, called Stochastic Continuous Greedy++ (SCG++), achieves a tight [(1 - 1/e)OPT - ε] solution while using O(1/ε²) stochastic gradients. Through an information theoretic argument, we also prove that SCG++'s convergence rate is optimal. Finally, for maximizing a nonmonotone continuous DR-submodular function, we can achieve a [(1/e)OPT - ε] solution by using O(1/ε²) stochastic gradients. We should highlight that our results and our novel variance reduction technique trivially extend to the standard and easier oblivious stochastic optimization settings for (non)convex and continuous submodular settings. [ABSTRACT FROM AUTHOR]

In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve non-smooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use predefined and dynamic sequences for parameters. We prove that our first algorithm can achieve an O(1/k) convergence rate on the primal-dual gap, and primal and dual objective residuals, where k is the iteration counter. Our rate is on the non-ergodic (i.e., the last iterate) sequence of the primal problem and on the ergodic (i.e., the averaging) sequence of the dual problem, which we call the semi-ergodic rate. By modifying the step-size update rule, this rate can be boosted even faster on the primal objective residual. When the problem is strongly convex, we develop a second primal-dual algorithm that exhibits an O(1/k²) convergence rate on the same three types of guarantees. Again by modifying the step-size update rule, this rate becomes faster on the primal objective residual. Our primal-dual algorithms are the first ones to achieve such fast convergence rate guarantees under mild assumptions compared to existing works, to the best of our knowledge. As byproducts, we apply our algorithms to solve constrained convex optimization problems and prove the same convergence rates on both the objective residuals and the feasibility violation. We still obtain at least O(1/k²) rates even when the problem is "semi-strongly" convex. We verify our theoretical results via two well-known numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we compare the definitions of convex sets and convex functions in finite dimensional integer spaces introduced by Adivar and Fang, Borwein, and Giladi, respectively. We show that their definitions of convex sets and convex functions are equivalent. We also provide exact formulations for convex sets, convex cones, affine sets, and convex functions and we analyze the separation between convex sets in finite dimensional integer spaces. As an application, we consider an integer linear programming problem with linear inequality constraints and obtain some necessary or sufficient optimality conditions by employing the image space analysis. We finally provide some computational results based on the above-mentioned optimality conditions. [ABSTRACT FROM AUTHOR]

In this paper, we study p-order methods for unconstrained minimization of convex functions that are p-times differentiable (p ≥ 2) with ν-Hölder continuous pth derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of O(ε-1/(p+ν-1)) for reducing the functional residual below a given ε ∈ (0, 1). Assuming that ν is known, we obtain an improved complexity bound of O(ε-1/(p+ν)) for the corresponding accelerated scheme. For the case in which ν is unknown, we present a universal accelerated tensor scheme with iteration complexity of O(ε-p/[(p+1)(p+ν-1)]). A lower complexity bound of O(ε-2/[3(p+ν)-2]) is also obtained for this problem class. [ABSTRACT FROM AUTHOR]

In this paper we propose a splitting scheme which hybridizes the generalized conditional gradient with a proximal step and which we call the CGALP algorithm for minimizing the sum of three proper convex and lower-semicontinuous functions in real Hilbert spaces. The minimization is subject to an affine constraint, that, in particular, allows one to deal with composite problems (a sum of more than three functions) in a separable way by the usual product space technique. While classical conditional gradient methods require Lipschitz continuity of the gradient of the differentiable part of the objective, CGALP needs only differentiability (on an appropriate subset) and hence circumvents the intricate question of Lipschitz continuity of gradients. For the two remaining functions in the objective, we do not require any additional regularity assumption. The second function, possibly nonsmooth, is assumed simple; i.e., the associated proximal mapping is easily computable. For the third function, again nonsmooth, we just assume that its domain is weakly compact and that a linearly perturbed minimization oracle is accessible. In particular, this last function can be chosen to be the indicator of a nonempty bounded closed convex set in order to deal with additional constraints. Finally, the affine constraint is addressed by the augmented Lagrangian approach. Our analysis is carried out for a wide choice of algorithm parameters satisfying so-called open loop rules. As main results, under mild conditions, we show asymptotic feasibility with respect to the affine constraint, weak convergence of the dual multipliers, and convergence of the Lagrangian values to the saddle-point optimal value. We also provide pointwise and ergodic rates of convergence for both the feasibility gap and the Lagrangian values. [ABSTRACT FROM AUTHOR]

We consider the optimization problem in which a continuous convex function is to be minimized over the joint numerical range of two Hermitian matrices. When those matrices are of large size, solving such problems by convex optimization can be computationally expensive. The goal of this paper is to present a novel nonlinear eigenvector method to accelerate the computation. We will show that the global minimizer of the optimization problem corresponds to a solution of a nonlinear eigenvalue problem with eigenvector nonlinearity (NEPv). The special structure of this NEPv allows for an efficient sequential subspace search algorithm, which is a nonlinear analogue to the NEPv of the commonly applied locally optimal conjugate gradient descent methods for Hermitian linear eigenvalue problems. Our new algorithm can be proven globally convergent to an eigenvector of the NEPv. Implementation details such as block iteration and preconditioning will be discussed. Numerical examples, with applications in computing the coercivity constant of boundary integral operators and solving multicast beamforming problems, show the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

The joint spectral radius (JSR) of a set of matrices characterizes the maximal asymptotic growth rate of an infinite product of matrices of the set. This quantity appears in a number of applications including the stability of switched and hybrid systems. A popular method used for the stability analysis of these systems searches for a Lyapunov function with convex optimization tools. We investigate dual formulations for this approach and leverage these dual programs for developing new analysis tools for the JSR. We show that the dual of this convex problem searches for the occupations measures of trajectories with high asymptotic growth rate. We both show how to generate a sequence of guaranteed high asymptotic growth rate and how to detect cases where we can provide lower bounds on the JSR. All results of this paper are presented for the general case of constrained switched systems, that is, systems for which the switching signal is constrained by an automaton. [ABSTRACT FROM AUTHOR]

The Douglas{Rachford algorithm (DRA) is a powerful optimization method for minimizing the sum of two convex (not necessarily smooth) functions. The vast majority of previous research dealt with the case when the sum has at least one minimizer. In the absence of minimizers, it was recently shown that for the case of two indicator functions, the DRA converges to a best approximation solution. In this paper, we present a new convergence result on the DRA applied to the problem of minimizing a convex function subject to a linear constraint. Indeed, a normal solution may be found even when the domain of the objective function and the linear subspace constraint have no point in common. As an important application, a new parallel splitting result is provided. We also illustrate our results through various examples. [ABSTRACT FROM AUTHOR]

This paper studies the class of two-stage stochastic programs with a linearly biparameterized recourse function defined by a convex quadratic program. A distinguishing feature of this new class of nonconvex stochastic programs is that the objective function in the second stage is linearly parameterized by the first-stage decision variable, in addition to the standard linear parameterization in the constraints. While a recent result has established that the resulting recourse function is of the difference-of-convex (dc) kind, the associated dc decomposition of the recourse function does not provide an easy way to compute a directional stationary solution of the two-stage stochastic program. Based on an implicit convex-concave property of the bi-parameterized recourse function, we introduce the concept of a generalized critical point of such a recourse function and provide a sufficient condition for such a point to be a directional stationary point of the stochastic program. We describe an iterative algorithm that combines regularization, convexification, and sampling and establish the subsequential convergence of the algorithm to a generalized critical point, with probability 1. [ABSTRACT FROM AUTHOR]

We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of nÃ--n matrices and an n-dimensional vector, find a sequence of K matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the K matrices and the given vector. This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to solve to optimality for state-of-the-art optimization software. We propose a simple exact algorithm for this problem. Our algorithm runs in polynomial time when the given set of matrices has the oligo-vertex property, a concept we introduce in this paper for a finite set of matrices. We derive several sufficient conditions for a set of matrices to have the oligo-vertex property. Numerical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global optimization solver. We also propose several open questions on the oligo-vertex property and discuss its potential connection with the finiteness property of a set of matrices, which may be of independent interest. [ABSTRACT FROM AUTHOR]

The boosted difference of convex functions algorithm (BDCA) was recently proposed for minimizing smooth difference of convex (DC) functions. BDCA accelerates the convergence of the classical difference of convex functions algorithm (DCA) thanks to an additional line search step. The purpose of this paper is twofold. First, we show that this scheme can be generalized and successfully applied to certain types of nonsmooth DC functions, namely, those that can be expressed as the difference of a smooth function and a possibly nonsmooth one. Second, we show that there is complete freedom in the choice of the trial step size for the line search, which is something that can further improve its performance. We prove that any limit point of the BDCA iterative sequence is a critical point of the problem under consideration and that the corresponding objective value is monotonically decreasing and convergent. The global convergence and convergence rate of the iterations are obtained under the Kurdyka– Lojasiewicz property. Applications and numerical experiments for two problems in data science are presented, demonstrating that BDCA outperforms DCA. Specifically, for the minimum sum-of-squares clustering problem, BDCA was on average 16 times faster than DCA, and for the multidimensional scaling problem, BDCA was 3 times faster than DCA. [ABSTRACT FROM AUTHOR]

Given a closed convex set A in a Banach space X, this paper considers the continuity and differentiability of A. The continuity of a closed convex set was introduced and studied by Gale and Klee [Math. Scand., 7 (1959), pp. 370--391] in terms of its support functional, and the differentiability of a closed convex set is a new notion introduced again in terms of its support functional. Using the technique of variational analysis, we prove that A is differentiable if and only if for every continuous linear (or convex) function f : X → R bounded below on A the corresponding optimization problem infxεA f(x) is well-posed solvable. In the reflexive space case, we prove that A is continuous if and only if for every continuous linear (or convex) function f : X → R bounded below on A the corresponding optimization problem infxεAf(x) is weakly well-posed solvable. We also prove that if the conjugate function f* of a given continuous convex function f on X is Fréchet differentiable (resp., continuous) on dom(f*), then for every closed convex set K in X with infxεKf(x) > - ∞ the corresponding optimization problem with objective f and constraint set K is well-posed (resp., weakly well-posed) solvable. In the framework of finite-dimensional spaces, several sharper results are established. [ABSTRACT FROM AUTHOR]

The classical convergence analysis of quasi-Newton methods assumes that function and gradient evaluations are exact. In this paper, we consider the case when there are (bounded) errors in both computations and establish conditions under which a slight modification of the BFGS algorithm with an Armijo–Wolfe line search converges to a neighborhood of the solution that is determined by the size of the errors. One of our results is an extension of the analysis presented in [R. H. Byrd and J. Nocedal, SIAM J. Numer. Anal., 26 (1989), pp. 727–739], which establishes that, for strongly convex functions, a fraction of the BFGS iterates are good iterates. We present numerical results illustrating the performance of the new BFGS method in the presence of noise. [ABSTRACT FROM AUTHOR]

This paper studies the class of non-smooth nonconvex problems in which the difference between a continuously differentiable function and a convex non-smooth function is minimized over linear constraints. Our goal is to attain a point satisfying the stationarity necessary optimality condition, defined as the lack of feasible descent directions. Although elementary in smooth optimization, this condition is nontrivial when the objective function is non-smooth, and, correspondingly, there are very few methods that obtain stationary points in such settings. We prove that stationarity in our model can be characterized by a finite number of directions and develop two methods, one deterministic and one random, that use these directions to obtain stationary points. Numerical experiments illustrate the benefit of obtaining a stationary point and the advantage of using the random method to do so. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the constrained sparse regression problem, where the loss function is convex but nonsmooth and the penalty term is defined by the cardinality function. First, we give an exact continuous relaxation problem in the sense that both problems have the same optimal solution set. Moreover, we show that a vector is a local minimizer with the lower bound property of the original problem if and only if it is a lifted stationary point of the relaxation problem. Second, we propose a smoothing proximal gradient (SPG) algorithm for finding a lifted stationary point of the continuous relaxation model. Our algorithm is a novel combination of the classical proximal gradient algorithm and the smoothing method. We prove that the proposed SPG algorithm globally converges to a lifted stationary point of the relaxation problem, has the local convergence rate of o(k \tau) with \tau \in (0, 1 2) on the objective function value, and identifies the zero entries of the lifted stationary point in finite iterations. Finally, we use three examples to illustrate the validity of the continuous relaxation model and good numerical performance of the SPG algorithm. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of structured nonsmooth difference-of-convex (DC)minimization in which the first convex component is the sum of a smooth and a nonsmooth function while the second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have weak convergence guarantees or exhibit slow convergence. Due to this, we propose two nonmonotone enhanced proximal DC algorithms for solving this problem. For possible acceleration, one uses a nonmonotone line-search scheme in which the associated Lipschitz constant is adaptively approximated by some local curvature information of the smooth function in the first convex component, and the other employs an extrapolation scheme. It is shown that every accumulation point of the solution sequence generated by them is a D-stationary point of the problem. These methods may, however, become inefficient when the number of convex smooth functions in defining the second convex component is large. To remedy this issue, we propose randomized counterparts for them and show that every accumulation point of the generated solution sequence is a D-stationary point of the problem almost surely. Some preliminary numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper analyzes the iteration complexity of a quadratic penalty accelerated in-exact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form f+h, where f is a differentiable function whose gradient is Lipschitz continuous and h is a closed convex function with possibly unbounded domain. The method, basically, consists of applying an accelerated inexact proximal point method for approximately solving a sequence of quadratic penalized subproblems associated with the linearly constrained problem. Each subproblem of the proximal point method is in turn approximately solved by an accelerated composite gradient (ACG) method. It is shown that the proposed scheme generates a p-approximate stationary point in at most O(p-3) ACG iterations. Finally, numerical results showing the effciency of the proposed method are also given. [ABSTRACT FROM AUTHOR]

In this paper, we study the behavior of solutions of the ODE associated to Nesterov acceleration. It is well-known since the pioneering work of Nesterov that the rate of convergence O(1/t²) is optimal for the class of convex functions with Lipschitz gradient. In this work, we show that better convergence rates can be obtained with some additional geometrical conditions, such as Łojasiewicz property. More precisely, we prove the optimal convergence rates that can be obtained depending on the geometry of the function F to minimize. The convergence rates are new, and they shed new light on the behavior of Nesterov acceleration schemes. We prove in particular that the classical Nesterov scheme may provide convergence rates that are worse than the classical gradient descent scheme on sharp functions: for instance, the convergence rate for strongly convex functions is not geometric for the classical Nesterov scheme (while it is the case for the gradient descent algorithm). This shows that applying the classical Nesterov acceleration on convex functions without looking more at the geometrical properties of the objective functions may lead to suboptimal algorithms. [ABSTRACT FROM AUTHOR]

The gradient method for minimizing a differentiable convex function on Riemannian manifolds with lower bounded sectional curvature is analyzed in this paper. An analysis of the method with three different finite procedures for determining the step size (namely, Lipschitz step size, adaptive step size, and Armijo's step size) is presented. The first procedure requires that the objective function has Lipschitz continuous gradient, which is not necessary for the other approaches. Convergence of the whole sequence to a minimizer, without any level set boundedness assumption, is proved. The iteration-complexity bound for functions with Lipschitz continuous gradient is also presented. Numerical experiments are provided to illustrate the effectiveness of the method in this new setting and certify the theoretical results. In particular, we consider the problem of finding the Riemannian center of mass and the so-called Karcher mean. Our numerical experiences indicate that the adaptive step size is a promising scheme that is worth considering. [ABSTRACT FROM AUTHOR]

The Douglas-Rachford algorithm is a classical and powerful splitting method for minimizing the sum of two convex functions and, more generally, finding a zero of the sum of two maximally monotone operators. Although this algorithm is well understood when the involved operators are monotone or strongly monotone, the convergence theory for weakly monotone settings is far from being complete. In this paper, we propose an adaptive Douglas-Rachford splitting algorithm for the sum of two operators, one of which is strongly monotone while the other one is weakly monotone. With appropriately chosen parameters, the algorithm converges globally to a fixed point from which we derive a solution of the problem. When one operator is Lipschitz continuous, we prove global linear convergence, which sharpens recent known results. [ABSTRACT FROM AUTHOR]

In this paper, given an admissible function φ, we consider φ-regularity and find it to be a suitable qualification for a function to satisfy the φ-growth condition and uniform φ-growth condition. We establish the relationships between φ-growth condition/uniform φ-growth condition of a φ-regular function and the corresponding strong metric subregularity/regularity of its subdifferential mapping. The results presented in this paper improve and generalize some existing ones on stable second-order local minimizers in the literature. [ABSTRACT FROM AUTHOR]

In this paper we consider a distributed stochastic optimization problem without gradient/subgradient information for local objective functions and subject to local convex constraints. Objective functions may be nonsmooth and observed with stochastic noises, and the network for the distributed design is time-varying. By adding stochastic dithers to local objective functions and constructing randomized differences motivated by the Kiefer--Wolfowitz algorithm, we propose a distributed subgradient-free algorithm for finding the global minimizer with local observations. Moreover, we prove that the consensus of estimates and global minimization can be achieved with probability one over the time-varying network, and we obtain the convergence rate of the mean average of estimates as well. Finally, we give numerical examples to illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Studying the landscape of nonconvex cost functions is key towards a better understanding of optimization algorithms widely used in signal processing, statistics, and machine learning. Meanwhile, the famous Kuramoto model has been an important mathematical model for studying the synchronization phenomena of coupled oscillators over various network topologies. In this paper, we bring together these two seemingly unrelated objects by investigating the optimization landscape of a nonlinear function E(θ ) = ½∑1≤i,j≤ n aij (1 - cos(θi - θj )) associated with an underlying network and exploring the relationship between the existence of local minima and the network topology. This function arises naturally in the Burer--Monteiro method applied to Z2 synchronization as well as matrix completion on the torus. Moreover, it corresponds to the energy function of the homogeneous Kuramoto model on complex networks for coupled oscillators. We prove that the minimizer of the energy function is unique up to a global translation under deterministic dense graphs and Erdös--Rényi random graphs with tools from optimization and random matrix theory. Consequently, the stable equilibrium of the corresponding homogeneous Kuramoto model is unique and the basin of attraction for the synchronous state of these coupled oscillators is the whole phase space minus a set of measure zero. In addition, our results address when the Burer--Monteiro method recovers the ground truth exactly from highly incomplete observations in Z 2 synchronization and shed light on the robustness of nonconvex optimization algorithms with respect to certain types of so-called monotone adversaries. Numerical simulations are performed to illustrate our results. [ABSTRACT FROM AUTHOR]

We characterize the subdifferential of the supremum function of finitely and infinitely indexed families of convex functions. The main contribution of this paper consists of providing formulas for such a subdifferential under weak continuity assumptions. The resulting formulas are given in terms of the exact subdifferential of the data functions at the reference point, and not at nearby points as in [Valadier, C. R. Math. Acad. Sci. Paris, 268 (1969), pp. 39--42]. We also derive new Fritz John- and KKT-type optimality conditions for semi-infinite convex optimization, omitting the continuity/closedness assumptions in [Dinh et al., ESAIM Control Optim. Calc. Var., 13 (2007), pp. 580--597]. When the family of functions is finite, we use continuity conditions concerning only the active functions, and not all the data functions as in [Rockafellar, Proc. Lond. Math. Soc. (3), 39 (1979), pp. 331--355; Volle, Acta Math. Vietnam., 19 (1994), pp. 137--148]. [ABSTRACT FROM AUTHOR]

The Moreau envelope is one of the key convexity-preserving functional operations in convex analysis, and it is central to the development and analysis of many approaches for convex optimization. This paper develops the theory for an analogous convolution operation, called the polar envelope, specialized to gauge functions. Many important properties of the Moreau envelope and the proximal map are mirrored by the polar envelope and its corresponding proximal map. These properties include smoothness of the envelope function, uniqueness, and continuity of the proximal map, which play important roles in duality and in the construction of algorithms for gauge optimization. A suite of tools with which to build algorithms for this family of optimization problems is thus established. [ABSTRACT FROM AUTHOR]