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]

The Mumford-Shah model is a classical segmentation model, but its objective function is nonconvex. The smoothing and thresholding (SaT) approach is a convex variant of the Mumford-Shah model, which seeks a smoothed approximation solution to the Mumford-Shah model. The SaT approach separates the segmentation into two stages: first, a convex energy function is minimized to obtain a smoothed image; then, a thresholding technique is applied to segment the smoothed image. The energy function consists of three weighted terms and the weights are called the regularization parameters. Selecting appropriate regularization parameters is crucial to achieving effective segmentation results. Traditionally, the regularization parameters are chosen by trial-and-error, which is a very time-consuming procedure and is not practical in real applications. In this paper, we apply a Bayesian inference approach to infer the regularization parameters and estimate the smoothed image. We analyze the convex variant Mumford-Shah variational model from a statistical perspective and then construct a hierarchical Bayesian model. A mean field variational family is used to approximate the posterior distribution. The variational density of the smoothed image is assumed to have a Gaussian density, and the hyperparameters are assumed to have Gamma variational densities. All the parameters in the Gaussian density and Gamma densities are iteratively updated. Experimental results show that the proposed approach is capable of generating high-quality segmentation results. Although the proposed approach contains an inference step to estimate the regularization parameters, it requires less CPU running time to obtain the smoothed image than previous methods. [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]

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 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]

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 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]

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]

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]

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 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]

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]

Robust low-rank tensor completion (RTC) problems have received considerable attention in recent years such as in signal processing and computer vision. In this paper, we focus on the bound constrained RTC problem for third-order tensors which recovers a low-rank tensor from partial observations corrupted by impulse noise. A widely used convex relaxation of this problem is to minimize the tensor nuclear norm for low rank and the\ell 1-norm for sparsity. However, it may result in biased solutions. To handle this issue, we propose a nonconvex model with a novel nonconvex tensor rank surrogate function and a novel nonconvex sparsity measure for RTC problems under limited sample constraints and two bound constraints, where these two nonconvex terms have a difference of convex functions structure. Then, a proximal majorization-minimization (PMM) algorithm is developed to solve the proposed model and this algorithm consists of solving a series of convex subproblems with an initial estimator to generate a new estimator which is used for the next subproblem. Theoretically, for this new estimator, we establish a recovery error bound for its recoverability and give the theoretical guarantee that lower error bounds can be obtained when a reasonable initial estimator is available. Then, by using the Kurdyka--\Lojasiewicz property exhibited in the resulting problem, we show that the sequence generated by the PMM algorithm globally converges to a critical point of the problem. Extensive numerical experiments including color images and multispectral images show the high efficiency of the proposed model. [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]

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]

An introduction is presented to a section on education on topics including Nesterov's method for convex optimization and comprehensive proof of Bertrand's theorem.

In this paper we combine the stochastic variance reduced gradient (SVRG) method [R. Johnson and T. Zhang, in Advances in Neural Information Processing Systems 26, 2013, pp. 315-323] with the primal dual fixed point method (PDFP) proposed in [P. Chen, J. Huang, and X. Zhang, Inverse Problems, 29 (2013)] to minimize a sum of two convex functions, one of which is linearly composite. This type of problems typically arise in sparse signal and image reconstruction. The proposed SVRGPDFP can be seen as a generalization of Prox-SVRG [L. Xiao and T. Zhang, SIAM J. Optim., 24 (2014), pp. 2057-2075] originally designed for the minimization of a sum of two convex functions. Based on some standard assumptions, we propose two variants, one for strongly convex objective functions and the other for the general convex case. Convergence analysis shows that the convergence rate of SVRG-PDFP is Ϭ(1/k) (here k is the iteration number) for the general convex objective function and linear for the strongly convex case. Numerical examples on machine learning and computerized tomography image reconstruction are provided to show the effectiveness of the 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]

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]

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]

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 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]

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]

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]

This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative, produces a sequence of matrices {Xk,Yk}, and at each step mainly performs a soft-thresholding operation on the singular values of the matrix Yk. There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates {Xk} is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which 1, 000 x 1, 000 matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are connected with the recent literature on linearized Bregman iterations for ℓ1 minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider numerical approximations of a constraint minimization problem, where the object function is a quadratic Dirichlet functional for vector fields and the interior constraint is given by a convex function. The solutions of this problem are usually referred to as harmonic maps. The solution is characterized by a nonlinear saddle point problem, and the corresponding linearized problem is well-posed near strict local minima. The main contribution of the present paper is to establish a corresponding result for a proper finite element discretization in the case of two space dimensions. Iterative schemes of Newton type for the discrete nonlinear saddle point problems are investigated, and mesh independent preconditioners for the iterative methods are proposed. [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]

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]

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]

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]

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]

Many optimization problems are naturally delivered in an uncertain framework, and one would like to exercise prudence against the uncertainty elements present in the problem. In previous contributions, it has been shown that solutions to uncertain convex programs that bear a high probability to satisfy uncertain constraints can be obtained at low computational cost through constraint randomization. In this paper, we establish new feasibility results for randomized algorithms. Specifically, the exact feasibility for the class of the so-called fully-supported problems is obtained. It turns out that all fully-supported problems share the same feasibility properties, revealing a deep kinship among problems of this class. It is further proven that the feasibility of the randomized solutions for all other convex programs can be bounded based on the feasibility for the prototype class of fully-supported problems. The feasibility result of this paper outperforms previous bounds and is not improvable because it is exact for fully-supported problems. [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]

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]

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]

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 new algorithmic structures with Douglas-Rachford (DR) operators to solve convex feasibility problems. We propose to embed the basic two-set-DR algorithmic operator into the string-averaging projections and into the block-iterative projection algorithmic structures, thereby creating new DR algorithmic schemes that include the recently proposed cyclic DR algorithm and the averaged DR algorithm as special cases. We further propose and investigate a new multiple-set-DR algorithmic operator. Convergence of all these algorithmic schemes is studied by using properties of strongly quasi-nonexpansive operators and firmly nonexpansive operators. [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]

A popular strategy for determining solutions to linear least-squares problems relies on using sparsitypromoting regularizers and is widely exploited in image processing applications such as, e.g., image denoising, deblurring, and inpainting. It is well known that, in general, nonconvex regularizers hold the potential for promoting sparsity more effectively than convex regularizers such as, e.g., those involving the l1 norm. To avoid the intrinsic difficulties related to non-convex optimization, the convex nonconvex (CNC) strategy has been proposed, which allows the use of nonconvex regularization while maintaining convexity of the total objective function. In this paper, a new CNC variational model is proposed, based on a more general parametric nonconvex nonseparable regularizer. The proposed model is applicable to a greater variety of image processing problems than prior CNC methods. We derive the convexity conditions and related theoretical properties of the presented CNC model, and we analyze existence and uniqueness of its solutions. A primal-dual forward-backward splitting algorithm is proposed for solving the related saddle-point problem. The convergence of the algorithm is demonstrated theoretically and validated empirically. Several numerical experiments are presented which prove the effectiveness of the proposed approach. [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]

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]