11 votes

What is required of the objective function in order to use Gauss Newton method?

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 ...
user avatar
10 votes
Accepted

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

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 ...
user avatar
8 votes
Accepted

Convex Optimization problem with sum of absolute value constraints

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} |...
user avatar
8 votes
Accepted

How do I check if a loss function can achieve its minimum?

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. ...
user avatar
8 votes
Accepted

Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?

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 ...
user avatar
  • 188
7 votes

Looking for name of optimization problem in form $\min \mathrm x^T \mathrm A \mathrm x$ subject to $\|\mathrm x\| = 1$

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 ...
user avatar
  • 101
7 votes

How to debug a constrained optimization algorithm?

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 ...
user avatar
  • 1,728
7 votes

How to debug a constrained optimization algorithm?

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 ...
user avatar
7 votes

Why would BFGS converge to a local minima of a non-convex function but maintain a large gradient?

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^...
user avatar
6 votes
Accepted

How to determine whether two cylinders intersect or not?

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 ...
user avatar
  • 331
6 votes
Accepted

Linear system solution with inequality constraints - methods?

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 ...
user avatar
6 votes
Accepted

Integration of differential equation with orthogonality constraint

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 ...
user avatar
  • 11.4k
6 votes
Accepted

Intersections of supports constraint

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 ...
user avatar
6 votes
Accepted

How to create an optimal pizza delivery plan and how to visualize it

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 ...
user avatar
  • 1,522
6 votes

Scaling/nondimensionalization for numerical optimization

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 ...
user avatar
  • 11.4k
6 votes
Accepted

Solvers for Quadratically Constrained Quadratic Programs (QCQP) with complex variables

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{...
user avatar
  • 8,006
6 votes
Accepted

Optimization with the constraint of rank=1

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 ...
user avatar
5 votes

Looking for open source numerical solver

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 ...
user avatar
5 votes
Accepted

Find $\min x^TAy$ subject to $1^Tx=1^Ty=1,x\ge 0,y\ge 0$

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}$...
user avatar
  • 505
5 votes
Accepted

Converting convex quadratic constraint to linear matrix inequality (LMI)

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. ...
user avatar
5 votes
Accepted

Rank constrained SDP

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 ...
user avatar
5 votes
Accepted

How to understand what's going wrong in a code for solving a problem with augmented lagrangian?

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 ...
user avatar
5 votes
Accepted

How to debug a constrained optimization algorithm?

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 ...
user avatar
5 votes
Accepted

Checking the feasibility of a system of inequalities

You can check feasibility of a set of linear inequalities by constructing a linear programming (LP) problem with a "dummy" objective, e.g., $$ \begin{align} \max_{\{x_i\}_{i=1}^n} &\;0\\ \text {...
user avatar
  • 731
5 votes
Accepted

Simulation-based Optimization vs PDE-constrained Optimization

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 ...
user avatar
5 votes
Accepted

Maximize a function of an orthogonal matrix

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 ...
user avatar
5 votes
Accepted

How to solve calculus of variations problems numerically?

In the specific problem you ask about (unlike Richard's more general answer), it turns out that you can relax the $=$ constraint into a $\leq$ without changing the optimal value, and that the ...
user avatar
  • 402
5 votes

How can I deal with optimization problems that have a sum of functions of Z as a constraint when Z is the quantity to be minimized?

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] \...
user avatar
4 votes

I have to solve a large binary programming task. Should I avoid branch and bound?

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 ...
user avatar
4 votes

How to test convergence of an algorithm for constrained optimization

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

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