Questions tagged [nonlinear-programming]
For questions about mathematical optimization problems involving a nonlinear objective function and/or nonlinear constraints.
61
questions
9
votes
6answers
1k views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
7
votes
1answer
94 views
Minimizing sum of functions with pairwise dependence
I have formulated a problem where I need to minimize the sum of $N$ functions, with only pairwise dependence between the functions (any single constraint involves only two functions having adjacent ...
6
votes
1answer
77 views
Does strong duality hold when I dualize only a subset of the constraints?
Suppose I know that for some non-convex program:
\begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align}
strong duality holds for this problem. Now, suppose I form ...
3
votes
0answers
45 views
Linearisation using SOS2
I am trying to linearise the following expresssion.
$C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $
I am trying to do this by using SOS2 sets.
I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
6
votes
2answers
151 views
Find Euclidean sub-distances for a given distance matrix
Assume I have a matrix $(d_{ji})_{ij}$ of distances between points $i$ and $j$. These distances could be anything fulfilling the triangle inequality.
Now I would like to find coordinates $(x_i,y_i)$ ...
2
votes
0answers
88 views
Gurobi is unable to give an optimal solution even when it exists
I am trying to solve Logarithmic Fuzzy Preference Programming (LFPP) for criteria weight evaluation, based on fuzzy comparisons between criteria, and I am solving it with Gurobi in Python 2.7. It is a ...
1
vote
1answer
63 views
Simple nonlinear programming using convexity analysis and KKT
I want to solve the following two-variate nonlinear programming using KKT conditions:
$$ \begin{align} \begin{split}
\max \quad & 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} \\
\text{s.t.} \quad &...
1
vote
1answer
142 views
How do I solve this Optimization problem?
Optimization of a simple expansion problem
minimise:
$$
\sum_{t=1}^{5}\left[\sum_{i=1}^{2}x_{i,t}CC_i\left(\frac{1+EIC}{1+r}\right)^t+UE_t*C_{UE}\right]
$$
subject to:
$$
0 \leq x_{i,t} \leq 5 \\
...
2
votes
1answer
92 views
How to detect unbounded problems
How can I algorithmically detect whether an (MI)NLP problem is unbounded or not?
Finding a source for this has proven tricky, because people in the literature seem to talk a lot about what to do if ...
4
votes
2answers
148 views
Is There Another Way To Code The Idea of a MAX Constraint Without The Use of Binary Variables?
I have a constraint of the following form that describes the growth of trees, where the population of trees in period $t$ is the previous period's population minus some trees infected with a virus:
$...
4
votes
0answers
43 views
Identifying saddle point in constrained optimization
Suppose we are minimizing $f(x)$. The first order necessary condition of $x^*$ being local minmum is:
$$\nabla f(x^*)= \mathbf{0}.$$
For sufficiency, we check if also $\nabla^2f(x^*) \succ 0$, i.e., ...
6
votes
3answers
988 views
Is it abnormal for a model to take 8+ hours to solve?
I am building my first optimization model, it is quite large and also a non-linear problem. I have had my model solving on the NEOS Optimization Server and after 8 hours of trying to solve, the server ...
3
votes
1answer
111 views
Rolling Horizon Methods in Knitro
I am trying to solve an NLP using the Knitro solver, but I am beginning to think that I will not be able to solve the model because it is too complex. I have heard that "rolling horizons" can be used ...
5
votes
2answers
112 views
Minimizing $x_1/x_2$ over a simplex in the positive orthant
I need to solve the following problem
\begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix.
The best thing I can think ...
4
votes
1answer
104 views
Software for multi-objective optimization
I am looking to solve a multi-objective chance-constrained blending problem. Are there any suggestions about the software to use to try and solve a problem like this?
4
votes
1answer
76 views
How to convert non-normal probabilistic constraints to deterministic ones for mathematical modelling?
I am working on a chance-constrained optimisation model that takes into account uncertainty. I am aware of how to convert constraints that are of a probabilistic nature into the equivalent ...
6
votes
1answer
74 views
Nonsmooth constrained convex optimisation: convergence results?
I am working on a projection problem on a very large set of highly related constraints:
\begin{align}
\min_x & \quad\|x-x_k\|_2^2 \\
\mathrm{s.t.} & \quad\max_{T\in\mathcal{T}} \sum_i \frac{...
12
votes
1answer
81 views
Benders subproblem feasible region dependent upon solution master problem
Suppose I want to solve a naturally MINLP problem of the following form:
$$
\min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}, y \in \mathbb{R}^+\}
$$
Here $G(x)$ ...
8
votes
1answer
146 views
Can Gurobi or CPLEX handle nonlinearly constrained problems?
Though my title is quite general (please feel free to edit), indeed, I wonder if the following models can be solved in Gurobi or CPLEX. Model 2 is just an alternative one to Model 1. Although we ...
4
votes
1answer
68 views
Dealing with a non-convex problem
I have the following objective function. The variables: $h_p$, $e_{trs}\left(h_p\right), w_{trs}\left(h_p\right)$ are all non-negative continuous. $T,R,S,\pi_{trs}$ are polynomially-sized sets. All ...
6
votes
4answers
139 views
Sequential quadratic programming source
What are the good text books to learn SQP? Are there any online courses that you can suggest?
6
votes
1answer
63 views
How to minimize a weighted sum of RMSE-like terms?
I am trying to solve the following problem: \begin{align}
\min&\quad f(x) = \sum_{i=1}^{n}{a_ix_i} + \sum_{i=1}^{n}{b_i\sqrt{\sum_{j=1}^{m}{\left(y_{i,j}-x_i\right)^2}}}\\\text{s.t.}&\quad
x_{...
8
votes
2answers
257 views
How can I transform this MILP into an LP problem?
I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
10
votes
1answer
190 views
Linearization of the product of two real valued variables - Binary expansion approach
I want to minimize the following objective function:
\begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align}
Since the objective function is ...
12
votes
2answers
200 views
Can Tuning Knitro Solver Considerably Make A Difference?
I have an NLP that I am hoping to solve with Knitro and I am aware of a multitude of different settings that you can "tune" in order to improve solution performance. I am not familiar with ...
11
votes
1answer
345 views
Suggested Resources for Non-Linear Optimization
I recently completed an undergraduate course in Linear Programming and Operations Research. I am willing to look into advanced concepts and Non-Linear Optimization algorithms and also, their method of ...
7
votes
1answer
148 views
Is this formulation linear or non-linear?
Can you help me figure out if this formulation constitutes a non-linear problem? I believe It is a linear problem but my solver (GAMS) is unable to produce a acceptable solution.
$x,y$ and $\text{...
7
votes
2answers
426 views
Why does a Max constraint work, but this non-negativity constraint does not?
Suppose I have the following constraint: \begin{align}x_{t} &= x_{t-1} + y_{t-1} - z_{t-1}\\x_{t} &\ge 0\end{align}
From my limited experience in coding my own problem, I have found that my ...
9
votes
1answer
135 views
Solving convex programs defined by separation oracles?
General question: What software can solve convex programs defined by a separation oracle?
The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I ...
5
votes
0answers
29 views
In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples
Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion.
...
11
votes
1answer
403 views
Solvers and saddle points
It seems like most solvers that can tackle nonlinear nonconvex optimization problems (e.g. IPOPT) operate on ultimately solving for the first-order optimality conditions. Can it therefore be assumed ...
10
votes
3answers
246 views
Parallel nonlinear solvers
I've noticed that parallel (CPU or GPU) nonlinear programming solvers are few and far between. It seems that if any parallelization is involved at all, it generally applies to solving the underlying ...
7
votes
1answer
229 views
Do the KKT conditions hold for mixed integer nonlinear problems?
I was wondering if the KKT conditions are applicable for for MINLPs, and if not, why not? What about the case when the integer variables are modeled using constraints involving just continuous ...
11
votes
2answers
465 views
Dedicated solver for convex problems
Are you aware of a fast solver (open source or commercial) for convex NLPs that is faster than IPOPT? I'm interested in problems in the 50K+ variable range, both dense and sparse. Ideally, it would be ...
15
votes
1answer
396 views
IPOPT with HSL vs MUMPS
What are the advantages (if any) of using IPOPT with HSL vs MUMPS? HSL has a reputation of being faster, but does it walk the walk? In particular, does HSL scale better for large-scale problems?
We ...
11
votes
0answers
122 views
Characterizing the solution of a (non) linear maximization program
I have the following maximization program
\begin{align}
\max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\
\text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \...
7
votes
1answer
99 views
Solutions to a parametrized optimization problem
I have the following maximization program
\begin{align}
\max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\
\text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \...
12
votes
2answers
160 views
Linearisation techniques for MINLPs
I am wondering what kinds of linearisations people do for MINLPs outside my field of expertise.
I work in global optimisation, so by "linearisation" we would typically mean one of the following:
...
8
votes
3answers
591 views
Matlab fmincon for a problem with many nonlinear constraints
Using Matlab to solve a problem which has linear objective function and many nonlinear constraints, I am trying to generate the inequality nonlinear constraints by a function and pass it to fmincon ...
14
votes
1answer
420 views
How to formulate a problem to prove/disprove convexity?
Given a general non-linear problem:
\begin{align}P:\qquad&\min_{x\in X} f(x)\\\text{s.t.}\qquad&g(x)\leq 0\end{align}
where $f$ is a non-linear function, $g$ is a vector of non-linear ...
4
votes
0answers
184 views
How can I formulate this multi-objective optimization problem?
Now, for each system $X$ $(X=A,B,C,E)$, my objective is
$$\max\min\frac{s_{x_u}}{d_{x_u}}$$
here, $x=a$ for system A, $x=b$ for system B and follows...
and for the whole system, my objective is
$$\max\...
12
votes
2answers
289 views
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
6
votes
1answer
118 views
Obtaining the intermediate solutions in AMPL
I know that for some solvers, for example, the constraint programming solver in Google OR-Tools, it is possible to see all the intermediate solutions that the solver finds while it searches for an ...
20
votes
4answers
1k views
Linearize or approximate a square root constraint
I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
14
votes
4answers
2k views
NLP solvers in pyomo other than ipopt?
I am solving a highly constrained (large number of constraints and large number of variables, but small degree of freedom) NLP problem, and for start, I was using Matlab's ...
8
votes
1answer
226 views
Disciplined convex programming representation of $x\cdot\min x$
How can I reformat the problem below to follow DCP rules?
DCP rules are Disciplined Convex Programming Rules that allow convex programs to be solved. DCP
Is there a way to reformat the problem ...
7
votes
1answer
252 views
How to reformulate (linearize/convexify) a budgeted assignment problem?
I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ ...
23
votes
5answers
4k views
Cubic programming and beyond?
It is almost inevitable in Operations Research to come across linear or quadratic programming problems. The overall structures of these problems are below: \begin{align}\begin{array}{ll}
\sf{Linear}\\
...
10
votes
1answer
222 views
Termination Criteria of Solver in Pyomo
I am solving a nonlinear optimization problem using Pyomo with Ipopt as solver. The solver exits with the status:
EXIT: Optimal Solution Found.
This I can cross ...
13
votes
1answer
333 views
Sum of Max terms maximization
Maximizing sum-of-max terms is an NP-hard problem. The objective function is a convex function and maximizing a convex function is a hard problem. Also, this is a non-differentiable function.
CPLEX ...
