###### Research Reports (Series B: Applied Mathematical Science) †

Dept. of Math. and Comp. Sciences

#### A robust Lagrangian-DNN method for a class of quadratic optimization problems †

ID: B-482 (February, 2016)

Author: Naohiko Arima, Sunyoung Kim, Masakazu Kojima and Kim-Chuan Toh

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-482.pdf

Abstract:

The Lagrangian-doubly nonnegative (DNN) relaxation has recently been
shown to provide
effective lower bounds for a large class of nonconvex quadratic optimization problems (QOPs) using the bisection method combined with first-order methods by Kim, Kojima and Toh in 2016.
While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower bound for the QOP depends on a prescribed parameter epsilon > 0.
To improve the performance of the bisection method for the Lagrangian-DNN relaxation, we propose a new technique that guarantees the validity of the computed lower bound at each iteration of the bisection method for any choice of epsilon > 0. It also accelerates the bisection method.
Moreover, we present a method to retrieve a primal-dual pair of optimal solutions of the Lagrangian-DNN relaxation using the primal-dual interior-point method. As a result, the method provides a better lower bound and substantially increases the robustness as well as the effectiveness of the bisection method.
Computational results on the binary QOPs, the multiple knapsack problems, the maximal stable set problems, and the quadratic assignment problems (QAPs) illustrate the robustness of the proposed method. In particular, a tight bound for QAPs with size n=50 could be obtained.

#### Binary Quadratic Optimization Problems That Are Difficult to Solve by Conic Relaxations †

ID: B-481 (July, 2015)

Author: Sunyoung Kim and Masakazu Kojima

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-481.pdf

Abstract:

Binary quadratic optimization problems (QOPs) have been an important
class of
optimization problems for their wide range of applications. Binary QOPs are known to be NP-hard, and the optimal values and solutions of binary QOPs have been approximated by conic relaxations, including semidefinite programming (SDP) relaxations and doubly nonnegative programming (DNN) relaxations. It is known that if the hierarchy of SDP relaxation by Lasserre is applied to binary QOPs, then the $n$th SDP with $2^n -1$ variables is guaranteed to attain the optimal value.
For some binary QOP instances, which include the max-cut problem of a graph with an odd number of nodes and equal weight, we show numerically that (1) neither the standard DNN relaxation nor the DNN relaxation derived from the completely positive programming formulation by Burer is effective, and (2) the hierarchy of SDP relaxation requires solving at least \lceil n/2 \rceil th SDP to attain the optimal value.

#### An efficient second-order cone programming approach for optimal selection in tree breeding †

ID: B-480 (June, 2015)

Author: Makoto Yamashita, Tim J. Mullin and Sena Safarina

Email: Makoto.Yamashita (at) is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-480.pdf

Abstract:

In this paper, we propose an SOCP (second-order cone programming) approach to reduce this
computation time. We demonstrate that the same solution is attained by the SOCP formulation,
but requires much less time. Since a simple SOCP formulation is not much more efficient compared
to the SDP approach, we exploit a sparsity structure of the numerator relationship matrix,
and formulate the SOCP constraint using Henderson's algorithm. Numerical results show that the
proposed SOCP approach reduced computation time in a case study from 39,200 seconds under the
SDP approach to less than 2 seconds.

#### New results on subgradient methods for strongly convex optimization problems with a unified analysis †

ID: B-479 (April, 2015)

Author: Masaru Ito

Email: ito1@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-479.pdf

Abstract:

We develop subgradient- and gradient-based methods for minimizing strongly convex functions under a notion which generalizes the standard Euclidean strong convexity. We propose a unifying framework for subgradient methods which yields two kinds of methods, namely, the Proximal Gradient Method (PGM) and the Conditional Gradient Method (CGM), unifying several existing methods. The unifying framework provides tools to analyze the convergence of PGMs and CGMs for non-smooth, (weakly) smooth, and further for structured problems such as the inexact oracle models. The proposed subgradient methods yield optimal PGMs for several classes of problems and yield (nearly) optimal CGMs for smooth and weakly smooth problems, respectively.

#### A trust-region method for box-constrained nonlinear semidefinite programs †

ID: B-478 (November, 2014)

Author: Akihiko Komatsu and Makoto Yamashita

Email: Makoto.Yamashita (at) is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-478.pdf

Abstract:

We propose a trust-region method for nonlinear semidefinite programs
with box-constraints.
The penalty barrier method can handle this problem,
but the size of variable matrices available in practical time
is restricted to be less than 500.
We develop a trust-region method
based on the approach of Coleman and Li (1996)
that utilizes the distance to the boundary of the box-constraints into consideration.
To extend this method to the space of positive semidefinite matrices,
we device a new search direction by incorporating
the eigenvectors of the variable matrix into the distance to the boundary.
In this paper,
we establish a global convergence of the proposed method, and
preliminary numerical experiments show that our method solves the problems
with the size being larger than 5000,
and it is faster than the feasible direction
for functions with nonlinearity higher than quadratic.

