Dual Greedy Algorithm for Conic Optimization Problem

Abstract

In the paper we propose an algorithm for nding approximate sparse solutions of convex optimization problem with conic constraints and examine convergence properties of the algorithm with application to the index tracking problem and unconstrained l1-penalized regression. Greedy algorithms have been intensively studied since the 80s of the last century, and their main credit consists in obtaining constructive methods for nding the best mterm approximations. The main contribution to the development of greedy algorithms was made by J. Friedman [1], S. Mallat [2], J. Zhang [3], P. Huber [4], L. Jones Jones, A. Barron [6], R. DeVore, V.N. Temlyakov [7], S.V. Konyagin [8] and others. Let X be a Banach space with norm ∥ ∥X . A set of elements D from the space X is called a dictionary if each element g 2 D has norm bounded by one, ∥g∥ 1; the closure of span D is X, i.e. spanD = X.

Keywords

• greedy algorithm
• constrained convex optimization
• conic optimization problem
• index tracking problem

-

Introduction ( 1 ) ( 2 ) where m(D) is the set of all m-term polynomials with respect to D:

{ m(D) = x 2 X : x = m ∑ cigi; gi 2 D i=1 }

The paper of V.N.Temlyakov [9] examines greedy algorithms for nding an approximate solution to the problem ( 2 ). It is shown that greedy algorithms with respect to the dictionary D solve the problem ( 1 ) as well.

The paper [9] proposes the weak greedy Chebyshev algorithm and proves some estimates of the convergence rate of the algorithm based on the geometric properties of the function E. The development of ideas presented in [9] can be found in [10], [11].

Let Y be the m-dimensional Euclidean space, Y = Rm. Let E be a convex function dened on X. Many convex constrained optimization problems can be expressed in the conic form:

E(x) ! A(xm)+inb2K; where A : X ! Y is a linear operator, b 2 Y and K is a closed cone in Y .

Recall that K is said to be a cone in Y if a1x1 + a2x2 2 K for any x1; x2 2 K and a1; a2 2 [0; 1).

At rst sight the constraint A(x) + b 2 K seems to be too specialized, but as it is pointed out in [12], any convex subset of Y = Rm may be represented in the conic form. In particular, as it was shown in [12] both Dantzig selector problem [13] and LASSO regression problem [14] can be reformulated in the form ( 4 ).

We are interested in nding an approximate solution to the problem ( 4 ). Furthermore, in many applications it is necessary to nd solutions of ( 4 ) that are sparse with respect to the dictionary D: It may turn out that the solution to the problem ( 4 ) can be inecient from the computational point of view since projection onto the set fx : A(x) + b 2 Kg may be expensive, as well as the nding of a single feasible point. For example, projection onto the set fx : ∥y Ax∥2 ϵg, x 2 Rn, y 2 Rm, is very computational expensive, while projection onto the dual cone is trivial.

The dual problem of the problem ( 4 ) is ( 3 ) ( 4 ) ( 5 ) ( 6 ) F ( ) ! max ; 2K where F ( ) is the Lagrange dual function:

F ( ) := inf L(x; ) = inf(E(x) x x ⟨ ; A(x) + b⟩); and K is the dual cone,

K := f 2 Y : ⟨ ; y⟩ 0 8y 2 Kg:

Let A : Rm ! Rn denote the adjoint of the linear operator A. Let E convex conjugate of E, i.e. be the E (z) = sup(⟨z; x⟩ x

E(x)): E (A ( )) ⟨b; ⟩ ! max : 2K Then the dual problem ( 6 ) can be rewritten in the following form:

Recall that the following inequality holds for any optimal primal/dual pair x and : E(x)

F ( ) = E(x) + E (A ( )) + ⟨b; ⟩ ⟨x; A ( )⟩ + ⟨b; ⟩ = ⟨A(x) + b; ⟩ 0: If the optimal solutions of the primal problem x and the dual problem are strictly feasible then E(x) = F ( ) and there exist (not necessary unique) points x ; , such that E(x ) = F ( ) = L(x ; ) and satisfying optimality conditions

A(x ) + b 2 K; 2 K ; ⟨A(x ) + b; ( 7 ) where @E is the subgradient of E.

Let := ftmgm1=1, tm 2 [0; 1], be a weakness sequence. Let satisfy ( 7 ).

