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

我们研究了以下三个主题：(I)线性规划中心轨迹的几何结构及其与内点算法计算复杂性的关系；(Ii)基于抽样的稳健优化问题近似最优解的稳健性能的评估；(Iii)分层最小二乘方法的数学。我们定义了中心轨迹的曲率，并证明了内点算法的迭代复杂度精确地逼近于曲率积分。此外，我们还证明了任何线性规划的中心轨迹的全曲率有界于(线性规划系数矩阵的条件数的对数)*((非负变量的个数)的3.5次方)。这是Sh…更重要的是，线性规划的病态程度只取决于系数矩阵。在(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