PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex optimization

Evgeniya Vorontsova, Roland Hildebrand, Alexander Gasnikov, Fedor Stonyakin

arXiv:2106.01946v4math.OCmath.NA

TL;DR

Convex optimization 방법은 모든 문제에 보편적으로 최적인 solver를 찾기보다 문제 구조를 활용해야 한다. 이 교재는 oracle 기반 complexity analysis와 advanced convex-optimization 방법을 전개하며, 일반 convex function에 대한 center-of-gravity method의 optimality를 보이고 accelerated 및 conic 접근법을 제시한다.

  • 문제

    Optimization method는 문제 class에 따라 성능이 다르므로, 효율적인 algorithm은 개별 instance의 구조를 활용해야 한다.

  • 방법

    이 교재는 oracle complexity를 통해 method를 분석하며, 이는 정해진 accuracy에 도달하는 데 필요한 oracle call 수를 측정한다. 또한 accelerated, proximal, interior-point 접근법을 전개한다.

  • 결과

    center-of-gravity method는 first-order oracle을 사용하는 모든 convex function class에 대한 유한차원 optimization에서 optimal하다.

  • 핵심 시사점 및 한계

    Oracle 기반 complexity는 문제 class와 accuracy가 달라지는 상황에서 optimization method를 비교하기 위한 원칙에 근거한 기반을 제공한다.

Abstract

from arXiv · show

This textbook is based on lectures given by the authors at MIPT (Moscow), HSE (Moscow), FEFU (Vladivostok), V.I. Vernadsky KFU (Simferopol), ASU (Republic of Adygea), and the University of Grenoble-Alpes (Grenoble, France). First of all, the authors focused on the program of a two-semester course of lectures on convex optimization, which is given to students of MIPT. The first chapter of this book contains the materials of the first semester ("Fundamentals of convex analysis and optimization"), the second and third chapters contain the materials of the second semester ("Numerical methods of convex optimization"). The textbook has a number of features. First, in contrast to the classic manuals, this book does not provide proofs of all the theorems mentioned. This allowed, on one side, to describe more themes, but on the other side, made the presentation less self-sufficient. The second important point is that part of the material is advanced and is published in the Russian educational literature, apparently for the first time. Third, the accents that are given do not always coincide with the generally accepted accents in the textbooks that are now popular. First of all, we talk about a sufficiently advanced presentation of conic optimization, including robust optimization, as a vivid demonstration of the capabilities of modern convex analysis.

R. Tyrrell Rockafellar [282]

이 교재는 여러 대학의 강의를 바탕으로 convex analysis, optimization modeling, numerical methods를 결합한 2학기 convex optimization 과정을 제시한다. 일부 증명을 생략해 범위를 의도적으로 확장하고, robust optimization을 포함한 고급 conic optimization을 다룬다.

  • Optimization의 토대: 이 교재는 convex analysis, mathematical modeling, numerical methods가 optimization의 세 가지 토대라는 상호의존성을 강조한다.저자들은 이 구성 요소들이 이론과 계산 양쪽에서 서로 연결되어 있다고 설명한다.
  • 강의 구성: 이 교재는 2학기 convex optimization 교육과정을 따른다. Chapter 1에서는 convex analysis와 optimization을 다루고, Chapters 2–3에서는 numerical methods를 다룬다.주된 방향은 MIPT에서 진행된 강의 프로그램이며, HSE, FEFU, V.I. Vernadsky KFU, ASU, University of Grenoble-Alpes에서도 관련 강의가 이루어졌다.
  • 서술상의 특징: 제시된 결과 중 일부의 증명을 생략해 연관성과 구성에 대한 더 폭넓은 내용을 다루는 대신, 교재의 self-contained 성격은 약화된다.이 접근은 일반적으로 주요 사실을 모두 증명하는 고전적 교재와 다르다.
  • 고급 내용: conic optimization과 robust optimization을 포함한 고급 내용은 현대 convex analysis의 역량을 보여주는 사례로서 이례적으로 비중 있게 다뤄진다.이 교재는 convex optimization 문제를 해결하는 데서 modern numerical methods가 하는 역할도 강조한다.

