Authors:Lorenzo Stella; Andreas Themelis; Panagiotis Patrinos Pages: 443 - 487 Abstract: The forward–backward splitting method (FBS) for minimizing a nonsmooth composite function can be interpreted as a (variable-metric) gradient method over a continuously differentiable function which we call forward–backward envelope (FBE). This allows to extend algorithms for smooth unconstrained optimization and apply them to nonsmooth (possibly constrained) problems. Since the FBE can be computed by simply evaluating forward–backward steps, the resulting methods rely on a similar black-box oracle as FBS. We propose an algorithmic scheme that enjoys the same global convergence properties of FBS when the problem is convex, or when the objective function possesses the Kurdyka–Łojasiewicz property at its critical points. Moreover, when using quasi-Newton directions the proposed method achieves superlinear convergence provided that usual second-order sufficiency conditions on the FBE hold at the limit point of the generated sequence. Such conditions translate into milder requirements on the original function involving generalized second-order differentiability. We show that BFGS fits our framework and that the limited-memory variant L-BFGS is well suited for large-scale problems, greatly outperforming FBS or its accelerated version in practice, as well as ADMM and other problem-specific solvers. The analysis of superlinear convergence is based on an extension of the Dennis and Moré theorem for the proposed algorithmic scheme. PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9912-y Issue No:Vol. 67, No. 3 (2017)

Authors:Tianxiang Liu; Ting Kei Pong Pages: 489 - 520 Abstract: In this paper, we further study the forward–backward envelope first introduced in Patrinos and Bemporad (Proceedings of the IEEE Conference on Decision and Control, pp 2358–2363, 2013) and Stella et al. (Comput Optim Appl, doi:10.1007/s10589-017-9912-y, 2017) for problems whose objective is the sum of a proper closed convex function and a twice continuously differentiable possibly nonconvex function with Lipschitz continuous gradient. We derive sufficient conditions on the original problem for the corresponding forward–backward envelope to be a level-bounded and Kurdyka–Łojasiewicz function with an exponent of \(\frac{1}{2}\) ; these results are important for the efficient minimization of the forward–backward envelope by classical optimization algorithms. In addition, we demonstrate how to minimize some difference-of-convex regularized least squares problems by minimizing a suitably constructed forward–backward envelope. Our preliminary numerical results on randomly generated instances of large-scale \(\ell _{1-2}\) regularized least squares problems (Yin et al. in SIAM J Sci Comput 37:A536–A563, 2015) illustrate that an implementation of this approach with a limited-memory BFGS scheme usually outperforms standard first-order methods such as the nonmonotone proximal gradient method in Wright et al. (IEEE Trans Signal Process 57:2479–2493, 2009). PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9900-2 Issue No:Vol. 67, No. 3 (2017)

Authors:Daniel O’Connor; Lieven Vandenberghe Pages: 521 - 541 Abstract: Image deblurring techniques based on convex optimization formulations, such as total-variation deblurring, often use specialized first-order methods for large-scale nondifferentiable optimization. A key property exploited in these methods is spatial invariance of the blurring operator, which makes it possible to use the fast Fourier transform (FFT) when solving linear equations involving the operator. In this paper we extend this approach to two popular models for space-varying blurring operators, the Nagy–O’Leary model and the efficient filter flow model. We show how splitting methods derived from the Douglas–Rachford algorithm can be implemented with a low complexity per iteration, dominated by a small number of FFTs. PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9901-1 Issue No:Vol. 67, No. 3 (2017)

Authors:Dingtao Peng; Naihua Xiu; Jian Yu Pages: 543 - 569 Abstract: The affine rank minimization problem is to minimize the rank of a matrix under linear constraints. It has many applications in various areas such as statistics, control, system identification and machine learning. Unlike the literatures which use the nuclear norm or the general Schatten \(q~ (0<q<1)\) quasi-norm to approximate the rank of a matrix, in this paper we use the Schatten 1 / 2 quasi-norm approximation which is a better approximation than the nuclear norm but leads to a nonconvex, nonsmooth and non-Lipschitz optimization problem. It is important that we give a global necessary optimality condition for the \(S_{1/2}\) regularization problem by virtue of the special objective function. This is very different from the local optimality conditions usually used for the general \(S_q\) regularization problems. Explicitly, the global necessary optimality condition for the \(S_{1/2}\) regularization problem is a fixed point inclusion associated with the singular value half thresholding operator. Naturally, we propose a fixed point iterative scheme for the problem. We also provide the convergence analysis of this iteration. By discussing the location and setting of the optimal regularization parameter as well as using an approximate singular value decomposition procedure, we get a very efficient algorithm, half norm fixed point algorithm with an approximate SVD (HFPA algorithm), for the \(S_{1/2}\) regularization problem. Numerical experiments on randomly generated and real matrix completion problems are presented to demonstrate the effectiveness of the proposed algorithm. PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9898-5 Issue No:Vol. 67, No. 3 (2017)

