Second-Order Variational Analysis in Conic Programming with Applications to Optimality and Stability

  • Boris S. Mordukhovich
  • Jiri V. Outrata
  • Héctor Ramírez
    • Categories Convex and Nonsmooth Optimization Tags , , , , , ,

    This paper is devoted to the study of a broad class of problems in conic programming modeled via parameter-dependent generalized equations. In this framework we develop a second-order generalized di erential approach of variational analysis to calculate appropriate derivatives and coderivatives of the corresponding solution maps. These developments allow us to resolve some important issues related … Read more

    A Framework of Constraint Preserving Update Schemes for Optimization on Stiefel Manifold

  • Yu-Hong Dai
  • Bo Jiang
    • Categories Applications - Science and Engineering, Nonlinear Optimization Tags , , , , , , , , , , ,

    This paper considers optimization problems on the Stiefel manifold $X^TX=I_p$, where $X\in \mathbb{R}^{n \times p}$ is the variable and $I_p$ is the $p$-by-$p$ identity matrix. A framework of constraint preserving update schemes is proposed by decomposing each feasible point into the range space of $X$ and the null space of $X^T$. While this general framework … Read more

    Risk-Averse Control of Undiscounted Transient Markov Models

  • Özlem Cavus
  • Andrzej Ruszczyński
    • Categories Dynamic Programming, Stochastic Programming

    We use Markov risk measures to formulate a risk-averse version of the undiscounted total cost problem for a transient controlled Markov process. We derive risk-averse dynamic programming equations and we show that a randomized policy may be strictly better than deterministic policies, when risk measures are employed. We illustrate the results on an optimal stopping … Read more

    A branch-and-bound algorithm for biobjective mixed-integer programs

  • Pietro Belotti
  • Banu Soylu
  • Margaret Wiecek
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more

    Partial Second-Order Subdifferentials in Variational Analysis and Optimization

  • Boris S. Mordukhovich
  • Nguyen Mau Nam
  • Nguyen Thi Yen Nhi
    • Categories Nonsmooth Optimization Tags , , , , , ,

    This paper presents a systematic study of partial second-order subdifferentials for extended-real-valued functions, which have already been applied to important issues of variational analysis and constrained optimization in finite-dimensional spaces. The main results concern developing extended calculus rules for these second-order constructions in both finite-dimensional and infinite-dimensional frameworks. We also provide new applications of partial … Read more

    Implementing cutting plane management and selection techniques

  • U. H. Suhl
  • Franz Wesselmann
    • Categories Cutting Plane Approaches Tags ,

    One main objective of research in the area of mixed-integer programming is developing cutting plane techniques to improve the solvability of mixed-integer programs (MIPs). Various cutting plane separators are typically available in MIP solvers. The large number of cutting planes generated by these separators, however, can pose a computational problem. Therefore, a sophisticated cut management … Read more

    Trajectories of Descent

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
  • Alexander D. Ioffe
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    Steepest descent drives both theory and practice of nonsmooth optimization. We study slight relaxations of two influential notions of steepest descent curves — curves of maximal slope and solutions to evolution equations. In particular, we provide a simple proof showing that lower-semicontinuous functions that are locally Lipschitz continuous on their domains — functions playing a … Read more

    Common Mathematical Foundations of Expected Utility and Dual Utility Theories

  • Darinka Dentcheva
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , , , ,

    We show that the main results of the expected utility and dual utility theories can be derived in a unified way from two fundamental mathematical ideas: the separation principle of convex analysis, and integral representations of continuous linear functionals from functional analysis. Our analysis reveals the dual character of utility functions. We also derive new … Read more

    On metric regularity for weakly almost piecewise smooth functions and some applications in nonlinear semidefinite programming

  • Peter Fusek
    • Categories Semi-definite Programming Tags , , ,

    The one-to-one relation between the points fulfilling the KKT conditions of an optimization problem and the zeros of the corresponding Kojima function is well-known. In the present paper we study the interplay between metric regularity and strong regularity of this a priori nonsmooth function in the context of semidefinite programming. Having in mind the topological … Read more

    A Continuous Characterization of the Maximum-Edge Biclique Problem

  • Nicolas Gillis
  • François Glineur
    • Categories Data-Mining, Meta Heuristics Tags , , ,

    The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a … Read more