볼록 해석의 기초

이 절에서는 볼록 해석과 최적화의 핵심 결과인 쌍대성, 민감도, 특수 문제, 볼록 원뿔의 표현 방법을 다룬다. 또한 선형계획법, 통계적 검정, 금융수학, 원뿔 최적화와의 연관성도 제시한다.

  • 특수 문제: trust region 문제는 행렬의 최소 고유값에 대응하는 정규화된 고유벡터로 풀리며, C ≻ 0일 때 quadratic programming은 강한 쌍대성을 갖는다.QCQP의 semidefinite relaxation은 제약이 하나뿐일 때 정확하다. relaxation에 rank 1인 해가 존재하기 때문이다.
  • 쌍대성과 민감도: 선형계획법에서 약한 쌍대성은 하한을 제공하고, 강한 쌍대성은 primal과 dual 문제의 유한 최적값이 일치함을 보장한다.섭동된 최적값에 대해 하한과 제약 변화에 대한 민감도 결론을 도출한다.
  • 쌍대성과 민감도: Slater 조건은 convex programming에서 강한 쌍대성을 보장하며, Lagrange multiplier는 제약의 가격으로 해석된다.비활성 제약조건에 해당하는 승수는 영이며, 양의 승수는 활성 제약조건에 대응한다.
  • 쌍대성의 응용: Neyman–Pearson lemma는 주어진 유의수준에서 가장 강력한 검정을 정립하며, Lagrange multiplier 방법은 likelihood ratio를 통해 그 기각 영역을 결정한다.귀무가설에서보다 대립가설에서 훨씬 더 가능성이 높은 점들을 포함한다.
  • 원뿔 최적화: 대칭 원뿔 위의 conic program은 LP, CQP/SOCP 및 SDP를 포괄하며, 표현의 최소 차원은 residual operator의 nonnegative rank와 semidefinite rank와 관련된다.residual operator가 matrix cone을 통해 인수분해되지 않으면 해당 원뿔은 semidefinite representable이 아니며, polyhedral cone은 Lorentz cone의 근사도 제공한다.

볼록 최적화 수치 방법의 효율성 · 2.2 저차원 문제를 위한 볼록 최적화 방법

이 장은 oracle complexity와 문제 구조를 통해 convex optimization의 효율성을 정식화하고, 다양한 convex function class에 대한 upper bound와 lower bound를 제시한다. Section 2.2에서는 이 framework를 low-dimensional problem에 특화하여, one-dimensional search, center-of-gravity method, ellipsoid method와 함께 명시적인 수렴 및 복잡도 보장을 다룬다.

  • 볼록 최적화 수치 방법의 효율성: Accelerated Meta-algorithm을 통해 accelerated gradient method와 tensor method를 구성할 수 있으며, gradient inexactness가 수렴률에 미치는 영향을 분석한다.이 결과들은 부정확한 gradient를 포함한 예시와 함께 최근의 발전으로 제시된다.
  • 볼록 최적화 수치 방법의 효율성: Oracle complexity는 정확도 ε에 도달하는 데 필요한 oracle call 수로 효율성을 측정하며, black-box model에서 상한과 하한을 설정할 수 있게 한다.이 model에서는 iterative method가 local oracle response만 사용한다고 가정하며, oracle call이 반복 횟수와 전체 실행 시간을 결정하는 경우가 많다.
  • 표기법: 표기법 절에서는 Q에 optimizer x*가 존재한다고 가정하고 최적값을 f*=f(x*)로 정의한다.Q는 minimum을 포함하는 영역으로 취급하며, 실질적인 domain이 R^n인 경우 명시적으로 선택한 bounded localization set도 포함한다.
  • 2.2 저차원 문제를 위한 convex optimization method: low-dimensional problem에서 Section 2.2의 method는 oracle call에 대해 차원에 선형 또는 이차적으로 의존하므로, 중간 정도 차원의 문제를 대상으로 한다.또한 Q에 대한 소속 여부를 인증하거나 separating hyperplane을 반환하는 cutting-plane oracle이 필요하다.
  • 2.2.1 일차원 문제 해결 method: 1차원 방법은 derivative-sign 또는 derivative-value 정보를 사용하며, bisection과 golden-section search는 모두 linear convergence를 달성한다.Bisection은 oracle이 query가 global minimizer의 어느 쪽에 있는지 판별할 수 있다고 가정하며, differentiable function에서는 oracle이 derivative sign을 반환한다.
  • 2.2.2 Center-of-gravity method: Center-of-gravity method는 최대 O(nlog(C/ε))회의 first- 및 zeroth-order oracle call로 정확도 ε에 도달하며, 유한 차원 first-order convex optimization에서는 개선할 수 없다.수렴률은 dimension과 초기 불확실성에 의존하며, 주어진 cutting-plane framework에서 minimum에 기하급수적으로 접근한다.
  • 2.2.3 Ellipsoid method: 반지름 R인 Euclidean ball 위의 M-Lipschitz function에 대해 ellipsoid method는 최대 2n^2 log(MR/ε)회의 oracle call로 f*를 ε 이내에서 구한다.Ellipsoid volume은 기하급수적으로 수축하며, 주어진 encoding 조건에서 linear-programming instance는 O(mn^3L)회의 arithmetic operation으로 풀 수 있다.