We suppose that function E is Ferchet dierentiable. We note that it follows from convexity of E that for any x; y where E′(x) denotes Ferchet dierential of

E at x. Denote

E(y)

E(x) + ⟨E′(x); y

x⟩; Q(x) := E(x) ⟨A(x) + b; ⟩:

Dual weak greedy Chebyshev algorithm. Let G0 := 0. For each m dene Gm by induction as follows. 1 we 1. (Gradient greedy step) Find the element ϕm 2 D satisfying 2. (Chebyshev-type step) Find real numbers ci , i = 1; : : : ; m, such that ⟨ Q′(Gm 1); ϕm⟩ tm sup⟨ Q′(Gm 1); g⟩:

g2D Q ( m ∑ ci ϕi i=1 ) = inf Q ci ( m ) ∑ ciϕi : i=1 3. Let Gm = ∑m i=1 ci ϕi.

The gradient greedy step maximizes a certain functional determined by gradient information from the previous steps of the algorithm. The Chebyshev-type step nds the best linear combination of m approximants fϕigim=1.

Let Ω := fx 2 X : E(x) E(0)g and suppose that Ω is bounded. The modulus of smoothness of function E on the bounded set Ω is dened as follows: (E; u) = 1

sup 2 x2Ω;∥y∥=1 jE(x + uy) + E(x uy) 2E(x)j: ( 8 ) Let A1(D) denote the closure (in X) of the convex hull of D.

Using results and ideas of [9] we can prove the following proposition. Theorem 1. Let E be a uniformly smooth convex function with modulus of smoothness (E; u) uq, 1 < q 2. Let V := fx 2 X : A(x) + b 2 Kg. Let ϵ > 0 and element f ϵ 2 D be such that

Q(f ϵ) inf Q(x) + ϵ; f ϵ=C(ϵ) 2 A1(D); x2D for some real number C(ϵ) 1. Let p = q=(q 1). Then E(Gm) where C(q; ), C(E; A; b; K; q; ) are positive constants not depending on k. Proof. We have (Q; u) = (E; u). It follows from Theorem 4.2 of [9] that Q(Gm) inf Q(x) x2D

Then (9) follows from (10) and

0 ( m max @2ϵ; C(q; )A(ϵ) C(Q; q; ) + ∑ tp

k k=1 )1 q1

A : Q(Gm) inf Q(x) = E(Gm) x2Ω

E(Gm) ⟨A(Gm) + b; ⟩ ⟨A(Gm) + b; ⟩ inf (E(x) x2Ω ⟨A(Gm) + b; ⟩) =

