Research report Series B (483-494)

• 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.

ID: B-494 (November, 2021)

A Robust Optimization Method with Successive Linear Programming for Intensity Modulated Radiation Therapy

Author

Masaaki Tamai and Makoto Yamashita

Email

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

Abstract

Intensity modulated radiation therapy (IMRT) is one of radiation therapies for cancers, and it is considered to be effective for complicated shapes of tumors, since dose distributions from each irradiation can be modulated arbitrary. Fluence map optimization (FMO), which optimizes beam intensities with given beam angles, is often formulated as an optimization problem with dose volume constraints (DVCs). Romeijn et al. (2003) developed a linear programming (LP) method that approximated DVCs, and Kishimoto and Yamashita (2018) modified it to a successive LP method (SLPM) to find a feasible treatment plan in a wider region than the method of Romeijn et al. However, these two methods did not consider uncertainty, like observational errors or beam inaccuracy, in a series of treatment planning. In this paper, we propose a numerical method that enhances SLPM utilizing a robust optimization approach. We mathematically prove that the proposed method with extended LP problems holds favorable properties of SLPM, even taking uncertainty in influence matrix into consideration. In particular, when the optimal value of the LP problem is non-positive, the proposed method guarantees that the output solution can satisfy all DVCs. Through numerical experiments, we observed that the proposed method found a feasible plan that SLPM could not find. Even when the proposed method could not output a feasible solution, it was still effective to reduce the largest deviations from DVCs.

ID: B-493 (September, 2020)

Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

Author

Godai Azuma, Mituhiro Fukuda, Sunyoung Kim, and Makoto Yamashita

Email

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

Abstract

We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less than $n-1$ and the matrix remains positive semidefinite after replacing some off-diagonal nonzero elements with zeros, then the standard SDP relaxation provides an exact optimal solution for the QCQP under feasibility assumptions. In particular, we demonstrate that QCQPs with forest-structured aggregate sparsity matrix, such as the tridiagonal or arrow-type matrix, satisfy the exactness condition on the rank. The exactness is attained by considering the feasibility of the dual SDP relaxation, the strong duality of SDPs, and a sequence of QCQPs with perturbed objective functions, under the assumption that the feasible region is compact. We generalize our result for a wider class of QCQPs by applying simultaneous tridiagonalization on the data matrices. Moreover, simultaneous tridiagonalization is applied to a matrix pencil so that QCQPs with two constraints can be solved exactly by the SDP relaxation.

In this paper, we propose an infeasible arc-search interior-point algorithm for solving nonlinear programming problems. Most algorithms based on interior-point methods are categorized as line search in the sense that they compute a next iterate on a straight line determined by a search direction which approximates the central path. The proposed arc-search interior-point algorithm uses an arc for the approximation. We discuss the convergence property of the proposed algorithm. We also conduct numerical experiments on the CUTEst benchmark problems and compare the performance of the proposed arc-search algorithm with that of an line-search algorithm. Numerical results indicate that the proposed arc-search algorithm reaches the optimal solution using less iterations than a line-search algorithm.

ID: B-492 (February, 2020)

Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

Author

Masaru Ito and Mituhiro Fukuda

Email

mituhiro (at) is.titech.ac.jp

Abstract

In the development of first-order methods for smooth (resp., composite) convex optimization problems minimizing L-smooth functions, the gradient (resp., gradient mapping) norm is a fundamental optimality measure for which the best known iteration complexity to obtain an \epsilon-solution is O(\sqrt{LD/\epsilon}\log(1/\epsilon)) for the distance D from the initial point to the optimal solution set. In this paper, we report an adaptive regularization approach attaining this iteration complexity without the prior knowledge of D which was required to be known in the existing regularization approach. To obtain further faster convergence adaptively, we secondly apply this approach to construct a first-order method that is adaptive to the Holderian error bound condition (or equivalently, the Lojasiewicz gradient property) which covers moderately wide class of applications. The proposed method attains nearly optimal iteration complexity with respect to the gradient mapping norm.

ID: B-491 (September, 2019)

An Infeasible Interior-point Arc-search Algorithm for Nonlinear Constrained Optimization

Author

Einosuke Iida, Yaguang Yang, and Makoto Yamashita

Email

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

Abstract

