An Iterative Method for Finding the Least Solution to the Tensor Complementarity Problem

In this paper, we are concerned with finding the least solution to the tensor complementarity problem. When the involved tensor is strongly monotone, we present a way to estimate the nonzero elements of the solution in a successive manner. The procedure for identifying the nonzero elements of the solution gives rise to an iterative method of solving the tensor complementarity problem. In each iteration, we obtain an iterate by solving a lower-dimensional tensor equation. After finitely many iterations, the method terminates with a solution to the problem. Moreover, the sequence generated by the method is monotonically convergent to the least solution to the problem. We then extend this idea for general case and propose a sequential mathematical programming method for finding the least solution to the problem. Since the least solution to the tensor complementarity problem is the sparsest solution to the problem, the method can be regarded as an extension of a recent result by Luo et al. (Optim Lett 11:471–482, 2017). Our limited numerical results show that the method can be used to solve the tensor complementarity problem efficiently.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

On merit functions for <Emphasis Type="Italic">p</Emphasis>-order cone complementarity problem

Merit function approach is a popular method to deal with complementarity problems, in which the complementarity problem is recast as an unconstrained minimization via merit function or complementarity function. In this paper, for the complementarity problem associated with p-order cone, which is a type of nonsymmetric cone complementarity problem, we show the readers how to construct merit functions for solving p-order cone complementarity problem. In addition, we study the conditions under which the level sets of the corresponding merit functions are bounded, and we also assert that these merit functions provide an error bound for the p-order cone complementarity problem. These results build up a theoretical basis for the merit method for solving p-order cone complementarity problem.     

Sparsest cut in planar graphs,maximum concurrent flows and their connections with the max-cut problem

We study the sparsest cut problem when the “capacity-demand” graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no \(K_5\) minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the “capacity-demand” graph has no \(K_6\) minor. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems.     

On linear and semidefinite programming relaxations for hypergraph matching

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following:

We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Füredi, Kahn and Seymour, showing that the integrality gap is exactly ${k-1+\frac{1}{k}}$ for k-uniform hypergraphs, and is exactly k ? 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems.

We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k ? 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most ${\frac{k+1}{2}}$ for k-uniform hypergraphs. The construction uses a result in extremal combinatorics.

We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovász ${\vartheta}$ -function provides an SDP relaxation with integrality gap at most ${\frac{k+1}{2}}$ . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming relaxations.

     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Complementarity problems over a hypermatrix (tensor) set

A hypermatrix (tensor) complementarity problem \(\textit{HMCP}(q,\mathcal {A})\) is to find a vector \(x\in \mathbb {R}^n\) such that \(x\ge 0,~\mathcal {A}x+q\ge 0,~x^T(\mathcal {A}x+q)=0,\) for every \(q\in \mathbb {R}^n\), where \(\mathcal {A}\) is an mth order hypermatrix (tensor) (Song and Qi in J Optim Theory Appl 165(3): 854–873, 2015). Uniqueness, feasibility, and strict feasibility of the solution of a complementarity problem induced by a (compact) set of hypermatrices are characterized in terms of the hypermatrices involved.     

New error bounds for the linear complementarity problem of <Emphasis Type="Italic">QN</Emphasis>-matrices

An error bound for the linear complementarity problem (LCP) when the involved matrices are QN-matrices with positive diagonal entries is presented by Dai et al. (Error bounds for the linear complementarity problem of QN-matrices. Calcolo, 53:647-657, 2016), and there are some limitations to this bound because it involves a parameter. In this paper, for LCP with the involved matrix A being a QN-matrix with positive diagonal entries an alternative bound which depends only on the entries of A is given. Numerical examples are given to show that the new bound is better than that provided by Dai et al. in some cases.     

Reformulation of mathematical programming problems as linear complementarity problems and investigation of their solution methods

A family of complementarity problems is defined as extensions of the well-known linear complementarity problem (LCP). These are:

Improved Approximation Algorithms for MAX \frac{n}{{\text{2}}}-DIRECTED-BISECTION and MAX \frac{n}{{\text{2}}}-DENSE-SUBGRAPH