2.3 부분 gradient 방법

볼록 Lipschitz 목적함수가 비매끄러울 수 있는 경우, stepsize를 적절히 선택하면 표준 subgradient method는 oracle complexity 측면에서 최적이다. 또한 부등식 제약이 있는 볼록 문제를 위해 productive/nonproductive subgradient scheme을 switching하는 방법을 전개하고, 논의를 duality와 비유클리드 노름으로 확장한다.

  • 최적성과 stepsize 선택: Euclidean norm을 사용하는 R^n상의 볼록 Lipschitz 목적함수에 대해, ordinary subgradient method는 ∥∇f(x_k)∥_2 ≤ M이라는 uniform subgradient bound하에서 비매끄러운 최소화에 대한 최적 방법으로 제시된다.여러 최적해가 존재할 때 분석은 가장 가까운 최적해를 선택하고, bounded-subgradient 가정으로부터 method의 수렴 추정치를 도출한다.
  • 최적성과 stepsize 선택: 차원 분석을 통해 반복 횟수의 스케일 N = M^2R^2/ε^2을 얻으며, ε/M^2 또는 R/M에 비례하는 stepsize를 뒷받침한다.여기서 R은 초기점과 최적해 사이의 거리를, M은 subgradient 노름의 상한을, ε은 목표 정확도를 나타낸다.
  • 제약이 있는 subgradient 방법: 닫힌 집합 Q에서의 부등식 제약 볼록 문제에 대해, switching method는 productive steps에서 목적함수 subgradient를 사용하고 nonproductive steps에서 제약식 subgradient를 사용하며, 별도의 Lipschitz bound M_f와 M_g를 둔다.Productive steps에서는 g(x_k) ≤ ε을 만족하고, nonproductive steps에서는 g(x_k) > ε일 때 제약식을 사용한다. Q로의 projection도 scheme의 일부다.
  • 제약이 있는 subgradient 방법: 제약이 있는 switching scheme은 주어진 Lipschitz 및 subgradient 가정하에서 미리 정한 반복 횟수 후 guaranteed convergence estimate를 갖는다.증명에서는 productive iteration과 nonproductive iteration을 별도로 bound하고, productive step의 집합이 공집합이 아님을 보인다.
  • Primal-dual 분석과 일반화: 제약이 있는 algorithm은 primal-dual approximation을 통해서도 분석된다. Slater’s condition하에서 duality gap Δ(x_N, λ_N)은 approximation quality의 자연스러운 척도를 제공하며, 결과는 비유클리드 노름으로 일반화할 수 있다.더 작은 duality gap은 primal 및 dual solution의 더 나은 approximation을 나타낸다.
  • 최적성과 stepsize 선택: 적절한 stepsize를 사용하면, subgradient method는 Lipschitz 목적함수 또는 functional constraint를 갖는 볼록 최적화에서 oracle call 수에 대해 상수배 범위 내에서 최적이다. 반면 gradient descent는 Lipschitz-gradient 목적함수에 대해 최적이 아니다.최적성에 관한 진술은 oracle call 수, 즉 subgradient evaluation 횟수에 대한 lower bound와 연관된다.

