We’re rewarding the question askers & reputations are being recalculated! Read more.
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

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


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

Depending on the problem structure, you can solve the ill-conditioned Augmented Lagrangian system directly. For example, BDDC/FETI-DP can solve almost-incompressible elasticity in primal form with a convergence rate independent of the Poisson ratio (piecewise constant on subdomains, but with arbitrary jumps). Similarly, multigrid methods that exactly ...


6

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


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

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


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

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

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.


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


4

10,000 variables is a lot for an integer programming problem, but everything depends on the details of your particular problem. With the information provided, there's really no way for us to tell you in advance how easy or hard it might be to solve this problem. My advice would be to try CPLEX's integer programming solver on this problem with its default ...


4

Unfortunately, L-BFGS-B simply isn't designed to handle this kind of problem. Here are a couple of suggestions that might be helpful. If you can define a smooth extension to your function $f(x)$ which increases very rapidly in value outside of the feasible region, then you may be able to get reasonable results using L-BFGS-B or some other unconstrained ...


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.) If $f$ is a twice continuously differentiable function, and you're interested in deterministic global optimization, you probably want to use a branch-and-bound ...


4

Introduce extra variables for the spoiling terms in the KT condition, and you can find a bigger symmetric system that is numerically well-behaved, with only the inverse of the penalty factor entering the matrix. To solve the ill-conditioned system $(A+\rho C^TC)x=b~$ when $\rho$ is large, introduce $y=\rho Cx$ and recast your problem in the form $Ax+C^Ty=b$,...


4

The first order necessary optimality conditions for a minimization problem with inequality constraints are not that the gradient vanishes, since the minimum can be attained at the boundary of the feasible set (where only the directional derivatives into the interior of the set have to be non-negative, i.e., going away from the boundary leads to an increase ...


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