# Tag Info

## Hot answers tagged non-convex-optimization

10

There is an orthogonal matrix $T$, such that $T^tAT$ is diagonal. Because of $v^t(T^tAT)v=(Tv)^tA(Tv)$ and $\|Tv\|=\|v\|$ one can $A$ assume to be diagonal and in this case the assertion is immediate, since $v^tAv = \sum_{i} v_i^2\lambda_i$ with the $\lambda_i$ being the diagonal elements (eigenvalues). Let me provide some more details: First of all we ...

8

If the point is $p$ and the ellipsoid is $x^T Q x = 1$, you want to minimize $(x-p)^T(x-p)$ subject to $x^T Q x = 1$, where $Q$ is a (symmetric) positive definite matrix. Using a Lagrange multiplier, we take $$F = (p-x)^T(p-x) + \lambda (x^T Q x -1)$$ Then we want $$\nabla F = 2 (x-p) + 2 \lambda Q x = 0$$ i.e. $x = (I+\lambda Q)^{-1} p$ where $\lambda$ ...

7

Diffence between 1st and 2nd order algorithm: Any algorithm that requires at least one first-derivative/gradient is a first order algorithm. In the case of a finite sum optimization problem, you may use only the gradient of a single sample, but this is still first order because you need at least one gradient. A second order algorithm is any algorithm that ...

6

Hint You found $$(x-1)^2+(y+1)^2=4$$ which is the equation of a circle centered in $(1,-1)$ and with radius $2$. The function $x^2+y^2$ is the square of the distance of $(x,y)$ to the origin. Which point $(x,y)$ on this circle is located the furthest from the origin? It helps to make a simple sketch. Alternatively, you can handle this as a constrained ...

5

Here's what's happening. First of all: at risk of re-stating something you already know, a convex optimization problem typically involves minimizing a convex function of the variables, subject to the constraint that the variables must lie in a convex set. Notice that the term "convex" is used in three ways: to describe the optimization model, to describe ...

5

You didn't specify but I presume you mean to use the Euclidian norm. Your problem is nonconvex so in general you won't be able to find an analytical expression for a solution. The problem without the bound constraints $$\min \|Ax-b\| \quad \text{subject to} \ \|x\| = \Delta$$ is well understood and, despite the fact that it is nonconvex, we have a ...

4

The problem does not have an analytical solution but can be easily solved using a projected gradient method. Let us rewrite your problem in an equivalent form: \begin{align} \min_x~& \frac{1}{2}\Vert Ax-b\Vert^2\\ s.t.~& \Vert x\Vert =1\\ & x\geq 0\end{align} The method works as follows: Let $x_0$ be a feasible point (eg $x_0=0$), and let $k=1$...

4

