Authors:Lluís-Miquel Munguía; Shabbir Ahmed; David A. Bader; George L. Nemhauser; Yufen Shao Pages: 1 - 24 Abstract: We present a parallel large neighborhood search framework for finding high quality primal solutions for general mixed-integer programs (MIPs). The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary MIPs, where subsets of the variables are fixed. In contrast to prior approaches, ours does not require a feasible starting solution. We leverage parallelism to perform multiple searches simultaneously, with the objective of increasing the effectiveness of our heuristic. We computationally compare the proposed framework with a state-of-the-art MIP solver in terms of solution quality, scalability, reproducibility, and parallel efficiency. Results show the efficacy of our approach in finding high quality solutions quickly both as a standalone primal heuristic and when used in conjunction with an exact algorithm. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9934-5 Issue No:Vol. 69, No. 1 (2018)

Authors:D. M. King; S. H. Jacobson; E. C. Sewell Pages: 25 - 49 Abstract: Every 10 years, United States Congressional Districts must be redesigned in response to a national census. While the size of practical political districting problems is typically too large for exact optimization approaches, heuristics such as local search can help stakeholders quickly identify good (but suboptimal) plans that suit their objectives. However, enforcing a district contiguity constraint during local search can require significant computation; tools that can reduce contiguity-based computations in large practical districting problems are needed. This paper applies the geo-graph framework to the creation of United States Congressional Districts from census blocks in four states—Arizona, Massachusetts, New Mexico, and New York—and finds that (a) geo-graph contiguity assessment algorithms reduce the average number of edges visited during contiguity assessments by at least three orders of magnitude in every problem instance when compared with simple graph search, and (b) the assumptions of the geo-graph model are easily adapted to the sometimes-irregular census block geography with only superficial impact on the solution space. These results show that the geo-graph model and its associated contiguity algorithms provide a powerful constraint assessment tool to political districting stakeholders. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9936-3 Issue No:Vol. 69, No. 1 (2018)

Authors:E. G. Birgin; G. Haeser; A. Ramos Pages: 51 - 75 Abstract: Augmented Lagrangian methods with convergence to second-order stationary points in which any constraint can be penalized or carried out to the subproblems are considered in this work. The resolution of each subproblem can be done by any numerical algorithm able to return approximate second-order stationary points. The developed global convergence theory is stronger than the ones known for current algorithms with convergence to second-order points in the sense that, besides the flexibility introduced by the general lower-level approach, it includes a loose requirement for the resolution of subproblems. The proposed approach relies on a weak constraint qualification, that allows Lagrange multipliers to be unbounded at the solution. It is also shown that second-order resolution of subproblems increases the chances of finding a feasible point, in the sense that limit points are second-order stationary for the problem of minimizing the squared infeasibility. The applicability of the proposed method is illustrated in numerical examples with ball-constrained subproblems. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9937-2 Issue No:Vol. 69, No. 1 (2018)

Authors:Jianjun Liu; Xiangmin Xu; Xuehui Cui Pages: 77 - 97 Abstract: Trust region method is a robust method for optimization problems. In this paper, we propose a novel adaptive nonmonotone technique based on trust region methods for solving unconstrained optimization. In order to accelerate the convergence of trust region methods, an adaptive trust region is generated according to the Hessian of the iterate point. Both the nonmonotone techniques and this adaptive strategies can improve the trust region methods in the sense of convergence. We prove that the proposed method is locally superlinear convergence under some standard assumptions. Numerical results show that the new method is effective and has a high speed of convergence in practice. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9941-6 Issue No:Vol. 69, No. 1 (2018)

Authors:Francisco J. Aragón Artacho; Rubén Campoy Pages: 99 - 132 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: 2018-01-01 DOI: 10.1007/s10589-017-9942-5 Issue No:Vol. 69, No. 1 (2018)

Authors:Haibin Chen; Zheng-Hai Huang; Liqun Qi Pages: 133 - 158 Abstract: Copositivity of tensors plays an important role in vacuum stability of a general scalar potential, polynomial optimization, tensor complementarity problem and tensor generalized eigenvalue complementarity problem. In this paper, we propose a new algorithm for testing copositivity of high order tensors, and then present applications of the algorithm in physics and hypergraphs. For this purpose, we first give several new conditions for copositivity of tensors based on the representative matrix of a simplex. Then a new algorithm is proposed with the help of a proper convex subcone of the copositive tensor cone, which is defined via the copositivity of Z-tensors. Furthermore, by considering a sum-of-squares program problem, we define two new subsets of the copositive tensor cone and discuss their convexity. As an application of the proposed algorithm, we prove that the coclique number of a uniform hypergraph is equivalent to an optimization problem over the completely positive tensor cone, which implies that the proposed algorithm can be applied to compute an upper bound of the coclique number of a uniform hypergraph. Then we study another application of the proposed algorithm on particle physics in testing copositivity of some potential fields. At last, various numerical examples are given to show the performance of the algorithm. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9938-1 Issue No:Vol. 69, No. 1 (2018)

