2025-11-13T13:58:10.839999

Proximity results in convex mixed-integer programming

Kocuk, Ramirez

We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of the continuous relaxation when the recession cone is full-dimensional. If the recession cone is not full-dimensional we give sufficient conditions to obtain a finite integrality gap. We then specialize our analysis to second-order conic IPs. In the case the feasible region is defined by a single Lorentz cone constraint, we give upper bounds on proximity and integrality gap in terms of the data of the problem (the objective function vector, the matrix defining the conic constraint, the right-hand side, and the covering radius of a related lattice). We also give conditions for these bounds to be independent of the right-hand side, akin to the linear IP case. Finally, in the case the feasible region is defined by multiple Lorentz cone constraints, we show that, in general, we cannot give bounds that are independent of the corresponding right-hand side. Although our results are presented for the integer lattice $\mathbb{Z}^n$, the bounds can be easily adapted to work for any general lattice, including the usual mixed-integer lattice $\mathbb{Z}^{n_1}\times\mathbb{R}^{n_2}$, by considering the appropriate covering radius when needed.

academic

볼록 혼합정수계획법의 근접성 결과

기본 정보

논문 ID: 2501.00638
제목: Proximity results in convex mixed-integer programming
저자: Burak Kocuk (Sabancı University), Diego A. Morán R. (Rensselaer Polytechnic Institute)
분류: math.OC (최적화 및 제어)
발표 시간: 2024년 12월 31일
논문 링크: https://arxiv.org/abs/2501.00638

초록

본 논문은 볼록정수계획법(IP)과 그 연속 완화(continuous relaxation) 사이의 근접성(proximity)과 정수성 간격(integrality gap) 문제를 연구한다. 저자들은 연속 완화 가능영역의 recession cone이 만차원일 때, 이러한 값들을 recession cone의 매개변수로 상한 추정할 수 있음을 증명했다. 만차원이 아닌 recession cone의 경우, 유한 정수성 간격을 얻기 위한 충분조건을 제시한다. 논문은 특히 이계 원뿔 정수계획법을 분석하며, 단일 Lorentz 원뿔 제약 조건 하에서 문제 데이터를 이용한 근접성과 정수성 간격의 상한을 제공하고, 이러한 상한이 우변 항과 무관한 조건을 제시한다.

연구 배경 및 동기

문제 정의 및 중요성

핵심 문제: 볼록정수계획법 $\min\{\alpha^T x : x \in S \cap \mathbb{Z}^n\}$ 과 그 연속 완화 $\min\{\alpha^T x : x \in S\}$ 사이의 거리 관계 연구. 여기서 $S \subseteq \mathbb{R}^n$ 은 볼록집합이다.
두 가지 핵심 개념:
- 근접성(Proximity): 연속 완화 최적해에서 가장 가까운 정수 가능해까지의 거리
- 정수성 간격(Integrality gap): 정수계획법 최적값과 연속 완화 최적값의 차이
연구의 의의:
- 완화의 품질을 정량화하여 알고리즘 설계에 이론적 기초 제공
- 볼록 이차 게임 등 응용 분야에서 중요한 가치 보유
- 선형정수계획법의 고전적 결과를 비선형 경우로 확장

기존 연구의 한계

선형 경우의 완전한 결과: Cook 등이 선형 IP의 근접성 상한이 우변 항과 무관함을 증명
비선형 경우의 제한된 연구: 분리가능 볼록함수 또는 분리가능 이차함수의 특수한 경우에만 한정
일반적 프레임워크의 부재: 일반 볼록 제약 집합을 다루는 체계적 방법 부족

핵심 기여

일반 볼록 IP의 근접성 결과: Recession cone이 만차원일 때 최적해와 무관한 근접성 및 정수성 간격 상한 제시
이계 원뿔 IP의 전문적 분석: 단순 이계 원뿔 집합에 대한 구조적 결과 및 근접성 상한 제공
우변 항 의존성 분석: 다중 Lorentz 원뿔 제약 조건 하에서 상한이 일반적으로 우변 항과 무관할 수 없음을 증명
혼합정수 격자의 일반화: 결과를 일반 격자 $\mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$ 로 확장
반례 구성: 구체적 예시를 통해 비선형 경우의 복잡성 설명

방법론 상세 설명

이론적 프레임워크

1. 일반 볼록집합의 근접성 분석

정리 2 (만차원 recession cone의 경우): $S$ 를 recession cone $K := \text{rec.cone}(S)$ 가 정칙인 볼록집합이라 하자. $x̂ \in S$ 에 대해:

$\text{Prox}_{x̂}(S) := \min_{x \in S \cap \mathbb{Z}^n} \|x - x̂\|_2 \leq \frac{\sqrt{n}}{2}\left(\frac{1}{\Psi_{K,\|\cdot\|_2}} + 1\right)$

