0
$\begingroup$

Suppose I have some data matrix $X$. I would like to find a linear combination of its rows $y = w^{\top}X$ where $w$ is a vector.

I would like choose $w$ so that $\sum_{i=1}^{N} y_{i}^{2}$ is maximized.

How would I solve such optimization problem? I have tested some solvers, which seem to work (e.g. Nelder-Mead). However, I feel I am missing something, in particular if I could use some fast classical technique here. For example, I'm not sure how to formulate a Jacobian/Hessian matrix of this for some solvers that require it. Would it just be $2y$ as entries?

All help is appreciated!

$\endgroup$

1 Answer 1

2
$\begingroup$

Completely revised answer, which means some of the comments below no longer apply.

You are maximizing $yy^T$, which equals $w^TXX^Tw$. That is equivalent to minimizing $-w^TXX^Tw$, which is a concave quadratic objective. I will presume there are constraints on $w$ according to either A or B as follows:

A. Constraint that $\Sigma w_i =a$. In that case, this is a concave Quadratic Programming problem. Available solvers to find the global optimum include CPLEX, and Gurobi 9.x, as well as general purpose global optimization solvers such as BARON. You don't need to supply any derivatives for any of the listed solvers. The answer for A alsp applies if there are other or additional constraints on $w$, providing that they are all linear constraints (equality and/or inequality).

B. Constraint that $w^tw \le a$. In that case, this is a convex quadratically-constrained concave Quadratic Programming problem. Because the(re is a) global optimum of a concave program with compact constraints is at the extreme of the constraints, there is a global optimum having $w^tw = a$. Nevertheless, from a computational point of view, you are better off providing the problem to the solver as $w^tw \le a$, even if you want $w^tw = a$, because the convex constraint $w^tw \le a$ is easier for solvers to handle. Available solvers include Gurobi 9.x, as well as general purpose global optimization solvers such as BARON. You don't need to supply any derivatives for any of the listed solvers.

You could instead choose to use a local solver which may not find the global optimum, but may be much faster executing. In that case, the gradient of the objective function (based on entering as a minimization problem) is -$X2X^Tw$ and the Hessian is $-2XX^T$

EDIT: See comment below by (and thanks to) @Rahul appliacable to the "pure" formulation B. Note however, that the framework provided in B for numerical solution can also handle the incorporation of additional linear or convex or non-convex quadratic constraints, in which case the solution provided by @Rahul would not apply.

$\endgroup$
16
  • 1
    $\begingroup$ It appears the problem is to maximize $yy^T$, which is unbounded since one can always multiply $w$ by a larger and larger scalar. $\endgroup$
    – user856
    Feb 9, 2020 at 13:38
  • 1
    $\begingroup$ I will revise my answer to cover both cases. $\endgroup$ Feb 9, 2020 at 15:13
  • 1
    $\begingroup$ That is standard matrix calculus en.wikipedia.org/wiki/Matrix_calculus $\endgroup$ Feb 9, 2020 at 16:13
  • 3
    $\begingroup$ @mmh, Mark: If you want to maximize the length of $w^TX$ subject to $w^Tw\le a$, then there is a closed-form solution: the optimal $w$ is proportional to the left singular vector of $X$ corresponding to the largest singular value. $\endgroup$
    – user856
    Feb 9, 2020 at 23:02
  • 1
    $\begingroup$ You are correct. Yet another typo, now corrected, from rushing my post. Sorry. But actually, it has probably worked out for the best for you as it got you to figure out and understand things. Now you understand it better. $\endgroup$ Feb 20, 2020 at 17:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .