A study on interior-point algorithms and robust optimization for Ill-conditioned optimization problems

我们研究了以下三个主题：(i)线性规划中心轨迹的几何结构及其与内点算法计算复杂度的关系；（ii）评估基于抽样的鲁棒优化问题的近似最优解的鲁棒性能；（三）分层最小二乘法的数学。在(i)中，我们分析了线性规划的原对偶内点算法的迭代复杂度与中心轨迹的几何结构之间的关系。我们定义了中心轨迹的曲率，并证明了内点算法的迭代复杂度可以用曲率积分精确逼近。进一步，我们建立了任何线性规划的中心轨迹的总曲率以（线性规划的系数矩阵的条件数的对数）*（（非负变量数）的3.5次方）为界。由此可见，线性规划的病态程度仅取决于系数矩阵。在（ii）中，我们开发了一种方法来评估用抽样方法计算的磁屏蔽设计鲁棒优化问题的近似最优解的鲁棒性能。在本文中，鲁棒优化的目的是在磁场受到一定扰动时，在保证屏蔽层厚度的前提下，设计出重量最小的屏蔽层。所开发的鲁棒优化方法从标称磁场的最优屏蔽开始，通过迭代增厚屏蔽以适应从摄动域提取的有限样本集（磁场）来进行优化。我们成功地开发了一种基于极大似然估计的可靠方法来估计所获得的磁屏蔽的鲁棒性能。在（iii）中，我们证明了上述磁屏蔽优化设计所基于的物理模型是通过将问题的变分公式考虑为加权最小二乘问题，然后取极限，使权重之间的比值趋于无穷而得到的。在极限下得到的问题可以解释为分层最小二乘问题。我们还建立了两个算子之间的差模的界，给出了分层最小二乘解和加权最小二乘解。该边界用加权最小二乘问题的权值与最小二乘问题的系数矩阵的条件数之比来表示。少

We studied the following three topics : (i) geometrical structure of central trajectories of linear programming and its relation to computational complexity of interior-point algorithms ; (ii) evaluation of robust performance of approximate optimal solutions to robust optimization problems based on sampling ; (iii) mathematics of layered-least squares methods.In (i), we analyzed relations between the iteration-complexity of the primal-dual interior-point algorithms for linear programming and geometrical structure of the central trajectories. We defined a curvature of the central trajectory and proved that the iteration-complexity of the interiorpoint algorithms is precisely approximated with the curvature integral. Furthermore, we established that the total curvature of the central trajectory of any linear program is bounded by (the logarithm of the condition number of the coefficient matrix of the linear program)*((the number of the nonnegative variables) to the power of 3.5). This sh … More ows that the degree of ill-condition of a linear program just depends on the coefficient matrix.In (ii), we developed a method to evaluate robust performance of an approximate optimal solution to a robust optimization problem of magnetic shielding design computed with a sampling method. The purpose of the robust optimization in our context is to design a shield with the least weight under the condition that the shield has enough thickness even when the magnetic field is subject to some perturbation. The method of robust optimization we developed performs optimization by thickening the shielding iteratively to adapt to the set of finite samples (of magnetic field) drawn from the domain of perturbation, starting from the optimal shielding for nominal magnetic field. We succeeded to develop a solid method to estimate robust performance of the obtained magnetic shielding based on the maximum likelihood estimation.In (iii), we demonstrated that the physical model on which the aforementioned optimal design of the magnetic shielding is based is obtained by considering a variational formulation of the problem as a weighted least squares problem and then by taking the limit letting the ratios among the weights to infinity. The problem obtained in the limit admits an interpretation as a layered-least squares problem. We also developed a bound on the norm of difference between two operators giving the layered least squares solution and the weighted least squares solution. The bound is written in terms of the ratios among the weights of the weighted least squares problem and the condition number of the coefficient matrix of the least squares problem. Less