Contributed Session Fri.1.H 0112

Friday, 10:30 - 12:00 h, Room: H 0112

Cluster 16: Nonlinear programming [...]

Complexity issues in optimization


Chair: Jianming Shi



Friday, 10:30 - 10:55 h, Room: H 0112, Talk 1

Stefan K├Ânig
Norm maximization is W[1]-hard

Coauthors: Christian Knauer, Daniel Werner


The problem of maximizing the pth power of a p-norm over a halfspace presented polytope in Rd is a convex maximization problem which plays a fundamental role in computational convexity. It has been known since 1986 that this problem is NP-hard for all values p ∈ N, if the dimension d of the ambient space is considered as part of the input.
In recent years, the theory of parametrized complexity has become a helpful tool in analysing how the hardness of problems depends on specific parameters of the input.
In this talk, we will briefly discuss the prerequisites from parametrized complexity and then investigate the complexity of norm maximization with the natural choice of d as parameter.
More precisely, we show that, for p=1, the problem is fixed parameter tractable (i.e., it can be considered as computationally feasible if only the dimension d is small) but that, for all p ∈ N \ {1}, norm maximization is W[1]-hard. The presented reduction also yields that, under standard complexity theoretic assumptions, there is no algorithm with running time no(d) that answers the problem correctly.



Friday, 11:00 - 11:25 h, Room: H 0112, Talk 2

Claudio Prata Santiago
An efficient algorithm for the projection of a point on the intersection of two hyperplanes and a box in Rn

Coauthors: Maria Helena C. Jardim, Nelson Maculan


In this work, we present an efficient strongly polynomial algorithm for the projection of a point on the intersection of two hyperplanes and a box in I\!Rn. Interior point methods are the most efficient algorithm in the literature to solve this problem. While efficient in practice, the complexity of interior point methods is bounded by a polynomial in the dimension of the problem and in the accuracy of the solution. In addition, their efficiency is highly dependent on a series of parameters depending on the specific method chosen (especially for nonlinear problems), such as step size, barrier parameter, accuracy, among others. We propose a new method based on the KKT optimality conditions. In this method, we write the problem as a function of the lagrangian multipliers of the hyperplanes and seek to find the pair of multipliers that corresponds to
the optimal solution. We prove that the algorithm has complexity O(n2 log n).



Friday, 11:30 - 11:55 h, Room: H 0112, Talk 3

Jianming Shi
A computational geometric approach for solving linear programming: Toward strong polynomial

Coauthor: Shi Jianming


The complexity of linear programming (LP) is still open because we don't know whether there exists a strongly polynomial algorithm for solving a Linear program. This talk is an effort toward this long-standing open problem.
Unlike previous approaches, the algorithm proposed in talk does not require the information of the vertices of the feasible region. Under the assumption that an interior point in the feasible region is available, we reformulate a LP as a computational geometric problem with a convex hull of the data points (vectors).
We will report the experiments results comparing the new approach and the existing methods, like the interior point method, Simplex method.


  In particular, Payday Loans Texas can cater to the needs of its residents. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.