# Tag Info

8

Unfortunately, your problem isn't a convex optimization problem because the constraint $\Sigma_{i} | a_{i}|=4$ describes a non-convex feasible region. If you could change this to $\Sigma_{i} | a_{i} | \leq 4$, you'd have a convex constraint. If the constraint were $\Sigma_{i} | a_{i} | \leq 4$, then you can introduce auxiliary variables $t_{i}$, and add ...

8

At least for the second question the answer is yes. See for example Mattheij, Robert MM, and Gustaf Söderlind. "On inhomogeneous eigenvalue problems. I." Linear Algebra and its Applications 88 (1987): 507-531, page 516. (The optimality conditions of your problem, $$Ax+b+2\lambda x = 0 \\ x^Tx = 1$$ constitute an inhomogenous eigenvalue problem)

6

David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf The short summary: like most convex-convex collision detection algorithms, you search systematically for a separating axis between the cylinders. For future reference on similar problems, the authors of Real-...

5

If the $s_{i}$ are integers, there are reformulations of integer polynomial terms that result in mixed-integer (linear) programs, at the cost of introducing additional variables and constraints. Fred Glover has a sequence of papers to that effect in the mid-to-late 1970s, and subsequent work has built upon it. For example: Fred Glover, "Improved Linear ...

5

If your problems are small, you could try a simple solver with dense data structures and use stack allocation (old Fortran codes). IPOPT uses sparse data structures and indeed, it takes a relatively long time to initialize IPOPT if your problems are small. Old Fortran codes with stack allocation are surprisingly fast if you have small problems. If the ...

5

