Linear, Cone and Semidefinite Programming

Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Control Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more

    A primal-dual second order cone approximations algorithm for symmetric cone programming

  • Chek Beng Chua
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    This paper presents the new concept of second-order cone approximations for convex conic programming. Given any open convex cone $K$, a logarithmically homogeneous self-concordant barrier for $K$ and any positive real number $r \le 1$, we associate, with each direction $x \in K$, a second-order cone $\hat K_r(x)$ containing $K$. We show that $K$ is … Read more

    Solving Method for a Class of Bilevel Linear Programming based on Genetic Algorithms

  • Zhong-Ping Wan
  • Guang-Min Wang
  • Xian-Jia Wang
    • Categories Linear, Cone and Semidefinite Programming, Multi-Criteria Optimization, Nonlinear Optimization Tags , ,

    The paper studies and designs an genetic algorithm (GA) of the bilevel linear programming problem (BLPP) by constructing the fitness function of the upper-level programming problem based on the definition of the feasible degree. This GA avoids the use of penalty function to deal with the constraints, by changing the randomly generated initial population into … Read more

    On an Extension of Condition Number Theory to Non-Conic Convex Optimization

  • Robert M. Freund
  • Fernando Ordóñez
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: z_* := min_x {c’x | Ax-b \in C_Y, x \in C_X }, to the more general non-conic format: (GP_d): z_* := min_x {c’x | Ax-b \in C_Y, x \in P}, where P is … Read more

    Linear Programming support in WSMP

  • Anshul Gupta
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags ,

    The Watson Sparse Matrix Package (WSMP) is a high-performance robust direct solver for both symmetric and unsymmetric large sparse systems of linear equations. Currently, it works in serial, multi-threaded parallel, message-passing parallel, and a combination of message-passing and multi-threaded modes on IBM RS6000 with AIX and IA32 with Linux. The symmetric solver has features to … Read more

    An annotated bibliography of network interior point methods

  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Linear Programming, Network Optimization Tags , ,

    This paper presents an annotated bibliography on interior point methods for solving network flow problems. We consider single and multi-commodity network flow problems, as well as preconditioners used in implementations of conjugate gradient methods for solving the normal systems of equations that arise in interior network flow algorithms. Applications in electrical engineering and miscellaneous papers … Read more

    Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization

  • Michael J. Todd
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility … Read more

    Nonsmooth Matrix Valued Functions Defined by Singular Values

  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

    A class of matrix valued functions defined by singular values of nonsymmetric matrices is shown to have many properties analogous to matrix valued functions defined by eigenvalues of symmetric matrices. In particular, the (smoothed) matrix valued Fischer-Burmeister function is proved to be strongly semismooth everywhere. This result is also used to show the strong semismoothness … Read more

    Smoothed Analysis of Interior-Point Algorithms: Termination

  • Daniel Spielman
  • Shang-Hua Teng
    • Categories Linear Programming Tags , , ,

    We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar’s interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound … Read more

    Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , , , , , ,

    The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that diagonally preconditioned conjugate residual method on … Read more