Matlab의 빠른 CVX 솔버

Question

Matlab에서 가장 빠른 볼록 옵티 마이저가 무엇인지 궁금하거나 현재의 솔버를 빠르게 할 수있는 방법이 있습니까? CVX를 사용하고 있지만 최적화 문제를 해결하는 데 영원히 걸리고 있습니다. I 가지고있는 최적화는 (A)의 크기 나 매우 큰

minimize norm(Ax-b, 2) 
subject to 
x >= 0 
and x d <= delta 

를 해결하는 것이다.

최소한 사각형 솔버로 해결할 수있는 방법이 있습니까? 그리고 구속 버전으로 전송하여 더 빨리 만들 수있는 방법이 있습니까?

Answer 1

내가 무엇 x.d <= delta 의미하는지 모르겠지만, 난 그냥 x <= delta 것으로 가정합니다.

투영 된 그라디언트 방법 또는 가속 투영 된 그라디언트 방법을 사용하여이 문제를 해결할 수 있습니다. 이것은 투영 된 그라디언트 방법을 약간 수정 한 것인데, "마법처럼"더 빨리 수렴됩니다. 다음은 최소화하는 방법을 보여주는 파이썬 코드입니다. Ax-b ||^2는 0 < = x < = 가속 투영법 인 FISTA를 사용하는 델타를 조건으로합니다. 투영 된 그라데이션 방법 및 FISTA에 대한 자세한 내용은 근위 알고리즘에 대한 Boyd의 manuscript에서 찾을 수 있습니다.

import numpy as np 
import matplotlib.pyplot as plt 

def fista(gradf,proxg,evalf,evalg,x0,params): 
    # This code does FISTA with line search 

    maxIter = params['maxIter'] 
    t = params['stepSize'] # Initial step size 
    showTrigger = params['showTrigger'] 

    increaseFactor = 1.25 
    decreaseFactor = .5 

    costs = np.zeros((maxIter,1)) 

    xkm1 = np.copy(x0) 
    vkm1 = np.copy(x0) 

    for k in np.arange(1,maxIter+1,dtype = np.double): 

     costs[k-1] = evalf(xkm1) + evalg(xkm1) 
     if k % showTrigger == 0: 
      print "Iteration: " + str(k) + " cost: " + str(costs[k-1]) 

     t = increaseFactor*t 

     acceptFlag = False 
     while acceptFlag == False: 
      if k == 1: 
       theta = 1 
      else: 
       a = tkm1 
       b = t*(thetakm1**2) 
       c = -t*(thetakm1**2) 
       theta = (-b + np.sqrt(b**2 - 4*a*c))/(2*a) 

      y = (1 - theta)*xkm1 + theta*vkm1 
      (gradf_y,fy) = gradf(y) 
      x = proxg(y - t*gradf_y,t) 
      fx = evalf(x) 
      if fx <= fy + np.vdot(gradf_y,x - y) + (.5/t)*np.sum((x - y)**2): 
       acceptFlag = True 
      else: 
       t = decreaseFactor*t 

     tkm1 = t 
     thetakm1 = theta 
     vkm1 = xkm1 + (1/theta)*(x - xkm1) 
     xkm1 = x 

    return (xkm1,costs) 


if __name__ == '__main__': 

    delta = 5.0 
    numRows = 300 
    numCols = 50 
    A = np.random.randn(numRows,numCols) 
    ATrans = np.transpose(A) 
    xTrue = delta*np.random.rand(numCols,1) 
    b = np.dot(A,xTrue) 
    noise = .1*np.random.randn(numRows,1) 
    b = b + noise 

    def evalf(x): 
     AxMinusb = np.dot(A, x) - b 
     val = .5 * np.sum(AxMinusb ** 2) 
     return val 

    def gradf(x): 
     AxMinusb = np.dot(A, x) - b 
     grad = np.dot(ATrans, AxMinusb) 
     val = .5 * np.sum(AxMinusb ** 2) 
     return (grad, val) 

    def evalg(x): 
     return 0.0 

    def proxg(x,t): 
     return np.maximum(np.minimum(x,delta),0.0) 

    x0 = np.zeros((numCols,1)) 
    params = {'maxIter': 500, 'stepSize': 1.0, 'showTrigger': 5} 
    (x,costs) = fista(gradf,proxg,evalf,evalg,x0,params) 

    plt.figure() 
    plt.plot(x) 
    plt.plot(xTrue) 

    plt.figure() 
    plt.semilogy(costs)