Month: May 2010

NCSOSTOOLS: A COMPUTER ALGEBRA SYSTEM FOR SYMBOLIC AND NUMERICAL COMPUTATION WITH NONCOMMUTATIVE POLYNOMIALS

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Optimization Software and Modeling Systems, Semi-definite Programming Tags , , ,

    Abstract. NCSOStools is a Matlab toolbox for – symbolic computation with polynomials in noncommuting variables; – constructing and solving sum of hermitian squares (with commutators) programs for polynomials in noncommuting variables. It can be used in combination with semidefi nite programming software, such as SeDuMi, SDPA or SDPT3 to solve these constructed programs. This paper provides … Read more

    On Maximal S-free Convex Sets

  • Santanu S. Dey
  • Diego Moran
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , ,

    Let S be a subset of integer points that satisfy the property that $conv(S) \cap Z^n = S$. Then a convex set K is called an S-free convex set if $int(K) \cap S = \emptyset$. A maximal S-free convex set is an S-free convex set that is not properly contained in any S-free convex set. … 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

    Central Swaths (A Generalization of the Central Path)

  • James Renegar
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We develop a natural generalization to the notion of the central path — a notion that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the “derivative cones” of a “hyperbolicity cone,” the derivatives being direct and mathematically-appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative … Read more

    A Non-monotonic Method for Large-scale Nonnegative Least Squares

  • Inderjit S. Dhillon
  • Dongmin Kim
  • Suvrit Sra
    • Categories Basic Sciences Applications, Bound-constrained Optimization, Nonlinear Systems and Least-Squares Tags , , , , , ,

    We present a new algorithm for nonnegative least-squares (NNLS). Our algorithm extends the unconstrained quadratic optimization algorithm of Barzilai and Borwein (BB) (J. Barzilai and J. M. Borwein; Two-Point Step Size Gradient Methods. IMA J. Numerical Analysis; 1988.) to handle nonnegativity constraints. Our extension diff ers in several basic aspects from other constrained BB variants. The … Read more

    Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization

  • Bingsheng He
  • Peng Zheng
  • Wang XiangFeng
    • Categories Complementarity and Variational Inequalities, Convex Optimization Tags , , ,

    Alternating direction method (ADM) has been well studied in the context of linearly constrained convex programming problems. Recently, because of its significant efficiency and easy implementation in novel applications, ADM is extended to the case where the number of separable parts is a finite number. The algorithmic framework of the extended method consists of two … Read more

    A Unified Approach for Minimizing Composite Norms

  • Necdet Serhat Aybat
  • Garud Iyengar
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , , , , , ,

    We propose a first-order augmented Lagrangian algorithm (FALC) to solve the composite norm minimization problem min |sigma(F(X)-G)|_alpha + |C(X)- d|_beta subject to A(X)-b in Q; where sigma(X) denotes the vector of singular values of X, the matrix norm |sigma(X)|_alpha denotes either the Frobenius, the nuclear, or the L2-operator norm of X, the vector norm |.|_beta … Read more

    An Efficient Method to Estimate the Suboptimality of Affine Controllers

  • Paul J. Goulart
  • Daniel Kuhn
  • Michael J. Hadjiyiannis
    • Categories Control Applications, Robust Optimization Tags ,

    We consider robust output feedback control of time-varying, linear discrete-time systems operating over a finite horizon. For such systems, we consider the problem of designing robust causal controllers that minimize the expected value of a convex quadratic cost function, subject to mixed linear state and input constraints. Determination of an optimal control policy for such … Read more

    Semidefinite code bounds based on quadruple distances

  • Dion C. Gijswijt
  • Hans D Mittelmann
  • Alexander Schrijver
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    Let A(n, d) be the maximum number of 0, 1 words of length n, any two having Hamming distance at least d. We prove A(20, 8) = 256, which implies that the quadruply shortened Golay code is optimal. Moreover, we show A(18, 6) ≤ 673, A(19, 6) ≤ 1237, A(20, 6) ≤ 2279, A(23, 6) … Read more