Questions tagged [nonconvex-programming]
For questions about non-convex optimization problems where the objective or any of the constraints are non-convex.
72
questions
1
vote
1
answer
28
views
$\min\{f(x_1),\dots,f(x_n)\}$ with other constraints
I have an optimization problem which goes:
\begin{align*}
\text{Minimize:}
\\
& \sqrt{x} + \sqrt{y} \tag{NL-objective}
\\
\text{Subject to:}
\\
&3x + 2y \geq 2 &...
- 11
1
vote
2
answers
113
views
Is there a way to obtain coefficient matrix A and RHS b of constraints equation from cplex or guribi in python?
I have a non-linear program, minimizing sum of concave functions subject to linear constraints. Hence I'm using a different solver(in Julia). However, that solver assumes we have constraints in $Ax \...
- 57
2
votes
2
answers
83
views
Potential methods for solving quadratic optmization problem
I am trying to solve a non-convex optimization problem with the help of sequential quadratic programming.
I need to develop an algorithm inside SQP to solve this subproblem. What potential methods (...
1
vote
1
answer
32
views
Non convex quadratic problem with complex variables
I am trying to solve a non convex optimization problem with the help of sequential quadric programing. My optimization variables are complex and I have expressions for gradients, hessian etc but all ...
1
vote
2
answers
103
views
My barrier function is always giving a complex number
I am working on implementing the interior point method, and the barrier function always gives me a complex number. B(x) = f(x) - t * sum(ln(hi(x))). I have changed the value of 't' to see the B(x) ...
1
vote
2
answers
548
views
Non linear programming
I want to solve a large scale non linear optimization problem and there are two methods interior point method and sequential quadric programing usually used to solve non linear optimization problem. I ...
2
votes
1
answer
108
views
Formulation of nonlinear nonconvex optimization problem and finding appropiate solver
Consider the notation and objective below for this sequential resource allocation problem:
Allocation channels $i \in (1, 2)$
Spend/Cost timestep i channel j: $C_{i, j}$
Total resource: $B$
Horizon: $...
2
votes
2
answers
251
views
An if-then-else logic to construct constraint
I was hoping to get some help in modelling the following logic, I know that it would use some kind of Big M formulation but I am not sure how. Thank you in advance!
$\Omega$ is a set whose values are ...
- 33
-1
votes
1
answer
99
views
Ipopt finds a better solution if I do not eliminate the zeros in the hessian matrix ?(we eliminate the zeros by defining the structure)
I use Ipopt to solve a problem with sparse hessian and jacobian matrices.
If I provide the hessian matrix: its structure, and the non zeros elements in the hessian matrix, it will be really fast.
If I ...
- 391
0
votes
1
answer
70
views
The max_wall_time and max_cpu_time in ipopt are not working?
The max_wall_time and max_cpu_time are not working in ipopt (cyipopt).
See example:
...
- 391
0
votes
0
answers
65
views
Can we use the Jax library with ipopt to calculate the hessian matrix and Jacobian and still be able to define the structures?
When solve with ipopt, we can use Jax to calculate the hessian matrix and jacobian instead of providing it ourselves. However, ipopt with Jax is very slow for large problems.
If we calculate the ...
- 391
1
vote
1
answer
196
views
Should I provide the hessian matrix, hessian structure, and Jacobian structure if I use cyipopt (IPOPT) if I am concerned about computation time?
If I use IPOPT (cyipopt) to solve nonlinear problems of large scale. It is optional to provide or not provide the hessian matrix, hessian structure, and Jacobian structure.
The question is which one ...
- 391
2
votes
0
answers
55
views
Minimizing sum of similar functions with a dependence
Consider an objective function in the form of minimization of maximization that is the sum of $N$ similar functions $f\left(x\right)\ge 0$, $\ \forall x$. The summation of all variables is constant (e....
4
votes
0
answers
82
views
How to linearize or convexify a constraint with a square root of sum of two variables?
Here is the constraint:
$$\text{Pa} + \text{Pb}=a + b \sqrt{\text{Ir}^2 +\text{Ii}^2} + c (\text{Ir}^2 +\text{Ii}^2)$$
Here $\text{Pa}, \text{Pb}, \text{Ir},$ and $\text{Ii}$ are variables. $a, b, c$ ...
1
vote
2
answers
121
views
Does the cvxpy replace the max function by MIP formulation under the hood?
Does the cvxpy replace the max function, which is convex, by MIP formulation under the hood when shows up in the constraints (for example, $\max(x,y)\le z$) or in the objective function? In gurobipy, ...
- 391
4
votes
1
answer
296
views
Endowment of an agent
I was going through the Shapley-Folkman-Starr Lemma (https://simons.berkeley.edu/sites/default/files/docs/3605/simons2.pdf) and I came across the term "endowment" of an agent.
My assumption ...
- 111
2
votes
1
answer
90
views
How do we call this optimization problem?
Let $f_k\colon\Bbb R^n\to\Bbb R$, $k=1,\dots,K$, be differentiable (possibly nonconvex) functions and $X\subset\Bbb R^n$ be a convex set.
Consider the following optimization problem:
$$
\min_{x\in X}\...
- 155
1
vote
0
answers
65
views
Does Gurobi solve QCQMIPs with Quadratic terms faster with then Bi-Linear terms in general?
Based on the color distance function defined here i try to find $n$ RGB colors with large inter set color distances and good color distance to white.
...
- 3,945
3
votes
1
answer
72
views
Methods to solve integer linear inequalities with products of two variables
I'm interested in solving the following system of equations over the integers:
\begin{align*}
x_l^3 &\le x_l^1x_l^2 & \text{ for } l = 1,\ldots,s \\
A x &\le b \\
0 &\le x
\end{align*}
...
- 173
8
votes
1
answer
240
views
Maximize correlation subject to nonconvex correlation constraints
Let $r, z$ and each of $u_i$ be a length $n$ vector. I’d like to maximize the correlation between $z$ and $r$ (when that correlation is positive) while keeping $z$ “away” from $u_i$’s. Formally,
\...
- 81
2
votes
0
answers
58
views
FOC point vs Stationary point in local optimization
In this SIAM Review paper the authors are giving the following necessary condition for a point being a local maximum of a convex function:
Let $F: \mathbb{R}^n \mapsto \mathbb{R}$ be convex. If $x$ ...
- 3,808
4
votes
1
answer
109
views
Convex-Constrained Nonconvex-Nonconcave Minimax Problem
In the mathematical optimization theory, I have taken a glance at many papers which deal with the unconstrained convex-concave or nonconvex-concave minimax optimization, i.e.,
$$
\min_{x\in X}\ \max_{...
- 155
4
votes
3
answers
139
views
How to find the point on the exterior of a given set of points?
Suppose we do have a set of points (all on a plane ).
How to find the smallest hull containing all these points ?
How to find the points (among these given points) that are at the exterior layers of ...
- 1,120
1
vote
2
answers
195
views
Branch and bound method for solving non-convex integer non-linear multi-objective optimization problem?
Following are the characteristics of my problem:
Objective function: two non-linear functions and one linear function
Decision variable: two integer variables ($X_1$ and $X_2$)
Constraint: three (two ...
- 159
5
votes
1
answer
420
views
What methods are used to solve multi-objective optimization problem with non-linear objective functions and integer decision variables?
Case 1: NLP
When either the objective function or at least one of the constraints or both are non-linear it is a NLP. We use generalized reduced gradient or Quadratic Programming to solve NLP. However,...
- 159
4
votes
1
answer
423
views
How to linearize a non-convex optimization objective function?
The non-convex multi-objective optimization problem in my case is defined below:
Objective 1: Minimize $f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)+C_3X_1+C_4X_2+C_5(X_2^2/X_1)$
Objective 2: Minimize $...
- 159
4
votes
1
answer
151
views
Maximization of a nonconvex bi-variate function
Suppose we have a bi-variate function like $f(x,y)$ which is concave in $x$, $\frac{d^2f(x,y)}{dx^2} = -g(x,y)<0$ (that is $f(x,y)$ can be a function with high order in $x$ ) but convex in $y$, ...
- 2,140
4
votes
1
answer
209
views
Is it always possible to optimize a multivariate function sequentially?
Suppose we have a multivariate function like $f(x,y,z)$ which should be maximized with the constraints $g_i(x,y,z)\le 0 \quad \forall i$. The general rule is to use KKT conditions and derive all KKT ...
- 2,140
1
vote
1
answer
99
views
Maximization of a differentiable and nonlinear function over a bounded space
I have a nonlinear bi-variate optimization problem like $\max \: f(x,y)$ where $f(x,y)$ is a nonlinear and differentiable function of both variables, and $0\le x\le 1$, $\:0\le y \le ub$. In order to ...
- 2,140
3
votes
1
answer
223
views
Non-Convex QCP model - Used Method in Gurobi
I have the following question:
I have a non-convex QCP model. In the parameter description for method it says that "Only barrier is available for continuous QCP models". However, the dual ...
- 291
1
vote
1
answer
275
views
How to convexify log(convex) function?
I have the following optimization problem: \begin{align}\max_x&\quad\log_2(1+|a+bx|^2+cx^2)\\\text{s.t.}&\quad0\le x\le1\\&\quad(1-x^2)\ge\text{constant}\end{align} where $a$ and $b$ are ...
1
vote
1
answer
153
views
Find an upper bound for an objective function
My objective function is $\log_2(1+{x^2y^2})$ and I found two upper bounds for $x^2$ and $y^2$.
For example, assumed that we have the following upper bounds:
$x^2\leq\text{constant}_1^2$ and $y^2\leq\...
1
vote
1
answer
206
views
Non-linear optimization local or global solution
In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
- 81
4
votes
0
answers
73
views
How can non-polyhedral sets be investigated?
To derive problem-specific cutting planes for some given problem (think something like TSP problem), one common way is to study small examples. To this end, one can create small instances for the ...
- 3,557
4
votes
1
answer
499
views
how to implement an optimization function with polynomial in Gurobi (Java)
I have the following problem:
I have an objective function with the optimization variable $x$, which looks simplified like this:
$ZF = (a+b)*(x+1)$
Here $a$ is simply a constant value.
However, behind ...
- 291
4
votes
1
answer
312
views
Maximizing a piecewise-linear convex function
Note: Initially posted on MathOverflow.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:...
- 141
11
votes
2
answers
2k
views
Trustful Nonlinear Programming
Is it possible for an NLP solver to claim that a knowingly feasible problem is infeasible?
Shouldn't the solver be able to provide a solution (of course not necessarily the global optimum but a ...
- 2,132
3
votes
1
answer
75
views
Maximize $\sum_{i=1}^n 1/x_i$ subject to an SDP constraint
I would like to solve the following problem: \begin{align}\max_{x_1, \ldots, x_n}&\quad\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}\\\text{s.t.}&\quad\sum_{i=1}^n x_i A_i \succeq A_0\...
- 31
3
votes
1
answer
170
views
"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?
Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints:
$$0\le v\le a$$
$$0\le w\le 1$$
$$w_1+\...
- 235
3
votes
0
answers
41
views
Stationary conditions for intersection
I wondered about this question for sometime.
Definition of Stationarity
(P)
$\mbox{min} f(x)$
s.t
$x\in C$
Let $f$ be $C^1$ function over a closed and convex set $C$ . then $x^*$ is called a ...
- 405
2
votes
3
answers
348
views
Find the farthest point in hypercube to an exterior point
Let $\mathcal{U} = \{ [x_1, ..., x_n] \in \mathbb{R}^n : 0 \leq x_i \leq 1\}$ be the unit hypercube and $C \in \mathbb{R}^n\setminus\mathcal{U}$ fixed. Let us consider the following problem
$$ \max_{X ...
- 497
2
votes
1
answer
189
views
Stationary condition for unit simplex
Consider the minimization problem $$\min_{x \in \Delta_n} f(x)$$ where $f$ is $C^1$ function over the unit simplex $\Delta_n$. Prove that $x^*\in\Delta_n$ is a stationary point of the problem iff ...
- 405
5
votes
0
answers
112
views
Is there a way to use lazy constraints with Baron?
I am solving a non-linear mixed-integer programme with BARON. The objective function looks like $\big( \sum_i x_i \big) \cdot \big(\prod_i e^{-y_i}\big)$ (binary $x$ and real-valued $y$) and it has ...
- 2,043
2
votes
2
answers
662
views
Pyomo + Ipopt. Speed Issue
I am using Pyomo + Ipopt as solver to solve a NLP problem. The problem is not extremely complex in terms of dimensionality and ...
- 1,429
3
votes
0
answers
89
views
Appropriate Rotation Matrix in Nonconvex Optimization with Barrier
Let $ x \in \mathbb{R}^n_+$ be a variable such that $\sum_{i=1}^n x_i = 1$. In other words, $x$ is in a probability simplex. I am working on barrier-like functions in nonconvex optimization over such ...
- 3,808
6
votes
0
answers
130
views
Cases where RLT/SDP relaxation does not work well with standard quadratic optimization
(For people who don't know what RLT is): I am maximizing an indefinite quadratic function over a standard simplex, i.e., the standard quadratic optimization problem. A well-known approach is to relax ...
- 3,808
4
votes
0
answers
160
views
Fast solvers for LASSO-type non-convex optimization problems
Given $y \in \mathbb{R}^{n \times 1}, X \in \mathbb{R}^{n \times p}$, $p > n$, assume a LASSO-type optimization problem in the form of
$$ \hat\beta=\underset{\beta}{\operatorname{argmin}}\frac{1}{2}...
- 141
6
votes
1
answer
184
views
Convexity of the variance of a mixture distribution
$X$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X \sim \sum_{i=1}^N w_i \cdot \mathbb{U}(x_i, x_{i+1}),$$
where $\mathbb{U}(x_i, x_{i+1})$ denotes ...
- 3,808
7
votes
1
answer
123
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 ...
- 239
6
votes
1
answer
117
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 ...
- 329