Optimization Online Digest — January 2010

Applications — OR and Management Sciences

On the complexity of maximizing the minimum Shannon capacity in wireless networks by joint channel assignment and power allocation
Mikael Fallgren

Applications — Science and Engineering

A Pure L1-norm Principal Component Analysis
J.P. Brooks, J.H. Dula, E.L. Boone

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing
Anatoli Juditsky, Fatma Kilinc Karzan, Arkadi Nemirovski

Combinatorial Optimization

Experimental analysis of heuristics for the bottleneck traveling salesman problem
John LaRusic, Abraham Punnen, Eric Aubanel

The Maximum Flow Problem with Disjunctive Constraints
Ulrich Pferschy, Joachim Schauer

An exact approach to the problem of extracting an embedded network matrix
R. M. V. Figueiredo, M. Labbé, C. C. de Souza

Convex and Nonsmooth Optimization

Convergence to the optimal value for barrier methods combined with Hessian Riemannian gradient flows and generalized proximal algorithms
Felipe Alvarez, Julio Lopez

A Feasible Directions Method for Nonsmooth Convex Optimization
Jose Herskovits, Wilhelm Freire, Mario Tanaka Fo.

Stability of error bounds for convex constraint systems in Banach spaces
Alexander Y. Kruger, Huynh Van Ngai, Michel Th\'era

A Fast Algorithm for Total Variation Image Reconstruction from Random Projections
Yunhai Xiao, Junfeng Yang

$L^p$-norms, log-barriers and Cramer transform in optimization
Jean B. Lasserre, E. Santillan Zeron

Efficiency of coordinate descent methods on huge-scale optimization problems
Yurii Nesterov

Global Optimization

A "joint+marginal" approach to parametric polynomial optimization
Jean B. Lasserre

Integer Programming

On Duality Gap in Binary Quadratic Programming
Xiaoling Sun, Chunli Liu , Duan Li, Jianjun Gao

Linear, Cone and Semidefinite Programming

Copositivity detection by difference-of-convex decomposition and omega-subdivision
Immanuel M. Bomze, Gabriele Eichfelder

Superlinear Convergence of Infeasible Predictor-Corrector Path-Following Interior Point Algorithm for SDLCP using the HKM Direction
Chee Khian Sim

A high-performance software package for semidefinite programs: SDPA 7
Makoto Yamashita, Katsuki Fujisawa, Kazuhide Nakata, Maho Nakata, Mituhiro Fukuda, Kazuhiro Kobayashi, Kazushige Goto

Nonlinear Optimization

On the convergence of a wide range of trust region methods for unconstrained optimization
MJD Powell

A Robust Implementation of a Sequential Quadratic Programming Algorithm with Successive Error Restoration
Klaus Schittkowski

Robust Optimization

Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty
Takafumi Kanamori, Akiko Takeda

An Efficient Decomposition Algorithm for Static, Stochastic, Linear and Mixed-Integer Linear Programs with Conditional-Value-at-Risk Constraints
Dharmashankar Subramanian, Pu Huang

Stochastic Programming

Fenchel Decomposition for Stochastic Mixed-Integer Programming
Lewis Ntaimo

Other Topics

Intractability of approximate multi-dimensional nonlinear optimization on independence systems
Jonathan Lee, Shmuel Onn, Robert Weismantel