Authors:Dang Van Hieu Pages: 571 - 594 Abstract: In this paper, three parallel hybrid subgradient extragradient algorithms are proposed for finding a common solution of a finite family of equilibrium problems in Hilbert spaces. The proposed algorithms originate from previously known results for variational inequalities and can be considered as modifications of extragradient methods for equilibrium problems. Theorems of strong convergence are established under the standard assumptions imposed on bifunctions. Some numerical experiments are given to illustrate the convergence of the new algorithms and to compare their behavior with other algorithms. PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9899-4 Issue No:Vol. 67, No. 3 (2017)

Authors:Christian Kanzow; Yekini Shehu Pages: 595 - 620 Abstract: The Krasnoselskii–Mann iteration plays an important role in the approximation of fixed points of nonexpansive operators; it is known to be weakly convergent in the infinite dimensional setting. In this present paper, we provide a new inexact Krasnoselskii–Mann iteration and prove weak convergence under certain accuracy criteria on the error resulting from the inexactness. We also show strong convergence for a modified inexact Krasnoselskii–Mann iteration under suitable assumptions. The convergence results generalize existing ones from the literature. Applications are given to the Douglas–Rachford splitting method, the Fermat–Weber location problem as well as the alternating projection method by John von Neumann. PubDate: 2017-07-01 DOI: 10.1007/s10589-017-9902-0 Issue No:Vol. 67, No. 3 (2017)

Authors:J. C. De Los Reyes; E. Loayza; P. Merino Pages: 225 - 258 Abstract: We present a second order algorithm, based on orthantwise directions, for solving optimization problems involving the sparsity enhancing \(\ell _1\) -norm. The main idea of our method consists in modifying the descent orthantwise directions by using second order information both of the regular term and (in weak sense) of the \(\ell _1\) -norm. The weak second order information behind the \(\ell _1\) -term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identification of the active set. We also prove that a reduced version of our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a specific choice of the algorithm parameters. We present several computational experiments to show the efficiency of our approach compared to other state-of-the-art algorithms. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9891-z Issue No:Vol. 67, No. 2 (2017)

Authors:Patrick R. Johnstone; Pierre Moulin Pages: 259 - 292 Abstract: This paper is concerned with convex composite minimization problems in a Hilbert space. In these problems, the objective is the sum of two closed, proper, and convex functions where one is smooth and the other admits a computationally inexpensive proximal operator. We analyze a family of generalized inertial proximal splitting algorithms (GIPSA) for solving such problems. We establish weak convergence of the generated sequence when the minimum is attained. Our analysis unifies and extends several previous results. We then focus on \(\ell _1\) -regularized optimization, which is the ubiquitous special case where the nonsmooth term is the \(\ell _1\) -norm. For certain parameter choices, GIPSA is amenable to a local analysis for this problem. For these choices we show that GIPSA achieves finite “active manifold identification”, i.e. convergence in a finite number of iterations to the optimal support and sign, after which GIPSA reduces to minimizing a local smooth function. We prove local linear convergence under either restricted strong convexity or a strict complementarity condition. We determine the rate in terms of the inertia, stepsize, and local curvature. Our local analysis is applicable to certain recent variants of the Fast Iterative Shrinkage–Thresholding Algorithm (FISTA), for which we establish active manifold identification and local linear convergence. Based on our analysis we propose a momentum restart scheme in these FISTA variants to obtain the optimal local linear convergence rate while maintaining desirable global properties. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9896-7 Issue No:Vol. 67, No. 2 (2017)

Authors:Frank E. Curtis; Arvind U. Raghunathan Pages: 317 - 360 Abstract: An algorithm for solving nearly-separable quadratic optimization problems (QPs) is presented. The approach is based on applying a semismooth Newton method to solve the implicit complementarity problem arising as the first-order stationarity conditions of such a QP. An important feature of the approach is that, as in dual decomposition methods, separability of the dual function of the QP can be exploited in the search direction computation. Global convergence of the method is promoted by enforcing decrease in component(s) of a Fischer–Burmeister formulation of the complementarity conditions, either via a merit function or through a filter mechanism. The results of numerical experiments when solving convex and nonconvex instances are provided to illustrate the efficacy of the method. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9895-8 Issue No:Vol. 67, No. 2 (2017)

