# Tag Info

12

Just to clarify notation, I'll be discussing the Gauss-Newton method for the problem $\min \phi(x)=(1/2) \| F(x) \|_{2}^{2}$ with the search direction $p$ computed as the solution to the linear system of equations $J(x^{(k)})^{T}J(x^{(k)}) p = - J(x^{(k)})^{T} F(x^{(k)})$ where $J(x)$ is the matrix of partial derivatives of components of $F(x)$ with ...

11

Interior point methods work by following the central path to an optimal solution. When you change the objective function, the optimal solution from the previous version of the problem is far from the central path for the new problem, so it takes several iterations to get back to the central path and furthermore has to return to a fairly well centered ...

10

This is the classic colorization using optimization problem. Optimization and Linear Algebra To see how this can be expressed as a linear system, it's helpful to use a slightly different notation (and a slightly different objective function). Think of your image as graph $G$ with a node for each pixel in the image. There is an edge $(i,j)$ between two ...

10

Since the optimization problem has a well-known closed-form solution, it is rarely used in itself and hence usually not given a name. The objective function $x^TAx$ (using $\|x\|=1$), however, is known under the name Rayleigh quotient; the set of its values is called field of values, or numerical range (of $A$). More generally, this is a textbook example ...

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

TL;DR: The property you are looking for is coercivity. This is satisfied for the example in your question (as are properties 1 and 3 below), and hence yes, the penalized objective attains its minimum. The classical proof of existence of minimizers of (a very general class of) functionals is the so-called direct method of the calculus of variations (...

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)

7

