Tagged Questions

28 views

Reentrant constraints in active set algorithm?

Problem definition Supposing you're trying to solve a quadratic program: $$\min_x f(x) = \frac{1}{2}x^T Q x + c^T x \\ \mbox{s.t} \, \; A x \ge b$$ Where Q is square ($n$x$n$), positive semi ...
117 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
51 views

Given $n^2$ constants $a_{11},a_{12},\ldots,a_{1n},a_{21},\ldots,a_{nn}$ and $n^2$ non-negative variables $x_{11},x_{12},\ldots,x_{1n},x_{21},\ldots,x_{nn}$. Find the minimum value of $$\sum_{i=1}^n ... 0answers 5 views Perturbation of Polyhedral Projection I am interested in understanding the behavior of the Euclidean projection \pi_K(x) as the polyhedral set K varies. I know there are different approaches to this, but for what I am doing it would ... 1answer 46 views Homogeneous non-negative least-squares I would like to least-squares-"solve" a set of linear equations (\underset{\mathbf{x}}{\mathrm{argmin}}\; \|\mathbf{Ax-b}\|_2). In my case, \mathbf{b=0}, e.g. the system is homogeneous. I also ... 1answer 29 views Equality constrained Quadratic Program Consider the QP$$ x^* = \arg \min_{\displaystyle x \in \mathbb{R}^n{\geq 0}} \ \frac{1}{2} x^\top P x + q^\top x \ \text{ sub. to: } A x = b, $$where P \succ 0. Without the non-negativity ... 0answers 17 views Uniqueness of the solution to a quadratic opt problem Consider a positive definite matrix \boldsymbol H, the known vectors {\boldsymbol b} and {\boldsymbol a}_i. Now the minimization problem is casted with respect to the vector {\boldsymbol x}  ... 0answers 31 views Implementing SVM: Help converting equation into form of another I'm currently programming a simple linear SVM (Support Vector Machine). For the optimization involved, I need to find a way to convert the equation \sum\limits_{i=1}^L a_i ... 2answers 57 views Trace of quadratic function with 2 PSD matrices - convex? If A & B are positive semi-definite, is this always convex:$$ trace(XAX^TB) $$There was a similar question asked here: Trace of a quadratic function, Convexity and here: Confusion related to ... 1answer 60 views Minimization problem convex set I'm trying to minimize the function:$$f(w)=w^T\mu+k\sqrt{w^T\Sigma w}$$where w is a vector in W=\{x \in \mathbb{R}^n|x_1+...+x_n=1 , x_i \geq 0 \forall i\}. The vector \mu \in \mathbb{R}^n, ... 0answers 57 views Quadratic Integer Programming Would anyone mind helping me solve this problem$$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda  where $x$ is a vector whose entries are positive ...
Given a real-rectangular matrix $S$ and inorder to solve this simple quadratic programming problem: Minimize $w'S'Sw = \|S w\|^2$ over $w$ subject to $e^Tw = 1$ and $w \geq 0$ using a solver I ...