Authors:Richard C. Barnard; Christian Clason Pages: 401 - 419 Abstract: This work is concerned with a class of PDE-constrained optimization problems that are motivated by an application in radiotherapy treatment planning. Here the primary design objective is to minimize the volume where a functional of the state violates a prescribed level, but prescribing these levels in the form of pointwise state constraints leads to infeasible problems. We therefore propose an alternative approach based on \(L^1\) penalization of the violation that is also applicable when state constraints are infeasible. We establish well-posedness of the corresponding optimal control problem, derive first-order optimality conditions, discuss convergence of minimizers as the penalty parameter tends to infinity, and present a semismooth Newton method for their efficient numerical solution. The performance of this method for a model problem is illustrated and contrasted with an alternative approach based on (regularized) state constraints. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9897-6 Issue No:Vol. 67, No. 2 (2017)

Authors:Anuj Bajaj; Warren Hare; Yves Lucet Pages: 421 - 442 Abstract: Computing explicitly the \(\varepsilon \) -subdifferential of a proper function amounts to computing the level set of a convex function namely the conjugate minus a linear function. The resulting theoretical algorithm is applied to the the class of (convex univariate) piecewise linear–quadratic functions for which existing numerical libraries allow practical computations. We visualize the results in a primal, dual, and subdifferential views through several numerical examples. We also provide a visualization of the Brøndsted–Rockafellar theorem. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9892-y Issue No:Vol. 67, No. 2 (2017)

Authors:Donald Goldfarb; Cun Mu; John Wright; Chaoxu Zhou Abstract: Minimization methods that search along a curvilinear path composed of a non-ascent negative curvature direction in addition to the direction of steepest descent, dating back to the late 1970s, have been an effective approach to finding a stationary point of a function at which its Hessian is positive semidefinite. For constrained nonlinear programs arising from recent applications, the primary goal is to find a stationary point that satisfies the second-order necessary optimality conditions. Motivated by this, we generalize the approach of using negative curvature directions from unconstrained optimization to equality constrained problems and prove that our proposed negative curvature method is guaranteed to converge to a stationary point satisfying second-order necessary conditions. PubDate: 2017-07-22 DOI: 10.1007/s10589-017-9925-6

Authors:E. Bergou; Y. Diouane; S. Gratton Abstract: We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem” in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model”. The latter is supposed to be adequate in a neighborhood of the current iterate. In this paper, we address an important practical question related with the choice of the norm for defining the neighborhood. More precisely, assuming here that the Hessian B of the model is symmetric positive definite, we propose the use of the so-called “energy norm”—defined by \(\Vert x\Vert _B= \sqrt{x^TBx}\) for all \(x \in \mathbb {R}^n\) —in both TR and ARC techniques. We show that the use of this norm induces remarkable relations between the trial step of both methods that can be used to obtain efficient practical algorithms. We furthermore consider the use of truncated Krylov subspace methods to obtain an approximate trial step for large scale optimization. Within the energy norm, we obtain line search algorithms along the Newton direction, with a special backtracking strategy and an acceptability condition in the spirit of TR/ARC methods. The new line search algorithm, derived by ARC, enjoys a worst-case iteration complexity of \(\mathcal {O}(\epsilon ^{-3/2})\) . We show the good potential of the energy norm on a set of numerical experiments. PubDate: 2017-07-21 DOI: 10.1007/s10589-017-9929-2

Authors:Simone Sagratella Abstract: We consider generalized potential games, that constitute a fundamental subclass of generalized Nash equilibrium problems. We propose different methods to compute solutions of generalized potential games with mixed-integer variables, i.e., games in which some variables are continuous while the others are discrete. We investigate which types of equilibria of the game can be computed by minimizing a potential function over the common feasible set. In particular, for a wide class of generalized potential games, we characterize those equilibria that can be computed by minimizing potential functions as Pareto solutions of a particular multi-objective problem, and we show how different potential functions can be used to select equilibria. We propose a new Gauss–Southwell algorithm to compute approximate equilibria of any generalized potential game with mixed-integer variables. We show that this method converges in a finite number of steps and we also give an upper bound on this number of steps. Moreover, we make a thorough analysis on the behaviour of approximate equilibria with respect to exact ones. Finally, we make many numerical experiments to show the viability of the proposed approaches. PubDate: 2017-07-18 DOI: 10.1007/s10589-017-9927-4

Authors:Mercedes Landete; Alfredo Marín; José Luis Sainz-Pardo Abstract: Decomposition methods for optimal spanning trees on graphs are explored in this work. The attention is focused on optimization problems where the objective function depends only on the degrees of the nodes of the tree. In particular, we deal with the Minimum Leaves problem, the Minimum Branch Vertices problem and the Minimum Degree Sum problem. The decomposition is carried out by identifying the articulation vertices of the graph and then its blocks, solving certain subproblems on the blocks and then bringing together the optimal sub-solutions following adequate procedures. Computational results obtained using similar Integer Programming formulations for both the original and the decomposed problems show the advantage of the proposed methods on decomposable graphs. PubDate: 2017-07-13 DOI: 10.1007/s10589-017-9924-7

