Arkadi Nemirovski

On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more

    Extending Scope of Robust Optimization: Comprehensive Robust Counterparts of Uncertain Problems

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Robust Optimization Tags , ,

    In this paper, we propose a new methodology for handling optimization problems with uncertain data. With the usual Robust Optimization paradigm, one looks for the decisions ensuring a required performance for all realizations of the data from a given bounded uncertainty set, whereas with the proposed approach, we require also a controlled deterioration in performance … Read more

    Convex Approximations of Chance Constrained Programs

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given (close to one) probability, a system of randomly perturbed convex constraints. Our goal is to build a computationally tractable approximation of this (typically intractable) problem, i.e., an explicitly given convex optimization program with the feasible … Read more

    Sums of Random Symmetric Matrices and Applications

  • Arkadi Nemirovski
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    Let B_i be deterministic symmetric m\times m matrices, and \xi_i be independent random scalars with zero mean and “of order of one” (e.g., \xi_i are Gaussian with zero mean and unit standard deviation). We are interested in conditions for the “typical norm” of the random matrix S_N = \xi_1B_1+…+\xi_NB_N to be of order of 1. … Read more

    Scenario Approximations of Chance Constraints

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Optimization of Simulated Systems, Stochastic Programming Tags , , , ,

    We consider an optimization problem of minimization of a linear function subject to chance constraints. In the multidimensional case this problem is, generically, a problem of minimizing under a nonconvex and difficult to compute constraints and as such is computationally intractable. We investigate the potential of conceptually simple scenario approximation of the chance constraints. The … Read more

    Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

  • Zhaosong Lu
  • Renato D.C. Monteiro
  • Arkadi Nemirovski
    • Categories Semi-definite Programming Tags , ,

    In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more

    On complexity of stochastic programming problems

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , , ,

    The main focus of this paper is discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multi-stage … Read more

    A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

  • Renato D.C. Monteiro
  • Arkadi Nemirovski
  • Jerome W. O'Neal
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , ,

    The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more

    ”Cone-Free” Primal-Dual Path-Following and Potential Reduction Polynomial Time Interior-Point Methods

  • Arkadi Nemirovski
  • Levent Tunçel
    • Categories Convex Optimization Tags , , ,

    We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the … Read more