Intractability of approximate multi-dimensional nonlinear optimization on independence systems

We consider optimization of nonlinear objective functions that balance $d$ linear criteria over $n$-element independence systems presented by linear-optimization oracles. For $d=1$, we have previously shown that an $r$-best approximate solution can be found in polynomial time. Here, using an extended Erdos-Ko-Rado theorem of Frankl, we show that for $d=2$, finding a $\rho n$-best solution … Read more

An exact approach to the problem of extracting an embedded network matrix

We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more

A high-performance software package for semidefinite programs: SDPA 7

The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more

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

We present an efficient decomposition algorithm for single-stage, stochastic linear programs, where conditional value at risk (CVaR) appears as a risk measure in multiple constraints. It starts with a well-known nonlinear, convex reformulation of conditional value at risk constraints, and establishes the connection to a combinatorially large polyhedral representation of the convex feasible set induced … Read more

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

We consider the synthesis problem of Compressed Sensing: given $s$ and an $M\times n$ matrix $A$, extract from $A$ an $m\times n$ submatrix $A_m$, with $m$ as small as possible, which is $s$-good, that is, every signal $x$ with at most $s$ nonzero entries can be recovered from observation $A_m x$ by $\ell_1$ minimization: $x … Read more

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

Interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In … Read more

Efficiency of coordinate descent methods on huge-scale optimization problems

In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. … Read more

The Maximum Flow Problem with Disjunctive Constraints

We study the maximum flow problem subject to binary disjunctive constraints in a directed graph: A negative disjunctive constraint states that a certain pair of arcs in a digraph cannot be simultaneously used for sending flow in a feasible solution. In contrast to this, positive disjunctive constraints force that for certain pairs of arcs at … Read more

Worst-Case Violation of Sampled Convex Programs for Optimization with Uncertainty

Uncertain programs have been developed to deal with optimization problems including inexact data, i.e., uncertainty. A deterministic approach called robust optimization is commonly applied to solve these problems. Recently, Calafiore and Campi have proposed a randomized approach based on sampling of constraints, where the number of samples is determined so that only small portion of … Read more

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

We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequencydivision multiple access (OFDMA). For a snap-shot in time, a joint channel assignment and power allocation optimization problem is presented, both in downlink and in uplink, where the objective is to maximize the minimum total … Read more