Most of the existing descent methods suffer from the computational burden in finding a descent direction of the objective function at the point under consideration. This is partly because they must solve a sequence of constrained quadratic programs to obtain a search direction.
In this thesis, we suggest a new direction finding subproblem. Our subproblem is minimizing a convex function which is the sum of a norm function and the original objective function. And we present an algorithm based on the subproblem and establish convergence properties for the algorithm. In particular, the algorithm is implementable when a certain norm function is introduced. Furthermore, our implementable algorithm solves a sequence of linear programs, instead of a sequence of constrained quadratic programs, to obtain a descent direction.
Limited computational experience with the implementable algorithm is also reported. In view of the computational experience, it is expected that our algorithm will complete successfully with other descent algorithms for minimizing nonsmooth convex functions.
미분불가능 최적화(nonsmooth optimization)를 위한 기존의 descent method들은 목적 함수의 감소 방향을 찾기 위해 많은 양의 계산을 필요로 하고 있다. 이것은 감소 방향을 찾기 위해 일련의, 제약식을 갖는 2차 계획 문제들을 풀어야 하기 때문이다.
본 논문에서는 기존의 방향 찾기 부문제들과 다른, 새로운 부문제를 제안했다. 우리의 부문제는 norm 함수와 본래의 목적 함수를 더한 볼록 함수를 최소화한다. 특히, 특정한 norm이 도입되는 경우, 일련의 선형 계획 문제를 풀어서 제안된 부문제를 근사적으로 해결할 수 있다. 그러한 방향 찾기 부문제에 기초한 하나의 알고리듬과 그 알고리듬의 수렴 특성도 또한 제시되었다.
알고리듬을 구현하고 시험해 본 결과, 우리의 알고리듬이 미분불가능 최적화를 위한 실제의 문제들에 잘 적용될 것으로 기대된다. 특히 우리의 알고리듬이 대규모 최적화 문제에 잘 적용될 것으로 기대되는데, 이것은 탐색방향을 찾기 위해 우리의 알고리듬은 일련의 2차 계획 문제들 대신 일련의 선형 계획 문제들을 풀기 때문이다.
