Authors:Jonathan Eckstein; Wang Yao Abstract: Abstract This paper presents two new approximate versions of the alternating direction method of multipliers (ADMM) derived by modifying of the original “Lagrangian splitting” convergence analysis of Fortin and Glowinski. They require neither strong convexity of the objective function nor any restrictions on the coupling matrix. The first method uses an absolutely summable error criterion and resembles methods that may readily be derived from earlier work on the relationship between the ADMM and the proximal point method, but without any need for restrictive assumptions to make it practically implementable. It permits both subproblems to be solved inexactly. The second method uses a relative error criterion and the same kind of auxiliary iterate sequence that has recently been proposed to enable relative-error approximate implementation of non-decomposition augmented Lagrangian algorithms. It also allows both subproblems to be solved inexactly, although ruling out “jamming” behavior requires a somewhat complicated implementation. The convergence analyses of the two methods share extensive underlying elements. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9911-z

Authors:Guoyin Li; Tianxiang Liu; Ting Kei Pong Abstract: Abstract We study the applicability of the Peaceman–Rachford (PR) splitting method for solving nonconvex optimization problems. When applied to minimizing the sum of a strongly convex Lipschitz differentiable function and a proper closed function, we show that if the strongly convex function has a large enough strong convexity modulus and the step-size parameter is chosen below a threshold that is computable, then any cluster point of the sequence generated, if exists, will give a stationary point of the optimization problem. We also give sufficient conditions guaranteeing boundedness of the sequence generated. We then discuss one way to split the objective so that the proposed method can be suitably applied to solving optimization problems with a coercive objective that is the sum of a (not necessarily strongly) convex Lipschitz differentiable function and a proper closed function; this setting covers a large class of nonconvex feasibility problems and constrained least squares problems. Finally, we illustrate the proposed algorithm numerically. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9915-8

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-11-01 DOI: 10.1007/s10589-017-9921-x

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-11-01 DOI: 10.1007/s10589-017-9918-5

Authors:Wei Kang; Lucas C. Wilcox Abstract: Abstract We address finding the semi-global solutions to optimal feedback control and the Hamilton–Jacobi–Bellman (HJB) equation. Using the solution of an HJB equation, a feedback optimal control law can be implemented in real-time with minimum computational load. However, except for systems with two or three state variables, using traditional techniques for numerically finding a semi-global solution to an HJB equation for general nonlinear systems is infeasible due to the curse of dimensionality. Here we present a new computational method for finding feedback optimal control and solving HJB equations which is able to mitigate the curse of dimensionality. We do not discretize the HJB equation directly, instead we introduce a sparse grid in the state space and use the Pontryagin’s maximum principle to derive a set of necessary conditions in the form of a boundary value problem, also known as the characteristic equations, for each grid point. Using this approach, the method is spatially causality free, which enjoys the advantage of perfect parallelism on a sparse grid. Compared with dense grids, a sparse grid has a significantly reduced size which is feasible for systems with relatively high dimensions, such as the 6-D system shown in the examples. Once the solution obtained at each grid point, high-order accurate polynomial interpolation is used to approximate the feedback control at arbitrary points. We prove an upper bound for the approximation error and approximate it numerically. This sparse grid characteristics method is demonstrated with three examples of rigid body attitude control using momentum wheels. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9910-0