One option here is to use the pseudoinverse of $\Sigma$ rather than the actual inverse. Appendix A of Boyd and Vandenberghe discusses a version of the Schur complement that includes this case. Another alternative is to find a factorization of $\Sigma$ as $\Sigma=M^{T}M$ (e.g. by eigenvalue decomposition), and then use the Schur theorem on $\left[ \... 5 Your problem is related to low rank approximation problems, about which there has been a lot of research in recent years. Are you looking for a solution in which$X$has a specified number of rows, or are you trying to find the smallest number of rows possible? In most cases, users are interested in finding$X$such that$X^{T}X$is close to$C$(in e.g.... 5 At first, I thought that Nicolas' answer was right, and then I looked at the question again. For a quadratic program (QP),$A$is symmetric by convention, and it's possible to re-express it as such, so without loss of generality, suppose that$A$is symmetric. If$A$is also positive semidefinite, then a local optimum is a global optimum, and the KKT ... 5 To ensure this does not drown in the comments, I make it an answer. The solver used is not SeDuMi, as claimed in the question. The solver used is quadprog, and that solver (or more specifically, a severely outdated version of it), apparently had numerical issues on this particular instance. A recent version of quadprog, or any reasonably robust solver, ... 5 Instead of e = eig(N'*A*N);, you can use [R,p]=chol(N'*A*N);, and test for p==0. Matlab function chol returns the cholesky factor R and a p which is zero if N'*A*N is positive definite. p is a positive integer if the matrix is not positive definite. Usually chol is much faster than eig. For example, with dimension n=2000, I found that chol(N'*A*N) is ... 4 Without knowing much about your question it is hard to answer more specifically. So first and foremost - no. These are not equivalent. Minimizing variangce will generally make you converge to some kind of sample mean, whereas minimizing absolute deviation would (generally) make you find some kind of sample median. A generally favourable property of sample ... 4 You can reformulate this as$x^{*}=\arg \min x^{T}Lx+ t $subject to$t \geq P^{T}x t \geq -P^{T}x x \in \left\{ 0, 1 \right\}^{n}$This is a 0-1 mixed integer quadratic programming problem (MIQP) The case where$L$is positive definite is well handled by solvers like CPLEX. 4 You do realize that there are at least two problems with your goal: This is, in general, a problem that can have$2^N$solutions where$N$is the number of variables. An example is if you tried to find the solution of $$\min_{x\in {\mathbb R}^N} \sum_{1\le i\le N} -x_i^2 \\ \text{subject to} \quad -1 \le x_i \le 1.$$ For this problem, every ... 4 Writing the Lagrangian gives rise to the following optimality conditions$B x^* =0 $and$A x^* + b +A^T\lambda^*=0 . Rewritten in matrix-form we have \begin{align} \underbrace{\begin{bmatrix} A&B^T \\B &0 \end{bmatrix}}_{=:K}\begin{bmatrix} x \\ \lambda\end{bmatrix} =\begin{bmatrix} -b \\ 0\end{bmatrix}. \end{align} IfK$is non singular ... 4 Quadratically constrained quadratic programming (QCQP) focuses on convex inequalities because those preserve the convexity of the problem. Quadratic equalities do not, so this problem is much harder. Any polynomial equation can be re-written as a system of quadratic equations. (For example:$x^3 = 1$is equivalent to$\{xy = 1,\, x^2 - y = 0\}$.) So solving ... 3 With$d=16$, the$Q$matrix is just 256 by 256. Thus the individual subproblems are quite small. Your$Q$matrices are singular, so the optimal solution to each of the subproblems is likely to be nonunique. Do you care which solutions you end up with? For example, are minimum norm solutions required? You write that "since n is very large, it is ... 3 cvxopt (for python) does QP, and can take advantage of sparsity (you can provide a custom KKT solver specific to your problem). An example of a custom solver is https://groups.google.com/forum/#!topic/cvxopt/W8kd3LHPwwA 3 Suppose $$z_{i} = x_{i} \times y_{i}$$ The constraint $$\sum_{i=1}^{n} x_{i}y_{i}\le 1$$ can be reformulated as linear constraints: 1) $$\sum_{i=1}^{n} z_{i}\le 1$$ 2) $$z_{i}\le x_{i}$$ 3) $$z_{i}\le y_{i}$$ 4) $$z_{i}\ge x_{i} + y_{i} -1$$ 3 Intropduce a new variable$z_i$to represent$x_iy_i$(logical and). Your constraint is$\sum_{i=1}^n z_i \leq 1$, and the product is modelled by$x_i + y_i -1 \leq z_i$. 3 To transform your original program into the form you specified, use the following mappings: First,$D = 2S'S$, and$D$is positive semidefinite.$b = w$, as you pointed out$d = 0$, as Nico notes$Atakes the following form: \begin{align} A = \left[\begin{array}{c} I \\ e^{T} \\ -e^{T}\end{array}\right] \end{align}b_0$takes the following form: \begin{... 3 Note that CPLEX 12.6 and later includes functionality to solve general nonconvex QPs and MIQPs. However, for the special case of the product of a binary and continuous variables, the reformulation in the previous answer is likely to run faster. But, for nonconvex QPs with products of continuous variables in the objective, this type of reformulation no ... 3 Hint: If the two cylinders are parallel, the problem is easy. Otherwise, if the perpendicular distance between the axis exceeds the sum of the radii, there is no intersection. Otherwise, there is an intersection curve between the two lateral surfaces. It can be expressed analytically: without loss of generality, the second cylinder is vertical with a base ... 3 Your conjecture can not be correct, for two purely formal reasons: In$x^T Q x$, if you multiplied this out as a sum$\sum_i \sum_j Q_{ij}x_ix_j$, every term in the sum is the product of two entries of the vector$x$. On the other hand, in your conjecture the formula (1) contains terms that are linear in the components of$x$. This can only be correct if ... 3 Newton-type methods are standard methods for solving system of nonlinear equations numerically. To make sure they can handle this, I tried solving your problem with NLsolve.jl in julia, and it seems to work just fine: using NLsolve using LineSearches using ForwardDiff function solve(d::Real, μ::Real, β::Real, T::Integer) @assert 0 < d < 1 @... 3 This problem can be formulated as a standard positive semidefinite QP with bounded variables. First, deal with the absolute value terms in the objective by letting$x=u-v$, where$u\geq 0$and$v \geq 0$. Then write the problem as$\min \;\; (A(u-v)-b)^{T}(A(u-v)-b)+c^{T}u+c^{T}v$subject to$B(u-v)=d$(equality constraints) Upper ... 3 Applying the transformation you suggested, we get: $$\min_{y \in\{0,1\}^n} (\mathbf{1}-y)^TP(\mathbf{1}-y)$$ $$\mathrm{s.t.}\;\;w^T(\mathbf{1}-y)\geq c\, ,$$ where$n$is the dimension where$x$lives and$\mathbf{1}$is a vector of$n\$ ones. Working with the objective function, \begin{align*} (\mathbf{1}-y)^T P(\mathbf{1}-y) & = \mathbf{1}^T P\... 3 Despite my comment, I think you can find \tilde{D} that contains the noise term as well. You have this equation:-M^{T} \tilde{D} M \phi(t) = -M^{T} D M \phi(t) + W(t)$$Where W(t) is the noise term vector. So:$$-M^{T} (\tilde{D}-D) M \phi(t) = W(t)$$Take \mathcal{D} = \tilde{D} - D. Let's expand this equation:$$(M \phi(t))_{i} = \sum_{j=1}^{...

2

Your problem is a non convex bounds constrained quadratic programming problem. There are lots of software packages that can solve such problems. See the list of solvers at http://plato.asu.edu/sub/nlores.html#QP-problem

2

x<=u is exactly in the form A*x<=b, trivially from A=I and b=u. Most solvers allow you to specify bounds explicitly though (i.e, you specify A, b, E, d, and lower bounds l and upper bounds u) A bound norm(x) <= u (Euclidean norm) cannot be represented using linear constraints. It leads to a so called second-order cone constraint. Changing the norm ...

2

It's a quadratic program with linear inequality constraints, which are efficiently solved by the active set method. I pose implementing this method as a homework in my optimization courses and it doesn't take my students more than at most a couple of hours, assuming you have a solver for the linear systems you need to solve in each iteration. I would ...

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