Research report Series B (465-482)

• Research report Series B (483-494)
• Research report Series B (465-482)
• Research report Series B (308-464)

Notice! Some reports in this list may not have complete on-line information. In this case, or in general, if you have any question, please contact to the contacting author of the report directly.

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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</h1>

ID

B-480 (June, 2015)

Author

Makoto Yamashita, Tim J. Mullin and Sena Safarina

Email

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

Document

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 (at) is.titech.ac.jp

Document

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

pdf

Abstract

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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

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

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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 (at) is.titech.ac.jp

Document

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

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 (at) is.titech.ac.jp

Document

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

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.

Recent Posts