An effective linear approximation method for separable programming problems

Among the numerous applications of piecewise linearization methods include data fitting, network analysis, logistics, and statistics. In the early 1950s, a concave function was found to be able to be linearized by introducing 0-1 variables. Most textbooks in Operations Research offer such methods for expressing linear approximations. Various methods of linearization have also been developed in recent literature. Nevertheless, the transformed linear scheme has a severe shortcoming: most standard procedures for linearizing typically involve a large increase in the number of binary variables. Consequently, the gains to be derived from dealing with linear functions are quite likely to be nullified by the increase in the size of the problem.Conventional methods for linearizing a concave function with m break points require m-1 binary variables. However, when m becomes large, the computation will be very time-consuming and may cause a heavy computational burden.This study proposes an effective approach in which only ⌈log₂(m-1)⌉ binary variables are used. The proposed method has the following features: (i) it offers more convenient and efficient means of expressing a piecewise linear function; (ii) fewer 0-1 variables are used; (iii) the computational results show that the proposed method is much more efficient and faster than the conventional one, especially when the number of break points becomes large.     

Generalized Newton method for linear optimization problems with inequality constraints

A dual problem of linear programming is reduced to the unconstrained maximization of a concave piecewise quadratic function for sufficiently large values of a certain parameter. An estimate is given for the threshold value of the parameter starting from which the projection of a given point to the set of solutions of the dual linear programming problem in dual and auxiliary variables is easily found by means of a single solution of the unconstrained maximization problem. The unconstrained maximization is carried out by the generalized Newton method, which is globally convergent in an a finite number of steps. The results of numerical experiments are presented for randomly generated large-scale linear programming problems.     

Concave-Convex Adaptive Rejection Sampling

We describe a method for generating independent samples from univariate density functions using adaptive rejection sampling without the log-concavity requirement. The method makes use of the fact that many functions can be expressed as a sum of concave and convex functions. Using a concave-convex decomposition, we bound the log-density by separately bounding the concave and convex parts using piecewise linear functions. The upper bound can then be used as the proposal distribution in rejection sampling. We demonstrate the applicability of the concave-convex approach on a number of standard distributions and describe an application to the efficient construction of sequential Monte Carlo proposal distributions for inference over genealogical trees. Computer code for the proposed algorithms is available online.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

Parallel implementation of Newton’s method for solving large-scale linear programs

Parallel versions of a method based on reducing a linear program (LP) to an unconstrained maximization of a concave differentiable piecewise quadratic function are proposed. The maximization problem is solved using the generalized Newton method. The parallel method is implemented in C using the MPI library for interprocessor data exchange. Computations were performed on the parallel cluster MVC-6000IM. Large-scale LPs with several millions of variables and several hundreds of thousands of constraints were solved. Results of uniprocessor and multiprocessor computations are presented.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Solving ℓ1 Regularization Problems With Piecewise Linear Losses

This article is concerned with the computational aspect of ?₁ regularization problems with a certain class of piecewise linear loss functions. The problem of computing the ?₁ regularization path for a piecewise linear loss can be formalized as a parametric linear programming problem. We propose an efficient implementation method of the parametric simplex algorithm for such a problem. We also conduct a simulation study to investigate the behavior of the number of “breakpoints” of the regularization path when both the number of observations and the number of explanatory variables vary. Our method is also applicable to the computation of the regularization path for a piecewise linear loss and the blockwise ?_∞ penalty. This article has supplementary material online.     

A primal-dual homotopy algorithm for $$\ell _{1}$$-minimization with $$\ell _{\infty }$$ℓ∞-constraints

In this paper we propose a primal-dual homotopy method for \(\ell _1\)-minimization problems with infinity norm constraints in the context of sparse reconstruction. The natural homotopy parameter is the value of the bound for the constraints and we show that there exists a piecewise linear solution path with finitely many break points for the primal problem and a respective piecewise constant path for the dual problem. We show that by solving a small linear program, one can jump to the next primal break point and then, solving another small linear program, a new optimal dual solution is calculated which enables the next such jump in the subsequent iteration. Using a theorem of the alternative, we show that the method never gets stuck and indeed calculates the whole path in a finite number of steps. Numerical experiments demonstrate the effectiveness of our algorithm. In many cases, our method significantly outperforms commercial LP solvers; this is possible since our approach employs a sequence of considerably simpler auxiliary linear programs that can be solved efficiently with specialized active-set strategies.     

