polynomial-time algorithm

A polynomial-time solvable class of sparse box-constrained polynomial optimization problems

Categories (Mixed) Integer Nonlinear Programming Tags , , , , ,

We study the problem of minimizing a multivariate polynomial function over the unit hypercube. Exploiting sparsity in the interaction graph or hypergraph, we identify variables that can be restricted to binary values at optimality and eliminate the remaining continuous variables component-wise, reducing the problem to structured binary polynomial optimization. For quadratic objectives, we obtain exact … Read more

Factorized binary polynomial optimization

Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more

Sparse PCA on fixed-rank matrices

Categories Global Optimization Theory, Quadratic Programming Tags , , , ,

Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if … Read more

Subset selection in sparse matrices

Categories Global Optimization Theory, Nonlinear Systems and Least-Squares Tags , , ,

In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow … Read more

A Deterministic Rescaled Perceptron Algorithm

Categories Convex Optimization Tags , ,

The perceptron algorithm is a simple iterative procedure for finding a point in a convex cone $F$. At each iteration, the algorithm only involves a query of a separation oracle for $F$ and a simple update on a trial solution. The perceptron algorithm is guaranteed to find a feasible point in $F$ after $\Oh(1/\tau_F^2)$ iterations, … Read more

Closedness of Integer Hulls of Simple Conic Sets

Categories (Mixed) Integer Nonlinear Programming Tags , ,

Let $C$ be a full-dimensional pointed closed convex cone in $R^m$ obtained by taking the conic hull of a strictly convex set. Given $A \in Q^{m \times n_1}$, $B \in Q^{m \times n_2}$ and $b \in Q^m$, a simple conic mixed-integer set (SCMIS) is a set of the form $\{(x,y)\in Z^{n_1} \times R^{n_2}\,|\,\ Ax +By … Read more

Graver basis and proximity techniques for block-structured separable convex integer minimization problems

Categories (Mixed) Integer Nonlinear Programming Tags , , , , , ,

We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more

Information Geometry and Primal-Dual Interior-point Algorithms

Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more

An Information Geometric Approach to Polynomial-time Interior-point Algorithms: Complexity Bound via Curvature Integral

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time … Read more