I know this should be a comment but I do not have enough reputation to comment. I just want to point out that for an arbitrary $A$ with real entries the solution (minimum) to this problem is the smallest eigenvalue of the symmetric part of $A$, namely $S(A)=\frac{(A+A^T)}{2}$, and in the special case when $A$ is symmetric this indeed (as in the original ...

7

Writing an optimization routine is like writing any other not too simple program and involves a fair amount of debugging. All things you mention in your question are good checks (i.e. taking care that all the things that theoretically should hold do indeed hold during iterations). Some more general checks are: Are you sure that solutions are unique? If ...

7

In addition to the things that @Dirk already states, run your algorithm on a problem that is simple enough that you can do each step of the algorithm exactly on a piece of paper. Then compare what your algorithm actually does. For example, run it on a problem where you try to minimize a low-degree polynomial with linear constraints.

7

For a bounds-constrained problem to minimize $f(x)$ subject to $h(x)\ge 0$, there is no reason for $\nabla f(x^\ast)$ to be small at the optimum $x^\ast$. All the theory guarantees is that $\nabla f(x^\ast) + \lambda^\ast \nabla h(x^\ast)=0$ if the optimum is at a place where the bound is active. In your case, you are imposing the bound via a penalty ...

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-...

6

This is a linear programming feasibility problem (since you don't have an objective function to minimize or maximize.) You can simply use an objective function of $0$ and hand this off to any reasonable LP solver. You'll either get back a solution or the bad news that the problem is infeasible.

6

In general, one cannot expect rk4 to maintain quadratic invariants of the system, it simply doesn't do that. Methods that do maintain specific invariants have to be specially devised — this usually goes by the name of geometric integration. Symplectic integrators are the most common kind of these methods, although not for your problem. See, for example, the ...

6

Suppose that $\mathbf{x}\ge0$ and $\mathbf{y}\ge0$. Then a necessary and sufficient condition for $\mathrm{supp}\{\mathbf{x}\}\cap\mathrm{supp}\{\mathbf{y}\}=\emptyset$ is for the two vectors to be orthogonal, $\mathbf{x}^{T}\mathbf{y}=0$. Indeed, this is the familiar strong duality condition for linear programming: $$\mathbf{x}_{i}\mathbf{y}_{i}=0\;\forall ... 6 Problem Formulation I can't guarantee that this is a perfect (or smallest-possible) formulation of the problem, but maybe it will help guide a better one. The road network is a directed graph consisting of intersections (nodes) connected by roads (edges). As input information, assume that you have an adjacency matrix \mathcal{A} enumerating the edges. \... 6 One thing that makes your non-dimensionalized ODE confusing is that you use the same symbols for dimensionalized and nondimensionalized variables, even though they are different variables. Consider writing it in a different way: let there be a new set of variables, \tilde t, \tilde x,\ldots, all unitless, defined by$$ \tilde t = n_{\mathrm{time}}t, \...

6

Let's consider the following minimization problem \begin{align} & \text{minimize} && \tfrac12 z^\mathrm{H} P_0 z + q_0^\mathrm{H} z\\ & \text{subject to} && \tfrac12 z^\mathrm{H} P_i z + q_i^\mathrm{H} z + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\ &&& Az = b, \end{align} where $P_i$ are Hermitian matrices. The ...

6

You can parameterize your rank-1 matrix $A$ as $A=xs^{T}$ where $x$ and $s$ are the unknown $n$ by $1$ column vectors. You then have an unconstrained problem $\min f(x,s)$. Depending on the function $f$, it may or may not be easy to express $f$ as $f(x,s)$ rather than as $f(A)$, and $f(x,s)$ might or might not be (probably not in practice) a convex ...

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 If there's no mistake then it's much easier than I thought. We will show that the minimum is equal to the smallest component of$A$, denoted by$a_{i_0j_0}$where$(i_0,j_0) = \arg\min_{(i,j)} a_{ij}$, and attained when$x_{i_0}=y_{j_0}=1$and$x_i=y_i=0\quad\forall i\neq i_0,j\neq j_0.Indeed, we have \begin{align} x^TAy=\sum_{1\le i\le m}\sum_{1\le j\... 5 IPOPT is a good interior point method solver for convex nonlinear problems, and has a MATLAB interface, although I haven't used the MATLAB interface. (The solver, called from GAMS, is very good.) CVX is also a good package for convex problems, and YALMIP is slightly more general; both of these packages provide a modeling language for posing nonlinear ... 5 The constraint\mbox{rank}(X) <= d$is in general a non-convex constraint. Sorry. A commonly used approach is to minimize the Schatten 1-norm of X (the sum of singular values of X) as a surrogate for minimizing the rank. This works similarly to minimizing the 1-norm of a vector x as a way of minimizing the number of nonzero entries in x. 5 It's very difficult to provide a useful answer to this question because you haven't provided enough details about your problem and what you have already tried. There are various conditions under which the augmented Lagrangian method is certain to converge asymptotically to an optimal solution. You should make sure that the problem you're trying to solve ... 5 You can use a Test Driven Development (TDD), the ideas behind are: before write code you write the test with the expected result; every line of code (almost all lines) is under test so when you modify a line you can check if there is the correct behavior or side effects. With this methodology you can find and prevent some erros described by Dirk. To ... 5 Both approaches apply to the same problem (numerical minimization of functionals which involve the solution of a PDE, although both extend to a larger class of problems). The difficulty is that for all but academic examples, the numerical solution of the PDEs requires a huge number of degrees of freedom which a) means that it takes a long time and b) ... 5 There are specialized methods for the minimization of a differentiable function$f(X)$subject to the orthogonality constraint$X^{T}X=I$. See for example: Lai, Rongjie, and Stanley Osher. “A Splitting Method for Orthogonality Constrained Problems.” Journal of Scientific Computing 58, no. 2 (2014): 431–449. Wen, Zaiwen, and Wotao Yin. “A Feasible Method ... 5 In the specific problem you ask about (unlike Richard's more general answer), it turns out that you can relax the$=$constraint into a$\leqwithout changing the optimal value, and that the resulting convex problem can be solved with the CVX software Richard mentioned. Details: Intuitively the relaxation is possible since if the function had arc length ... 5 This is just an NLP (Non-Linear Programming) model. You can rewrite it as: \begin{align}\min \>& Z \\ & \sum_i w_i = 1 \\ & \sum_i f_i(w_i\cdot Z)\ge k\cdot Z \\ & w_i \in [0,1] \end{align} Getting rid of a division is always a good idea. If we can assumeZ\gt0$, then a slightly different formulation can look like:$\begin{align}\... 4 The isolated bilinear and trilinear terms make your problem nonconvex. (Occasionally, these terms can be gathered into sums or differences of squares, but that does not appear to be the case here.) Iff\$ is a twice continuously differentiable function, and you're interested in deterministic global optimization, you probably want to use a branch-and-bound ...

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