We consider the MAX $\frac{n}{{\text{2}}}$ -DIRECTED-BISECTION problem, i.e., partitioning the vertices of a directed graph into two blocks of equal cardinality so as to maximize the total weight of the edges in the directed cut. A polynomial approximation algorithm using a semidefinite relaxation with 0.6458 performance guarantee is presented for the problem. The previous best-known results for approximating this problem are 0.5 using a linear programming relaxation, 0.6440 using a semidefinite relaxation. We also consider the MAX $\frac{n}{{\text{2}}}$ -DENSE-SUBGRAPH problem, i.e., determine a block of half the number of vertices from a weighted undirected graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We present an 0.6236 approximation of the problem as opposed to 0.6221 of Halperin and Zwick.     

Eigenvalue analysis of constrained minimization problem for homogeneous polynomial

In this paper, the concepts of Pareto H-eigenvalue and Pareto Z-eigenvalue are introduced for studying constrained minimization problem and the necessary and sufficient conditions of such eigenvalues are given. It is proved that a symmetric tensor has at least one Pareto H-eigenvalue (Pareto Z-eigenvalue). Furthermore, the minimum Pareto H-eigenvalue (or Pareto Z-eigenvalue) of a symmetric tensor is exactly equal to the minimum value of constrained minimization problem of homogeneous polynomial deduced by such a tensor, which gives an alternative methods for solving the minimum value of constrained minimization problem. In particular, a symmetric tensor \({\mathcal {A}}\) is strictly copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is positive, and \({\mathcal {A}}\) is copositive if and only if every Pareto H-eigenvalue (Z-eigenvalue) of \({\mathcal {A}}\) is non-negative.     

SOS-Convex Semialgebraic Programs and its Applications to Robust Optimization: A Tractable Class of Nonsmooth Convex Optimization

In this paper, we introduce a new class of nonsmooth convex functions called SOS-convex semialgebraic functions extending the recently proposed notion of SOS-convex polynomials. This class of nonsmooth convex functions covers many common nonsmooth functions arising in the applications such as the Euclidean norm, the maximum eigenvalue function and the least squares functions with ? ₁-regularization or elastic net regularization used in statistics and compressed sensing. We show that, under commonly used strict feasibility conditions, the optimal value and an optimal solution of SOS-convex semialgebraic programs can be found by solving a single semidefinite programming problem (SDP). We achieve the results by using tools from semialgebraic geometry, convex-concave minimax theorem and a recently established Jensen inequality type result for SOS-convex polynomials. As an application, we show that robust SOS-convex optimization proble ms under restricted spectrahedron data uncertainty enjoy exact SDP relaxations. This extends the existing exact SDP relaxation result for restricted ellipsoidal data uncertainty and answers an open question in the literature on how to recover a robust solution of uncertain SOS-convex polynomial programs from its semidefinite programming relaxation in this broader setting.     

Weakly chained diagonally dominant <Emphasis Type="Italic">B</Emphasis>-matrices and error bounds for linear complementarity problems

The class of weakly chained diagonally dominant B-matrices, a subclass of P-matrices is introduced. Error bounds for the linear complementarity problem are presented when the involved matrix is a weakly chained diagonally dominant B-matrix. Numerical examples are given to show the sharpness of the proposed bounds.     

<Emphasis Type="Italic">l</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>,<Emphasis Type="Italic">s</Emphasis></Superscript>-Singular values and spectral radius of partially symmetric rectangular tensors

The real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we first study properties of l ^k,s -singular values of real rectangular tensors. Then, a necessary and sufficient condition for the positive definiteness of partially symmetric rectangular tensors is given. Furthermore, we show that the weak Perron-Frobenius theorem for nonnegative partially symmetric rectangular tensor keeps valid under some new conditions and we prove a maximum property for the largest l ^k,s -singular values of nonnegative partially symmetric rectangular tensor. Finally, we prove that the largest l ^k,s -singular value of nonnegative weakly irreducible partially symmetric rectangular tensor is still geometrically simple.     

Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization

This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in ${\mathbb{R}^m}$ which are determined by a freely chosen m × m positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based on the basic idea of lifting, we first present a conceptual min-max problem to determine an ellipsoidal set with the smallest size in this class which encloses a given subset of ${\mathbb{R}^m}$ . Then we derive a numerically tractable enclosing ellipsoidal set of a given semialgebraic subset of ${\mathbb{R}^m}$ as a convex relaxation of the min-max problem in the lifting space. A main feature of the proposed method is that it is designed to incorporate into existing SDP relaxations with exploiting sparsity for various optimization problems to compute error bounds of their optimal solutions. We discuss how we adapt the method to a standard SDP relaxation for quadratic optimization problems and a sparse variant of Lasserre’s hierarchy SDP relaxation for polynomial optimization problems. Some numerical results on the sensor network localization problem and polynomial optimization problems are also presented.     

Solving the Continuous <Emphasis Type="Italic">p</Emphasis>-Dispersion Problem Using Non-linear Programming

The problem of locating p maximally dispersed points in a convex space is considered. This problem is formulated as a non-linear programming problem. It is shown that this problem, in a square, is equivalent to the problem of packing the square with p equal circles of largest possible radius. Computational experience with the non-linear programming formulation of the dispersion problem is reported. Four of the solutions found are superior to the best known solutions in the literature for the corresponding circle-packing problem.     

Strictly semi-positive tensors and the boundedness of tensor complementarity problems

In this paper, we present the boundedness of solution set of tensor complementarity problem defined by a strictly semi-positive tensor. For strictly semi-positive tensor, we prove that all \(H^+(Z^+)\)-eigenvalues of each principal sub-tensor are positive. We define two new constants associated with \(H^+(Z^+)\)-eigenvalues of a strictly semi-positive tensor. With the help of these two constants, we establish upper bounds of an important quantity whose positivity is a necessary and sufficient condition for a general tensor to be a strictly semi-positive tensor. The monotonicity and boundedness of such a quantity are established too.     

Variational Analysis on Local Sharp Minima via Exact Penalization

In this paper we study local sharp minima of the nonlinear programming problem via exact penalization. Utilizing generalized differentiation tools in variational analysis such as subderivatives and regular subdifferentials, we obtain some primal and dual characterizations for a penalty function associated with the nonlinear programming problem to have a local sharp minimum. These general results are then applied to the ? _p penalty function with 0 ≤ p ≤ 1. In particular, we present primal and dual equivalent conditions in terms of the original data of the nonlinear programming problem, which guarantee that the ? _p penalty function has a local sharp minimum with a finite penalty parameter in the case of \(p\in (\frac {1}{2}, 1]\) and \(p=\frac {1}{2}\) respectively. By assuming the Guignard constraint qualification (resp. the generalized Guignard constraint qualification), we also show that a local sharp minimum of the nonlinear programming problem can be an exact local sharp minimum of the ? _p penalty function with p ∈ [0, 1] (resp. \(p\in [0, \frac {1}{2}]\)). Finally, we give some formulas for calculating the smallest penalty parameter for a penalty function to have a local sharp minimum.     

Approximation of an optimal control problem in coefficient for variational inequality with anisotropic <Emphasis Type="Italic">p</Emphasis>-Laplacian

We study an optimal control problem for a variational inequality with the so-called anisotropic p-Laplacian in the principle part of this inequality. The coefficients of the anisotropic p-Laplacian, the matrix A(x), we take as a control. The optimal control problem is to minimize the discrepancy between a given distribution \({y_d \in L^{2}(\Omega)}\) and the solutions \({y \in K \subset W^{1,p}_{0}(\Omega)}\) of the corresponding variational inequality. We show that the original problem is well-posed and derive existence of optimal pairs. Since the anisotropic p-Laplacian inherits the degeneracy with respect to unboundedness of the term \({|(A(x)\nabla y, \nabla y)_{\mathbb{R}^N}|^{\frac{p-2}{2}}}\), we introduce a two-parameter model for the relaxation of the original problem. Further we discuss the asymptotic behavior of relaxed solutions and show that some optimal pairs to the original problem can be attained by the solutions of two-parametric approximated optimal control problems.