Authors:Fanz Rendl; Renata Sotirov Pages: 159 - 187 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: 2018-01-01 DOI: 10.1007/s10589-017-9943-4 Issue No:Vol. 69, No. 1 (2018)

Authors:William W. Hager; James T. Hungerford; Ilya Safro Pages: 189 - 223 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: 2018-01-01 DOI: 10.1007/s10589-017-9945-2 Issue No:Vol. 69, No. 1 (2018)

Authors:Anders Forsgren; Tove Odland Pages: 225 - 241 Abstract: This paper concerns exact linesearch quasi-Newton methods for minimizing a quadratic function whose Hessian is positive definite. We show that by interpreting the method of conjugate gradients as a particular exact linesearch quasi-Newton method, necessary and sufficient conditions can be given for an exact linesearch quasi-Newton method to generate a search direction which is parallel to that of the method of conjugate gradients. We also analyze update matrices and give a complete description of the rank-one update matrices that give search direction parallel to those of the method of conjugate gradients. In particular, we characterize the family of such symmetric rank-one update matrices that preserve positive definiteness of the quasi-Newton matrix. This is in contrast to the classical symmetric-rank-one update where there is no freedom in choosing the matrix, and positive definiteness cannot be preserved. The analysis is extended to search directions that are parallel to those of the preconditioned method of conjugate gradients in a straightforward manner. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9940-7 Issue No:Vol. 69, No. 1 (2018)

Authors:Milan Hladík Pages: 243 - 266 Abstract: In the recent years, there has been an intensive research of absolute value equations \(Ax-b=B x \) . Various methods were developed, but less attention has been paid to approximating or bounding the solutions. We start filling this gap by proposing several outer approximations of the solution set. We present conditions for unsolvability and for existence of exponentially many solutions, too, and compare them with the known conditions. Eventually, we carried out numerical experiments to compare the methods with respect to computational time and quality of estimation. This helps in identifying the cases, in which the bounds are tight enough to determine the signs of the solution, and therefore also the solution itself. PubDate: 2018-01-01 DOI: 10.1007/s10589-017-9939-0 Issue No:Vol. 69, No. 1 (2018)

Authors:Andreas Rademacher; Korinna Rosin Abstract: In this article, we present a-posteriori error estimations in context of optimal control of contact problems; in particular of Signorini’s problem. Due to the contact side-condition, the solution operator of the underlying variational inequality is not differentiable, yet we want to apply Newton’s method. Therefore, the non-smooth problem is regularized by penalization and afterwards discretized by finite elements. We derive optimality systems for the regularized formulation in the continuous as well as in the discrete case. This is done explicitly for Signorini’s contact problem, which covers linear elasticity and linearized surface contact conditions. The latter creates the need for treating trace-operations carefully, especially in contrast to obstacle contact conditions, which exert in the domain. Based on the dual weighted residual method and these optimality systems, we deduce error representations for the regularization, discretization and numerical errors. Those representations are further developed into error estimators. The resulting error estimator for regularization error is defined only in the contact area. Therefore its computational cost is especially low for Signorini’s contact problem. Finally, we utilize the estimators in an adaptive refinement strategy balancing regularization and discretization errors. Numerical results substantiate the theoretical findings. We present different examples concerning Signorini’s problem in two and three dimensions. PubDate: 2018-01-31 DOI: 10.1007/s10589-018-9982-5

Authors:J. Preininger; P. T. Vuong Abstract: We revisit the gradient projection method in the framework of nonlinear optimal control problems with bang–bang solutions. We obtain the strong convergence of the iterative sequence of controls and the corresponding trajectories. Moreover, we establish a convergence rate, depending on a constant appearing in the corresponding switching function and prove that this convergence rate estimate is sharp. Some numerical illustrations are reported confirming the theoretical results. PubDate: 2018-01-29 DOI: 10.1007/s10589-018-9981-6

Authors:Eduardo Casas; Mariano Mateos; Arnd Rösch Abstract: We discretize a directionally sparse parabolic control problem governed by a linear equation by means of control approximations that are piecewise constant in time and continuous piecewise linear in space. By discretizing the objective functional with the help of appropriate numerical quadrature formulas, we are able to show that the discrete optimal solution exhibits a directional sparse pattern alike the one enjoyed by the continuous solution. Error estimates are obtained and a comparison with the cases of having piecewise approximations of the control or a semilinear state equation are discussed. Numerical experiments that illustrate the theoretical results are included. PubDate: 2018-01-27 DOI: 10.1007/s10589-018-9979-0

Authors:Leopoldo Marini; Benedetta Morini; Margherita Porcelli Abstract: We address the solution of constrained nonlinear systems by new linesearch quasi-Newton methods. These methods are based on a proper use of the projection map onto the convex constraint set and on a derivative-free and nonmonotone linesearch strategy. The convergence properties of the proposed methods are presented along with a worst-case iteration complexity bound. Several implementations of the proposed scheme are discussed and validated on bound-constrained problems including gas distribution network models. The results reported show that the new methods are very efficient and competitive with an existing affine-scaling procedure. PubDate: 2018-01-25 DOI: 10.1007/s10589-018-9980-7

