nonlinear convex optimization을 푸는 CVXOPT 솔버

https://cvxopt.org/userguide/solvers.html

Nonlinear Convex Optimization — CVXOPT User's Guide

 

 

nonlinear convex optimization 문제를 위한 함수는 다음과 같이 호출할 수 있다. 

cvxopt.solvers.cp(F, G, h, dims, A, b, kktsolver)

F, G, h, dims, A, b 는 가진 문제를 아래 포멧에 맞춰 해석하면 알아낼 수 있다. 

설명이 이렇게 나와있는데 특히 F 를 어떻게 정의해서 전달해야하는지 이해하기 쉽지가 않다. 아래 예제 코드를 보고 더 잘 이해해보자.

 

다음과 같은 최적화 문제가 있다고 하자. 

 

def as_column(x):
    return np.array(x).reshape(-1,1)
def m(x):
    return cvxopt.matrix(x, tc='d')

def F(x=None, z=None): // 위에 F function 을 정의하는 것의 예시이다. 
    if x is None and z is None: // x, z 가 둘다 주어지지 않았을때, 
        return (0, m(as_column([0,0])))
    ([p],[q]) = np.array(x)
    f = as_column(p*p + 2*q*q)
    Df = np.zeros((1,2))
    Df[0,:] = [2*p, 4*q]
    if z is None: // x 만 주어졌을때 
        return (m(f), m(Df))
    // x, z 둘다 주어 졌을때
    [[z]] = np.array(z)
    H = np.array([[2,0],[0,4]]) * z
    return (m(f), m(Df), m(H))

G = m(np.array([[-1,0],[1,0],[0,-1],[0,1]]))
h = m(as_column([0,1,0,1]))
A = m(np.array([[1,1]]))
b = m(as_column(1))

res = cvxopt.solvers.cp(F, G=G, h=h, A=A, b=b)

 

By default, the functions cp and cpl do not exploit problem structure. Two mechanisms are provided for implementing customized solvers that take advantage of problem structure.

 

위 함수를 호출했을때 가장 시간이 많이 소요되는 연산은 KKT equation 을 푸는 것이다. 이 연산을 빠르게 해주기 위해 kktsolver 을 지정할 수 있다. 

 

 

https://en.wikipedia.org/wiki/Convex_optimization

Convex optimization - Wikipedia

 

교재 추천

https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

 

https://web.archive.org/web/20170918180026/http://infohost.nmt.edu/~borchers/presentation.pdf