⟨A(x) + b; ⟩) = E(Gm) inf (E(x) x2Ω inf E(x) x2Ω

E(Gm) Greedy algorithms showed an excellent performance in solution of practical problems of machine learning and optimization. This section will show the use of such techniques in ( 10 ) ⊔⊓ solving the index tracking problem. Index tracking is a passive nancial strategy that tries to replicate the performance of a given index or benchmark. The aim of investor is to nd the weights of assets in her/his portfolio that minimize the tracking error, i.e. dierence between the performance of the index and the portfolio.

For any q > 0 and x = (x1; : : : ; xn)T 2 Rn, let ∥x∥q := (∑in=1 jxijq)1=q and ∥x∥0 = limq!0+ ∥x∥q = (the number of non-zero elements of x). If q 1 then ∥x∥q denotes lq-norm of x 2 Rn. Let n be the number of investable assets. Denote rti the return of asset i at time t, 1 i n, 1 t k, R = (rti) is the k n matrix. A portfolio is dened to be a vector of weights, x = (x1; : : : ; xn)T 2 Rn. We do not allow the portfolio changes over time and do not take into account transaction costs. We will assume that 1. one unit of capital is available, i.e. xT 1n = 1, where 1n denotes the vector from Rn in which every component is equal to 1; 2. short selling is allowed, i.e. weights xi can be negative.

Let It be the index return at time t, 1 t k, and I = (I1; : : : ; Ik)T 2 Rk. In the traditional index tracking optimization, the objective is to nd a portfolio which has minimal tracking error variance, the sum of squared deviations between portfolio returns and market index returns (see e.g. [15]):

1 x = arg min k ∥I Rx∥22 s:t: xT 1n = 1:

It should be noted that the standard Markovitz model is a special case of index tracking portfolio model ( 11 ) (see, for example [16], [17]). Since the problem ( 11 ) is the problem of convex optimization, it can be easily solved by Lagrange method.

In this section we examine algorithm for solving the problem ( 11 ) with the cardinality constraint: ( 11 ) x = arg min 1 k ∥I

Rx∥22 s:t: xT 1n = 1; ∥x∥0

K; ( 12 ) where K is the limit on the number of assets in the portfolio with non-zero weights. It is supposed that K is substantially smaller than n, K ≪ n.

Classical methods usually require convexity and relatively well-behaved objective functions and they are usually based on gradients for descent direction. Therefore, standard optimization techniques can be no longer used if we add constraints on the number of assets in portfolio. In such problems, classical optimization methods do not work eciently and many researchers have to resort to heuristic optimization [18].

For solution to the problem ( 12 ), in this paper we propose to use greedy algorithms. The choice of the greedy algorithm for our analysis is based on the fact that greedy algorithms showed an excellent performance in the papers [19], [16] for practical problem solution, and therefore we may assume that they look promising for solving the cardinality constrained index tracking problem. On the other hand, greedy algorithms do not necessarily yield an optimal solution.

The constraint xT 1n = 1 can be rewritten in the conic form A(x) + b 2 K with

The following proposition follows from Theorem 1 and nds the rate of convergence of the dual greedy algorithm for the index tracking problem.

Corollary 1. Let E(x) := k1 ∥I Rx∥22 and V := fx 2 Rn : xT 1n = 1g. Let the dictionary D be such that D = f ej gjn=1, where ej 2 Rn with eji = 1 if i = j and eji = 0 otherwise. Then

E(Gm) where Gm is the element obtained in the step m of the dual greedy algorithm with A, b, K dened in ( 13 ).

= K = R2+. It easy to verify that (E; u)

Primal greedy algorithms for the index tracking problems were empirically examined in the papers [16] (in l2-norm) and [20] (in l1-norm). The analysis of heuristic algorithms for portfolio optimization problems with the cardinality constraint can be found in the work [18]. Let us consider the problem of recovering an unknown vector x0 2 Rn from the data y 2 Rk and the model

y = Bx0 + z; where B is a known k n matrix, z is a noise. In many practical problems there are fewer observations/measurements than unknowns, i.e. k ≪ n. Recent works have shown that accurate estimation is often possible under reasonable sparsity constraints on x0. One practically and theoretically eective estimator is unconstrained l1-penalized regression.

Unconstrained l1-penalized regression can be written as follows: ∥y

Bx∥22 + ∥x∥1 ! min : where is a positive real parameter.

Homotopy method for solving the problem ( 15 ) was proposed in papers [21], [22]. The method is also known as Least Angle Regression or LARS [23]. u2:

⊔⊓ ( 14 ) ( 15 ) Let us to rewrite the problem ( 15 ) in the following way:

Bx∥2 ! min; s:t: ∥x∥1 ϵ; where ϵ is a positive scalar. The real ϵ should be adjusted so that the true x0 is feasible, at least with high probability, when the noise term z is stochastic.

The equivalent conic formulation of the problem ( 16 ) is

E(x) ! ∥y k

Bx∥2; A(x) ! (Bx; 0); b ! ( y; ϵ); K ! L1 ; where L1k := f(y; t) 2 Rk+1 : ∥y∥1 tg.

The following corollary of Theorem 1 shows that the rate of convergence of the dual greedy algorithm for the unconstrained l1-penalized regression ( 16 ) is m 1. Corollary 2. Let E(x) := ∥y Bx∥2 and V := fx 2 Rn : dictionary D consists of all columns of matrix B multiplied by ∥x∥1 1. Then ϵg. Let the E(Gm) where Gm is the element obtained in the step m of the dual greedy algorithm with A, b, K dened in ( 17 ).

Proof. We have (E; u)

where E is a convex function dened on a Banach space X, A : X ! Y is a linear operator, b 2 Y and K is a closed cone in Y . Since the solution to the problem ( 4 ) can be inecient from the computational point of view, we propose the dual greedy algorithm for the conic optimization problem. Theorem 1 nds estimates on the rate of convergence for the dual greedy algorithm. We should mention that the approach used in this paper is based on the ideas and results developed in the paper [9]. Based on Theorem 1 we proved that the rate of convergence of dual greedy algorithms for index tracking problem ( 12 ) and the unconstrained l1-penalized regression ( 16 ) is m 1. ( 16 ) ( 17 ) ⊔⊓

References

1. Friedman J . Greedy Function Approximation: A Gradient Boosting Machine The Annals of Statistics 2001 , Vol. 29 , No. 5 , 1189 - 1232

2. Davis G. , Mallat S. , Avellaneda M. Adaptive greedy approximation Constr . Approx . 13 ( 1997 ), pp. 57 - 98

3. Zhang Z., Shwartz S. , Wagner L. , Miller W. A greedy algorithm for aligning DNA sequences J . Comput. Biol . 2000 Feb-Apr; ( 1-2 ): 203 - 14

4. Huber P. J. Projection pursuit Ann. Statist., 13 ( 1985 ), pp. 435 - 525

5. Jones L. On a conjecture of Huber concerning the convergence of projection pursuit regression Ann . Statist. 15 ( 1987 ), 880 - 882

6. Barron A. R. , Cohen A. , Dahmen W. , DeVore R. A. Approximation and Learning by Greedy Algorithms The Annals of Statistics 2008 , Vol. 36 , No. 1 , 64 - 94

7. DeVore R. A ., Temlyakov V.N. Some remarks on greedy algorithms Advances in Computational Mathematics 5 ( 1996 ) 173 - 187

8. Konyagin S. V. , Temlyakov V. N. A remark on greedy approximation in Banach spaces East J . Approx. 5 ( 1999 ), no. 3 , 365 - 379

9. V. N. Temlyakov , Greedy approximation in convex optimization , Constructive Approximation 41 ( 2 ) ( 2015 ) 269296 .

10. H. Nguyen , G. Petrova, Greedy strategies for convex optimization , Calcolo 41 ( 2 ) ( 2016 ) 118 .

11. V. N. Temlyakov , Dictionary descent in optimization, Analysis Mathematica 42 ( 1 ) ( 2016 ) 6989 .

12. S. R. Becker , E. J. Candes and M. C. Grant , Templates for convex cone problems with applications to sparse signal recovery , Mathematical Programming Computation , 3 ( 3 ) ( 2011 ) 165218 .

13. E. Candes and T. Tao , The Dantzig selector: Statistical estimation when p is much larger than n . Annals of Statistics 35 ( 2007 ) 23132351 .

14. Tibshirani R . Regression shrinkage and selection via the LASSO , Journal of the Royal Statistical Society (Series B) 58 ( 1996 ) 267288 .

15. Roll R. A Mean/Variance Analysis of Tracking Error . The Journal of Portfolio Management , 18 ( 4 ): 1322 , 1992 .

16. Takeda A. , Niranjan M. , ya Gotoh J., Kawahara Y. Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios . Computational Management Science , 10 ( 1 ): 2149 , 2013 .

17. Brodie J. , Daubechies I. , De Mol Ch., Giannone D. , Loris I . Sparse and stable Markowitz portfolios . Proc. of the National Academy of Sciences of the USA , 106 ( 30 ): 1226712272 , 2009 .

18. Beasley J. E. , Meade N. , Chang T.-J. An evolutionary heuristic for the index tracking problem . European Journal of Operational Research , 148 ( 3 ): 621643 , 2003 .

19. Das A. , Kempe D. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection . In Lise Getoor and Tobias Scheer , editors, Proceedings of the 28th Int. Conf. on Machine Learning (ICML-11) , pages 10571064 , New York, NY, USA, June 2011 . ACM.

20. Sidorov S. P. , Faizliev A. R. , Khomchenko A. A. Algorithms for l1-Norm Minimization of Index Tracking Error and Their Performance . Int. J. of Mathematics in Operational Research , 2016 , to appear

21. Osborne M. R. , Presnell B. , and Turlach B. A. A New Approach to Variable Selection in Least Squares Problems . IMA Journal of Numerical Analysis , 20 ( 3 ): 389403 , 2000 .

22. Osborne M. R. , Presnell B. , and Turlach B. A. On the LASSO and Its Dual . Journal of Computational and Graphical Statistics , 9 ( 2 ): 319337 , 2000 .

23. Efron B. , HastieT., Johnstone I. , Tibshirani R . Least Angle Regression . Annals of Statistics , 32 ( 2 ): 407499 , 2004 .