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