17

Your problem can be conveniently re-written as \begin{eqnarray} \underset{x \in \mathbb{R}^K}{\text{min }}f(x) + g(x), \end{eqnarray} where $f: x \mapsto \frac{1}{2}\|Ax-b\|^2$ and $g = i_{\mathbb{R}^K_+}$, the indicator function (in the convex analytic sense) of the nonnegative $K$th orthant. $f$ is smooth with Lipschitz gradient ($\|A\|^2$ is a possible ...


13

It can be shown that every Linear Least Squares problem is in fact a Quadratic Programming Problem as follows: $$\frac12 \| Q x - c \|^2 = \frac12 (Qx-c)^T(Qx-c) =\frac12 \left( x^T Q^T Q x - x^T Q^T c - c^T Q x + c^T c\right)$$ $$= \frac12 \left( x^T Q^T Q x - 2 x^T Q^T c + c^T c\right)$$ Since $c^Tc$ is a fixed quantity, it is sufficient to solve the ...


13

The problem as written has no analytic solution for general $A$, $b$. (Yes, indeed, there are exceptions. If the solution of the same problem with the inequalities removed happens to produce a positive solution, then you've solved the original problem. But in the far more likely event that the inequality-free solution has negative entries, there is no ...


12

The Moore-Penrose pseudoinverse is a natural consequence from applying the singular value decomposition to the least squares problem. The SVD resolves the least squares problem into two components: (1) a range space part which can be minimized, and (2) a null space term which cannot be removed - a residual error. The first part will naturally create the ...


12

\begin{eqnarray*} (a-b)^2+(2-a-b)^2+(2a-3b)^2=6a^2-12ab+11b^2-4(a+b)+4 \\ =6\left(a-b-\frac{1}{3}\right)^2+5\left(b-\frac{4}{5}\right)^2+\color{red}{\frac{2}{15}}. \end{eqnarray*}


10

To answer your questions directly: A loss function is a scoring function used to evaluate how well a given boundary separates the training data. Each loss function represents a different set of priorities about what the scoring criteria are. In particular, the hinge loss function doesn't care about correctly classified points as long as they're correct, but ...


7

Oh, absolutely, there are lots of tools. Do a search for proximal gradient methods in your favorite search engine; these are generalizations of projected gradient methods. For specific tools, search for TFOCS (disclosure below), FISTA, NESTA, SPGL1, GPSR, SpaRSA, L1LS... and the bibliographies for these will lead to even more options. Even better, see this ...


6

By defining $r := b - Ax$, you simply restate the objective of the problem as $\|r\|^2$ (in fact, your function $f$ states it as $\tfrac{1}{2} \|r\|^2$, which is an equivalent objective to minimize; the $\tfrac{1}{2}$ neatly cancels out the $2$ that appears when you differentiate). But now you must include this definition of $r$ as a constraint of the ...


6

As the others show, the answer to your question is affirmative. However, I don't see what's the point of doing so, when the problem can actually be converted into an unconstrained least square problem. Let $Q$ be a real orthogonal matrix that has $\frac{v}{\|v\|}$ as its last column. For instance, you may take $Q$ as a Householder matrix: $$ Q = I - 2uu^T,\ ...


6

We have the following least-norm problem $$\begin{array}{ll} \text{minimize} & \mathrm \| \mathrm X \|_{\text F}^2\\ \text{subject to} & \mathrm X \mathrm A = \mathrm I\end{array}$$ where $\mathrm A \in \mathbb R^{m \times n}$ is given. Let the Lagrangian be $$\mathcal L (\mathrm X, \Lambda) := \frac 12 \mathrm \| \mathrm X \|_{\text F}^2 + \...


5

[Major changes here, sorry! I realized the matrix calculus approach has some real advantages here after I submitted my first answer.] Yes, this problem can indeed be examined and solved in a variety of ways. Kronecker products. Kronecker products provide a concise way to relate matrix equations and standard matrix-vector equations. Using them, we can say ...


5

By the first equation we may write $$ \alpha_0 = \sin(x), \alpha_1=\cos(x)$$ and by the second $$\beta_0 = \sin(y), \beta_1 = \cos(y).$$ Multiplying the third and fourth equations then gives $$(\sin(x)\cos(x))(\sin(y)\cos(y)) = \left(\frac{1}{2}\sin(2x)\right)\left(\frac{1}{2}\sin(2y)\right) = \frac{1}{2} $$ $$\iff \sin(2x)\sin(2y) = 2 $$ which is not ...


5

Your problem corresponds to orthogonally projecting the point $\textbf{v} \in \mathbb R^n$ onto the unit simplex. The problem can be solved analytically in $\mathcal O(n)$ using Kiwiel's algorithm (e.g see Algorithm 3 of this paper). Needless to say this is the best possible theoretical bound. If you want something a bit simpler (implementation-wise) with ...


5

Denoting by $\operatorname{vec}:\mathbb{R}^{m\times n} \rightarrow \mathbb{R}^{mn}$ the operator transforming an $m\times n$ matrix into a column vector of $mn$ elements by "stacking" the matrix columns, it holds $$ \operatorname{vec}(\mathbf{L} \mathbf{X} \mathbf{R}) = \left(\mathbf{R}^T \otimes \mathbf{L} \right) \operatorname{vec}(\mathbf{X}), $$ where ...


5

Let $a=\frac{17}{15}$ and $b=\frac{4}{5}$. Hence, we get a value $\frac{2}{15}$. Thus, it remains to prove that $$(a-b)^2 + (2-a-b)^2 + (2a-3b)^2\geq\frac{2}{15}$$ or $$10(3a-3b-1)^2+3(5b-4)^2\geq0$$ Done! I got my solution by the following way. We need to find a maximal $k$ for which the following inequality is true for all reals $a$, $b$ and $c$. $$(a-...


4

You are asking about the nonnegative least squares problem. Matlab has a function to solve this type of problem. Here is a paper about an algorithm to solve nonnegative least squares problems: Arthur Szlam, Zhaohui Guo and Stanley Osher, A Split Bregman Method for Non-Negative Sparsity Penalized Least Squares with Applications to Hyperspectral Demixing, ...


4

For problems of this kind it is often convenient to treat the $\mathbf{x}$ and $\mathbf{x}^H$ as independent variables (in the end they are linearly related to real and imaginary part of $x$). So we want to minimize $$E= \mathbf{x}^H Q \mathbf{x} - (\mathbf{x}^H \mathbf{b} + \mathbf{b}^H \mathbf{x}) +1.$$ In this case as $E$ is a real function (as it ...


4

First of all just delete y. Modify the constraints and use dummy variables to get rid of functional inequalities $$g_1(x)+s_1=-(x-3.0)^2+s_1=-1$$ $$g_2(x)+s_2=-(x-5.3)^2+s_2=-1$$ $$g_3(x)+s_3=-(x-7.0)^2+s_3=-1$$ $$s_1,s_2,s_3\ge 0$$ Construct your Lagrangian $$Z=L(x)+\lambda_1(r_1-g_1(x)-s_1)+\lambda_2(r_2-g_2(x)-s_2)+\lambda_3(r_3-g_3(x)-s_3)$$ where ...


4

Take $$(k_1,x_1)=(500004,1000002)$$ $$(k_2,x_2)=(500000,1000006)$$ Then, $$k_1x_1^2 + 4x_1 = k_2x_2^2 + 4x_2 = 500006000022000024$$ More generally, any integer $S$ can be used to produce an at-least-twice-expressible number: $$(k_1,x_1)=(S+4, 2S+2)$$ $$(k_2,x_2)=(S,2S+6)$$ both result in $$n=4(S+1)(S+2)(S+3)$$


4

First order condition: $$\frac{d}{dx}||Ax-b||_2^2=\frac{d}{dx}(Ax-b)'(Ax-b)=A'(Ax-b)=0$$ Thus, $$x=(A'A)^{-1}A'b=A^+b$$


4

I ran into the same question studying SVR, and even if this post is 2 years old maybe it can help others so here is an answer. The slack variables in SVR are defined as such: -> ξi+ is 0 if the training point is below the upper bound and positive if above -> ξi- is 0 if the training point is above the lower bound and positive below So you can see that ...


4

Yes, this can be a very difficult problem to solve to optimality. This is called a non-convex problem (even though your functions are convex) and you need some kind of global solver for this. One specialized solver is GloMIQO. Otherwise BARON is also doing a good job on these. Furthermore the commercial solver Cplex has also added facilities to solve non-...


4

No, the matrix is not necessarily positive definite. For any $k$, there's a simplex of $k+1$ points in $\mathbb R^k$ all at distance $\frac{3\pi}2$ from each other. The corresponding matrix has $1$ on the diagonal and $-2/(3\pi)$ elsewhere, and its eigenvalues are $1+2/(3\pi)$ and $1-2k/(3\pi)$, so for $k\gt\frac{3\pi}2\lt5$ the matrix is indefinite.


4

As I'm sure you know, the solutions are all vectors $x$ satisfying the optimality conditions: $$\nabla f(x) = 0 \quad\Longleftrightarrow\quad Ax + b = 0$$ It's important to note that if $b\not\in\mathop{\textrm{Range}}(A)$, the objective is unbounded below, and there is no minimum. But if $b\in\mathop{\textrm{Range}}(A)$, one solution is $x=-A^{\dagger} b$, ...


4

As for A, I think the statement is trivial. Given the answer to $A$, the answer to $B$ is found with the KKT conditions for the problem. Consider $$\min_x \{ \sum a_i x_i^2 : \sum x_i \geq 1, x_i \geq 0 \}$$ where the index $i$ is restricted to the $T$ elements from A. I replaced the equality with an inequality since that simplifies the solution ($\lambda \...


4

Substitution of $b=\frac{4-a-c}{2}$ into $ab+bc+ca$ gives: $$\begin{align}-\frac{a^2}{2} + 2 a -\frac{c^2}{2} + 2 c & = \tfrac{1}{2}\left( 4a-a^2+4c-c^2\right) \\[3pt] & = \tfrac{1}{2}\left( 4-\left(2-a \right)^2+4-\left(2-c \right)^2 \right) \\[3pt] & = 4-\tfrac{1}{2}\left(2-a \right)^2-\tfrac{1}{2}\left(2-c \right)^2 \end{align}$$ And this is ...


4

Suppose we are given a convex quadratic program (QP) in $\mathrm x \in \mathbb R^n$ $$\begin{array}{ll} \text{minimize} & \mathrm x^\top \mathrm Q \, \mathrm x + \mathrm r^{\top} \mathrm x + s\\ \text{subject to} & \mathrm A \mathrm x \leq \mathrm b\end{array}$$ where $\mathrm Q \in \mathbb R^{n \times n}$ is symmetric and positive semidefinite, $\...


4

$$(a-b)^2 + (2-a-b)^2 + (2a-3b)^2 = \left\| \,\, \begin{bmatrix} 1 & -1\\ 1 & 1\\ 2 & -3\end{bmatrix} \begin{bmatrix} a\\ b\end{bmatrix} - \begin{bmatrix} 0\\ 2\\ 0\end{bmatrix} \,\, \right\|_2^2$$ This is a least-squares problem. Since the matrix has full column rank, the minimum is $$\left\| \,\, \begin{bmatrix} 1 & -1\\ 1 & 1\\ 2 &...


4

The beginning looks fine. However, note that you need one Lagrange multiplier per constraint. Thus you need a vector $\lambda$. The function to minimize is then $$\operatorname{tr}(A^T-B^T)(A-B) - \lambda^T (B x -v). $$ Taking the gradient with respect to $B$, we arrive at $$2 (B-A)- \lambda x^T =0. $$ We can solve this for $B$ with the result $$ B = A + \...


4

$||z||_2^2 + ||w||_2^2$ is equal to $\left|\left|\begin{matrix}z\\w\end{matrix}\right|\right|_2^2$ so you already have the answer as all you have to do is to stack your expressions (i.e. create a large $A$ and $b$ matrix from the given ones)


Only top voted, non community-wiki answers of a minimum length are eligible