Convex and Nonsmooth Optimization

Weak Stationarity: Eliminating the Gap between Necessary and Sufficient Conditions

  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , , , ,

    Starting from known necessary extremality conditions in terms of strict subdifferentials and normals the notion of weak stationarity is introduced. It is defined in terms of initial space elements. The necessary conditions become necessary and sufficient (for stationarity). CitationSchool of Information Technology and Mathematical Sciences, Centre of Information and Applied Optimization, University of Ballarat, POB … Read more

    When LP is not a good idea – using structure in polyhedral optimization problems

  • Michael Osborne
    • Categories Convex Optimization, Linear Programming, Statistics Tags , , , , , , , , ,

    It has been known for almost 50 years that the discrete l_1 approximation problem can be solved effectively by linear programming. However, improved algorithms involve a step which can be interpreted as a line search, and which is not part of the standard LP solution procedures. l_1 provides the simplest example of a class of … Read more

    Convergence rate estimates for the gradient differential inclusion

  • Osman Guler
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    Let f be a lower semi-continuous convex function in a Euclidean space, finite or infinite dimensional. The gradient differential inclusion is a generalized differential equation which requires that -x'(t) be in the subgradient of f at x. It is the continuous versions of the gradient descent method for minimizing f in case f is differentiable, … Read more

    Convergence of infeasible-interior-point methods for self-scaled conic programming

  • Bharath Kumar Rangarajan
  • Michael J. Todd
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We present results on global and polynomial-time convergence of infeasible-interior-point methods for self-scaled conic programming, which includes linear and semidefinite programming. First, we establish global convergence for an algorithm using a wide neighborhood. Next, we prove polynomial complexity for the algorithm with a slightly narrower neighborhood. Both neighborhoods are related to the wide (minus infinity) … Read more

    Lift-and-project for 0–1 programming via algebraic geometry

  • Javier F. Peña
  • Juan Vera
  • Luis F. Zuluaga
    • Categories 0-1 Programming, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Recently, tools from algebraic geometry have been successfully applied to develop solution schemes for new classes of optimization problems. A central idea in these constructions is to express a polynomial that is positive on a given domain in terms of polynomials of higher degree so that its positivity is readily revealed. This resembles the “lifting” … Read more

    A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization

  • James V. Burke
  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization Tags , ,

    Let $f$ be a continuous function on $\Rl^n$, and suppose $f$ is continuously differentiable on an open dense subset. Such functions arise in many applications, and very often minimizers are points at which $f$ is not differentiable. Of particular interest is the case where $f$ is not convex, and perhaps not even locally Lipschitz, but … Read more

    The Reduced Density Matrix Method for Electronic Structure Calculations and the Role of Three-Index Representability Conditions

  • Bastiaan J. Braams
  • Mituhiro Fukuda
  • Michael L. Overton
  • Jerome K. Percus
  • Zhengji Zhao
    • Categories Basic Sciences Applications, Convex Optimization, Semi-definite Programming Tags

    The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more

    A Pivotting Procedure for a Class of Second-Order Cone Programming

  • Masakazu Muramatsu
    • Categories Convex Optimization, Second-Order Cone Programming Tags , , ,

    We propose a pivotting procedure for a class of Second-Order Cone Programming (SOCP) having one second-order cone. We introduce a dictionary, basic variables, nonbasic variables, and other necessary notions to define a pivot for the class of SOCP. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering to or … Read more

    The Bundle Method in Combinatorial Optimization

  • Ilse Fischer
  • Franz Rendl
  • Renata Sotirov
  • Gerald Gruber
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , ,

    We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a … Read more