Authors:Lorenzo Stella; Andreas Themelis; Panagiotis Patrinos Pages: 443 - 487 Abstract: 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: 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: 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: 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: 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: 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:Chengjing Wang; Peipei Tang Abstract: Abstract In this paper, we propose a primal majorized semismooth Newton-CG augmented Lagrangian method for large-scale linearly constrained convex programming problems, especially for some difficult problems. The basic idea of this method is to apply the majorized semismooth Newton-CG augmented Lagrangian method to the primal convex problem. And we take two special nonlinear semidefinite programming problems as examples to illustrate the algorithm. Furthermore, we establish the global convergence and the iteration complexity of the algorithm. Numerical experiments demonstrate that our method works very well for the testing problems, especially for many ill-conditioned ones. PubDate: 2017-07-28 DOI: 10.1007/s10589-017-9930-9

Authors:Mingqiang Li; Congying Han; Ruxin Wang; Tiande Guo Abstract: Abstract Total variation regularization introduced by Rudin, Osher, and Fatemi (ROF) is widely used in image denoising problems for its capability to preserve repetitive textures and details of images. Many efforts have been devoted to obtain efficient gradient descent schemes for dual minimization of ROF model, such as Chambolle’s algorithm or gradient projection (GP) algorithm. In this paper, we propose a general gradient descent algorithm with a shrinking factor. Both Chambolle’s and GP algorithm can be regarded as the special cases of the proposed methods with special parameters. Global convergence analysis of the new algorithms with various step lengths and shrinking factors are present. Numerical results demonstrate their competitiveness in computational efficiency and reconstruction quality with some existing classic algorithms on a set of gray scale images. PubDate: 2017-07-27 DOI: 10.1007/s10589-017-9931-8

Authors:Jesús Sánchez-Oro; Anna Martínez-Gavara; Manuel Laguna; Rafael Martí; Abraham Duarte Abstract: Abstract Automated graph-drawing systems utilize procedures to place vertices and arcs in order to produce graphs with desired properties. Incremental or dynamic procedures are those that preserve key characteristics when updating an existing drawing. These methods are particularly useful in areas such as planning and logistics, where updates are frequent. We propose a procedure based on the scatter search methodology that is adapted to the incremental drawing problem in hierarchical graphs. These drawings can be used to represent any acyclic graph. Comprehensive computational experiments are used to test the efficiency and effectiveness of the proposed procedure. PubDate: 2017-07-27 DOI: 10.1007/s10589-017-9926-5

Authors:Geovani N. Grapiglia; Ekkehard W. Sachs Abstract: Abstract A general class of non-monotone line search algorithms has been proposed by Sachs and Sachs (Control Cybern 40:1059–1075, 2011) for smooth unconstrained optimization, generalizing various non-monotone step size rules such as the modified Armijo rule of Zhang and Hager (SIAM J Optim 14:1043–1056, 2004). In this paper, the worst-case complexity of this class of non-monotone algorithms is studied. The analysis is carried out in the context of non-convex, convex and strongly convex objectives with Lipschitz continuous gradients. Despite de nonmonotonicity in the decrease of function values, the complexity bounds obtained agree in order with the bounds already established for monotone algorithms. PubDate: 2017-07-26 DOI: 10.1007/s10589-017-9928-3

Authors:Peter A. Graf; Stephen Billups Abstract: Abstract Computational materials design has suffered from a lack of algorithms formulated in terms of experimentally accessible variables. Here we formulate the problem of (ternary) alloy optimization at the level of choice of atoms and their composition that is normal for synthesists. Mathematically, this is a mixed integer problem where a candidate solution consists of a choice of three elements, and how much of each of them to use. This space has the natural structure of a set of equilateral triangles. We solve this problem by introducing a novel version of the DIRECT algorithm that (1) operates on equilateral triangles instead of rectangles and (2) works across multiple triangles. We demonstrate on a test case that the algorithm is both robust and efficient. Finally, we offer an explanation of the efficacy of DIRECT—specifically, its balance of global and local search—by showing that “potentially optimal rectangles” of the original algorithm are akin to the Pareto front of the “multi-component optimization” of global and local search. PubDate: 2017-07-24 DOI: 10.1007/s10589-017-9922-9

Authors:Donald Goldfarb; Cun Mu; John Wright; Chaoxu Zhou Abstract: 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: 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: 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: 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: 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: 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: 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: 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: 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