Global Minimization via Piecewise-Linear Underestimation

Given a function on Rⁿ with many multiple local minima we approximate it from below, via concave minimization, with a piecewise-linear convex function by using sample points from the given function. The piecewise-linear function is then minimized using a single linear program to obtain an approximation to the global minimum of the original function. Successive shrinking of the original search region to which this procedure is applied leads to fairly accurate estimates, within 0.57%, of the global minima of synthetic nonconvex piecewise-quadratic functions for which the global minima are known exactly.     

Piecewise convex formulations of binary and permutation problems

It is well known that the problem of maximization of any difference of convex functions can be turned into a convex maximization problem; here, the aim is a piecewise convex maximization problem instead. Although this may seem harder, sometimes the dimension may be reduced by 1, and the local search may be improved by using extreme points of the closure of the convex hull of better points. We show that it is always the case for both binary and permutation problems and give, as such instances, piecewise convex formulations for the maximum clique problem and the quadratic assignment problem.     

An algorithm for the estimation of a regression function by continuous piecewise linear functions

The problem of the estimation of a regression function by continuous piecewise linear functions is formulated as a nonconvex, nonsmooth optimization problem. Estimates are defined by minimization of the empirical L ₂ risk over a class of functions, which are defined as maxima of minima of linear functions. An algorithm for finding continuous piecewise linear functions is presented. We observe that the objective function in the optimization problem is semismooth, quasidifferentiable and piecewise partially separable. The use of these properties allow us to design an efficient algorithm for approximation of subgradients of the objective function and to apply the discrete gradient method for its minimization. We present computational results with some simulated data and compare the new estimator with a number of existing ones.     

Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

Discontinuous piecewise linear optimization

A theoretical framework and a practical algorithm are presented to solve discontinuous piecewise linear optimization problems dealing with functions for which theridges are known. A penalty approach allows one to consider such problems subject to a wide range of constraints involving piecewise linear functions. Although the theory is expounded in detail in the special case of discontinuous piecewiselinear functions, it is straightforwardly extendable, using standard nonlinear programming techniques, tononlinear (discontinuous piecewise differentiable) functions.The descent algorithm which is elaborated uses active-set and projected gradient approaches. It is a generalization of the ideas used by Conn to deal with nonsmoothness in thel ₁ exact penalty function, and it is based on the notion ofdecomposition of a function into a smooth and a nonsmooth part. The constrained case is reduced to the unconstrained minimization of a (piecewise linear)l ₁ exact penalty function. We also discuss how the algorithm is modified when it encounters degenerate points. Preliminary numerical results are presented: the algorithm is applied to discontinuous optimization problems from models in industrial engineering. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the Natural Sciences and Engineering Council of Canada and the Centre de Recherches Mathématiques, Université de Montréal.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No. F49620-91-C-0079. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.     

On a quadrature algorithm for the piecewise linear wavelet collocation applied to boundary integral equations

In this paper, we consider a piecewise linear collocation method for the solution of a pseudo‐differential equation of order r=0, ?1 over a closed and smooth boundary manifold. The trial space is the space of all continuous and piecewise linear functions defined over a uniform triangular grid and the collocation points are the grid points. For the wavelet basis in the trial space we choose the three‐point hierarchical basis together with a slight modification near the boundary points of the global patches of parametrization. We choose linear combinations of Dirac delta functionals as wavelet basis in the space of test functionals. For the corresponding wavelet algorithm, we show that the parametrization can be approximated by low‐order piecewise polynomial interpolation and that the integrals in the stiffness matrix can be computed by quadrature, where the quadrature rules are composite rules of simple low‐order quadratures. The whole algorithm for the assembling of the matrix requires no more than O(N [logN]³) arithmetic operations, and the error of the collocation approximation, including the compression, the approximative parametrization, and the quadratures, is less than O(N^?(2?r)/2). Note that, in contrast to well‐known algorithms by Petersdorff, Schwab, and Schneider, only a finite degree of smoothness is required. In contrast to an algorithm of Ehrich and Rathsfeld, no multiplicative splitting of the kernel function is required. Beside the usual mapping properties of the integral operator in low order Sobolev spaces, estimates of Calderón–Zygmund type are the only assumptions on the kernel function. Copyright © 2003 John Wiley & Sons, Ltd.     