2.4 경사하강법 유형의 방법 · 2.5 매끄러운 볼록 최적화 문제에서 경사하강법 수렴 속도 평가

이 절에서는 이차 문제와 매끄러운 볼록 문제를 위한 경사법을 체계화하며, 최적 Chebyshev 방법, Taylor–Drori 방법, Kim–Fessler 방법을 포함한다. 경사하강법의 수렴 속도를 정확히 평가하기 위해 문제를 유한차원 semidefinite relaxation으로 환원하며, 충분히 큰 차원에서는 이 완화가 정확하다.

  • 2.4 경사하강법 유형의 방법: μI_n ⪯ A ⪯ LI_n인 이차 문제에서 경사하강법은 Ax = b 시스템을 풀며, μ와 L은 각각 strong convexity와 gradient의 Lipschitz 성질을 규정한다.분석은 유클리드 노름에서 수행되며 일정한 step을 사용하는 방법군을 다룬다.
  • 2.4 경사하강법 유형의 방법: 표준 경사하강법의 수렴 평가는 일반적으로 개선할 수 없지만, Chebyshev 방법은 더 일반적인 방법군에서 minimax 최적 평가를 달성한다.step을 최적으로 선택해도 평가는 위에서 제시한 최적 수준까지만 개선된다.
  • 2.4 경사하강법 유형의 방법: μ = 0이면 argument에 대한 수렴은 사라지지만, h ≤ 1/L인 경우 function에 대한 수렴은 유지된다.합리적인 선택은 h = 1/L이며, conjugate gradient는 μ와 L을 몰라도 적응성을 유지한다 [66].
  • 2.4 경사하강법 유형의 방법: μ-strongly convex이고 L-Lipschitz gradient를 갖는 문제에서는 가속 Taylor–Drori 방법이 최적이며, 2N+1 ≤ n일 때 이에 대응하는 lower bound가 성립한다 [298].이는 제시된 수렴 속도를 해당 방법군에서의 최적성과 연결한다.
  • 2.4 경사하강법 유형의 방법: L-Lipschitz gradient를 갖는 볼록 문제에서는 가속 Kim–Fessler 방법이 최적이며, lower bound는 N+1 ≤ n일 때 성립한다.이 방법과 대응하는 lower bound는 strong convexity를 요구하지 않는 볼록 문제군에 속한다.
  • 2.5 매끄러운 볼록 최적화 문제에서 경사하강법 수렴 속도 평가: F_μ,L에서 경사하강법의 속도를 정확히 평가하기 위해, 함수의 존재성을 유한한 값·점·gradient 집합에 대한 이차 조건으로 환원한다.일정한 step에 대한 분석에서는 초기점을 최솟값 주변 반지름 R인 공 안에 둔다.
  • 2.5 매끄러운 볼록 최적화 문제에서 경사하강법 수렴 속도 평가: semidefinite relaxation은 d ≥ 2k+1일 때 정확해지므로, 임의의 차원을 갖는 문제에서 방법의 속도를 정확히 특성화한다.벡터에 대한 이차식은 해당 벡터들의 Gramian 원소에 대한 선형식으로 대체된다.
  • 2.5 매끄러운 볼록 최적화 문제에서 경사하강법 수렴 속도 평가: function value 기준에서 최악의 함수는 일차원 piecewise-quadratic 형태를 가지며, 최적 step은 k에 의존하고 k → ∞일 때 2/(L+μ)로 수렴한다.이 형태와 점근적 step은 F_μ,L 함수군에 대한 수치적·해석적 분석에서 따른다.

