Questions tagged [nonlinear-programming]

Questions about the theory and numerical algorithms for optimizing (minimizing or maximizing) nonlinear functions, possibly subject to equality and/or inequality constraints.

Filter by
Sorted by
Tagged with
81
votes
17answers
91k views

Is there a high quality nonlinear programming solver for Python?

I have several challenging non-convex global optimization problems to solve. Currently I use MATLAB's Optimization Toolbox (specifically, fmincon() with algorithm=<...
21
votes
8answers
3k views

Software package for constrained optimization?

I am looking to solve a constrained optimization problem where I know the bounds on some of the variables (specifically a boxed constraint). $$ \arg \min_u f(u,x) $$ subject to $$ c(u,x) = 0 $$ $$ ...
15
votes
1answer
2k views

Intuitive motivation for BFGS update

I am teaching a numerical analysis survey class and am seeking motivation for the BFGS method for students with limited background/intuition in optimization! While I don't have time to prove ...
12
votes
2answers
1k views

Decomposition methods for solving large optimization problems

I was wondering if anybody had any suggestions for texts or survey articles on decomposition methods (e.g. primal, dual, Dantzig–Wolfe decompositions) for solving large mathematical programming ...
9
votes
2answers
1k views

Why is SQP better than Augmented Lagrangian for nonlinear programming?

