All Questions
Tagged with convex-optimization non-convex-optimization
231 questions
1
vote
1
answer
36
views
Biconjugate of a nonconvex function and global minimum
Since the convex biconjugate of a function is the largest convex function bellow it, I assume that the minimum of the biconjugate function is the same as the global minimum of the original function in ...
- 23
2
votes
0
answers
103
views
Similar SVMs with only different misclassification weights!
I am working on understanding the relationship between the solutions of two related SVM optimization problems, defined as follows:
Problem 1:
\begin{equation}
\min \frac{1}{2} \|w\|^2 + C \sum_{i=...
- 381
0
votes
1
answer
52
views
Two questions on feasible cones of closures of open connected domains in $\mathbb{R}^n$ at a boundary point
Let $U$ be an open domain in $\mathbb{R}^n.$ The feasible cone at a boundary point $x\in \partial{U}$ is defined by:
$$F_x(\bar{U}):=\{v\in \mathbb{R}^n: \exists t_0 > 0 \text{ so that } x + tv \...
- 2,556
0
votes
1
answer
25
views
KKT-conditions of $\min t$ such that $t-x\geq0, t+x \geq 0, x^2 -4x + 4 = 0$
I want to solve
\begin{align*}
\min_{t,x} t\\
\text{s.t. } t-x &\geq 0 \\
t+x &\geq 0 \\
x^2 -4x + 4 &= 0
\end{align*}
with the help of KKT conditions. Obviously, the solution is given by $...
- 777
0
votes
2
answers
133
views
How to solve this maximization?
I'm facing this problem recently, how to optimize the problem?
$$\max_{\textbf{B}}\ \text{tr}\left(\textbf{A}\left(\textbf{B} \otimes\textbf{I}\right)\right)$$
$$\text{tr}(\textbf{B})\leq p$$
$\textbf{...
- 31
1
vote
0
answers
14
views
How to model a more generalized hyperbolic constraint as an SOCP constraint?
It is well known that the hyperbolic constraint $xy \ge t^2$ can be modeled as an SOCP constraint by the following transformation $\frac{1}{4}(x+y)^2 \ge t^2 + \frac{1}{4}(x-y)^2 \Leftrightarrow \...
0
votes
0
answers
41
views
How to transform this problem into a convex problem
We have the following optimisation problem:
\begin{align}\label{P1}
\underset{\mathbf{A,B,C,D,}\boldsymbol{\Theta }}{\mathrm{min}} &\quad f(\mathbf{A})\\
&\text{s.t.} \left[ \begin{...
- 31
0
votes
1
answer
40
views
How can I prove the convexity of this function?
Let
$f(x, \omega) = x_{1} + x_{2}\cos \omega + x_{3}\cos 2\omega + \cdots +x_{n}\cos (n-1)\omega$ and $g(x, \omega) = -\log f(x, \omega)$.
The question is 'Is $g(x,\omega)$ convex when $\omega(\in[0,\...
- 1
1
vote
0
answers
82
views
Converting $x^3$ Optimization to an Equivalent LP Problem
Suppose we want to find the minimum of a a strictly increasing function $f: [-a, a] \to \mathbb{R} $, for some $a > 0$, which is also concave in $[-a, 0]$ and convex in $[0, a]$ (exactly like the $...
- 11
1
vote
0
answers
67
views
How to set up a convex concave procedure for the minimization of $abc$?
From this post, it seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure. Out of curiosity, suppose that I have a simple problem that is
$\begin{...
2
votes
0
answers
28
views
Maximizing a semi-concave function
A function $f:\mathbb{R}^d\to\mathbb{R}$ is called semi-concave if $x\rightarrow f(x)-\frac{\lambda}{2}\|x\|^2$ is concave for some $\lambda>0$.
Suppose I want to maximize a function $f$ which is ...
- 299
0
votes
1
answer
336
views
How does McCormick envelope work for inequality constraints?
I have a question regarding the McCormick envelope in mathematical optimization.
The McCormick envelope allows to create a convex relaxation for a bilinear term.
Given the bilinear constraint $w = x \...
- 53
0
votes
0
answers
32
views
Is it possible to convexify the inequality constraint $z \leq x^3 \cdot y$?
Is there a way to convexify the inequality constraint $z \leq x^3 \cdot y$ in a nonlinear optimization problem with $x, y, z$ being nonnegative variables?
- 53
1
vote
1
answer
68
views
Assessing the Convexity of an Optimization Problem
I am trying to analyze the following optimization problem
Objective Function:
The objective is to maximize the total yield (alloc_yield) obtained from allocating assets to different pools.
$$\text{...
2
votes
0
answers
40
views
Can the following optimization problem be reformulated into a standard form convex problem?
I have the following optimization problem given:
$$
\begin{aligned}
\max \quad & E \cdot p - c_A * A - c_h * h - c_C * C \\
\textrm{subject to:} \quad & v \leq \log(h) \\
& E \leq v^3 \...
- 53
1
vote
2
answers
94
views
A simple constrained optimization problem
Let $v\in \mathbb{R}^n$. Define $E(v) = \sum_{i=1}^n (v_i^2-1)^2$ be the energy to be minimized. Define the constraint $\sum_{i=1}^n v_i = cn$. This means the average value of all $v_i$'s is $c$. ...
- 2,277
1
vote
1
answer
61
views
Finding the global minimum of a convex-like optimization problem
Given an optimization problem of the following form:
$$
\begin{aligned}
\min_{x \in \mathbb{R}^n} \quad & f(x)\\
\textrm{s.t.} \quad & g_i(x) \leq 0 \\
& h_j(x) = 0
\end{aligned}
$$
with $...
- 53
4
votes
1
answer
160
views
Bounding a sequence involving minimizers of strictly convex quadratic functions
Suppose that $H\succ 0$ and we have a sequence $\{x_j\}_{j\ge 1}$ such that each one is the unique solution of the following problem:
$$
x_{j} = \text{argmin}_{x\in \mathbb R^n}(x-x_{j-1})^T\nabla f(...
- 381
1
vote
1
answer
59
views
Existence of a lower-bound for an interesting function!
Suppose that $$h(x,z):= (x-z)^T\nabla f(z)+\frac{1}{2}(x-z)^TH(x-z),$$ where $f$ is a smooth function in $\mathbb R^n$. Also, suppose $H\succ 0$ and $\|\nabla f(u)\|\le \gamma; \forall u\in \mathbb R^...
- 381
3
votes
2
answers
163
views
Why having a global convex upper bound is considered as an advantage for the convex-concave procedure?
I am reading this paper "Variations and extension of the convex–concave procedure" and on page 5/25, second paragraph, the authors state that "Another advantage of CCP is that the over ...
2
votes
0
answers
39
views
Changing convexity by changing metrics
I was wondering if for a given functional $F$ on some space $X$, is it possible to construct explicit metrics $(X,d_1)$ and $(X,d_2)$ such that $F$ is convex w.r.t $d_1$ while $F$ is non convex w.r.t $...
- 337
0
votes
1
answer
191
views
What's the purpose of the KKT condition when first-order optimality condition exists?
Given a convex optimization problem $$\min f(x), x \in D$$ $f, D$ convex.
The first-order optimality condition says $x$ is the minimizer if and only if $\nabla f(x)^T (x-y) \geq 0, \forall y\in D.$ ...
- 8,374
0
votes
1
answer
56
views
Variance of Concave Function
Let $X:=[X_1,\dots, X_n]$ be a random vector with $X_i \in (0,2)$ and having a joint distribution $F_X$. Take a constant vector $a:=[a_1,\dots, a_n]$ with $a_i \in [0,1]$ and $\sum_{i=1}^n a_i = 1$. ...
- 1,258
4
votes
1
answer
374
views
Optimizing sum of a quadratic function and $l_1$ norm on a sphere
I am currently attempting to derive the dual and KKT conditions for the following optimization problem:
\begin{equation}
\min_{x\in \mathbb R^n} \quad x^TMx+a ||x||_1^2 \quad \text{subject to} \quad ||...
- 381
1
vote
0
answers
46
views
How to deal with the optimization problem with non-convex feasible set?
How to deal with the problem with non-convex feasible set.
\begin{align}
&({\rm P1})\ \underset{\bf x}{\min} f({\bf x})={\bf x}^T{\bf x}+{\bf f}^T{\bf x}\\
&{s.t.}\\
&\|{\bf x}-{\bf x}_z\|...
- 31
0
votes
0
answers
43
views
Are there practical problems in optimization where its dual problem is computationally easier to solve?
In a class I learned that optimization problems can have "dual counterparts"
For example, a problem of the type
$$\min_{x} f(x) + g(x)$$
has a "Fenchel" dual problem:
$$\max_{y} -f^...
- 5,603
0
votes
1
answer
36
views
what are the generic methods to prove solution existence!?
Suppose we are in $\mathbb R^n$ and consider $$\min f(x) \qquad s.t. \qquad x\in P.$$
Under what conditions on $f$ and $P$, we can guarantee this problem obtains a solution?
The most generic ...
- 381
1
vote
1
answer
130
views
Single constraint quadratic optimization dual form expression using the Schur complement
Strong duality result for non-convex problem with two quadratic functions is a related question. However, I am trying to understand how the dual form problem comes about.
This dual form ...
- 113
0
votes
0
answers
35
views
Try to analyze the given function is convex , non-convex, concave or non-concave?
The function is given as follows:
$\hat{\mathbf{b}}^{H}\left ( \boldsymbol{\theta} \right ) = \left ( \mathbf{b_{u}} + \mathbf{A_{u}}diag \left ( \mathbf{d_{u}} \right )\boldsymbol{\theta} \right ) \...
0
votes
1
answer
52
views
C-VaR approximation problem
In the paper written by Rockafellar about C-VaR (https://www.ise.ufl.edu/uryasev/files/2011/11/CVaR1_JOR.pdf), it is explained that this quantity can be approximated using the following problem (...
- 381
0
votes
0
answers
90
views
Proof of convergence for a heavy-ball adaptive step-size algorithm for non-convex functions
I am struggling with prooving convergence for an optimizer which uses adaptive step-size with heavy ball algorithm for convex and non-convex functions. In some literature, I could find a regret bound ...
- 21
3
votes
0
answers
100
views
Equivalence of Matrix Determinant Maximization Problems?
I am interested in an optimization problem involving parameters $\boldsymbol{\mu}$ and $\boldsymbol{\pi}$, both strictly positive stochastic vectors, and variable $n \times n$ matrix $W$:
\begin{...
- 182
1
vote
1
answer
40
views
Minimizing sum of square of three distances under monotone transformation -- is the solution unique?
Let $f:[0,1]\to[0,1]$ be a differentiable, strictly increasing, and concave function with $f(0)=0,$ $f(1)=1$, and $f'(0)<\infty$. Does the function
$$
F(x,y) = \alpha (x-y)^2 + f^2(x) + \big(1-f(...
- 1,628
0
votes
0
answers
38
views
The dual of this SDP with a simple nonconvex constraint
In this problem we're optimizing over variables $X\in \text{PSD}_n$ and $Y\in\mathbb R^{d\times n}$ for some $d\le n$.
\begin{align}
&\text{Maximize}&&\langle A_0, Z\rangle\\
&\...
- 86
1
vote
0
answers
173
views
IPOPT solver cannot solve MPC problem in presence of non-convex objective
I am using the IPOPT solver to solve a multi-agent MPC problem. I notice that once I add quadratic collision avoidance cost - 100 * (||xi - xj||-radius)**2, where <...
0
votes
1
answer
107
views
Conditions for the squared gradient norm to be convex?
Let $f\colon \mathbb{R}^n \to \mathbb{R}$ be a differentiable function. I am looking for conditions under which the function $$x\mapsto \Vert\nabla f(x)\Vert^2$$ is convex.
It obviously hold if $f$ is ...
- 203
0
votes
0
answers
94
views
Two methods for solving bivariate optimization problems — how do they compare?
Consider the unconstrained non-convex optimization problem:
$$\min\limits_{x,y} f(x,y)$$
Suppose that for fixed $x$, the function $y \mapsto f(x,y)$ is convex. In this case, I believe there are two ...
- 1
2
votes
2
answers
119
views
Minimum of a non-convex function
Let,
\begin{align}
f(x,y)=\frac{1}{y^2}+\left(\frac{x}{y}+\sqrt{2-\frac{1-x^2}{y^2}}\right)^2,
\end{align}
where $0 \le x\le 1$, $-1 \le y \le0$, $x^2 + y^2 \le 1$ and $x^2 + 2y^2 \ge 1$. What is the $...
- 85
0
votes
1
answer
54
views
Convexity of set of mixture distributions
A set of mixture distributions $Q$ is defined as,
$Q = \{f | f(.) = \sum_{i=1}^{k} q_{i} f_{i}(.) \}$,
where each $f_{i}$ is a probability density and $\sum_{i=1}^{k} q_{i}=1$ and $q_{i}>0$.
Is set ...
- 53
0
votes
1
answer
157
views
Optimal solution to the primal and the Lagrangian dual when there is duality gap
Consider the primal problem $\max_{x\in\mathcal{X}} f(x)$ subject to $g(x)\leq 1$ and its Lagrangian dual $\min_{\lambda\geq 0}\max_{x\in\mathcal{X}}\{f(x)+\lambda(1-g(x)\}$ with no convexity ...
- 397
0
votes
2
answers
544
views
Indicator constraint in optimization
I am trying to formulate an optimization problem with the following constraint:
$y = 1$ if $x \le c$ and $y = 0$ if $x > c$ which is basically an indicator function $y = 1[x \le c]$ and $c$ would ...
- 35
3
votes
0
answers
148
views
Minimizing a strictly convex quadratic function subject to a single nonconvex quadratic constraint
For $A\succ 0, B\succeq 0, \rho,\phi>0$, and a given $y$, I am trying the find a cheap yet numerically stable method for solving a sequence of the following problem (it is a penalty method and $\...
- 381
1
vote
1
answer
114
views
Saddle point in a non-convex objective function
I am investigating the following minimization problem as follows. It is the summation of two fractional functions that mirror each other around $(y_c,y_n)=(\frac{1}{2},\frac{1}{2})$:
$Min\ z(y_c,y_n)=\...
1
vote
3
answers
114
views
How to deal with the constraint $a \leq \|x\|_2 \leq b$ in an optimization problem?
How to solve the following optimization problem?
$$\begin{array}{c l} \underset {x} {\text{minimize}} & c^{\top} x\\ \text{subject to}~& a \leq \|x\|_2 \leq b
\end{array} $$
Can we convert it ...
- 697
1
vote
0
answers
97
views
Maximizing $(x-5)^2$ subject to $0 \leqslant x \leqslant 10$
I am working on a simple case of convex optimization. I modeled the system on paper and now am using Python the RSOME library. I want to maximise $(x-5)^2$ (bounded between $0 \leqslant x \leqslant 10$...
- 21
1
vote
1
answer
205
views
Clarke Subdifferential for a function of two variables.
I am looking of an example where equality don't hold in the below relation:
let $f: \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R} $ be locally lipschitz and regular at $ x = (x_1 , x_2)^T \in \...
- 41
1
vote
0
answers
245
views
Inequality constraints of convex relaxation with McCormick envelope
I have a nonconvex optimization problem for which I am calculating a lower bound using the McCormick envelope. Each bilinear term is replaced with an auxiliary variable which has the following ...
- 11
0
votes
0
answers
36
views
Multi-variable non-convex optimization problem where the problem is convex if one variable is fixed
I have a non-convex optimization problem in the form
$$
\begin{align}
& \min{f(x,y)} \\
& \text{s.t. } h(x,y) \le 0
\end{align}
$$
I cannot derive a closed form solution. However, if I assume $...
- 73
1
vote
1
answer
65
views
Boyd & Vandenberghe, example 3.34 — quasiconvex example
Example 3.34 (Page 97 in my version) in their book defines $$\mathrm{PV}(x,r):=\sum_{i=1}^n (1+r)^{-i}x_i$$ for every $r\geq 0$ and $x \in \Bbb R^n$ such that $x_0 < 0$ and $\sum_{i=1}^n x_i>0$. ...
- 329
0
votes
1
answer
129
views
Is the difference of two concave functions non-convex/non-concave?
I have a problem:
\begin{align}
\max_{p,q} \log_2(1+ph)\\
s.t: \log_2(1+ph)\leq \log_2(1+qf)\\
p<P\\
q<Q
\end{align}
where $h$ and $f$ are positive real numbers. We can rewrite the problem as:
\...
- 177