Akira Kitaoka

Akira Kitaoka

We consider the approximation of minimal geodesics between two closed sets in $\mathbb{R}^D$ endowed with a smooth Riemannian metric. The continuous problem is formulated as the minimization of the energy functional over piecewise smooth curves joining the two sets. We study discrete approximations obtained by finite differences together with numerical integration, and reconstruct continuous curves from discrete minimizers by linear interpolation. Our main result is a direct convergence analysis of the trapezoidal-rule discretization. We prove that the energy of the linearly interpolated discrete minimizer converges to the minimum energy, and that the squared length of the reconstructed curve converges to the squared minimal length, both with rate $O(N^{-1/2})$ as the number of subintervals $N$ tends to infinity. We also obtain the corresponding reconstruction estimates for the left-endpoint rule. In addition, we give an explicit example showing that a direct discretization of the length functional does not, in general, converge to the minimal length.

Akira Kitaoka

We consider the inverse optimization problem of estimating the weights of the objective function such that the given solution is an optimal solution for a mixed integer linear program (MILP). In this inverse optimization problem, the known methods exhibit inefficient convergence. Specifically, if $d$ denotes the dimension of the weights and $k$ the number of iterations, then the error of the weights is bounded by $O(k^{-1/(d-1)})$, leading to slow convergence as $d$ increases. We propose a projected subgradient method with a step size of $k^{-1/2}$ based on suboptimality loss. We theoretically show and demonstrate that the proposed method efficiently learns the weights. In particular, we show that there exists a constant $γ> 0$ such that the distance between the learned and true weights is bounded by $ O\left(k^{-1/(1+γ)} \exp\left(-\frac{γk^{1/2}}{2+γ}\right)\right), $ or the optimal solution is exactly recovered. Furthermore, experiments demonstrate that the proposed method solves the inverse optimization problems of MILP using fewer than $1/7$ the number of MILP calls required by known methods, and converges within a finite number of iterations.

Akira Kitaoka

In mixed-integer linear programming, data-driven inverse optimization that learns the objective function and the constraints from observed data plays an important role in constructing appropriate mathematical models for various fields, including power systems and scheduling. However, to the best of our knowledge, there is no known method for learning both the objective functions and the constraints. In this paper, we propose a two-stage method for a class of problems where the objective function is expressed as a linear combination of functions and the constraints are represented by functions and thresholds. Specifically, our method first learns the constraints and then learns the objective function. On the theoretical side, we show the proposed method can solve inverse optimization problems in finite dataset, develop statistical learning theory in pseudometric spaces and sub-Gaussian distributions, and construct a statistical learning for inverse optimization. On the experimental side, we demonstrate that our method is practically applicable for scheduling problems formulated as integer linear programmings with up to 100 decision variables, which are typical in real-world settings.

Akira Kitaoka, Riki Eto

We prove Wasserstein inverse reinforcement learning enables the learner's reward values to imitate the expert's reward values in a finite iteration for multi-objective optimizations. Moreover, we prove Wasserstein inverse reinforcement learning enables the learner's optimal solutions to imitate the expert's optimal solutions for multi-objective optimizations with lexicographic order.

Akira Kitaoka, Riki Eto

We show the convergence of Wasserstein inverse reinforcement learning for multi-objective optimizations with the projective subgradient method by formulating an inverse problem of the multi-objective optimization problem. In addition, we prove convergence of inverse reinforcement learning (maximum entropy inverse reinforcement learning, guided cost learning) with gradient descent and the projective subgradient method.