Linear Programming

Computational and Economic Limitations of Dispatch Operations in the Next-Generation Power Grid

  • Audun Botterud
  • Emil M. Constantinescu
  • Victor M. Zavala
  • Jianhui Wang
    • Categories Dynamic Programming, Linear Programming, Production and Logistics Tags , , , , ,

    We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more

    On the Equivalencey of Linear Programming Problems and Zero-Sum Games

  • Ilan Adler
    • Categories Game Theory, Linear Programming Tags , , , , ,

    In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more

    Shrink-Wrapping trajectories for Linear Programming

  • Yuriy Zinchenko
    • Categories Linear Programming

    Hyperbolic Programming (HP) –minimizing a linear functional over an affine subspace of a finite-dimensional real vector space intersected with the so-called hyperbolicity cone– is a class of convex optimization problems that contains well-known Linear Programming (LP). In particular, for any LP one can readily provide a sequence of HP relaxations. Based on these hyperbolic relaxations, … Read more

    A Pure L1-norm Principal Component Analysis

  • E.L. Boone
  • J. Paul Brooks
  • JH Dulá
    • Categories Data-Mining, Linear Programming Tags , ,

    The L1 norm has been applied in numerous variations of principal component analysis (PCA). L1-norm PCA is an attractive alternative to traditional L2-based PCA because it can impart robustness in the presence of outliers and is indicated for models where standard Gaussian assumptions about the noise may not apply. Of all the previously-proposed PCA schemes … Read more

    A sufficiently exact inexact Newton step based on reusing matrix information

  • Anders Forsgren
    • Categories Constrained Nonlinear Optimization, Linear Programming, Nonlinear Systems and Least-Squares Tags , ,

    Newton’s method is a classical method for solving a nonlinear equation $F(z)=0$. We derive inexact Newton steps that lead to an inexact Newton method, applicable near a solution. The method is based on solving for a particular $F'(z_{k’})$ during $p$ consecutive iterations $k=k’,k’+1,\dots,k’+p-1$. One such $p$-cycle requires $2^p-1$ solves with the matrix $F'(z_{k’})$. If matrix … Read more

    Matrix-Free Interior Point Method

  • Jacek Gondzio
    • Categories Linear Programming, Quadratic Programming Tags , , , , ,

    In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods … Read more

    Arc-Search Path-Following Interior-Point Algorithms for Linear Programming

  • Yaguang Yang
    • Categories Linear Programming Tags , ,

    Arc-search is developed in optimization algorithms. In this paper, simple analytic arcs are used to approximate the central path of the linear programming. The primal-dual path-following interior-point method is then used to search optimizers along the arcs for linear programming. They require fewer iterations to find the optimal solutions in all the tested problems in … Read more

    The L1-Norm Best-Fit Hyperplane Problem

  • J. Paul Brooks
  • JH Dulá
    • Categories Data-Mining, Linear Programming, Statistics Tags , , ,

    We formalize an algorithm for solving the L1-norm best-fit hyperplane problem derived using first principles and geometric insights about L1 projection and L1 regression. The procedure follows from a new proof of global optimality and relies on the solution of a small number of linear programs. The procedure is implemented for validation and testing. This … Read more

    A Nonstandard Simplex Algorithm for Linear Programming

  • Ping-Qi Pan
    • Categories Linear Programming Tags , , ,

    The simplex algorithm travels, on the underlying polyhedron, from vertex to vertex until reaching an optimal vertex. With the same simplex framework, the proposed algorithm generates a series of feasible points (which are not necessarily vertices). In particular, it is exactly an interior point algorithm if the initial point used is interior. Computational experiments show … Read more

    Solving multi-objective network flow problems with an interior point method

  • José Rui Figureira
  • Margarida Fonseca
  • Mauricio G.C. Resende
    • Categories Linear Programming, Multi-Criteria Optimization, Network Optimization Tags , , ,

    In this paper we present a primal-dual interior-point algorithm to solve a class of multi-objective network flow problems. More precisely, our algorithm is an extension of the single-objective primal-dual infeasible and inexact interior point method for multi-objective linear network flow problems. A comparison with standard interior point methods is provided and experimental results on bi-objective … Read more