2.6 조건부 그래디언트 방법 또는 프랭크–울프 알고리즘 · 2.7 가속 메타 알고리즘

프랭크–울프 방법은 목적함수를 선형화하고, compact convex set 위에서 선형함수 최소화로 projection을 대체하여 다양한 norm과 희소해를 다룰 수 있게 한다. 가속 메타 알고리즘은 smooth convex optimization의 가속 방법들을 하나의 proximal wrapper로 통합하며, 추가 조건하에서 최적 complexity bound를 달성한다.

  • 2.6 조건부 그래디언트 방법 또는 프랭크–울프 알고리즘: 프랭크–울프 방법은 각 iteration에서 Q 위 함수의 선형 근사를 최소화하고, 구한 점을 이동 방향으로 사용한다.이 방법은 compact convex Q에서의 linear optimization이 원래 문제보다 간단하다고 가정한다.
  • 2.6 조건부 그래디언트 방법 또는 프랭크–울프 알고리즘: 프랭크–울프 방법의 적용 가능성은 Q에서의 linear optimization이 얼마나 간단한지에 의해 결정된다. polytope에서는 linear program이고, 일부 ball과 그 projection에서는 subproblem을 명시적으로 풀 수 있다.각 iteration에서 f(x_k) − μ_k는 duality gap의 상한이다.
  • 2.6 조건부 그래디언트 방법 또는 프랭크–울프 알고리즘: 프랭크–울프 방법은 실제 projection을 필요로 하지 않고 norm의 종류에 의존하지 않으며 sparsity를 활용할 수 있다.polytope에서는 iteration point가 꼭짓점들의 convex combination으로 표현되며, vertex인 초기점에서는 k iteration 후 k개 꼭짓점의 combination이 된다.
  • 2.6 조건부 그래디언트 방법 또는 프랭크–울프 알고리즘: 프랭크–울프 방법은 affine invariant하다. 즉, x_0가 같으면 affine coordinate transformation 후에도 동일한 점의 sequence를 생성한다.이 성질은 initial point가 일치할 때 유지된다.
  • 2.7 가속 메타 알고리즘: 가속 메타 알고리즘은 하나의 가속 proximal wrapper만으로 smooth convex unconstrained optimization에서 알려진 모든 가속 방법을 얻을 수 있음을 보인다.일부 경우에는 complexity bound와 lower bound 사이의 logarithmic gap을 제거한다.
  • 2.7.1 주요 결과: 정리 2.9는 p≥1 및 H≥(p+1)L_p,f에서 가속 메타 알고리즘의 수렴을 보장하며, p≥2에서는 정리에 제시된 bound에 따라 정확도 ε에 도달한다.보조 문제는 부정확하게 풀 수 있으며, 이 경우 bound (2.41)의 우변이 12/5의 인자로 변한다.
  • 2.7.1 주요 결과: 가속 메타 알고리즘의 수렴 속도 bound는 Lipschitz p차 도함수를 갖는 convex 문제에 대해 수치 인자 c_p를 제외하면 optimal하다.F가 uniformly convex이면 optimal method는 restart를 사용하여 UM을 기반으로 구성되며, 보조 문제의 계산 횟수는 정리 2.10에서 정해진다.

2.8 가속 메타-알고리즘의 응용