In this paper, we propose an infeasible arc-search interior-point algorithm for solving nonlinear programming problems. Most algorithms based on interior-point methods are categorized as line search in the sense that they compute a next iterate on a straight line determined by a search direction which approximates the central path. The proposed arc-search interior-point algorithm uses an arc for the approximation. We discuss the convergence property of the proposed algorithm. We also conduct numerical experiments on the CUTEst benchmark problems and compare the performance of the proposed arc-search algorithm with that of an line-search algorithm. Numerical results indicate that the proposed arc-search algorithm reaches the optimal solution using less iterations than a line-search algorithm.

ID: B-490 (Dec, 2018)

A dual spectral projected gradient method for log-determinant semidefinite problems

Author

Takashi Nakagaki, Mituhiro Fukuda, Sunyoung Kim and Makoto Yamashita

Email

mituhiro (at) is.titech.ac.jp

Abstract

We extend the result on the spectral projected gradient method by Birgin {\it et al.} in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectral projected gradient method for the dual problem. Our method is based on alternate projections on the intersection of two convex sets, which first projects onto the box constraints and then onto a set defined by a linear matrix inequality. By exploiting structures of the two projections, we show the same convergence properties can be obtained for the proposed method as Birgin’s method where the exact orthogonal projection onto the intersection of two convex sets is performed. Using the convergence properties, we prove that the proposed algorithm attains the optimal value or terminates in a finite number of iterations. The efficiency of the proposed method is illustrated with the numerical results on randomly generated synthetic/deterministic data and gene expression data, in comparison with other methods including the inexact primal-dual path-following interior-point method, the adaptive spectral projected gradient method, and the adaptive Nesterov’s smooth method. For the gene expression data, our results are compared with the quadratic approximation for sparse inverse covariance estimation method. We show that our method outperform

ID: B-489 (May, 2018)

Polyhedral-based Methods for Mixed-Integer SOCP in Tree Breeding

Author

Sena Safarina, Tim J. Mullin, Makoto Yamashita

Email

sena4 (at) is.titech.ac.jp

Abstract

Optimal contribution selection (OCS) is a mathematical optimization problem that aims to maximize the total benefit from selecting a group of individuals under a constraint on genetic diversity. We are specifically focused on OCS as applied to forest tree breeding, when selected individuals will contribute equally to the gene pool. Since the diversity constraint in OCS can be described with a second-order cone, equal deployment in OCS can be mathematically modeled as mixed-integer second-order cone programming (MI-SOCP). If we apply a general solver for MI-SOCP, non-linearity embedded in OCS requires a heavy computation cost. To address this problem, we propose an implementation of lifted polyhedral programming (LPP) relaxation and a cone-decomposition method (CDM) to generate effective linear approximations for OCS. In particular, CDM successively solves OCS problems much faster than generic approaches for MI-SOCP. The approach of CDM is not limited to OCS, so that we can also apply the approach to other MI-SOCP problems.

ID: B-488 (March, 2018)

Sums of Squares Representation of Polynomials by Alternating Directional Augmented Lagrangian Methods with Fast Convergence

Author

Hikaru Komeiji, Sunyoung Kim and Makoto Yamashita

Email

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

Abstract

We study expressing a polynomial as sums of squares (SOS) of polynomials of lower degree by formulating the problem as semidefinite programs (SDPs). To efficiently solve the SDPs whose size grows very rapidly with the degree and number of variables of the polynomial, the alternative direction augmented Lagrangian (ADAL) method is investigated. We present conditions for the ADAL method to converge to an optimal solution in a few iterations and prove its convergence under the conditions. In addition, for the problem of representing a univariate trigonometric polynomial as an SOS, we also provide similar conditions for the fast convergence of the ADAL method to an optimal solution. Numerical results demonstrate the fast convergence of the method if the conditions are satisfied and the strictly feasible region is not very small. Test instances include SDPs with 11,476 variables and 22,533,126 constraints.

B-487 (February, 2018)

Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods

Author

Masaki Kimizuka, Sunyoung Kim and Makoto Yamashita

Email

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

Abstract

The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For P-formulation of the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the semidefinite programming relaxation. The equivalence among the optimal values of the three relaxations is also computationally shown. Moreover, a rescheduling method is proposed to efficiently refine the solution obtained by the SOCP or LP relaxation. The efficiency of the SOCP and the LP relaxation and the proposed rescheduling method is illustrated with numerical results on the test instances from the work of Nishi in 2010, some large instances, and Foulds 3, 4, 5 test problems.