Authors:Yong Zhang; Wanzhou Ye; Jianjun Zhang Abstract: Abstract In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q} (0<q \le 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9916-7

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-11-01 DOI: 10.1007/s10589-017-9919-4

Authors:Adam N. Letchford; Qiang Ni; Zhaoyu Zhong Abstract: Abstract We consider a challenging resource allocation problem arising in mobile wireless communications. The goal is to allocate the available channels and power in a so-called OFDMA system, in order to maximise the transmission rate, subject to quality of service constraints. Standard MINLP software struggled to solve even small instances of this problem. Using outer approximation, perspective cuts and several implementation “tricks”, we are able to solve realistic instances in about one minute. A novel ingredient of our algorithm is what we call pre-emptive cut generation: the generation of cutting planes that are not violated in the current iteration, but are likely to be violated in subsequent iterations. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9914-9

Authors:Lijun Xu; Bo Yu; Yin Zhang Abstract: Abstract Structure-enforced matrix factorization (SeMF) represents a large class of mathematical models appearing in various forms of principal component analysis, sparse coding, dictionary learning and other machine learning techniques useful in many applications including neuroscience and signal processing. In this paper, we present a unified algorithm framework, based on the classic alternating direction method of multipliers (ADMM), for solving a wide range of SeMF problems whose constraint sets permit low-complexity projections. We propose a strategy to adaptively adjust the penalty parameters which is the key to achieving good performance for ADMM. We conduct extensive numerical experiments to compare the proposed algorithm with a number of state-of-the-art special-purpose algorithms on test problems including dictionary learning for sparse representation and sparse nonnegative matrix factorization. Results show that our unified SeMF algorithm can solve different types of factorization problems as reliably and as efficiently as special-purpose algorithms. In particular, our SeMF algorithm provides the ability to explicitly enforce various combinatorial sparsity patterns that, to our knowledge, has not been considered in existing approaches. PubDate: 2017-11-01 DOI: 10.1007/s10589-017-9913-x

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-11-01 DOI: 10.1007/s10589-017-9920-y

Authors:Xiaoliang Song; Bo Chen; Bo Yu Abstract: Abstract In this paper, elliptic optimal control problems involving the \(L^1\) -control cost ( \(L^1\) -EOCP) is considered. To numerically discretize \(L^1\) -EOCP, the standard piecewise linear finite element is employed. However, different from the finite dimensional \(l^1\) -regularization optimization, the resulting discrete \(L^1\) -norm does not have a decoupled form. A common approach to overcome this difficulty is employing a nodal quadrature formula to approximately discretize the \(L^1\) -norm. It is clear that this technique will incur an additional error. To avoid the additional error, solving \(L^1\) -EOCP via its dual, which can be reformulated as a multi-block unconstrained convex composite minimization problem, is considered. Motivated by the success of the accelerated block coordinate descent (ABCD) method for solving large scale convex minimization problems in finite dimensional space, we consider extending this method to \(L^1\) -EOCP. Hence, an efficient inexact ABCD method is introduced for solving \(L^1\) -EOCP. The design of this method combines an inexact 2-block majorized ABCD and the recent advances in the inexact symmetric Gauss–Seidel (sGS) technique for solving a multi-block convex composite quadratic programming whose objective contains a nonsmooth term involving only the first block. The proposed algorithm (called sGS-imABCD) is illustrated at two numerical examples. Numerical results not only confirm the finite element error estimates, but also show that our proposed algorithm is more efficient than (a) the ihADMM (inexact heterogeneous alternating direction method of multipliers), (b) the accelerated proximal gradient method. PubDate: 2017-10-12 DOI: 10.1007/s10589-017-9951-4

Authors:T. Scarinci; V. M. Veliov Abstract: Abstract This paper considers a linear-quadratic optimal control problem where the control function appears linearly and takes values in a hypercube. It is assumed that the optimal controls are of purely bang–bang type and that the switching function, associated with the problem, exhibits a suitable growth around its zeros. The authors introduce a scheme for the discretization of the problem that doubles the rate of convergence of the Euler’s scheme. The proof of the accuracy estimate employs some recently obtained results concerning the stability of the optimal solutions with respect to disturbances. PubDate: 2017-10-06 DOI: 10.1007/s10589-017-9948-z

Authors:A. Fischer; M. Herrich; A. F. Izmailov; W. Scheck; M. V. Solodov Abstract: Abstract The LP-Newton method for constrained equations, introduced some years ago, has powerful properties of local superlinear convergence, covering both possibly nonisolated solutions and possibly nonsmooth equation mappings. A related globally convergent algorithm, based on the LP-Newton subproblems and linesearch for the equation’s infinity norm residual, has recently been developed. In the case of smooth equations, global convergence of this algorithm to B-stationary points of the residual over the constraint set has been shown, which is a natural result: nothing better should generally be expected in variational settings. However, for the piecewise smooth case only a property weaker than B-stationarity could be guaranteed. In this paper, we develop a procedure for piecewise smooth equations that avoids undesirable accumulation points, thus achieving the intended property of B-stationarity. PubDate: 2017-10-04 DOI: 10.1007/s10589-017-9950-5

Authors:Mahdi Noorizadegan; Abbas Seifi Abstract: Abstract We propose an efficient solution method based on a decomposition of set-partitioning formulation of an integrated surgery planning and scheduling problem with chance constraints. The studied problem is characterized by a set of identical operating rooms (ORs), a set of surgeries with uncertain durations, a set of surgeons, and surgery dependent turnover times. The decision variables include the number of ORs to open, assignments of surgeries and surgeons to ORs in admissible periods, and the sequence of surgeries to be performed in a period. The objective is to minimize the cost of opening ORs and the penalties associated with turnover times.In the proposed formulation, the column generation subproblem is decomposed over ORs and time periods. The structure of the subproblem is further exploited and transformed to a shortest path problem. A search algorithm has been devised to efficiently solve the resulting subproblem, subject to some optimality and feasibility conditions. The proposed computational method outperforms the standard chance constrained model and reduces the solution time significantly. Furthermore, extensive simulation experiments have been carried out to compare the performance of three variants of the underlying formulations and evaluate the sensitivity of the decisions to the probability of exceeding a session length. PubDate: 2017-10-04 DOI: 10.1007/s10589-017-9947-0

Authors:William W. Hager; James T. Hungerford; Ilya Safro Abstract: Abstract The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. The Vertex Separator Problem was formulated in the paper 10.1016/j.ejor.2014.05.042 as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. We develop a method for improving upon a given vertex separator by applying a Mountain Climbing Algorithm to the bilinear program using an incidence vector for the separator as a starting guess. Sufficient conditions are developed under which the algorithm can improve upon the starting guess after at most two iterations. The refinement algorithm is augmented with a perturbation technique to enable escapes from local optima and is embedded in a multilevel framework for solving large scale instances of the problem. The multilevel algorithm is shown through computational experiments to perform particularly well on communication and collaboration networks. PubDate: 2017-10-04 DOI: 10.1007/s10589-017-9945-2

Authors:Gonzalo Muñoz; Daniel Espinoza; Marcos Goycoolea; Eduardo Moreno; Maurice Queyranne; Orlando Rivera Letelier Abstract: Abstract We study a Lagrangian decomposition algorithm recently proposed by Dan Bienstock and Mark Zuckerberg for solving the LP relaxation of a class of open pit mine project scheduling problems. In this study we show that the Bienstock–Zuckerberg (BZ) algorithm can be used to solve LP relaxations corresponding to a much broader class of scheduling problems, including the well-known Resource Constrained Project Scheduling Problem (RCPSP), and multi-modal variants of the RCPSP that consider batch processing of jobs. We present a new, intuitive proof of correctness for the BZ algorithm that works by casting the BZ algorithm as a column generation algorithm. This analysis allows us to draw parallels with the well-known Dantzig–Wolfe decomposition (DW) algorithm. We discuss practical computational techniques for speeding up the performance of the BZ and DW algorithms on project scheduling problems. Finally, we present computational experiments independently testing the effectiveness of the BZ and DW algorithms on different sets of publicly available test instances. Our computational experiments confirm that the BZ algorithm significantly outperforms the DW algorithm for the problems considered. Our computational experiments also show that the proposed speed-up techniques can have a significant impact on the solve time. We provide some insights on what might be explaining this significant difference in performance. PubDate: 2017-10-03 DOI: 10.1007/s10589-017-9946-1

Authors:Waltraud Huyer; Arnold Neumaier Abstract: Abstract We propose new algorithms for (i) the local optimization of bound constrained quadratic programs, (ii) the solution of general definite quadratic programs, and (iii) finding either a point satisfying given linear equations and inequalities or a certificate of infeasibility. The algorithms are implemented in Matlab and tested against state-of-the-art quadratic programming software. PubDate: 2017-10-03 DOI: 10.1007/s10589-017-9949-y

Authors:Fanz Rendl; Renata Sotirov Abstract: Abstract We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus on a new class of semidefinite relaxations, based on matrices of order \(2n+1\) which provide a good compromise between quality of the bound and computational effort to actually compute it. Here, n is the order of the graph. Our numerical results indicate that the new bounds are quite strong and can be computed for graphs of medium size ( \(n \approx 300\) ) with reasonable effort of a few minutes of computation time. Further, we exploit those bounds to obtain bounds on the size of the vertex separators. A vertex separator is a subset of the vertex set of a graph whose removal splits the graph into two disconnected subsets. We also present an elegant way of convexifying non-convex quadratic problems by using semidefinite programming. This approach results with bounds that can be computed with any standard convex quadratic programming solver. PubDate: 2017-09-18 DOI: 10.1007/s10589-017-9943-4

Authors:Souvik Roy; Mario Annunziato; Alfio Borzì; Christian Klingenberg Abstract: Abstract A Fokker–Planck control strategy for collective motion is investigated. This strategy is formulated as the minimisation of an expectation objective with a bilinear optimal control problem governed by the Fokker–Planck equation modelling the evolution of the probability density function of the stochastic motion. Theoretical results on existence and regularity of optimal controls are provided. The resulting optimality system is discretized using an alternate-direction implicit Chang–Cooper scheme that guarantees conservativeness, positivity, \(L^1\) stability, and second-order accuracy of the forward solution. A projected non-linear conjugate gradient scheme is used to solve the optimality system. Results of numerical experiments validate the theoretical accuracy estimates and demonstrate the efficiency of the proposed control framework. PubDate: 2017-09-15 DOI: 10.1007/s10589-017-9944-3

Authors:Francisco J. Aragón Artacho; Rubén Campoy Abstract: Abstract In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas–Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces. PubDate: 2017-09-06 DOI: 10.1007/s10589-017-9942-5