Questions tagged [nonconvex-programming]
For questions about non-convex optimization problems where the objective or any of the constraints are non-convex.
54
questions
3
votes
1
answer
60
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*}
...
- 131
8
votes
1
answer
210
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
44
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,776
4
votes
1
answer
81
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_{...
- 133
4
votes
3
answers
120
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
vote
2
answers
86
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
253
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
223
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
146
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,105
4
votes
1
answer
91
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,105
1
vote
1
answer
86
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,105
3
votes
1
answer
115
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 ...
- 191
1
vote
1
answer
188
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
86
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
168
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
69
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,467
4
votes
1
answer
339
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 ...
- 191
3
votes
1
answer
185
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:...
- 131
10
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 ...
- 1,936
3
votes
1
answer
61
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
123
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+\...
- 215
3
votes
0
answers
34
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 ...
- 395
2
votes
3
answers
343
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 ...
- 487
2
votes
1
answer
152
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 ...
- 395
5
votes
0
answers
80
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 ...
- 1,993
2
votes
2
answers
430
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,399
3
votes
0
answers
79
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,776
6
votes
0
answers
113
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,776
4
votes
0
answers
122
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
153
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,776
7
votes
1
answer
114
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 ...
- 229
6
votes
1
answer
100
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
8
votes
2
answers
133
views
(Iterative?) Solutions to a certain quadratic program with non-convex constraints
Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$
I would like to efficiently solve the following problem:
Problem 1
Choose $\alpha,z\in\mathbb{R}^m,\beta\...
- 215
2
votes
1
answer
96
views
AdaGrad - Sparsity of parameters
I read on Wikipedia:
AdaGrad (for adaptive gradient algorithm) is a modified stochastic gradient descent algorithm with per-parameter learning rate, first published in 2011. Informally, this ...
- 129
5
votes
2
answers
140
views
Local optimum of dual of non-linear program
In general, suppose you have a non-convex optimization problem with constraints and you form the dual problem. If you find a local optimum for the dual problem, will the corresponding primal solution ...
- 329
4
votes
1
answer
69
views
Maximizing 1-norm: using binary variables to relax non-convexity
It is well-known that when we maximize a 1-norm, e.g., $\|Ax\|_1$, we can use binary variables and obtain a mixed-integer convex problem (otherwise maximizing 1-norm is non-convex). I am mentioning ...
- 3,776
3
votes
0
answers
133
views
SDP relaxation with greater-than and less-than inequalities at the same time
I am dealing with the following nonconvex fractional quadratic optimization problem
\begin{align}
& \min_{\boldsymbol{x}} && \max_{t \in \mathcal{T}} \frac{\boldsymbol{a}_t^T \boldsymbol{...
3
votes
1
answer
489
views
Supported pyomo free solvers for (non-convex) quadratic programming
Any one had the chance to use pyomo with free/open-source solvers that handle quadratic optimization problems, which they could be convex or not, but preferably as general as possible.
- 534
3
votes
1
answer
192
views
Approximation methods for a mixed integer convex optimization problem
I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.
I am currently aware of AIMMS'...
- 3,776
4
votes
1
answer
176
views
Minimize a convex function over a sphere
Problem description
Let $\mathcal{C} = \{X \in \mathbb{R}^n \mid g(X) \leq 0\}$ with $g(X)$ a convex function. Suppose I need to solve the feasibility problem, for a given $r>0$
$$ \exists ^?X \...
- 487
4
votes
0
answers
92
views
Strong Duality and Slater Condition
I am studying the Duality Chapter of Convex Optimization by Boyd. Is it possible that strong duality holds for non-convex optimization? If yes, is there any specific condition? And, what is the ...
- 2,105
4
votes
1
answer
89
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 ...
- 1,229
6
votes
1
answer
173
views
Linearizing the square root of binary summations
My question is similar to this one and almost identical with this. I am so confused due to indexing and could not make sure if I could apply the solution in here to this indexed version as shown below....
- 1,229
6
votes
1
answer
74
views
Linearizing the square root of two binary summations
My question is similar to this one though a bit more complicated. Though my question also includes indices, I am removing them to ease readability.
Let binary variables $x,y\in\{0,1\}$, non-negative ...
- 1,229
13
votes
2
answers
1k
views
Is This Constraint Convex?
I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...
- 2,249
11
votes
1
answer
474
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 ...
- 695
9
votes
3
answers
631
views
Examples of problems with non-convex constraint functions but convex feasible region
I'm looking for examples of (classes of) problems with a non-convex, non-linear formulation, but convex feasible region.
That is, a problem of the sort:
$$
\begin{array}{lll}
\text{minimize} & ...
- 2,265
16
votes
1
answer
1k
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.1k
11
votes
0
answers
154
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 \...
- 591
9
votes
1
answer
237
views
Rules of thumb for using classic methods (e.g. branch and bound) vs. meta-heuristics (G.A, S.A, etc..) for non-convex problems?
Are there any rules of thumb for when to use classical methods like branch and bound, branch and cut, etc...for non-convex problems, vs using meta-heuristic methods like genetic algorithms, ...
- 2,009