Authors:C. Yalçın Kaya Abstract: Markov–Dubins path is the shortest planar curve joining two points with prescribed tangents, with a specified bound on its curvature. Its structure, as proved by Dubins in 1957, nearly 70 years after Markov posed the problem of finding it, is elegantly simple: a selection of at most three arcs are concatenated, each of which is either a circular arc of maximum (prescribed) curvature or a straight line. The Markov–Dubins problem and its variants have since been extensively studied in practical and theoretical settings. A reformulation of the Markov–Dubins problem as an optimal control problem was subsequently studied by various researchers using the Pontryagin maximum principle and additional techniques, to reproduce Dubins’ result. In the present paper, we study the same reformulation, and apply the maximum principle, with new insights, to derive Dubins’ result again. We prove that abnormal control solutions do exist. We characterize these solutions, which were not studied adequately in the literature previously, as a concatenation of at most two circular arcs and show that they are also solutions of the normal problem. Moreover, we prove that any feasible path of the types mentioned in Dubins’ result is a stationary solution, i.e., that it satisfies the Pontryagin maximum principle. We propose a numerical method for computing Markov–Dubins path. We illustrate the theory and the numerical approach by three qualitatively different examples. PubDate: 2017-07-12 DOI: 10.1007/s10589-017-9923-8

Authors:Georg Müller; Anton Schiela Abstract: We consider optimal control problems with distributed control that involve a time-stepping formulation of dynamic one body contact problems as constraints. We link the continuous and the time-stepping formulation by a nonconforming finite element discretization and derive existence of optimal solutions and strong stationarity conditions. We use this information for a steepest descent type optimization scheme based on the resulting adjoint scheme and implement its numerical application. PubDate: 2017-07-07 DOI: 10.1007/s10589-017-9918-5

Authors:Fabrice Poirion; Quentin Mercier; Jean-Antoine Désidéri Abstract: An algorithm for solving the expectation formulation of stochastic nonsmooth multiobjective optimization problems is proposed. The proposed method is an extension of the classical stochastic gradient algorithm to multiobjective optimization using the properties of a common descent vector defined in the deterministic context. The mean square and the almost sure convergence of the algorithm are proven. The algorithm efficiency is illustrated and assessed on an academic example. PubDate: 2017-06-28 DOI: 10.1007/s10589-017-9921-x

Authors:Sebastiaan Breedveld; Bas van den Berg; Ben Heijmen Abstract: While interior-point methods share the same fundamentals, the implementation determines the actual performance. In order to attain the highest efficiency, different applications may require differently tuned implementations. In this paper we describe an implementation specifically designed for optimisation in radiation therapy. These problems are large-scale nonlinear (and sometimes nonconvex) constrained optimisation problems, consisting of both sparse and dense data. Several application-specific properties are exploited to enhance efficiency. Permuting, tiling and mixed precision arithmetic allow the algorithm to optimally process the mixed dense and sparse data matrices (making this step 2.2 times faster, and overall runtime reduction of \(55\%\) ) and scalability (16 threads resulted in a speed-up factor of 9.8 compared to singlethreaded performance, against a speed-up factor of 7.7 for the less optimised implementation). Predefined cost-functions are hard-coded and the computationally expensive second derivatives are written in canonical form, and combined if multiple cost-functions are defined for the same clinical structure. The derivatives are then computed using a scaled matrix–matrix product. A cheap initialisation strategy based on the background knowledge reduces the number of iterations by \(11\%\) . We also propose a novel combined Mehrotra–Gondzio approach. The algorithm is extensively tested on a dataset consisting of 120 patients, distributed over 6 tumour sites/approaches. This test dataset is made publicly available. PubDate: 2017-06-28 DOI: 10.1007/s10589-017-9919-4

Authors:A. El Hamidi; H. Ossman; M. Jazar Abstract: The approximation of solutions to partial differential equations by tensorial separated representations is one of the most efficient numerical treatment of high dimensional problems. The key step of such methods is the computation of an optimal low-rank tensor to enrich the obtained iterative tensorial approximation. In variational problems, this step can be carried out by alternating minimization (AM) technics, but the convergence of such methods presents a real challenge. In the present work, the convergence of rank-one AM algorithms for a class of variational linear elliptic equations is studied. More precisely, we show that rank-one AM-sequences are in general bounded in the ambient Hilbert tensor space and are compact if a uniform non-orthogonality condition between iterates and the reaction term is fulfilled. In particular, if a rank-one AM-sequence is weakly convergent then it converges strongly and the common limit is a solution of the rank-one optimization problem. PubDate: 2017-06-27 DOI: 10.1007/s10589-017-9920-y