Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wish to find the vector of real numbers, $\mathbf{w}$, that minimizes the function:

$$f(\mathbf{w}\mid\mathbf{p},\mathbf{q})=\sum_{t=0}^T \left[\left(\sum_{i=0}^I w_ip_{ti}\right)-q_t\right]^2,$$

where $\mathbf{p}$ is a $T \times I$ matrix of known real numbers and $\mathbf{q}$ is a vector of length $T$ containing known real numbers. Were $\mathbf{w}$ unconstrained, this is solvable by taking the necessary partial derivatives and solving the resultant system of equations; however, I'm seeking a solution wherein $\mathbf{w}$ is constrained such that:

$$w_i<w_{i+1}$$

for all $w_i$. Can this be solved analytically?

(I apologize in advance if I failed to express my question clearly. Thanks!)

share|improve this question
    
First of all, as a software developper I am not a linear programmer expert. You should have noticed that this is a linearly constrained least-squares problem. And since you are constricting $w$ within a polyhedron. If the solution of the unconstrained least-squares problem lies within this polyhedron you're good. But in any other case, the solution will be on a face of the polyhedron. Which one ? It is a discrete non-continuous function of $P$ and $q$ which would invole many cases. –  matovitch May 28 at 22:11

1 Answer 1

After some calculation, your problem reads (p_t is a column for me):

$$ min \sum_t w^T p_t p_t^T w + 2q_t p_t^T w + q^2_t$$

$$ w_i\leq w_{i+1}$$

which is a quadratic linearly constrained optimization problem. No closed form afaik. I think the problem is convex, as $p_t p_t^T$ should be positive semi-definite. If it is not, then you have a non-convex NP-Hard problem. If it is convex, you need just a convex optimizer (as MOSEK, CPLEX). Another formulation is a conic one:

$$ min \sum_t z_t $$

$$ (1/2, z_i, p_t^T w -q_t) \in Q_r^{3}, \forall t in T$$

where $Q_r$ is a rotated quadratic cone. You need in this case a conic convex optimizer (as MOSEK).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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