A new sequential optimality condition for constrained optimization and algorithmic consequences

Categories Nonlinear Optimization Tags , , ,

Necessary first-order sequential optimality conditions provide adequate theoretical tools to justify stopping criteria for nonlinear programming solvers. These conditions are satisfied by local minimizers of optimization problems independently of the fulfillment of constraint qual- i cations. A new strong sequential optimality condition is introduced in the present paper. A proof that a well established Augmented Lagrangian … Read more

Local superlinear convergence of polynomial-time interior-point methods for hyperbolic cone optimization problems

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

In this paper, we establish the local superlinear convergence property of some polynomial-time interior-point methods for an important family of conic optimization problems. The main structural property used in our analysis is the logarithmic homogeneity of self-concordant barrier function, which must have {\em negative curvature}. We propose a new path-following predictor-corrector scheme, which work only … Read more

An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more

A Factorization with Update Procedures for a KKT Matrix Arising in Direct Optimal Control

Categories Quadratic Programming, Systems governed by Differential Equations Optimization Tags , ,

Quadratic programs obtained for optimal control problems of dynamic or discrete–time processes usually involve highly block structured Hessian and constraints matrices. Efficient numerical methods for the solution of such QPs have to respect and exploit this block structure. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite … Read more

An Improved Branch-and-Bound Method for Maximum Monomial Agreement

Categories 0-1 Programming, Branch and Cut Algorithms, Data-Mining Tags , , , ,

The NP-hard Maximum Monomial Agreement (MMA) problem consists of finding a single logical conjunction that best fits a weighted dataset of “positive” and “negative” binary vectors. Computing classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we describe an exact branch and … Read more

Tightened L0 Relaxation Penalties for Classification

Categories (Mixed) Integer Linear Programming, Data-Mining, Statistics Tags , , , , , ,

In optimization-based classification model selection, for example when using linear programming formulations, a standard approach is to penalize the L1 norm of some linear functional in order to select sparse models. Instead, we propose a novel integer linear program for sparse classifier selection, generalizing the minimum disagreement hyperplane problem whose complexity has been investigated in … Read more

Most tensor problems are NP-hard

Categories Applications - Science and Engineering, Global Optimization Theory, Graphs and Matroids Tags , , , , , , , , , ,

We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list here includes: determining the feasibility of a system of bilinear equations, deciding whether a tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining a best … Read more

A Time Bucket Formulation for the TSP with Time Windows

Categories Integer Programming

The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into sub-windows, which we call “buckets”. We … Read more

A Facial Reduction Algorithm for Finding Sparse SOS Representations

Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. CitationTechnical Report CS-09-02, Department of … Read more

A simple branching scheme for Vertex Coloring Problems

Categories Graphs and Matroids Tags , ,

We present a branching scheme for some Vertex Coloring Problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as the graph multicoloring, where each vertex requires a multiplicity of colors, … Read more