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

本文研究了以下三个问题：（1）线性规划中心轨线的几何结构及其与邻域点算法计算复杂性的关系;（2）基于抽样的鲁棒优化问题近似最优解的鲁棒性能评价;（iii）分层最小二乘法的数学。在（i）中，分析了线性规划原对偶邻域点算法的迭代复杂度与中心轨线几何结构之间的关系。我们定义了中心轨迹的曲率，并证明了曲率积分可以精确地逼近邻域点算法的迭代复杂度。进一步证明了任何线性规划的中心轨线的全曲率都有（线性规划系数矩阵条件数的对数）*（（非负变量个数）的3.5次方）的界.这破 关于我们 证明了线性规划的病态程度只取决于系数矩阵.在（ii）中，我们提出了一种方法来评估用抽样方法计算的磁屏蔽设计鲁棒优化问题的近似最优解的鲁棒性能.在我们的上下文中，鲁棒优化的目的是在屏蔽具有足够厚度的条件下设计具有最小重量的屏蔽，即使当磁场受到一些扰动时。我们开发的鲁棒优化方法通过迭代地加厚屏蔽来进行优化，以适应从扰动域中提取的（磁场的）有限样本集，从标称磁场的最佳屏蔽开始。我们成功地开发了一种基于最大似然估计来估计所获得的磁屏蔽的鲁棒性能的可靠方法。我们证明了上述磁屏蔽优化设计所基于的物理模型是通过将问题的变分形式考虑为加权最小二乘问题，然后通过取极限使权重之间的比率为无穷大.在极限中得到的问题承认作为一个分层最小二乘问题的解释。我们还开发了两个运营商之间的差异，分层最小二乘解决方案和加权最小二乘解决方案的范数上界。该界用加权最小二乘问题的权值与最小二乘问题的系数矩阵的条件数之比来表示。少

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