In the technical report on Galahad[1], the authors state, in the context of general nonlinear programming problems, To our minds, there had never really been much doubt that SQP [sequential ...
9
votes
2answers
13k views

C++ library for nonlinear constrained minimization

I am currently trying to solve nonlinear constrained minimization problem as implemented in matlab "fmincon" function. My expectations are, minimize(fun1,x0,uB,lB,fun2) where x0 is initial state, fun1 ...
8
votes
3answers
2k views

Is there a constrained nonlinear optimization library like IPOPT that runs on GPUs?

Somebody on my team wants to paralelize IPOPT. (at least some of functions of it). I have not been able to find a GPU implementation of it or a similar package. Nor I've found anything on their docs. ...
8
votes
3answers
380 views

What is too big for standard linear algebra/optimization methods?

Different numerical linear algebra and numerical optimization methods have different size regimes where they're a 'good idea', in addition to their own properties. For example, for very large ...
8
votes
2answers
2k views

Minimizing a quadratic function with nonlinear constraints

what would be good methods (and/or software packages) to try for solving a problem minimizing a quadratic function $f(x) = \sum_{i=1}^N{(x_i - y_i)^2}$, s.t. $0 \leq x_i \leq 1$, and there are more ...
6
votes
4answers
2k views

parameters estimation

I have to estimate a parameter (K), but I don't know how I can do it. I think by a regression model (minimum least square?), but I'm not sure. The system is: ...
6
votes
2answers
2k views

linear independence constraint qualification: what to do when they don't hold?

I want to solve a general nonlinear constrained optimization problem $$\min_q\ f(q)\quad \textrm{s.t.}\quad g_i(q) = 0,\ h_j(q) \geq 0.$$ The problem is that while the equality constraints $g_i(q)$ ...
6
votes
1answer
437 views

Reducing degeneracy in constrained (convex) optimization problem

DISCLAIMER: I've edited the question repeatedly for clarity and to target the most relevant answer. I have the following general problem $$ \min \|h_1\cdot h_2\|^2 $$ such that $$\|g_1\wedge g_2-h_1\...
5
votes
2answers
209 views

Is there guaranteed global solver for such an eigenvalue problem?

The original nonlinear optimization problem I have is as follows: For constant symmetric matrices $A=A^T, B_i=B_i^T(\forall i\in\mathbb{N}) \in \mathbb{R}^{n\times n}, \text{rank}(A)=n,$ $$\arg\min\...
5
votes
2answers
266 views

Levenberg optimizer halts quickly when given more variables, or fewer constraints

I'm using the g2o C++ optimization library to refine a GPS trajectory using accelerometer data. The program uses a Levenberg-Marquardt optimizer over data points representing the position and ...
5
votes
2answers
1k views

Scaling of optimisation function in non-linear least squares problem

Suppose I am minimizing the following function: $$g(\alpha)=\sum_{i=1}^n(y_i-f(x_i,\alpha))^2,$$ where $y_i$ and $x_i$ are data, $f$ is a known non-linear function and $\alpha$ parameter (of ...
5
votes
1answer
136 views

Largest hypercuboid inside a polyhedron

Given a polyhedron $\mathbf{Ax} \leq \mathbf{b}$, how to find the largest hypercuboid, with unknown center $\mathbf{x_{0}}$ and side lengths $2\epsilon_{i}$, which are aligned along the co-ordinate ...
5
votes
1answer
91 views

$L_2$ projection with integer constraints and prescribed sum

Suppose I am given a vector $v^0\in\mathbb{R}^n$ and integers $k,\ell\in\mathbb{Z}$. Assuming $k$ is close to zero (e.g. $0\leq k\leq5$), is there an algorithm for solving the following integer ...
5
votes
2answers
2k views

How to solve a Rayleigh-quotient-like minimization with inequality constraints

What I am trying to solve is the following Rayleigh-quotient-like minimization: \begin{eqnarray} \begin{split} (P_0)\quad\min_x \frac{\left( Ax - b\right)^\top \left( Ax - b\right)}{x^\top x}\\ s.t. \...
4
votes
2answers
7k views

Tikhonov regularization in the non-negative least square - NNLS (python:scipy)

I am working on a project that I need to add a regularization into the NNLS algorithm. Is there a way to add the Tikhonov regularization into the NNLS implementation of scipy [1]? [2] talks about it, ...
4
votes
2answers
1k views

Line search for Newton method

If we want to solve nonlinear minimization problem $$\min_{x} f(x),$$ making least-squares assumption and using Gauss-Newton method so that at k$th$ iteration we have: $$J_k^T J_k p_k = - J_k^T ...
4
votes
2answers
791 views

nonlinear conjugate gradient for multivariable functions

For the optimization problem $\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$, we can use the following standard nonlinear conjugate gradient method to find the solution: $...
4
votes
2answers
2k views

Optimization with matrix determinant as constraint

I'm solving a constrained optimization for matrix $\mathbf{A}$ with dimension 6x6, where one of the constraints is $\mathrm{det}(\mathbf{A})>0$. I use the NLopt package to solve my problem and ...
4
votes
1answer
178 views

Piecewise linear optimization with resource allocation constraints

I have this problem: \begin{align} \min_{\mathbf{w}} & \sum_{i=1}^N c_i P_i(w_i)\\ s.t & \notag\\ & \sum_{i =1 }^N w_i = w \\ & 0 \leq w_i \leq w_{max},~~\forall i \in 1, ..., N \...
4
votes
2answers
331 views

best way to optimize a function with linear/non-linear parameters

I am trying to fit some raw data using a function of the form $f(r) = \sum_{i=1}^{K} d_kS_k(n_k,\alpha_k,r)$ where $S_k(n_k,\alpha_k,r) = \frac{\alpha_k ^{n_k+3}}{(n_k+2)!}r^{n_k}\exp(-\alpha_kr)$ ...
4
votes
1answer
196 views

How to solve the following Frobenius norm-minimization problem?

Background We know how to solve the following minimization problem $$ \min_{X} \lVert AX - B \rVert_F^2 $$ But what about the extended version? $$ \min_{X} \lVert A \begin{bmatrix} X & X^2 \...
4
votes
1answer
332 views

Does the amount of correlation of model parameters matter for nonlinear optimizers?

I am using nonlinear optimizers such as BOBYQA to train a model with 10-20 parameters. It so happens that some of the parameters have high correlation. Roughly speaking, imagine that you are fitting ...
4
votes
1answer
225 views

constrained minimization in N dimensions

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ f\...
4
votes
1answer
319 views

Sum of Inverse of Variables in an Optimization Problem

I have the following optimization problem: $$ \begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array} $$ where ...
4
votes
2answers
674 views

Large-scale nonlinear optimization problem

I want to solve a nonlinear optimization problem of the following form \begin{equation} min( \sum_i d^{x_i}c_{i})\\ 0 \leq x_{i} \leq a\\ \sum_{i} x_{i} \leq b \end{equation} $a$, $b$, $0.95 < d ...
4
votes
1answer
173 views

Is there a nonlinear solver similar to CGNR evaluating only $A^TAx$?

First of all, I am quite new to this field and I excuse myself in advance for any stupid content in this question. In the field of compressed sensing or deblurring I have a nonlinear optimization ...
4
votes
1answer
233 views

Methods for Constrained Optimization Problems with Box Constraints

Consider this problem: \begin{equation} \begin{array}{ll} \text{minimize } & f(x) \\ \text{subject to } & a \leq x \leq b \end{array} \end{equation} where $a,b,x \in \mathbb{...
3
votes
2answers
175 views

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

In the following problem, $A$ is a given $\mathbb{R}^{m\times n}$ matrix: \begin{align} \mbox{minimize}\quad & x^TAy \\ \mbox{subject to}\quad & 1^Tx=1^Ty=1, \\ & x\ge 0,y\ge 0. \end{...
3
votes
1answer
200 views

How to solve this optimization problem with abs object function?

Helo, every one. May I ask for help about how to solve this problem. $\begin{align} & \text{max}_{x_i} \quad |\sum_{i=1}^{4} a_i x_i | \\ & s.t. \quad \sum_{i=1}^4 x_i^2=1 \end{align} $ ...
3
votes
1answer
197 views

Can BFGS be used to minimise several functions at once?

I have multiple objective functions which are related to several parameters. I want to minimise more than one objective functions using several parameters. Is it even possible using BFGS? When I used ...
3
votes
2answers
122 views

MINLP with GEKKO - Modeling discrete variables

I'm trying to define a MINLP optimization problem with GEKKO in Python, and I want to use some variables with fixed values. For my first variable, x1, I need to define the following values (as would ...
3
votes
2answers
66 views

Gradient of function after renormalization of variables

I have to minimize a function $f(\mathbf{x})$, where the vector $\mathbf{x}\in\mathbb{R}^n$ satisfies $|\mathbf{x}|=1$. So I tweaked the code of $f$ so that it renormalizes $\mathbf{x}$ as the first ...
3
votes
1answer
260 views

minimization of normalized constrained quadratic function

I'm a computer science student. Please I need a help in solving a constrained normalized quadratic function. I'm familiar with solving quadratic constrained optimization function with matlab by ...
3
votes
2answers
503 views

Affect of approximating a non-differentiable function on optimisation of minimisation

I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable. My question is what ...
3
votes
1answer
74 views

Geometric Programming - symbolic version

I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
3
votes
1answer
260 views

Symmetric nonnegative matrix factorization

Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving $$ \begin{array}{rl} \min_U & \sum_{ij} \left(A_{ij}\ln\frac{A_{ij}}{[UU^\top]_{ij}}+[...
3
votes
2answers
133 views

A separable nonnegative quadratic program

I have spent quite some time trying to solve the following quadratic program: $$\min \sum_{i=1}^n (\frac{1}{2}x_i^TQx_i+c_i^Tx_i), \quad \mathrm{s.t. } \quad x_i\ge 0 \quad \forall i,$$ where $n$ is ...
3
votes
1answer
146 views

Excluding roots from a system of nonlinear equations

I have a system of nonlinear equations of which I know it has a single root I am interested in, and has a continuum of roots I am not interested in. I am currently using Newton with line-searching in ...
3
votes
1answer
129 views

Obtaining a feasible solution for underdetermined system of linear equations satisfying inequality constraints

I would like to obtain a feasible solution for an under-determined system of linear equations, $$Ax=b$$ where, $A \in \mathbb{R}^{7\times9}, \, x \in \mathbb{R}^{9\times1}\text{and } b\in\mathbb{R}^...
3
votes
2answers
723 views

NP-Completeness

Consider an instance of non-convexoptimization problem: It seems that this problem is NP-complete. How can I find a suitable reduction for this?
3
votes
1answer
231 views

Why do active set methods or the simplex method pivot only one variable at a time?

Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
3
votes
0answers
71 views

Large-scale optimization of nonlinear equations

I'm looking to find a computationally efficient solution to a large system of nonlinear equations. I'm trying to maximize the following function: $$ f(\vec{x}) = \sum_i^N C_i (x_i-A_i)x_i^{\epsilon_{...
3
votes
0answers
27 views

How to set up and solve acceleration-limited trajectory optimization problems?

I've been trying to learn how to solve simple acceleration-limited trajectory planning problems. I'm working in C++ and I've been using the Eigen library to do linear systems solving. I'm doing the ...
3
votes
0answers
160 views

Find constrained vectors maximizing angles between them - methods?

This is related to a question I had asked earlier, with the distinction that earlier I did not have a non-linear objective functional to minimize. The problem is reproduced below with added ...
3
votes
0answers
104 views

Efficient principal pivots

It was suggested I should try posting this question here from Mathematics Background I'm working on a numerical linear algebra package in C#. I'm trying to implement a variety of "principal ...
2
votes
1answer
438 views

0,1 binary polynomial programming

Is there a mathematical optimization branch that explicitly tries to optimize this (type) problem? $$\eqalign{ & \min \cr & \sum\limits_{i = 1}^N {(J*s[i] + {J_1}*s[i]*s[i + 1] + {J_2}...