シンポジウム：錐線形計画とその周辺
このシンポジウムでは、錐線形計画問題やその周辺分野の最新の研究内容について 学術交流を行います。
18:00 より吉祥寺駅周辺で意見交換会を行う予定です。予約の関係で人数を把握したいと思いますので、 参加を希望される方は2月19日（月）までに以下の参加フォームからご登録ください。（登録が必要なのは 意見交換会のみです。）
このシンポジウムでは、錐線形計画問題やその周辺分野の最新の研究内容について 学術交流を行います。
18:00 より吉祥寺駅周辺で意見交換会を行う予定です。予約の関係で人数を把握したいと思いますので、 参加を希望される方は2月19日（月）までに以下の参加フォームからご登録ください。（登録が必要なのは 意見交換会のみです。）
This paper is concerned with the computation of the local Lipschitz constant of feedforward neural networks (FNNs) with activation functions being rectified linear units (ReLUs). The local Lipschitz constant of an FNN for a target input is a reasonable measure for its quantitative evaluation of the reliability. By following a standard procedure using multipliers that capture the behavior of ReLUs, we first reduce the upper bound computation problem of the local Lipschitz constant into a semidefinite programming problem (SDP). Here we newly introduce copositive multipliers to capture the ReLU behavior accurately. Then, by considering the dual of the SDP for the upper bound computation, we second derive a viable test to conclude the exactness of the computed upper bound. However, these SDPs are intractable for practical FNNs with hundreds of ReLUs. To address this issue, we further propose a method to construct a reduced order model whose input-output property is identical to the original FNN over a neighborhood of the target input. We finally illustrate the effectiveness of the model reduction and exactness verification methods with numerical examples of practical FNNs. https://arxiv.org/abs/2310.11104
近年，大規模線形方程式系の数値解法において，ランダム射影に基づく求解法が注目されている．これらの手法を用いることで，従来のクリロフ部分空間法と比較し，高速かつ同等の精度で近似解が得られる．本講演では，一般化シルベスター方程式AX+YB=Cやリアプノフ方程式AX+XA^T=Hの解法において，線形方程式系の求解が計算上のボトルネックになる点に着目し，ランダム射影に基づく高速求解法を紹介する．理論解析では，提案手法による解の残差の確率的上界を導出する．数値実験では，既存の有名なアルゴリズムと比較し，解の精度を維持しつつ高速に近似解が得られることを示す．
We study the convergence rate of the alternating projection method(APM) for the intersection of an affine subspace and the second-order cone. We show that when they intersect non-transversally, the convergence rate is O(k^{−1/2}), where k is the number of iterations of the APM. In particular, when the intersection is not at the origin or forms a half-line with the origin as the endpoint, the obtained convergence rate can be exact because a lower bound of the convergence rate is evaluated. These results coincide with the worst-case convergence rate obtained from the error bound. Moreover, we consider the convergence rate of the APM for the intersection of an affine subspace and the product of two second-order cones. We provide an example that the worst-case convergence rate of the APM is better than the rate expected from the error bound for the example. This is a jointwork with Hiroyuki Ochiai and Yoshiyuki Sekiguchi.
ランク1行列補完問題は一部の行列要素の真の値をヒントにして、ランク1になるように残りの行列要素を決定する問題である。二次制約をもつ非凸最適化問題として定式化できるが、直接的な求解は困難であるために緩和手法が使われる。近年、モーメント行列のトレースを目的関数とした緩和次数2のLasserre緩和問題は厳密（タイト）な最適値を持ち、行列を正確に補完できることが示された。本発表ではLasserre緩和問題の双対である二乗和緩和問題に注目し、この問題が厳密な最適値を持つための目的関数の疎性構造について議論する。また、条件を満たすような目的関数を構成可能な発見的アルゴリズムを提案する。
最適化分野において重要な位置づけにある制約付き多項式最適化問題に対して，third-order tensor空間上の半正定値計画（T-SDP）を用いた緩和手法を提案する． 多項式最適化問題へのアプローチとしては一般にLasserreやParriloによる半正定値計画緩和がよく知られているが，緩和問題はサイズが大きくなりやすく計算コストがかかることが多い． 本提案手法はT-SDPの構造を利用して従来の緩和手法よりも小さなサイズの緩和問題を導出でき，計算コストの削減を目的としている．さらに，提案手法によって導出される緩和問題の実行可能性や大域的最適性などの理論的解析も行う． また，数値実験でテスト問題を用いて従来の緩和手法より優れていることを示す．
We study properties of the central path underlying a nonlinear semidefinite optimization problem, called NSDP for short. The latest radical work on this topic was contributed by Yamashita and Yabe (2012): they proved that the Jacobian of a certain equation-system derived from the Karush-Kuhn-Tucker (KKT) conditions of the NSDP is nonsingular at a KKT point under the second-order sufficient condition (SOSC), the strict complementarity condition (SC), and the nondegeneracy condition (NC). This yields uniqueness and existence of the central path through the implicit function theorem. In this research, we consider the following three assumptions on a KKT point: the strong SOSC, the SC, and the Mangasarian-Fromovitz constraint qualification. Under the absence of the NC, the Lagrange multiplier set is not necessarily a singleton and the nonsingularity of the above-mentioned Jacobian is no longer valid. Nonetheless, we establish that the central path exists uniquely, and moreover prove that the dual component of the path converges to the so-called analytic center of the Lagrange multiplier set. As another notable result, we clarify a region around the central path where Newton’s equations relevant to primal-dual interior point methods are uniquely solvable.