Contributed Session Mon.3.H 2036

Monday, 15:15 - 16:45 h, Room: H 2036

Cluster 4: Conic programming [...]

Semidefinite programming applications


Chair: Tomohiko Mizutani



Monday, 15:15 - 15:40 h, Room: H 2036, Talk 1

Sunyoung Kim
A successive SDP relaxation method for distance geometry problems

Coauthors: Masakazu Kojima, Makoto Yamashita


We present a numerical method using cliques and successive application of
sparse semidefinite programming relaxation (SFSDP) for determining the
structure of the conformation of large molecules from the Protein Data Bank.
A subproblem of a clique and its neighboring nodes is initially solved by SFSDP
and refined by the gradient method. This subproblem is gradually
expanded to the entire problem by fixing the nodes computed with high
accuracy as anchors and successively applying SFSDP. Numerical experiments
show that the performance of the proposed algorithm is robust and efficient.



Monday, 15:45 - 16:10 h, Room: H 2036, Talk 2

Robert Michael Freund
Implementation-robust design: Modeling, theory, and application to photonic crystal design with bandgaps

Coauthors: Han Men, Ngoc Cuong Nguyen, Jaime Peraire, Joel Saa-Seoane


We present a new theory for incorporating considerations of implementation into optimization models quite generally. Computed solutions of many optimization problems cannot be implemented directly due to (i) the deliberate simplification of the model, and/or (ii) human factors and technological reasons. We propose a new alternative paradigm for treating issues of implementation that we call "implementation robustness.'' This paradigm is applied to the setting of optimizing the fabricable design of photonic crystals with large band-gaps. Such designs enable a wide variety of prescribed interaction with and control of mechanical and electromagnetic waves. We present and use an algorithm based on convex conic optimization to design fabricable two-dimensional photonic crystals with large absolute band gaps. Our modeling methodology yields a series of finite-dimensional eigenvalue optimization problems that are large-scale and non-convex, with low regularity and non-differentiable objective. By restricting to appropriate eigen-subspaces, we reduce the problem to a sequence of small-scale SDPs for which modern SDP solvers are successfully applied.



Monday, 16:15 - 16:40 h, Room: H 2036, Talk 3

Tomohiko Mizutani
SDP relaxations for the concave cost transportation problem

Coauthor: Makoto Yamashita


We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP) with p suppliers and q demanders. The key idea of the relaxation methods is in the change of variables to CCTPs, and due to this, we can construct SDP relaxations whose matrix variables depend on min{p, q} at each relaxation order. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order goes to infinity. We show the performance of the relaxation methods through numerical experiments.


  short term loans . This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.