Questions tagged [nonconvex-programming]
For questions about non-convex optimization problems where the objective or any of the constraints are non-convex.
34
questions
4
votes
0answers
61 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+\...
3
votes
0answers
24 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 ...
2
votes
3answers
331 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 ...
2
votes
1answer
73 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 ...
5
votes
0answers
67 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
votes
2answers
121 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 ...
3
votes
0answers
67 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 ...
6
votes
0answers
84 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 ...
4
votes
0answers
74 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}...
7
votes
1answer
128 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 ...
8
votes
1answer
100 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
90 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 ...
8
votes
2answers
116 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\...
2
votes
1answer
66 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 ...
6
votes
2answers
107 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 ...
4
votes
1answer
53 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
votes
0answers
122 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
1answer
132 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.
3
votes
1answer
158 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'...
4
votes
1answer
104 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 \...
3
votes
0answers
71 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 ...
4
votes
1answer
77 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
1answer
132 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....
6
votes
1answer
60 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 ...
14
votes
2answers
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 ...
12
votes
1answer
430 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 ...
9
votes
3answers
528 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} & ...
17
votes
1answer
645 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 ...
12
votes
0answers
136 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 \...
9
votes
1answer
152 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, ...
15
votes
1answer
284 views
Convexity of Variance Minimization
$X$ is a discrete random variable taking value $x_n$ with probability $1/N$ for $n=1,
\ldots,N$. I would like to set the $x_n$ values in an optimization problem. My objective is to minimize the ...
12
votes
2answers
276 views
Convex vs Strictly Quasiconvex Functions in Optimization
I have read/heard quite a few time that in the old days, it was considered that linear programs constitute the class of optimization problems that can be solved efficiently in practice (as a rule of ...
14
votes
1answer
438 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 ...
10
votes
2answers
142 views
Global optimality condition of non-convex quadratic programs
We know that a convex quadratic maximization (not minimization!) on a polyhedron has its global optimal value on a vertex.
Also, I have read in some papers that checking whether a vertex is globally ...