A new smoothing Newton-type method for second-order cone programming problems

A new smoothing function of the well-known Fischer–Burmeister function is given. Based on this new function, a smoothing Newton-type method is proposed for solving second-order cone programming. At each iteration, the proposed algorithm solves only one system of linear equations and performs only one line search. This algorithm can start from an arbitrary point and it is Q-quadratically convergent under a mild assumption. Numerical results demonstrate the effectiveness of the algorithm.     

Maximizing concave piecewise affine functions on the unitary group

We show that a convex relaxation, introduced by Sridharan, McEneaney, Gu and James to approximate the value function of an optimal control problem arising from quantum gate synthesis, is exact. This relaxation applies to the maximization of a class of concave piecewise affine functions over the unitary group.     

Piecewise-linear programming: The compact (CPLP) algorithm

A compact algorithm is presented for solving the convex piecewise-linear-programming problem, formulated by means of a separable convex piecewise-linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteritic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions arem×(n+1), wherem is the number of constraints andn the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.     

The Cayley-Bacharach theorem for continuous piecewise algebraic curves over cross-cut triangulations

A piecewise algebraic curve is a curve determined by the zero set of a bivariate spline function. In this paper, we propose the Cayley-Bacharach theorem for continuous piecewise algebraic curves over cross-cut triangulations. We show that, if two continuous piecewise algebraic curves of degrees m and n respectively meet at mnT distinct points over a cross-cut triangulation, where T denotes the number of cells of the triangulation, then any continuous piecewise algebraic curve of degree m + n − 2 containing all but one point of them also contains the last point.     

Theory of differential equations in discontinuous piecewise‐defined functions

A truly general and systematic theory of finite element methods (FEM) should be formulated using, as trial and test functions, piecewise‐defined functions that can be fully discontinuous across the internal boundary, which separates the elements from each other. Some of the most relevant work addressing such formulations is contained in the literature on discontinuous Galerkin (dG) methods and on Trefftz methods. However, the formulations of partial differential equations in discontinuous functions used in both of those fields are indirect approaches, which are based on the use of Lagrange multipliers and mixed methods, in the case of dG methods, and the frame, in the case of Trefftz method. This article addresses this problem from a different point of view and proposes a theory, formulated in discontinuous piecewise‐defined functions, which is direct and systematic, and furthermore it avoids the use of Lagrange multipliers or a frame, while mixed methods are incorporated as particular cases of more general results implied by the theory. When boundary value problems are formulated in discontinuous functions, well‐posed problems are boundary value problems with prescribed jumps (BVPJ), in which the boundary conditions are complemented by suitable jump conditions to be satisfied across the internal boundary of the domain‐partition. One result that is presented in this article shows that for elliptic equations of order 2m, with m ≥ 1, the problem of establishing conditions for existence of solution for the BVPJ reduces to that of the “standard boundary value problem,” without jumps, which has been extensively studied. Actually, this result is an illustration of a more general one that shows that the same happens for any differential equation, or system of such equations that is linear, independently of its type and with possibly discontinuous coefficients. This generality is achieved by means of an algebraic framework previously developed by the author and his collaborators. A fundamental ingredient of this algebraic formulation is a kind of Green's formulas that simplify many problems (some times referred to as Green‐Herrera formulas). An important practical implication of our approach is worth mentioning: “avoiding the introduction of the Lagrange multipliers, or the ‘frame’ in the case of Trefftz‐methods, significantly reduces the number of degrees of freedom to be dealt with.” © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

A new geometric condition for Fenchel's duality in infinite dimensional spaces

In 1951, Fenchel discovered a special duality, which relates the minimization of a sum of two convex functions with the maximization of the sum of concave functions, using conjugates. Fenchel's duality is central to the study of constrained optimization. It requires an existence of an interior point of a convex set which often has empty interior in optimization applications. The well known relaxations of this requirement in the literature are again weaker forms of the interior point condition. Avoiding an interior point condition in duality has so far been a difficult problem. However, a non-interior point type condition is essential for the application of Fenchel's duality to optimization. In this paper we solve this problem by presenting a simple geometric condition in terms of the sum of the epigraphs of conjugate functions. We also establish a necessary and sufficient condition for the ε-subdifferential sum formula in terms of the sum of the epigraphs of conjugate functions. Our results offer further insight into Fenchel's duality. Dedicated to Terry Rockafellar on his 70th birthday