Reports with Abstracts
DPS1284
A Primal Barrier Function Phase I Algorithm for Nonsymmetric Conic Optimization Problems (PDF: Nonember 2011)
by Yasuaki Matsukawa and Akiko Yoshise
Abstract:
We call a positive semidefinite matrix whose elements are nonnegative a {\em doubly nonnegative matrix}, and the set
of those matrices the {\em doubly nonnegative cone} (DNN cone).
The DNN cone is not symmetric but can be represented as the projection of a symmetric cone embedded in a higher dimension.
In \cite{aYOSHISE10}, the authors demonstrated the efficiency of the DNN relaxation using the symmetric cone representation of the DNN cone.
They showed that the DNN relaxation gives significantly tight bounds for a class of quadratic assignment problems, but the computational time is not affordable as long as we employ the symmetric cone representation.
They then suggested a primal barrier function approach for solving the DNN optimization problem directly, instead of using the symmetric cone representation.
However, most of existing studies on the primal barrier function approach assume the availability of a feasible interior point.
This fact means that those studies are not inextricably tied to the practical usage.
Motivated by these observations, we propose a primal barrier function Phase I algorithm for solving conic optimization problems over the closed convex cone $K$ having the following properties:
(a) $K$ is not necessarily symmetric, (b) a self-concordant function $f$ is defined over the interior of $K$, and
(c) its dual cone $K^*$ is not explicit or is intractable,
all of which are observed when $K$ is the DNN cone.
We analyze the algorithm and provide a sufficient condition for finite termination.
DPS1262
Complementarity Problems over Symmetric Cones: A Survey of Recent Developments in Several Aspects (PDF: July 2010, Revised December 2010)
by Akiko Yoshise
Abstract:
The complementarity problem over a symmetric cone (that we call the Symmetric Cone Complementarity Problem, or the SCCP) has received much attention of researchers in the last decade.
Many of studies done on the SCCP can be categorized into the three research themes,
interior point methods for the SCCP, merit function methods for the SCCP, and various properties of the SCCP.
In this paper, we will provide a brief survey on the recent developments on these three themes.
DPS1250
On Optimization over the Doubly Nonnegative Cone (PDF: February 2010)
by Yasuaki Matsukawa and Akiko Yoshise
Abstract:
In recent years, many studies have focused on semidefinite relaxation for combinatorial optimization problems and their usefulness.
While those studies force the solution matrix of the relaxation problem to be symmetric and positive semidefinite, we often see that each element of the solution matrix is meant to be nonnegative.
A positive semidefinite matrix whose elements are nonnegative is called a {\em doubly nonnegative matrix}.
It would be natural to obtain a better relaxation by considering an optimization problem over the set of such matrices (we call it the {\em doubly nonnegative cone}).
In this paper, we will show that the doubly nonnegative relaxation gives significantly tight bounds for a class of quadratic assignment problems, while the computational time may not be affordable as long as we solve the relaxation as usual, i.e., as an optimization problem over the symmetric cone given by the direct sum of the semidefinite cone and the nonnegative orthant.
Aiming to develop new and efficient algorithms for solving the doubly nonnegative optimization problems, we provide some basic properties of the doubly nonnegative cone focusing on barrier functions on its interior.
DPS1130
A Homogeneous Model for Mixed Complementarity Problems over Symmetric Cones (PDF: September 2005)
by Yedong Lin and Akiko Yoshise
Abstract:
In this paper, we propose a homogeneous model for solving monotone mixed complementarity problems over symmetric cones, by extending the results in [11] for standard form of the problems. We show that the extended model inherits the following desirable features: (a) A path exists, is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then every accumulation point of the path gives us a finite certificate proving infeasibility. We also show that the homogeneous model is directly applicable to the primal-dual convex quadratic problems over symmetric cones.
DPS890
Self-regular proximities and new search directions for nonlinear $P_*(\kappa)$ complementarity problems
by J. Peng, C. Roos, T.Terlaky and A. Yoshise
Abstract:
We deal with interior point methods (IPMs) for solving a class of
so-called $\Pstar$ complementarity problems (CPs). First of all,
several elementary results about $\Pstar$ mappings and $\Pstar$
CPs are presented. Then we extend some notions introduced
recently by Peng, Roos and
Terlaky for linear optimization
problems to the case of CPs. New large-update IPMs for solving
CPs are introduced based on the so-called {\em self-regular}
proximities.
To build up the complexity of these new algorithms, we impose
a new smoothness condition on the underlying mapping and this
condition can be viewed as a natural generalization of the {\em
relative Lipschitz} condition for convex programs introduced by
Jarre~\cite{int:JarreTh}. By utilizing various appealing
properties of {\em self-regular} proximities, we will show that if
the undertaken problem satisfies certain conditions, then these
new large-update IPMs for solving CPs have polynomial
$\O\br{n^{\frac{q+1}{2q}}\log\frac{n}{\epsilon}}$ iteration bounds
where $q$ is a constant, the so-called barrier degree of the
corresponding proximity.