이 절에서는 가속 메타-알고리즘(УМ)이 컴포지트 최적화, 프록시멀 문제, 새들 문제를 위한 가속 방법을 어떻게 생성하는지 보인다. 이 보편적 구조를 사용하면 원하는 정확도에 대해 로그 인자를 제외하면 최적인 방법을 얻을 수 있다.

  • 컴포지트 최적화: 단순한 하위 문제 (2.40)의 경우, УМ은 임의 차수의 컴포지트 최적화를 위한 가속 방법을 기술하며, g는 비매끄러울 수 있다.알고리즘의 5번째 줄에서는 g의 subgradient를 사용하므로, (2.40) 우변의 subgradient가 영에 가까워진다.
  • 프록시멀 방법: p=1, f≡0, H>0일 때 УМ은 보조 문제를 매우 정확하게 풀 필요가 없는 가속 프록시멀 방법을 제공한다 [193].하위 문제의 강한 2-균등 볼록성 덕분에 그 복잡도는 원래 문제의 원하는 정확도와 무관해진다.
  • Catalyst: Catalyst 는 가속 프록시멀 포락선을 비가속 방법의 래퍼로 해석하는 УМ의 특수한 경우로 얻어진다.이 방법들은 적절한 H를 선택하여 각 반복에서 보조 문제 (2.40)을 푼다.
  • Saddle 문제: saddle 문제에서 УМ은 의 유사한 scheme을 로그 배만큼 개선하고, 이를 영이 아닌 f와 h로 일반화한다 [319].이 scheme은 비볼록-강오목 saddle 문제로도 일반화된다 [325].
  • 새들 문제: УМ은 볼록-오목 매끄러운 새들 문제를 위한 최적 gradient 방법을 볼록 최적화의 최적 가속 방법을 기반으로 구성할 수 있게 한다.f≡0 및 h≡0일 때 이는 알려진 하한으로 확인되며, 이 구조는 로그 인자를 제외하면 최적성을 달성한다.

2.9 내부점법

내부점법은 원뿔 내부에서 반복점을 생성해 conic 문제를 해결한다. 적용 가능성은 작은 파라미터를 갖는 효율적으로 계산 가능한 self-concordant barrier에 의해 결정된다. central path를 따르면 short-step의 다항식 복잡도가 보장되며, symmetric 및 self-scaled cone에서는 long-step으로 실제 수렴을 크게 가속할 수 있다.

  • 일반적 개요: 내부점법은 conic 문제에 적용되며, extreme point를 따라가는 방법과 달리 convex cone의 내부에서 반복점의 수열을 생성한다.적용 가능성은 효율적으로 계산 가능한 self-concordant barrier의 존재로 결정되며, short-step은 다항식 복잡도를 갖는다.
  • Central path 추적: central path-following method에서 파라미터 nu를 갖는 barrier는 log tau를 nu^-1/2 정도 증가시키며, 이는 tau를 1+O(nu^-1/2)배 하는 것과 같다.barrier 파라미터 nu가 작을수록 방법의 수렴은 빨라진다.
  • 최종 조건: 내부점법에는 작은 파라미터 nu를 갖는 효율적으로 계산 가능한 logarithmically homogeneous self-concordant barrier가 필요하며, central path는 conic 제약을 보조 문제의 족으로 대체한다.각 보조 문제는 self-concordant function의 최소화로 환원된다.
  • 특수 barrier: symmetric cone에서 표준 barrier는 최적 파라미터를 가지며 self-scaled이므로, 특히 효율적인 long-step이 가능하다.universal barrier와 canonical barrier에 대해서는 파라미터 nu=n인 구성이 제시되며, canonical barrier는 dual cone 위의 canonical barrier와 dual 관계에 있다.
  • 복잡도와 step 변형: short-step은 O(sqrt(nu) log epsilon)회의 반복으로 주어진 정확도에 도달하는 반면, self-scaled barrier에서는 경계까지의 거리 정도인 step을 선택할 수 있다.실제로 long-step은 보통 수십 회의 반복만 필요하며 문제의 차원에 대한 의존성도 약하다.

2.10 부정확한 함수 모델의 개념과 이러한 모델의 존재가 허용되는 문제를 위한 그래디언트 유형 방법