여기서 $\Psi_{K,\|\cdot\|}$ 는 원뿔 $K$ 의 핵심 매개변수이다:

$\Psi_{K,\|\cdot\|} := \max_{d \in K} \left\{\min_{f \in K^*} \{f^T d : \|f\|_* = 1\} : \|d\| = 1\right\}$

2. 혼합정수 격자의 피복 반경

정의 4: 만차원 혼합정수 격자 $L(E,F) = \{Ez + Fy : z \in \mathbb{Z}^{n_1}, y \in \mathbb{R}^{n_2}\}$ 의 피복 반경:

$\mu(E,F) = \max_x \left\{\min_{x'} \{\|x - x'\|_2 : x' \in L(E,F)\} : x \in \mathbb{R}^n\right\}$

핵심 성질 (사실 1): 직교 표현에 대해 $\mu(E,F) = \mu(E)$ 이므로, 피복 반경은 정수 성분에만 의존한다.

이계 원뿔 계획법의 전문적 방법

1. 이차 집합의 구조 분석

이차 집합 $Q = \{x \in \mathbb{R}^n : x^T M x - 2\beta^T x + \gamma \leq 0\}$ 에 대해 행렬 $M$ 의 고유값에 따라 분류:

타원체: $M \succ 0$
포물면: $M \succeq 0$ , $\lambda_n = 0$
쌍곡면/평행이동 원뿔: $M$ 이 음의 고유값 보유

2. 두 가지 분석 방법

방법 1: 근접성 주도

경계점 $x̂$ 가 주어졌을 때, 정수점을 포함하는 충분히 큰 타원체 탐색
내부 근사 기법 및 피복 반경 이론 활용

방법 2: 정수성 간격 주도

수준 집합 $S_\delta = \{x \in S : x_n = \delta\}$ 를 통한 분석
반경이 충분히 큰 타원체 단면 탐색

기술적 혁신점

원뿔 매개변수 $\Psi_K$ 의 계산: Lorentz 원뿔에 대해 $\Psi_{L^n,\|\cdot\|_2} = 1$ 임을 증명
대형 구 포함 성질: 무한 이차 집합이 임의로 큰 만차원 구를 포함함을 증명
타원체 내부 근사: 근접성 분석을 위한 이차 집합의 타원체 내부 근사 구성

실험 설정

이론적 검증 예제

예제 5 (포물면의 경우)

이계 원뿔 정수계획법을 고려: $\inf_{x \in \mathbb{Z}^2} \left\{\alpha_1 x_1 + \alpha_2 x_2 : \left\|\begin{bmatrix} x_1 - b_1 \\ \frac{1}{2}x_2 - b_2 \end{bmatrix}\right\|_2 \leq \frac{1}{2}x_2 - d\right\}$

매개변수 선택 $\alpha = [1,1]^T$ , $b = [4N+\frac{1}{2}, 4N]^T$ , $d = 4N - \frac{1}{4N}$ 을 통해 정수성 간격 획득: $IG(N) = N + \frac{5}{16N} - \frac{1}{2}$

예제 6 (타원체와 반공간의 교집합)

$\inf_{x \in \mathbb{Z}^2} \{x_2 : x_1^2 + x_2^2 \leq (N+1)^2, x_1 \geq \frac{1}{2}\}$

정수성 간격 $IG(N) = \sqrt{N + \frac{3}{4}}$ 는 우변 항과의 의존 관계를 보여준다.

실험 결과

주요 이론적 결과

1. 타원체의 경우 (명제 6)

타원체 $S = \{x : \|Qx - p\|_2 \leq r\}$ 에 대해: $\text{Prox}_{x̂}(S) \leq 2\|Q(Q^TQ)^{-1}\|_2 \mu(Q)$ $IG(S) \leq 2\|Q(Q^TQ)^{-1}\alpha\|_2 \mu(Q)$

2. 포물면의 경우 (명제 8)

$\text{Prox}_{x̂}(S) \leq \frac{\sqrt{n}}{2} + \Gamma_{x̂}\left(M, \beta, \gamma, \frac{\sqrt{n}}{2}\right)$

여기서 $\Gamma$ 는 반정부호 계획법으로 해결된다.

3. 정수성 간격 주도 방법의 상한

타원체 (명제 13):

경우 1: $IG(S) \leq \sqrt{\frac{q_1^2 - 4q_2q_0}{-q_2}} \leq 2\sqrt{\frac{\mu(\bar{Q})^2}{-q_2} + \frac{1}{4}}$
경우 2: $IG(S) \leq \frac{\mu(\bar{Q})}{\sqrt{-q_2}} + 1$