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:Teobaldo Bulhões; Anand Subramanian; Gilberto F. Sousa Filho; Lucídio dos Anjos F. Cabral Pages: 293 - 316 Abstract: Given an input graph, the p-cluster editing problem consists of minimizing the number of editions, i.e., additions and/or deletions of edges, so as to create p vertex-disjoint cliques (clusters). In order to solve this \({\mathscr {NP}}\) -hard problem, we propose a branch-and-price algorithm over a set partitioning based formulation with exponential number of variables. We show that this formulation theoretically dominates the best known formulation for the problem. Moreover, we compare the performance of three mathematical formulations for the pricing subproblem, which is strongly \({\mathscr {NP}}\) -hard. A heuristic algorithm is also proposed to speedup the column generation procedure. We report improved bounds for benchmark instances available in the literature. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9893-x 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:Matúš Benko; Helmut Gfrerer Pages: 361 - 399 Abstract: We propose an SQP algorithm for mathematical programs with vanishing constraints which solves at each iteration a quadratic program with linear vanishing constraints. The algorithm is based on the newly developed concept of \({\mathcal {Q}}\) -stationarity (Benko and Gfrerer in Optimization 66(1):61–92, 2017). We demonstrate how \({\mathcal {Q}}_M\) -stationary solutions of the quadratic program can be obtained. We show that all limit points of the sequence of iterates generated by the basic SQP method are at least M-stationary and by some extension of the method we also guarantee the stronger property of \({\mathcal {Q}}_M\) -stationarity of the limit points. PubDate: 2017-06-01 DOI: 10.1007/s10589-017-9894-9 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:Nicholas I. M. Gould; Daniel P. Robinson Pages: 1 - 38 Abstract: The details of a solver for minimizing a strictly convex quadratic objective function subject to general linear constraints are presented. The method uses a gradient projection algorithm enhanced with subspace acceleration to solve the bound-constrained dual optimization problem. Such gradient projection methods are well-known, but are typically employed to solve the primal problem when only simple bound-constraints are present. The main contributions of this work are threefold. First, we address the challenges associated with solving the dual problem, which is usually a convex problem even when the primal problem is strictly convex. In particular, for the dual problem, one must efficiently compute directions of infinite descent when they exist, which is precisely when the primal formulation is infeasible. Second, we show how the linear algebra may be arranged to take computational advantage of sparsity that is often present in the second-derivative matrix, mostly by showing how sparse updates may be performed for algorithmic quantities. We consider the case that the second-derivative matrix is explicitly available and sparse, and the case when it is available implicitly via a limited memory BFGS representation. Third, we present the details of our Fortran 2003 software package DQP, which is part of the GALAHAD suite of optimization routines. Numerical tests are performed on quadratic programming problems from the combined CUTEst and Maros and Meszaros test sets. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9886-1 Issue No:Vol. 67, No. 1 (2017)

Authors:B. Jadamba; A. Khan; M. Sama Pages: 39 - 71 Abstract: In this paper, we study new aspects of the integral contraint regularization of state-constrained elliptic control problems (Jadamba et al. in Syst Control Lett 61(6):707–713, 2012). Besides giving new results on the regularity and the convergence of the regularized controls and associated Lagrange multipliers, the main objective of this paper is to give abstract error estimates for the regularization error. We also consider a discretization of the regularized problems and derive numerical estimates which are uniform with respect to the regularization parameter and the discretization parameter. As an application of these results, we prove that this discretization is indeed a full discretization of the original problem defined in terms of a problem with finitely many integral constraints. Detailed numerical results justifying the theoretical findings as well as a comparison of our work with the existing literature is also given. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9885-2 Issue No:Vol. 67, No. 1 (2017)

Authors:Xiaojing Zhu Pages: 73 - 110 Abstract: In this paper we propose a new Riemannian conjugate gradient method for optimization on the Stiefel manifold. We introduce two novel vector transports associated with the retraction constructed by the Cayley transform. Both of them satisfy the Ring-Wirth nonexpansive condition, which is fundamental for convergence analysis of Riemannian conjugate gradient methods, and one of them is also isometric. It is known that the Ring-Wirth nonexpansive condition does not hold for traditional vector transports as the differentiated retractions of QR and polar decompositions. Practical formulae of the new vector transports for low-rank matrices are obtained. Dai’s nonmonotone conjugate gradient method is generalized to the Riemannian case and global convergence of the new algorithm is established under standard assumptions. Numerical results on a variety of low-rank test problems demonstrate the effectiveness of the new method. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9883-4 Issue No:Vol. 67, No. 1 (2017)

Authors:Porfirio Suñagua; Aurelio R. L. Oliveira Pages: 111 - 127 Abstract: The class of splitting preconditioners for the iterative solution of linear systems arising from Mehrotra’s predictor-corrector method for large scale linear programming problems needs to find a basis through a sophisticated process based on the application of a rectangular LU factorization. This class of splitting preconditioners works better near a solution of the linear programming problem when the matrices are highly ill-conditioned. In this study, we develop and implement a new approach to find a basis for the splitting preconditioner, based on standard rectangular LU factorization with partial permutation of the scaled transpose linear programming constraint matrix. In most cases, this basis is better conditioned than the existing one. In addition, we include a penalty parameter in Mehrotra’s predictor-corrector method in order to reduce ill-conditioning of the normal equations matrix. Computational experiments show a reduction in the average number of iterations of the preconditioned conjugate gradient method. Also, the increased efficiency and robustness of the new approach become evident by the performance profile. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9887-0 Issue No:Vol. 67, No. 1 (2017)