ID: B-486 (July, 2017)

Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

Author

Naoki Ito, Sunyoung Kim, Masakazu Kojima, Akiko Takeda and Kim-Chuan Toh

Email

kojima@is.titech.ac.jp

Abstract

Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we prove the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition, a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical results on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.

ID: B-485 (March, 2017)

Conic relaxation approaches for equal deployment problems

Author

Sena Safarina, Satoko Moriguchi, Tim J. Mullin and Makoto Yamashita

Email

safarina.s.aa (at) m.titech.ac.jp

Abstract

An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et al. (2015) exploits the structural sparsity of the quadratic constraints and reduces the computation time drastically while attaining the same optimal solution.

This paper is concerned with the special case of equal deployment (ED), in which we solve the optimal selection problem with the constraint that contribution of genotypes must either be a fixed size or zero. This involves a nature of combinatorial optimization, and the ED problem can be described as a mixed-integer SOCP problem.

In this paper, we discuss conic relaxation approaches for the ED problem based on LP (linear programming), SOCP, and SDP (semidefinite programming). We analyze theoretical bounds derived from the SDP relaxation approaches using the work of Tseng (2003) and show that the theoretical bounds are not quite sharp for tree breeding problems. We propose a steepest-ascent method that combines the solution obtained from the conic relaxation problems with a concept from discrete convex optimization in order to acquire an approximate solution for the ED problem in a practical time. From numerical tests, we observed that among the LP, SOCP, and SDP relaxation problems, SOCP gave a suitable solution from the viewpoints of the optimal values and the computation time. The steepest-ascent method starting from the SOCP solution provides high-quality solutions much faster than an existing method that has been widely used for the optimal selection problems and a branch-and-bound method.

ID: B-484 (December, 2016)

A Successive LP Approach with C-VaR Type Constraints for IMRT Optimization

Author

Shogo Kishimoto and Makoto Yamashita

Email

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

Abstract

Radiation therapy is considered to be one of important treatment protocols for cancers. Radiation therapy employs several beams of ionizing radiation to kill cancer tumors, but such irradiation also causes damage to normal tissues. Therefore, a treatment plan should satisfy dose-volume constraints (DVCs). Intensity-modulated radiotherapy treatment (IMRT) enables to control the beam intensities and gives more flexibility for the treatment plan to satisfy the DVCs. Romeijn et al. [Physics in Medicine and Biology, 48(21):3521, 2003] replaced the DVCs in an IMRT optimization with C-VaR (Conditional Value-at-Risk) type constraints, and proposed a numerical method based on linear programming (LP). Their approach reduced the computation cost of the original DVCs, but the feasible region of their LP problems was much narrow compared to the DVCs, therefore, their approach often failed to find a feasible plan even when the DVCs were not so tight.

In this paper, we propose a successive LP approach with the C-VaR type constraints. We detect outliers form the solution of LP problems, and remove them from the domain of the C-VaR type constraints. This eases the sensitivity of C-VaR type constraints to outliers and we can search feasible plans from wider regions. Furthermore, we can give a mathematical proof that if the optimal value of the LP problem in the proposed approach is non-positive, the corresponding optimal solution satisfies all the DVCs. From numerical experiments on test data sets, we observed that our approach found feasible solutions more appropriately than existing LP approaches. In addition, our approach required fewer LP problems, and this led to a short computation time.

ID: B-483 (July, 2016)

Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints

Authors

Sunyoung Kim, Masakazu Kojima and Kim-Chuan Toh

Email

kojima (at) is.titech.ac.jp

Abstract

We propose doubly nonnegative (DNN) relaxations for polynomial optimization problems (POPs) with binary and box constraints to find tight lower bounds for their optimal values using a bisection and projection (BP) method. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems (QOPs) to POPs. We show how the dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which the BP algorithm can be applied. To compute the metric projection efficiently in the BP method, we introduce a class of polyhedral cones as a basic framework for various DNN relaxations. Moreover, we prove using the basic framework why the tight lower bounds of QOPs were obtained numerically by the Lagrangian-DNN relaxation of QOPs in the work by the authors in 2016. Preliminary numerical results on randomly generated POPs with binary and boxed constraints and the maximum complete satisfiability problems are provided to demonstrate the numerical efficiency of the proposed method for attaining tight bounds.

Recent Posts