Applications – Science and Engineering

Preconditioning and Globalizing Conjugate Gradients in Dual Space for Quadratically Penalized Nonlinear-Least Squares Problems

  • Serge Gratton
  • Philippe L. Toint
  • Selime Gürol
    • Categories Nonlinear Systems and Least-Squares, Optimization of Simulated Systems, Optimization of Systems modeled by PDEs Tags , , , , ,

    When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each … Read more

    Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

  • Antoine Deza
  • Tamás Terlaky
  • Anthony Vannelli
  • Chris Dickson
  • Hu Zhang
    • Categories Integer Programming, VLSI layout Tags , ,

    Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are … Read more

    The Convex Geometry of Linear Inverse Problems

  • Venkat Chandrasekaran
  • Benjamin Recht
  • Pablo A. Parrilo
  • Alan S. Willsky
    • Categories Applications - Science and Engineering, Convex Optimization, Semi-definite Programming

    In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees … Read more

    On Computation of Performance Bounds of Optimal Index Assignment

  • Hans D Mittelmann
  • Xiaolin Wu
  • J. Wang
  • X. Wang
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more

    Numerical estimation of the relative entropy of entanglement

  • Shmuel Friedland
  • Gilad Gour
  • Yuriy Zinchenko
    • Categories Applications - Science and Engineering, Basic Sciences Applications Tags , , ,

    We propose a practical algorithm for the calculation of the relative entropy of entanglement(REE), defined as the minimum relative entropy between a state and the set of states with positive partial transpose. Our algorithm is based on a practical semi-definite cutting plane approach. In low dimensions the implementation of the algorithm in MATLAB provides an … Read more

    A quasi-Newton projection method for nonnegatively constrained image deblurring

  • Germana Landi
  • Elena Loli Piccolomini
    • Categories Basic Sciences Applications, Bound-constrained Optimization Tags , , , ,

    In this paper we present a quasi-Newton projection method for image deblurring. The mathematical problem is a constrained minimization problem, where the objective function is a regularization function and the constraint is the positivity of the solution. The regularization function is a sum of the Kullback-Leibler divergence, used to minimize the error in the presence … Read more

    Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation

  • Pedro J. de Rezende
  • Cid C. de Souza
  • Guilherme Kunigami
  • Tallys H. Yunes
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications, Branch and Cut Algorithms Tags , , ,

    Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel … Read more

    Finding approximately rank-one submatrices with the nuclear norm and l1 norm

  • Xuan Vinh Doan
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining

    We propose a convex optimization formulation with the nuclear norm and $\ell_1$-norm to find a large approximately rank-one submatrix of a given nonnegative matrix. We develop optimality conditions for the formulation and characterize the properties of the optimal solutions. We establish conditions under which the optimal solution of the convex formulation has a specific sparse … Read more

    A modified DIRECT algorithm for a problem in astrophysics

  • Daniela di Serafino
  • Giampaolo Liuzzi
  • Veronica Piccialli
  • Gerardo Toraldo
  • Filippo Riccio
    • Categories Applications - Science and Engineering, Global Optimization Applications Tags , ,

    We present a modification of the DIRECT algorithm, called DIRECT-G, to solve a box-constrained global optimization problem arising in the detection of gravitational waves emitted by coalescing binary systems of compact objects. This is a hard problem since the objective function is highly nonlinear and expensive to evaluate, has a huge number of local extrema … Read more

    Accuracy guarantees for ℓ1-recovery

  • Anatoli Juditsky
  • Fatma Kılınç-Karzan
  • Arkadi Nemirovski
    • Categories Statistics Tags , , ,

    We discuss two new methods of recovery of sparse signals from noisy observation based on ℓ1- minimization. They are closely related to the well-known techniques such as Lasso and Dantzig Selector. However, these estimators come with efficiently verifiable guaranties of performance. By optimizing these bounds with respect to the method parameters we are able to … Read more