#### A Family of Subgradient-Based Methods for Convex Optimization Problems in a Unifying Framework †

ID: B-477 (February, 2014)

Author: Masaru Ito and Mituhiro Fukuda

Email: ito1@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-477.pdf

Abstract:

We consider subgradient- and gradient-based methods for convex optimization problems whose feasible region is simple enough. We unify the way of constructing the subproblems which are necessary to be solved at each iteration of these methods. Our unifying framework provides a novel analysis of (sub)gradient-based methods and permit us to propose a family of optimal complexity methods. For the non-smooth case, we propose an extension of the mirror-descent method originally proposed by Nemirovski and Yudin and overcame its drawback on optimal convergence. Our analysis is also applied to the dual-averaging method proposed by Nesterov using simpler arguments for its complexity analysis. Finally, we propose (inexact) gradient-based methods for structured optimization problems such as with composite structure or using an inexact oracle model. The proposed family of classical gradient methods and its accelerations generalizes some of primal/dual gradient and Tseng’s accelerated proximal gradient methods.

#### Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems †

ID: B-476 (January, 2014)

Author: Naohiko Arima, Sunyoung Kim, Masakazu Kojima and Kim-Chuan Toh

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-476.pdf

Abstract:

We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I.
The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the completely positive programming relaxation for QOPs. Under a copositivity condition, we characterize the equivalence of the optimal values between the POP and its MC relaxation. A hierarchy of sparse Lagrangian-SDP relaxations, which is parameterized by a positive integer $\omega$ called the relaxation order, is proposed for an equality constrained POP.
It is obtained by combining a sparse variant of Lasserre's hierarchy of SDP relaxation of POPs and the basic idea behind the conic and Lagrangian-conic relaxations from the unified framework. We prove under a certain assumption that the optimal value of the Lagrangian-SDP relaxation with the Lagrangian multiplier $\lambda$ and the relaxation order $\omega$ in the hierarchy converges to that of the POP as $\lambda \rightarrow \infty$ and $\omega \rightarrow \infty$. The hierarchy of sparse Lagrangian-SDP relaxations
is designed to be used in combination with the bisection and $1$-dimensional Newton methods, which was proposed in Part I, for solving large-scale POPs efficiently and effectively.

#### Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems †

ID: B-475 (January, 2014)

Author: Naohiko Arima, Sunyoung Kim, Masakazu Kojima and Kim-Chuan Toh

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-475.pdf

Abstract:

In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimizationproblem (COP) in a finite dimensional vector space endowed with an inner product,
where the cone used is not necessarily convex. By imposing a copositive condition on the COP, we establish fundamental theoretical results for the COP, its conic relaxations, its Lagrangian-conic relaxations, and their duals. A linearly constrained QOP with complementarity constraints and a general POP can be reduced to the COP satisfying the copositivity condition. Then, the conic and Lagrangian-conic relaxations of such a QOP and POP are discussed in a unified manner. The Lagrangian-conic relaxation takes one of the simplest forms, which is very useful to design efficient numerical methods. As for applications of the framework, we discuss the completely positive programming relaxation, and a sparse doubly nonnegative relaxation for a linearly constrained QOP with complementarity constraints. The unified framework is applied to general POPs in Part II.

#### Fast implementation for semidefinite programs with positive matrix completion †

ID: B-474 (October, 2013)

Author: Makoto Yamashita

