Search

We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207‐211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109‐138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence and complexity properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and more stable than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109‐138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one. [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 is concerned with the following partially dissipative viscoelastic Timoshenko system { ρ 1 ϕ t t − κ (ϕ x + ψ) x + κ ∫ 0 t g (t − s) (ϕ x + ψ) x d s = 0 in (0 , L) × R + , ρ 2 ψ t t − b ψ x x + κ (φ x + ψ) − κ ∫ 0 t g (t − s) (ϕ x + ψ) d s = 0 in (0 , L) × R + , with damping mechanism acting only on the shear force, and with Dirichlet boundary conditions. We consider a very general relaxation function g ′ (t) ≤ − ξ (t) H (g (t)) , ∀ t ≥ 0. Under appropriate conditions on ξ and H, we establish a general stability result. The result is obtained under the assumption of equal speed of wave propagation. This work extends and generalizes many results in literature such as Alves et al. [On modeling and uniform stability of a partially dissipative viscoelastic Timoshenko system. SIAM J Math Anal. 2019;51(6):4520–4543]. [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]

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]

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]

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]

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]

In this paper, to find a common element of the fixed point set of common fixed points of a countable family of nonexpansive mappings and the solution set of the variational inequality for α-inverse-strongly monotone, we introduce an iterative approximation method in a real Hilbert space. Then the strong convergence theorem is proved under some appropriate conditions imposed on the parameters. This result extended and improved the corresponding results of Yao and Yao [15] and many others. [ABSTRACT FROM AUTHOR]

For solving strongly convex optimization problems, we propose and study the global convergence of variants of the accelerated hybrid proximal extragradient (A-HPE) and large-step A-HPE algorithms of R.D.C. Monteiro and B.F. Svaiter [An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM J. Optim. 23 (2013), pp. 1092–1125.]. We prove linear and the superlinear O (k − k (p − 1 p + 1) ) global rates for the proposed variants of the A-HPE and large-step A-HPE methods, respectively. The parameter p ≥ 2 appears in the (high-order) large-step condition of the new large-step A-HPE algorithm. We apply our results to high-order tensor methods, obtaining a new inexact (relative-error) tensor method for (smooth) strongly convex optimization with iteration-complexity O (k − k (p − 1 p + 1) ) . In particular, for p = 2, we obtain an inexact proximal-Newton algorithm with fast global O (k − k / 3) convergence rate. [ABSTRACT FROM AUTHOR]

We consider a variable metric and inexact version of the fast iterative soft-thresholding algorithm (FISTA) type algorithm considered in [L. Calatroni and A. Chambolle, SIAM J. Optim., 29 (2019), pp. 1772-1798; A. Chambolle and T. Pock, Acta Numer., 25 (2016), pp. 161-319] for the minimization of the sum of two (possibly strongly) convex functions. The proposed algorithm is combined with an adaptive (nonmonotone) backtracking strategy, which allows for the adjustment of the algorithmic step-size along the iterations in order to improve the convergence speed. We prove a linear convergence result for the function values, which depends on both the strong convexity moduli of the two functions and the upper and lower bounds on the spectrum of the variable metric operators. We validate the proposed algorithm, named Scaled Adaptive GEneralized FISTA (SAGE-FISTA), on exemplar image denoising and deblurring problems where edge-preserving total variation (TV) regularization is combined with Kullback-Leibler-type fidelity terms, as is common in applications where signal-dependent Poisson noise is assumed in the data. [ABSTRACT FROM AUTHOR]

We introduce an inexact variant of stochastic mirror descent (SMD), called inexact stochastic mirror descent (ISMD), to solve nonlinear two-stage stochastic programs where the second stage problem has linear and nonlinear coupling constraints and a nonlinear objective function which depends on both first and second stage decisions. Given a candidate first stage solution and a realization of the second stage random vector, each iteration of ISMD combines a stochastic subgradient descent using a prox-mapping with the computation of approximate (instead of exact for SMD) primal and dual second stage solutions. We provide two convergence analysis of ISMD, under two sets of assumptions. The first convergence analysis is based on the formulas for inexact cuts of value functions of convex optimization problems shown recently in Guigues (SIAM J. Optim. 30(1), 407–438, 2020). The second convergence analysis provides a convergence rate (the same as SMD) and relies on new formulas that we derive for inexact cuts of value functions of convex optimization problems assuming that the dual function of the second stage problem for all fixed first stage solution and realization of the second stage random vector, is strongly concave. We show that this assumption of strong concavity is satisfied for some classes of problems and present the results of numerical experiments on two simple two-stage problems which show that solving approximately the second stage problem for the first iterations of ISMD can help us obtain a good approximate first stage solution quicker than with SMD. [ABSTRACT FROM AUTHOR]

For an inequality system defined by an infinite family of proper lower semicontinuous convex functions in normed linear space, we consider the Farkas--Minkowski (FM for short) type qualification and the basic constraint qualification (BCQ for short). By employing a new approach based on some new results established here on the SECQ (sum of epigraphs constraint qualification) for families of closed convex sets, some sufficient conditions involving further relaxing Slater type conditions for ensuring the FM qualification are provided. As applications, new sufficient conditions for ensuring the BCQ are given. These results significantly improve the corresponding ones in [C. Li and K. F. Ng, SIAM J. Optim., 15 (2005), pp. 488-512] and [C. Li, X. P. Zhao, and Y. H. Hu, SIAM J. Optim., 23 (2013), pp. 2208-2230], and they are obtained without the key continuity assumption on the sup-function of the inequality system which the previous works depend heavily on. Some examples are also presented to illustrate the applicability of our results. [ABSTRACT FROM AUTHOR]