이 절에서는 부정확한 함수 모델의 개념을 발전시키고 이를 비가속 및 가속 그래디언트 방법에 적용한다. 여기에는 composite optimization과 보조 하위 문제의 부정확한 해법이 포함된다. 비가속 방법에는 prox 함수의 1-강한 볼록성이 필요하지 않은 반면, 가속 방법은 최적 평가를 달성하지만 오차 누적에 더 민감함을 보인다.

  • 함수 모델과 composite optimization: 함수 모델의 개념은 가속 그래디언트 방법을 composite convex optimization 문제에 적용할 수 있게 하며, smooth convex 문제의 경우와 유사한 수렴 평가를 제공한다.이를 통해 폭넓은 문제군을 하나의 모델 부등식으로 기술할 수 있다.
  • 비가속 방법: 비가속 그래디언트 방법은 임의의 점에서 부정확한 모델을 갖는 문제에 적용할 수 있으며 prox 함수의 1-강한 볼록성을 요구하지 않는다.prox 함수의 볼록성과 모델 조건은 수렴 속도 평가를 보장하며, 충분히 폭넓은 상대적 smooth convex 문제군에서 이러한 평가는 최적이다 [147].
  • prox 함수와 보조 문제: 전체 공간에서 1-강하게 볼록한 prox 함수는 해를 사전에 국소화하지 않고도 비가속 및 가속 방법을 적용할 수 있게 한다. 희소성에서는 1-노름을 선택하는 것이 자연스럽다.일반적인 가정하에서도 보조 하위 문제에 대해 선형 수렴 속도를 얻을 수 있다.
  • 가속 방법: 정확한 oracle을 사용하는 경우 가속 방법은 smooth convex 문제에서 상수까지 최적이지만, 부정확한 oracle에서는 오차가 누적될 수 있다.알고리즘 2.12에는 상수 8이 제시되며, 더 나은 상수를 대략 1로 얻는 것은 불가능하다.
  • 부정확한 하위 문제: 가속 방법은 중간 하위 문제 해법의 오차에 더 강건하지만, 요구되는 하위 문제의 정확도는 반복 번호에 따라 증가한다.근사해 개념을 사용하면 이러한 오차가 그래디언트 방법의 최종 결과에 미치는 영향을 고려할 수 있다.
  • Regularization과 restart: 강하게 볼록한 문제를 푸는 방법은 regularization과 가속 방법의 restart를 통해 일반적인 볼록 문제에 적용할 수 있다.이 전환은 regularization parameter μ = ε/(2R^2)를 사용하며 ε-정확한 해를 보장한다.

2.11 부정확한 gradient의 다른 개념

이 절에서는 부정확한 gradient의 여러 개념을 비교한다. 표준 모델은 매끄러운 strongly convex 문제에서도 regularization이나 조기 중단 없이는 나쁜 추정치를 줄 수 있는 반면, 정교화된 모델은 오차 누적을 제어하면서 목표 정확도에 도달하도록 한다. ill-posed inverse problem의 예를 통해 이러한 부정확한 gradient가 수치적으로 풀어야 하는 direct 및 adjoint boundary-value problem 두 개를 통해 계산됨을 보인다.

  • 부정확한 gradient의 개념: 표준 부정확 gradient 개념은 regularization이나 조기 중단 없이는 매끄러운 strongly convex 문제에서도 좋은 추정치를 보장하지 않는다.퇴화된 경우 하한에는 분모에 작은 strong convexity 상수 μ가 포함되며, accelerated method에서는 더 큰 문제가 예상된다.
  • 부정확한 gradient의 개념: f(x_k) − f(x*) = ε은 non-accelerated method와 accelerated method에서 δ(2.115) ≃ ε/˜R일 때 exact gradient의 경우와 같은 차수의 반복 횟수로 달성된다.이 명제는 생성된 점들과 해 사이의 최대 거리 ˜R가 유계라는 가정을 전제로 한다.
  • 부정확한 gradient의 개념: ˜R가 유계이면 정교화된 개념이 오차를 제어하지만, 퇴화된 문제에서는 이 조건이 깨질 수 있다. regularization과 조기 중단으로 문제를 완화한다.μ ≃ ε/R^2인 regularization은 ˜R ≃ R을 초래하며, 조기 중단은 오차 누적을 제한하는 대안으로 사용된다.
  • 예: ill-posed inverse problem: ill-posed inverse problem에서는 direct 및 adjoint boundary-value problem을 수치적으로만 풀 수 있으므로 목적 functional의 gradient를 근사적으로 계산한다.관측값 b로부터 계수 q를 추정하는 inverse problem에서 optimization problem은 gradient 계산을 problem (P)와 problem (D)의 풀이로 환원한다.
  • 예: ill-posed inverse problem: ∇𝔍(q)(y)의 계산은 정사각형 위에서 elliptic type의 well-posed initial-boundary-value problem 두 개를 푸는 것으로 환원된다.먼저 direct problem (P)을 푼 다음 adjoint problem (D)을 풀고, adjoint solution을 통해 gradient를 얻는다.