Email: Makoto.Yamashita(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-474.pdf

Abstract:

Solving semidefinite programs (SDP) in a short time is the key to
managing various mathematical optimization problems in practical time.
The matrix-completion primal-dual interior-point method (MC-PDIPM)
extracts a structural sparsity of input SDP by factorizing the variable
matrices, and it shrinks the computation time. In this paper, we
propose a new factorization based on the inverse of the variable matrix
to enhance the performance of the MC-PDIPM. We also combine
multithreaded parallel computing to resolve the major bottlenecks in the
MC-PDIPM. The numerical results show that the new factorization and the
multithreaded computing successfully reduce the computation time for the
SDPs that posses the structural sparsity.

#### Spatial stochastic models for analysis of heterogeneous cellular networks with repulsively deployed base stations †

ID: B-473 (October, 2013)

Authors: Itaru Nakata and Naoto Miyoshi

Email: miyoshi(at)is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-473.pdf

Abstract:

We consider spatial stochastic models of downlink heterogeneous
cellular networks (HCNs) with multiple tiers, where the base stations
(BSs) of each tier have a particular spatial density, transmission
power and path-loss exponent. Prior works on such spatial models of
HCNs assume, due to its tractability, that the BSs are deployed
according to homogeneous Poisson point processes. This means that the
BSs are located independently of each other and their spatial
correlation is ignored. In the current paper, we propose two spatial
models for the analysis of downlink HCNs, in both of which the BSs are
deployed according to $\alpha$-Ginibre point processes. The
$\alpha$-Ginibre point processes constitute a class of determinantal
point processes and account for the repulsion between the BSs.
Besides, the degree of repulsion can be adjusted according to the
value of $\alpha\in(0,1]$. For such proposed models, we derive
computable representations for the coverage probability of a typical
user---the probability that the downlink
signal-to-interference-plus-noise ratio for the typical user achieves
a target threshold. We exhibit the results of some numerical
experiments and compare the proposed models and the Poisson based
model.

#### A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds †

for a Class of Quadratic Optimization Problems

ID: B-472 (October, 2013)

Author: Sunyoung Kim, Masakazu Kojima and Kim-Chuan Toh

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-472.pdf

Abstract:

We propose an efficient computational method
for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints
based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms.
The simplified Lagrangian-CPP relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012
takes one of the simplest forms, an unconstrained conic linear optimization problem
with a single Lagrangian parameter in a completely positive (CPP) matrix variable with its
upper-left element fixed to 1.Replacing the CPP matrix variable by a DNN matrix variable,
we derive the Lagrangian-DNN relaxation, and establish the equivalence between the optimal
value of the DNN relaxation of the original QOP and that of the Lagrangian-DNN relaxation.
We then propose an efficient numerical method for the Lagrangian-DNN relaxation using
a bisection method combined with the proximal alternating direction multiplier and the accelerated
proximal gradient methods.Numerical results on binary QOPs, quadratic multiple knapsack problems,
maximum stableset problems, and quadratic assignment problems illustrate the superior performance
of the proposed method for attaining tight lower bounds in shorter computational time.

#### Extension of Completely Positive Cone Relaxation to Polynomial Optimization †

ID: B-471 (February, 2013)

Author: Naohiko Arima, Sunyoung Kim and Masakazu Kojima

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-471.pdf

Abstract:

We propose the moment cone relaxation for a class of polynomial optimization problems (POPs) to extend the results on the completely positive cone programming relaxation for the quadratic optimization (QOP) model by Arima, Kim and Kojima. The moment cone relaxation is constructed to take advantage of sparsity of the POPs, so that efficient numerical methods can be developed in the future. We establish the equivalence between the optimal value of the POP and that of the moment cone relaxation under conditions similar to the ones assumed in the QOP model. The proposed method is compared with the canonical convexification procedure recently proposed by Pena, Vera and Zuluaga for POPs. The moment cone relaxation is theoretically powerful, but numerically intractable. For tractable numerical methods, the doubly nonnegative cone relaxation is derived from the moment cone relaxation. Exploiting sparsity in the doubly nonnegative cone relaxation and its incorporation into Lasserre's semidefinite relaxation are briefly discussed.

#### Parallel Implementation of Successive Sparse SDP Relaxations for Large-Scale Euclidean Distance Geometry Problems †

ID: B-470 (November, 2012)

Author: Sunyoung Kim, Masakazu Kojima and Makoto Yamashita

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-470.pdf

Abstract:

The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor
network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, is a more challenging problem and can be handled with only a few methods. We propose an efficient and robust numerical method for large-scale EDGPs with exact and corrupted distances including anchor-free three-dimensional problems. The method is based on successive application of the sparse version of full semidefinite programming relaxation (SFSDP) proposed by Kim, Kojima, Waki and Yamashita, and can be executed in parallel. Numerical results on large-scale anchor-free three-dimensional problems with more than 10000 nodes demonstrate that the proposed method performs better than the direct application of SFSDP and the divide and conquer method of Leung and Toh in terms of efficiency and/or effectiveness measured in the root mean squared distance.

#### Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables †

ID: B-469 (October, 2012)

Author: Naohiko Arima, Sunyoung Kim and Masakazu Kojima

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-469.pdf

Abstract:

For a quadratic optimization problem (QOP) with linear equality constraints
in continuous nonnegative variables and binary variables, we propose
three relaxations in simplified forms with a parameter lambda: Lagrangian,
completely positive, and copositive relaxations. These relaxations are obtained
by reducing the QOP to an equivalent QOP with a single quadratic equality
constraint in nonnegative variables, and applying the Lagrangian relaxation
to the resulting QOP. As a result, an unconstrained QOP with a Lagrangian
multiplier lambda in nonnegative variables is obtained. The other
two relaxations are a primal-dual pair of a completely positive programming
(CPP) relaxation in a variable matrix with the upper-left element set to 1 and
a copositive programming (CP) relaxation in a single variable. The CPP relaxation
is derived from the unconstrained QOP with the parameter lambda, based
on the recent result by Arima, Kim and Kojima. The three relaxations with a same
parameter value lambda > 0 work as relaxations of the original QOP.
The optimal values zeta(lambda) of the three relaxations coincide, and
monotonically converge to the optimal value of the original QOP as lambda
tends to infinity under a moderate assumption. The parameter lambda serves
as a penalty parameter when it is chosen to be positive. Thus, the standard
theory on the penalty function method can be applied to establish the convergence.

#### A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming †

ID: B-468 (September, 2012)

Author: Naohiko Arima, Sunyoung Kim and Masakazu Kojima

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-468.pdf

Abstract:

We propose a class of quadratic optimization problems whose exact optimal objective
values can be computed by their completely positive cone programming relaxations.
The objective function can be any quadratic form. The constraints of each problem
are described in terms of quadratic forms with no linear terms, and all constraints
are homogeneous equalities, except one inhomogeneous equality where a quadratic form
is set to be a positive constant. For the equality constraints, ``a hierarchy of
copositvity" condition is assumed. This model is a generalization of the standard
quadratic optimization problem of minimizing a quadratic form over the standard simplex,
and covers many of the existing quadratic optimization problems studied for exact
copositive cone and completely positive cone programming relaxations. In particular,
it generalizes the recent results on quadratic optimization problems by Burer and
the set-semidefinite representation by Eichfelder and Povh.

#### A cellular network model with Ginibre configurated base stations †

ID: B-467 (June, 2012)

Authors: Naoto Miyoshi and Tomoyuki Shirai

Email: miyoshi(at)is. titech. ac. jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-467.pdf

Abstract:

Recently, stochastic geometry models for wireless communication
networks have been attracting much attention. This is because the performance of such networks critically depends on the spatial configuration of wireless nodes and the irregularity of node configuration in a real network can be captured by a spatial point process. However, most analyses of such stochastic geometry models for wireless networks assume, due to its tractability, that the wireless nodes are located according to homogeneous Poisson point processes. This means that the wireless nodes are located independently with each other and their spatial correlation is ignored. In this work, we propose a stochastic geometry model of cellular networks such that the wireless base stations are located according to the Ginibre point process. The Ginibre point process is one of the determinantal point processes and accounts for the repulsion between the base stations. For the proposed model, we derive a computable representation for the coverage probability---the probability that the signal-to-interference-plus-noise ratio (SINR) for a mobile user achieves a target threshold. To capture its qualitative property, we further investigate the asymptotics of coverage probability as the SINR threshold becomes large in a special case. The results of numerical experiments are also exhibited.

#### A Continuation Method for Large-sized Sensor Network Localization Problems †

ID: B-466 (August, 2011)

Author: Sunyoung Kim and Masakazu Kojima

Email: kojima@is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/~research-report/B/B-449.pdf

Abstract:

SFSDP is a Matlab package for solving sensor network localization problems.
The package contains four functions, SFSDP.m, SFSDPplus.m, generateProblem.m, test_SFSDP.m, and some numerical examples.
The function SFSDP.m is an Matlab implementation of the semidefinite programming (SDP) relaxation proposed in the recent paper by Kim,
Kojima and Waki for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) by Biswas and Ye.
To improve the efficiency of FSDP, SFSDP.m exploits the aggregated and correlative sparsity of a sensor network localization problem.
The function SFSDPplus.m analyzes the input data of a sensor network localization problem, solves the problem,
and displays graphically computed locations of sensors.
The function generateProblem.m creates numerical examples of sensor network localization problems with some typical anchor locations.
The function test_SFSDP.m is for numerical experiments on SFSDPplus.m applied to test problems generated by generateProblem.m.
The package SFSDP and this manual are available at http://www.is.titech.ac.jp/~kojima/SFSDP.

#### Fluid limit analysis of the FIFO and RR caching for the independent reference model †

ID: B-465 (July, 2011)

Author: Naoki Tsukada, Ryo Hirade and Naoto Miyoshi

Email: miyoshi(at)is.titech.ac.jp

Document: http://www.is.titech.ac.jp/research/research-report/B/B-465.pdf

Abstract:

We study the fluid limit analysis of the random replacement (RR) caching for the independent reference model.
Applying the limit theorem for the mean field interaction model, we derive the fluid limit of fault probability
in the transient state as well as in the steady state. Since it is known that the stationary fault probability
for the RR cache is identical to that for the first-in first-out (FIFO) cache, our result on the stationary
fault probability is valid for the FIFO caching. We see that the fluid limit of stationary fault probability,
which we obtain, is coincident with the known result by an intuitive approximation; that is, our fluid limit
analysis gives a rigorous theoretical foundation to the intuitive approximation.