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.


  There are three major facts that should be watched out for in all payday loans in the United States. In rare cases, the smarting in eyes and the tumefaction of eyelids can happen. In case of long term Cialis Black administration the side effects become less perceptible or disappear at all.