예제 문제

이 절에서는 최적 수송, 다항식 비음성, 준정부호 완화 문제에 convex optimization을 적용하는 방법을 보여준다. 해의 존재, convex formulation, 정확도 및 도출된 방법의 계산 복잡도를 다룬다.

  • 최적 수송: 최적 수송 이론은 공간의 기하를 고려하여 확률 분포를 비교하며, Wasserstein 거리는 수송 문제의 최적값으로 표현된다.Kantorovich 완화는 질량의 분할을 허용하여 동일한 크기의 히스토그램 비교에 대한 Monge formulation의 제약을 제거하며, 일반적인 가정하에서 해가 존재한다.
  • 최적 수송: Wasserstein barycenter를 구하는 문제는 해의 존재가 증명된 convex optimization 문제로 정식화되며, 효율적인 수치 방법을 사용할 수 있다.도출된 smooth unconstrained problem에는 가속된 primal-dual gradient method를 적용할 수 있으며, dual space에서의 수열을 통해 원문제의 해를 복원한다.
  • 다항식 비음성: 다항식의 sums of squares는 positive definite matrix cone의 projection과 선형적으로 연결되며, nonnegative polynomial cone과의 정확한 일치는 min(d, n) ≤ 2 또는 (d, n) = (4, 3)인 경우에만 성립한다.nonnegative matrix cone에 대한 소속성 판정은 co-NP-complete인 반면, 다항식의 희소성으로 인해 훨씬 작은 행렬을 사용하는 경우가 많다.
  • 준정부호 완화: 콤팩트 집합에 대한 semidefinite relaxation hierarchy는 d→∞에서 점근적으로 정확하지만, 고정 차수 relaxation이 정확하려면 최소화 대상 함수가 상수여야 한다.기술하기 어려운 조건을 semidefinite 및 선형 necessary conditions의 집합으로 대체하면 원문제의 semidefinite relaxation을 얻는다.
  • 계산 복잡도: dual problem으로 전환하면 원래 프로그램의 O(n7)에 비해 문제 해결 복잡도가 감소한다. 변수 수의 감소가 cone의 복잡도 증가를 상쇄하기 때문이다.primal-dual pair에 대해 알고리즘은 dual variables를 국소화할 때 원문제의 2ε-근사해를 보장하며, 희소성은 iteration cost를 추가로 줄인다.

교재

교육용 출판물에는 저자, 편집자 및 기술 제작에 관한 정보가 수록되어 있으며, 11.06.2021에 250부 발행으로 인쇄 확정되었다.

  • 발행 정보: 이 교재에는 저자 예브게니야 알렉세예브나 보론초바, 롤란트 팔코비치 힐데브란트, 알렉산드르 블라디미로비치 가스니코프와 편집자, 교정 및 편집 조판 담당자가 명시되어 있다.편집자: В. А. Дружинина, И. А. Волкова, О. П. Котова; 교정 및 computer 조판 담당자 — Н. Е. Кобзева; 표지 디자인 — Е. А. Казённова.
  • 발행 정보: 11.06.2021 인쇄 승인을 받았으며, 판형은 60×84 1/16, 분량은 22,75 인쇄용지와 20,3 출판 회계용지, 발행 부수는 250부다.주문 번호 58이 기재되어 있다.
  • 발행 정보: 이 책은 모스크바의 ООО «Печатный салон ШАНС»가 제공된 원고·편집본에 완전히 부합하도록 인쇄했다.발행 정보에는 인쇄소 주소와 전화번호가 기재되어 있다.
Loading 2106.01946v4…