3
$\begingroup$

all, I've tried to find an answer to this question and have come across some related threads but nothing I was able to apply to my problem given my relative lack of experience in this arena.

I basically have a constrained minimization problem using both inequality and equality constraints. I will have more variables (~10) than equality constraints (6), so generally speaking there will be an infinite number of solutions to the system. The wrinkle is that I want my solution vector to have as many zero elements as possible, or more precisely I want to minimize the number of non-zero elements. The real-world application is that each variable represents a trade in a portfolio, so I want to hit my "targets" in the portfolio with the fewest number of necessary trades.

My initial approach was to use the fmincon function in Matlab with the objective function as

fun=@(x)nnz(x);

But this approach results in a spurious solution even for the most basic test example I could come up with. Is a problem like this solvable in Matlab? Any help would be much appreciated, I'm really at an impasse. Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

A common solution to this problem when you have a cardinality constraint (or an $\ell_0$ regularization term, it's not clear to me from your description), is to relax the non-convex cardinality constraint to either a convex $\ell_1$ constraint, or a convex $\ell_1$ regularization term.

So, for example, a problem like $$ \text{minimize}\quad \mathbf{card}(x), \qquad \text{subject to}\quad x\in\mathcal{C} $$ could be (heuristically) replaced with $$ \text{minimize}\quad \|x\|_1, \qquad \text{subject to}\quad x\in\mathcal{C}. $$ A constraint like $\mathbf{card}(x)\leq k$ could be replaced by a regularization term $\gamma\|x\|_1$, or a constraint $\|x_1\|\leq \beta$, where the appropriate values of $\beta$ or $\gamma$ have to be determined later to make the result match the original constraint.

In Convex Optimization by Boyd, Vandenberghe this is Example 6.4.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The one-norm minimization problem can easily be formulated as an LP and solved with MATLAB's optimization toolbox. An another software package that is well suited to this is CVX. $\endgroup$
    – Brian Borchers
    Jan 19, 2016 at 19:34
  • $\begingroup$ @BrianBorchers thanks, it's good to know that this problem can be solved as an LP. Would it be possible to get some additional help on how to actually set this up as an LP in matlab? $\endgroup$
    – jd98
    Jan 19, 2016 at 19:47
  • $\begingroup$ See the textbook by Boyd and Vandenberghe- it's available as a free .pdf online. $\endgroup$
    – Brian Borchers
    Jan 19, 2016 at 20:29
  • $\begingroup$ Hi, so I tracked down the exact problem in that textbook and it was very helpful. The problem in that textbook uses the objective function norm(Ax - b,2) + gamma*norm(x,1). My problem only has inequality constraints, so my A and b matrices are empty. So does my problem reduce to literally just minimizing the L1-norm of the solution vector? Am I thinking about that correctly or is that too simplistic? $\endgroup$
    – jd98
    Jan 19, 2016 at 23:29
  • $\begingroup$ Your going to want to minimize norm(x,1) subject to the linear equality and inequality constraints. These constraints won't appear in the objective function. $\endgroup$
    – Brian Borchers
    Jan 20, 2016 at 4:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.