## 第9回 †日時 2008年2月13日(水) 16:00-17:00 会場 西8号館10階W1008号室 講演者 Elvira Hernandez 氏 (E.T.S.I. Industriales, UNED, Spain) 題目 Remarks on two criteria of solution for a set-valued optimization problem 要旨 The goal of this work is to explore solution concepts in set-valued optimization and to clarify some links between them. We consider both criteria of solution associated to a set-valued optimization problem, the vector criterion and the set criterion. We show that both criteria of solution coincide for a certain class of set-valued maps. We present relationships between solutions of vector type and solutions of set type. Finally, we give several optimality conditions for a set optimization problem. ## 第8回 †日時 2007年12月18日(火) 15:00-16:30 会場 E1011号室（西8号館E棟10階） 講演者 Kirill Morozov 氏 (Research Center for Information Security, AIST) 題目 Oblivious Transfer via McEliece's PKC and Permuted Kernels 要旨 We present two efficient protocols for two flavors of oblivious transfer (OT): the Rabin and 1-out-of-2 OT using the McEliece cryptosystem and Shamir's zero-knowledge identification scheme based on permuted kernels. This is a step towards diversifying computational assumptions on which OT -- the primitive of central importance -- can be based. Although we obtain a weak version of Rabin OT (where the malicious receiver may decrease his erasure probability), it can nevertheless be reduced to secure 1-out-of-2 OT. Elaborating on the first protocol, we provide a practical construction for 1-out-of-2 OT. ## 第7回 †日時 2007年11月30日(金) 15:00-16:30 会場 西8号館W棟9階W911号室 講演者 Renata Sotirov 氏 (Tilburg University, The Netherlands) 題目 Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem 要旨 The Quadratic Assignment Problem (QAP) is a classical combinatorial optimization problem, and is also know as a generic model for various real-life problems. The QAP is an NP-hard problem, and in practice has proven to be extremely difficult to solve to optimality. In this talk we consider semidefinite programming relaxations of the QAP, and show how to exploit group symmetry in the problem data. We also show that several instances in the QAP library involve matrices with large automorphism groups, and for some of these problem instances we report the best known lower bounds. ## 第6回 †日時 2007年11月12日(月) 10:30-12:00 会場 西8号館W棟8階W809号室 講演者 Marielba Rojas 氏 (Informatics and Mathematical Modelling, Technical University of Denmark) 題目 LSTRS: MATLAB Software for Large-Scale Trust-Region Subproblems and Regularization 要旨 We describe the features of a MATLAB implementation of the method LSTRS from: M. Rojas, S.A. Santos and D.C. Sorensen. A new matrix-free method for the large-scale trust-region subproblem, SIAM J. Optim. 11(3): 611-646, 2000. LSTRS is designed for large quadratic problems with one quadratic constraint. These problems arise in trust-region methods for optimization and in the regularization of discrete forms of ill-posed problems. The method is a limited-memory, iterative procedure that requires the solution of a large eigenvalue problem at each step. In the software, the eigensolver can be chosen from several options, and can also be supplied by the user. The Hessian matrix can be provided explicitly, or as a matrix-vector multiplication routine. Therefore, the software preserves the matrix-free nature of the algorithm. We describe the method, the features of the software, and present examples to illustrate its use. We also present comparisons with other state-of-the-art methods for large trust-region subproblems. Joint work with: Sandra A. Santos and Danny C. Sorensen ## 第5回 †日時 2007年10月10日(水) 13:30-15:00 会場 西8号館W棟8階W809号室 講演者 Elizabeth Wegner Karas 氏 (Federal University of Parana, Brazil) 題目 Filter Methods for Nonlinear Programming 要旨 In this talk we present some results related to filter methods for nonlinear programming. We present a general filter algorithm that allows a great deal of freedom in the step computation. Each iteration of the algorithm consists basically in computing a point which is not forbidden by the filter, from the current point. Either the original filter or the slanting filter criterion can be used for accept or reject the step. We prove its global convergence, assuming that the step must be efficient, in the sense that, near a feasible non-stationary point, the reduction of the objective function is ``large''. We show that this condition is reasonable, by presenting two ways of performing the step which satisfy it. In the first one, the step is computed by sequential quadratic programming. In the second, the step is obtained by the inexact restoration method \cite{martinez1} in which each iteration is composed of two phases. The first one reduces a measure of infeasibility, while in the second one the objective function value is reduced in a tangential approximation of the feasible set. The slanting filter criterion for accepting the new iterates enables a stronger statement about feasibility, namely, that every accumulation point of the sequence generated by the algorithm is feasible, independently of how these iterates are computed. Furthermore, computing the new iterates by the inexact restoration method, we prove stationarity of all accumulation points of the sequence. ## 第4回 †日時 2007年7月5日(木) 13:20-14:50 会場 西8号館W棟8階W809号室 講演者 Andreas Futschik 氏 (Department of Statistics, University of Vienna) 題目 On the inadmissibility of Watterson's estimate 要旨 We focus on the estimation of the scaled mutation parameter $\theta$, which is one of the parameters of key interest in population genetics. One of the most popular estimates in this context is Watterson's estimate. We show that Watterson's estimate is inadmissible when taking the mean squared error as the measure of performance. Subsequently we propose an alternative estimator that is easy to calculate and has a smaller mean squared error than Watterson's estimate for all possible parameter values $0<\theta<\infty.$ We show furthermore that this estimate is admissible in the class of all linear estimates. We also propose improved versions of related estimates and investigate their practical performance. ## 第3回 †日時 2007年5月16日(水) 16:30-17:00 会場 西8号館W棟10階W1008号室 講演者 Alex Fukunaga 氏 (Global Edge Institute, Tokyo Institute of Technology) 題目 Algorithms for resource allocation and scheduling 要旨 The multiple knapsack problem, bin-packing problem, and bin-covering problem are basic, NP-complete optimization problems involving the assignment of a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systems, and can also be found as subproblems of scheduling problems. In this talk, I will describe a new branch-and-bound strategy for finding optimal solutions for these problems. In addition, I will give a brief overview of my other, current work on planning and scheduling algorithms and systems. ## 第2回 †日時 2007年5月9日(水) 15:30-17:00 会場 西8号館W棟10階W1008号室 講演者 Danny Calegari 氏 (caltech, tokyo tech) 題目 Real places and torus bundles 要旨 Let M be a hyperbolic 3-manifold, with the structure of a once-punctured torus bundle over the circle. Associated to the hyperbolic structure on M is an algebraic object, the so-called *trace field* K. We show in this talk that K as above has no real places (i.e. it is not isomorphic to a subfield of the real numbers). As a corollary, we give the first known example of a noncompact hyperbolic 3-manifold which contains no immersed totally geodesic surface. ## 第1回 †日時 2007年4月26日(木) 13:20-14:50 会場 西8号館W棟8階W809号室 講演者 T. Y. Li 氏 (Michigan State University) 題目 The numerical computation of the Jordan Canonical form 要旨 The Jordan Canonical Form is highly sensitive to perturbation, and its numerical computation remains a formidable challenge. A two staged numerical algorithm for computing the approximate Jordan Canonical Form will be presented in this talk. At the first stage, the method calculates the Jordan structure of the matrix and an initial approximation to the multiple eigenvalues. The staircase decomposition is then constructed by an iterative algorithm at the second stage. As a result, the approximate Jordan Canonical decomposition along with multiple eigenvalues can be computed with high accuracy even if the underlying matrix is perturbed. |