Authors:Federico Cabassi; Luca Consolini; Marco Locatelli Abstract: Range reduction techniques often considerably enhance the performance of algorithmic approaches for the solution of nonconvex problems. In this paper we propose a range reduction technique for a class of optimization problems with some special structured constraints. The procedure explores and updates the values associated to the nodes of a suitably defined graph. Convergence of the procedure and some efficiency issues, in particular related to the order into which the nodes of the graph are explored. The proposed technique is applied to solve problems arising from a relevant practical application, namely velocity planning along a given trajectory. The computational experiments show the efficiency of the procedure and its ability of returning solutions within times much lower than those of nonlinear solvers and compatible with real-time applications. PubDate: 2018-01-11 DOI: 10.1007/s10589-017-9978-6

Authors:Xianchao Xiu; Lingchen Kong; Yan Li; Houduo Qi Abstract: In this paper, we focus on the \(\ell _1-\ell _p\) minimization problem with \(0<p<1\) , which is challenging due to the \(\ell _p\) norm being non-Lipschizian. In theory, we derive computable lower bounds for nonzero entries of the generalized first-order stationary points of \(\ell _1-\ell _p\) minimization, and hence of its local minimizers. In algorithms, based on three locally Lipschitz continuous \(\epsilon \) -approximation to \(\ell _p\) norm, we design several iterative reweighted \(\ell _1\) and \(\ell _2\) methods to solve those approximation problems. Furthermore, we show that any accumulation point of the sequence generated by these methods is a generalized first-order stationary point of \(\ell _1-\ell _p\) minimization. This result, in particular, applies to the iterative reweighted \(\ell _1\) methods based on the new Lipschitz continuous \(\epsilon \) -approximation introduced by Lu (Math Program 147(1–2):277–307, 2014), provided that the approximation parameter \(\epsilon \) is below a threshold value. Numerical results are also reported to demonstrate the efficiency of the proposed methods. PubDate: 2018-01-05 DOI: 10.1007/s10589-017-9977-7

Authors:Guanglin Xu; Samuel Burer Abstract: We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which in turn leads to a class of tractable, semidefinite-based approximations that are at least as strong as the affine policy. We investigate several examples from the literature demonstrating that our tractable approximations significantly improve the affine policy. In particular, our approach solves exactly in polynomial time a class of instances of increasing size for which the affine policy admits an arbitrarily large gap. PubDate: 2017-12-27 DOI: 10.1007/s10589-017-9974-x

Authors:Nikolaus von Daniels Abstract: We consider Tikhonov regularization of control-constrained optimal control problems. We present new a-priori estimates for the regularization error assuming measure and source-measure conditions. In the special case of bang–bang solutions, we introduce another assumption to obtain the same convergence rates. This new condition turns out to be useful in the derivation of error estimates for the discretized problem. The necessity of the just mentioned assumptions to obtain certain convergence rates is analyzed. Finally, a numerical example confirms the analytical findings. PubDate: 2017-12-23 DOI: 10.1007/s10589-017-9976-8

Authors:Weizhe Gu; Wei-Po Chen; Chun-Hsu Ko; Yuh-Jye Lee; Jein-Shan Chen Abstract: In this paper, we propose two new smooth support vector machines for \(\varepsilon \) -insensitive regression. According to these two smooth support vector machines, we construct two systems of smooth equations based on two novel families of smoothing functions, from which we seek the solution to \(\varepsilon \) -support vector regression ( \(\varepsilon \) -SVR). More specifically, using the proposed smoothing functions, we employ the smoothing Newton method to solve the systems of smooth equations. The algorithm is shown to be globally and quadratically convergent without any additional conditions. Numerical comparisons among different values of parameter are also reported. PubDate: 2017-12-18 DOI: 10.1007/s10589-017-9975-9

Authors:Jiawang Nie; Xinzhen Zhang Abstract: This paper discusses the computation of real \(\mathtt {Z}\) -eigenvalues and \(\mathtt {H}\) -eigenvalues of nonsymmetric tensors. A generic nonsymmetric tensor has finitely many Z-eigenvalues, while there may be infinitely many ones for special tensors. The number of \(\mathtt {H}\) -eigenvalues is finite for all tensors. We propose Lasserre type semidefinite relaxation methods for computing such eigenvalues. For every tensor that has finitely many real \(\mathtt {Z}\) -eigenvalues, we can compute all of them; each of them can be computed by solving a finite sequence of semidefinite relaxations. For every tensor, we can compute all its real \(\mathtt {H}\) -eigenvalues; each of them can be computed by solving a finite sequence of semidefinite relaxations. PubDate: 2017-12-04 DOI: 10.1007/s10589-017-9973-y