Authors:A. F. Izmailov; E. I. Uskov Pages: 129 - 154 Abstract: The stabilized sequential quadratic programming (SQP) method has nice local convergence properties: it possesses local superlinear convergence under very mild assumptions not including any constraint qualifications. However, any attempts to globalize convergence of this method indispensably face some principal difficulties concerned with intrinsic deficiencies of the steps produced by it when relatively far from solutions; specifically, it has a tendency to produce long sequences of short steps before entering the region where its superlinear convergence shows up. In this paper, we propose a modification of the stabilized SQP method, possessing better “semi-local” behavior, and hence, more suitable for the development of practical realizations. The key features of the new method are identification of the so-called degeneracy subspace and dual stabilization along this subspace only; thus the name “subspace-stabilized SQP”. We consider two versions of this method, their local convergence properties, as well as a practical procedure for approximation of the degeneracy subspace. Even though we do not consider here any specific algorithms with theoretically justified global convergence properties, subspace-stabilized SQP can be a relevant substitute for the stabilized SQP in such algorithms using the latter at the “local phase”. Some numerical results demonstrate that stabilization along the degeneracy subspace is indeed crucially important for success of dual stabilization methods. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9890-5 Issue No:Vol. 67, No. 1 (2017)

Authors:Xin-He Miao; Yu-Lin Chang; Jein-Shan Chen Pages: 155 - 173 Abstract: Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with p-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving p-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the p-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving p-order cone complementarity problem. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9889-y Issue No:Vol. 67, No. 1 (2017)

Authors:Biao Qu; Changyu Wang; Naihua Xiu Pages: 175 - 199 Abstract: In this paper, based on a merit function of the split feasibility problem (SFP), we present a Newton projection method for solving it and analyze the convergence properties of the method. The merit function is differentiable and convex. But its gradient is a linear composite function of the projection operator, so it is nonsmooth in general. We prove that the sequence of iterates converges globally to a solution of the SFP as long as the regularization parameter matrix in the algorithm is chosen properly. Especially, under some local assumptions which are necessary for the case where the projection operator is nonsmooth, we prove that the sequence of iterates generated by the algorithm superlinearly converges to a regular solution of the SFP. Finally, some numerical results are presented. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9884-3 Issue No:Vol. 67, No. 1 (2017)

Authors:Filippo Pecci; Edo Abraham; Ivan Stoianov Pages: 201 - 223 Abstract: In this paper, we investigate the application of penalty and relaxation methods to the problem of optimal placement and operation of control valves in water supply networks, where the minimization of average zone pressure is the objective. The optimization framework considers both the location and settings of control valves as decision variables. Hydraulic conservation laws are enforced as nonlinear constraints and binary variables are used to model the placement of control valves, resulting in a mixed-integer nonlinear program. We review and discuss theoretical and algorithmic properties of two solution approaches. These include penalty and relaxation methods that solve a sequence of nonlinear programs whose stationary points converge to a stationary point of the original mixed-integer program. We implement and evaluate the algorithms using a benchmarking water supply network. In addition, the performance of different update strategies for the penalty and relaxation parameters are investigated under multiple initial conditions. Practical recommendations on the numerical implementation are provided. PubDate: 2017-05-01 DOI: 10.1007/s10589-016-9888-z Issue No:Vol. 67, No. 1 (2017)

Authors:Jonathan Eckstein; Wang Yao 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-04-17 DOI: 10.1007/s10589-017-9911-z

Authors:A. Rösch; K. G. Siebert; S. Steinig Abstract: We derive a reliable a posteriori error estimator for a state-constrained elliptic optimal control problem taking into account both regularisation and discretisation. The estimator is applicable to finite element discretisations of the problem with both discretised and non-discretised control. The performance of our estimator is illustrated by several numerical examples for which we also introduce an adaptation strategy for the regularisation parameter. PubDate: 2017-04-10 DOI: 10.1007/s10589-017-9908-7

Authors:Lorenzo Stella; Andreas Themelis; Panagiotis Patrinos 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-04-10 DOI: 10.1007/s10589-017-9912-y

Authors:Puya Latafat; Panagiotis Patrinos Abstract: In this work we propose a new splitting technique, namely Asymmetric Forward–Backward–Adjoint splitting, for solving monotone inclusions involving three terms, a maximally monotone, a cocoercive and a bounded linear operator. Our scheme can not be recovered from existing operator splitting methods, while classical methods like Douglas–Rachford and Forward–Backward splitting are special cases of the new algorithm. Asymmetric preconditioning is the main feature of Asymmetric Forward–Backward–Adjoint splitting, that allows us to unify, extend and shed light on the connections between many seemingly unrelated primal-dual algorithms for solving structured convex optimization problems proposed in recent years. One important special case leads to a Douglas–Rachford type scheme that includes a third cocoercive operator. PubDate: 2017-04-08 DOI: 10.1007/s10589-017-9909-6

Authors:Wei Kang; Lucas C. Wilcox 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-04-08 DOI: 10.1007/s10589-017-9910-0