## 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**

**Abstract:**

The problem of maximizing the *p*th power of a *p*-norm over a halfspace presented polytope in **R**^{d} 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 *n*^{o(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 **R**^{n}

**Coauthors: Maria Helena C. Jardim, Nelson Maculan**

**Abstract:**

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\!R^{n}. 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(n*^{2} *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**

**Abstract:**

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.