Based on your comments, the problem is the fact that you need to express the constraint $X \succeq xx^T$ as a linear matrix inequality. As written, of course, it is not, because it is quadratic in $x$. But we can actually use a Schur complement approach: $$X \succeq xx^T \quad\Longleftrightarrow\quad \begin{bmatrix} X & x \\ x^T & 1 \end{bmatrix} \... 4 Your proposed solution is not correct. Let's consider the simplest case: m=n, k=1, and A is invertible. Then our problem is$$\min_{x\in\mathbb R^n} \|Ax-b\|^2\quad\text{s.t.}\quad \|x\|^2=1.$$The set \{x:\|x\|^2=1\} is the unit sphere, so the transformed set \{Ax:\|x\|^2=1\} is an ellipsoid, and we want to find the point Ax on this ellipsoid ... 4 I would use the Projected Gradient Descend for this case. Though the problem isn't Convex it will work nicely. The algorithm is as following: Calculate the Gradient at the current point. Update the solution  x = x - 2 t M x  where  2 M x  is the Gradient of the Objective Function and  t  is the step size. Project the output of previous step into  {\... 4 You've got this slightly backwards. Recall that the definition of f^*(z) is$$ f^*(z) = \sup_x ( \langle x,z \rangle - f(x) ), $$hence$$ f^*(z) \geq \langle x,z \rangle - f(x), $$which holds for each z, and for each x in the domain of f (it's true for every z if we take f^*(z)=\infty when there is no finite supremum). Phrased this way, it ... 4 CVXGEN only addresses LPs and convex QPs. So I am guessing you are interested in convex Mixed Integer QPs (MIQPs), or perhaps MILPs. Those are addressed, by among others, GUROBI, CPLEX, and MOSEK, all of which also handle the more general Mixed Integer Second Order Cone Problems (MISOCPs). Once you get into the mixed integer realm, all bets are off ... 4 For every k between 1 and M, solve the MILP with the constraint \sum x_i = k. With the sum (i.e. 1-norm) fixed, the denominator does not influence the optimal solution. Hence, you want to maximize c^Tx with the constraint that you have exactly k non-zeros. The optimal solution is obtained by ordering c and picking the k largest elements and ... 4 The function is L-Lipschitz, where L is the operator norm of A. The operator norm is defined as$$\|A\|_{op} := \sup_{x \ne 0} \frac{\|A x\|_2}{\|x\|_2}.$$Indeed, from your work we have$$\|\nabla f(x) - \nabla f(y)\|_2 = \|A(x-y)\|_2 \le \|A\|_{op} \|x-y\|_2$$simply by the definition of operator norm. One can show that the operator norm is equal to ... 4 With the help of the slack variables \epsilon_i and calling$$ L(p,\mu,\epsilon,\lambda)= p_1 p_2 p_3 p_4 p_5+\mu _5 \left(p_1-p_2-\epsilon _5^2\right)+\mu _4 \left(p_2-p_3-\epsilon _4^2\right)+\mu _3 \left(p_3-p_4-\epsilon _3^2\right)+\mu _2 \left(p_4-p_5-\epsilon _2^2\right)+\mu _1 \left(p_5-\epsilon _1^2\right)+\lambda \left(p_1 x_1+p_2 \left(x_2-...

4

The 3x3 moment matrix is $\begin{pmatrix} 1 & x & y\\x & x^2 & xy\\y & xy & y^2\end{pmatrix}$ which is psd and rank-1. Introduce relaxation variables and your semidefinite relaxation is $\begin{pmatrix} 1 & x & y\\x & X_{20} & X_{11}\\y & X_{11} & X_{02}\end{pmatrix}\succeq 0$ (with $z$ thus being $X_{11}$). ...

3

I'll make here a very informal attempt at explaining what eigenvectors of smallest and greatest eigenvalues have to do with minimizing $v^{T}Av$. It will be neither rigorous nor will it cover all cases, but certainly I hope it will enlighten you. Decompositions Matrices can often be re-expressed as a product of two, three or more other matrices, usually ...

3

Sounds like you want to look into the theory of Löwner-John ellipsoids (which states that the relation between the (by volume) largest possible inscribed ellipsoid inside a convex set $K$, and an outer circumscribing ellispoid, is bounded by $n$ ($\sqrt{n}$ for symmetric bodies). From there, you would get a volume bound.)

3

This isn't pretty, but it's direct. We proceed by the usual method of finding the critical points of a function followed by the critical points on the boundary. The maximum occurs at once of these points. To find the critical points of the objective function, differentiate: $$df(x) = (1/2) (dx)^T A x + (1/2) x^T A dx + b^T dx = (dx)^T (Ax + b)$$ so the ...

3

As far as I know, there's not an exact, precise term. Personally, I refer to first-order methods as those methods that use first derivatives and second-order methods as those that use second-derivative information. I also tend to consider second-order methods those methods that use second-order derivative information, but not the entire second-order ...

3

"First-order", in the term "first-order method", does not refer to the convergence rate of the method. It refers to the fact that only first-order derivatives are used by the method.

3

$$\min \qquad \frac{1}{a^{\top} X a}$$ $$\text{subject to} \qquad \mathrm{trace}(X) = 1$$ $$\qquad \ \ \ \ \ X \succeq 0$$ The optimization problem can also be posed as follows, $$-\min \qquad \mathrm{trace}(XA)$$ $$\text{subject to} \qquad \mathrm{trace}(X) = 1$$ $$\qquad \quad X \succeq 0$$ where $A=-aa^{\top}$. This is an SDP. If I am not wrong then ...

3

This is a non-convex problem (as you are maximizing a convex function), so it may be difficult. Cplex should be able to do it, though, if the number of variables is not too big.

3

The mean square error is convex in that the MSE is convex on its input and parameters by itself. Applied to the neural network case (e.g. with the model including parameters from the neural network), MSE is certainly not convex unless the network is trivial.

3

It is not convex. Take $N=1$, $p=1$ and $y=-1$. Take $X_1 = 1$. In this case, your function is a one-dimensional function defined by: $$\ln[1+w^2]$$ It is not convex by the second derivative test. You can also plot it and see visually.

3

This is (a variant of) the trust-region problem, and the solution can be computed rather easily, although not an analytical solution See, e.e., https://www8.cs.umu.se/kurser/5DA001/HT07/lectures/trust-handouts.pdf I'm reparameterizing your problem slightly, you can easily change your model to be $\max x^TQx + c^Tx + b$ subject to $x^Tx\leq 1$. At ...

3

We have the following optimization problem in tall matrix $\mathrm X \in \mathbb R^{n \times k}$ $$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm X - \mathrm B \|_{\text{F}}^2\\ \text{subject to} & \mathrm X^\top \mathrm X = \mathrm I_k\end{array}$$ where tall matrices $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm B \in \mathbb R^{... 3 The problem that you've stated is in general NP-Hard, so you can't expect an "efficient" (meaning polynomial time) solver for all cases. You haven't said anything about the convexity/concavity of the objective function. If$Q$is negative semi-definite, then you've got a convex QP that can easily be solved to a global optimum by many software packages ... 3 A bilinear problem is an extension of a linear problem, allowing in the objective an expression of the form$x^TQy$, where$x,y$is a partition of all the problem variables. So you allow mixed quadratic terms$x_iy_j$, but not a product within$x$or$y\$. Bilinear problems are as you see a special case of quadratic problems. They are nonconvex. The pooling ...

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