Questions tagged [non-convex-optimization]

A non-convex optimization problem is one where either the objective function is non-convex in a minimization problem (or non-concave in a maximization problem) or where the feasible region is not convex.

Filter by
Sorted by
Tagged with
1
vote
1answer
16 views

Approximating large quadratic optimization problems

For some positive-definite matrix $A \in \mathbb{R}^{K \times K}$ I want to solve the quadratic optimization problem $$\max_{x\in [0,1]^K} x^T A x \\ \text{s.t.} \\ \sum_{i=1}^{K}x_{i}=1$$ The problem ...
0
votes
0answers
14 views

Validity of minimum of possibly unbounded set equated to zero, e.g. $\min_{d} { \nabla F_{i}(z) d } = 0$.

There's a construction in an optimisation paper concerning complementarity constraints, [1], that seems usual. For functions $F,G: \mathbb{R}^{n} \to \mathbb{R}^m$, the complementarity constraints are ...
0
votes
0answers
34 views

linear programming with $L_p$ norm constraint

$$\text{minimize } c^Tx$$ $$\text{s.t. } \|x\|_p = 1, x_i \geq 0. $$ How to derive the optimal explicit solution $x^*$? Note that $c$ is a constant vector.
0
votes
0answers
17 views

Question on application of randomized algorithms to solve nonconvex optimization problems

In Convex Optimization, Boyd & Vandenberghe give the following example of a randomized algorithm to solve a nonlinear convex optimization problem using convex optimization: [given a nonconvex ...
15
votes
3answers
590 views

How do I solve $\min_x \max(c_1^Tx, c_2^Tx, \dots, c_k^Tx)$ for $\lVert x \rVert_2 = 1$.

Let $f(x) = \max(c_1^Tx, c_2^Tx, \dots, c_k^Tx)$. where $x, c_1, c_2, \dots, c_k \in \mathbb R^n$. What fast iterative methods are available for finding the (approximate) min of $f$ with the ...
0
votes
0answers
22 views

Sub-differential of a sum of non-convex functions

For functions, $f_1, f_2, ...$, which are all convex, the sub-differential of their sum is the sum of their sub-differentials, $\partial \sum\limits_{i} f_i = \sum_\limits{i} \partial f_i$ What could ...
1
vote
0answers
37 views

Black box optimization

I have a simulation which gives a scalar result depending on the choice of some continuous design variables. I am trying to minimize the output of the simulation. As a first step, I want to study the ...
0
votes
1answer
30 views

sum of linear fractional function in constraints set

I have the following optimization problem, which includes a sum of fractional functions constraint as follows \begin{align} \text{P1}:~& \underset{t,y,x}{\text{maximize}} \: \: t\\ &\text{...
1
vote
0answers
26 views

Characterizing (stationary) points by the number of valleys one can descent into

In non-convex optimizing of more than 2 times differentiable $f: \mathbb{R}^2 \mapsto \mathbb{R}$ we can encounter saddle points that have multiple valley one could descent into. At $(0,0)$ there are ...
0
votes
0answers
8 views

Does Von Neumann stability guarantee that any numerical difference scheme is unstable if it has a coefficient of $U_i^n$ is a positive number?

I am new to the subject of stability analysis of swarm optimization algorithms so kindly pardon me if my question is too obvious. Consider a numerical scheme of the form, $$U_i^{t+1} = U_i^t + r(U_i^t-...
1
vote
0answers
14 views

Thoughts on creating nonconvex bounded below function.

I want to check an algorithm whose dimension of its argument is large and it involves the least squares loss. Also, I need this function to have a gradient and Hessian easily computable. I came up ...
0
votes
0answers
30 views

Is this reasonable for the convexity of function??

There is a convex and non-negative function f(x) and g(x,y) is multiplication of f(x) and (1-y) where -1<= y <=1. In that case, could I say since within a range of y, g(x,y) is form of f(x) ...
0
votes
0answers
23 views

How to find a optimal center for a bounding sphere of a convex set

I have a special convex set which is a hypersphere sliced by every hyperplane vertical to every axis. Is there an analytical or approximated method for obtaining the shape's bounding sphere which ...
-2
votes
1answer
47 views

Proving quasiconvexity of $x^3 + y^3$ [closed]

I was studying quasiconvex functions, and suddenly I have stumbled upon the function $f(x,y)= x^3+y^3$. Is it quasiconvex? From the graph it seems like.
1
vote
1answer
71 views

Maximizing quadratic function over unit Euclidean ball

I am considering the following maximization problem $$\begin{array}{ll} \text{maximize} & \| A x - b \|_2^2\\ \text{subject to} & \| x \|_2 \leq 1\end{array}$$ For easiness, let's assume $A\in\...
4
votes
1answer
71 views

Does every compact (not necessarily convex) set have extreme points?

Let $A$ be a set in a normed vector space. Call a point $p$ in $A$ extreme if there do not exist $p_0, p_1$ in $A$, distinct from $p$, such that $\lambda p_0+(1-\lambda)p_1=p$, for $\lambda \in [0,1]$....
0
votes
1answer
55 views

Is this function of a sum of indicator functions convex?

let $x=x_1,x_2,...,x_n$ for $x \ge 0$, let $I(x) =max(x_i, 0) $ for $i \in [1,n]$ $f(x) = I(c-x)a^T+I(x-c)b^T$ where $a,b,c$ are constant vectors Is this a convex function? How is this proven?
1
vote
1answer
35 views

Find binary vector furthest away from set of binary vectors? [closed]

How can I find the binary vector furthest away from a set of binary vectors?
2
votes
0answers
21 views

Which is stronger, Kurdyka-Łojasiewicz property or regular? If the comparison is not proper, what are their range of applications?

(Kurdyka-Eojasiewicz property and exponent). We say that a proper closed function $h: \mathbb{X} \rightarrow \overline{\mathbb{R}}$ satisfies the Kurdyka-Eojasiewicz $(K L)$ property at $\hat{x} \in$ ...
0
votes
0answers
49 views

Find stationary points of QCQP

I'm given the following: $$\begin{align} \min &\qquad x^TQx\\ \mathrm{s.t}&\qquad x^TAx <= 1 \end{align}$$ where $A$ is a positive definite. I'm not sure if and or how this would change ...
0
votes
0answers
41 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 ...
0
votes
0answers
14 views

How to prove the equivalency of the following two optimization problems?

The following two problems are equivalent (P1) $\underset{\mathbf x}{\arg\min}\,\, f(\mathbf x)+g(\mathbf x)$ (P2) $\underset{\mathbf x,y}{\arg\min}\,\, f(\mathbf x)+y\quad \quad \text{s.t.}\,\,\, g(\...
0
votes
0answers
17 views

Dual of a constrained optimization problem

We would like to find the Lagragian dual problem of \begin{align*} \min_{v_1, v_2, v_3, w_1, w_2} & \frac{1}{2} (v_1^2 + v_2^2 + v_3^2 ) + (w_1 + w_2)\\ \text{s.t. } & v_1 - v_2 + v_3 + w_1 \...
0
votes
1answer
32 views

How to frame this optimisation problem mathematically so it can be coded up.

I am trying to develop a methodology for solving a constrained optimisation problem I am facing, I would appreciate any help/pointers on how best to frame this problem so that it can be coded up ...
0
votes
1answer
30 views

converting con-convex region to convex [closed]

I'm trying to model a problem using Linear Programming theory, though the feasible region of the problem is non-convex. Yet, I think using Big-M and some binary variables this region can be converted ...
0
votes
0answers
28 views

Maximization of non-convex function over a convex set.

I have ${n\choose 2}$ non negative variables $0\leq v_{ij}\leq \frac{1}{2}$, $1\leq i<j\leq n$, and I'm trying to solve the maximization $$ \max_{v_{ij}}\sum_{\begin{subarray}{l}|S|=r\\ S\subseteq [...
1
vote
0answers
34 views

Minimising kurtosis. Can I prove solution uniqueness under particular assumptions using real algebraic geometry or an alternative approach?

I consider a weighted sum of $n$ correlated and identically-distributed random variables. The weights in the sum, $w_i$ for $i=1, 2,...,n$, are non-negative and sum to 1. I am investigating solutions ...
0
votes
0answers
7 views

maximum of a concave function over nonconvex set

Let $f(v)$ be a convcave (smooth and nice) function of the $n$-dimensional vector $v$. Let $p(v)$ be a polynomial in $v$ such that $p(v)$ is a sum of products of $v_1,\cdots,v_n$ and $1-v_1,\cdots, 1-...
1
vote
1answer
19 views

Operations that preserve non-convexity

There are a number of operations that may be done for convex functions such that the resulting function is convex as well. What about the opposite? Do the operations that preserve convexity also ...
1
vote
1answer
98 views

A matrix norm optimization problem involving matrix inversion

I am trying to characterize the the matrix $X^*$ that solves the following optimization (that is an analytical or semi-analytical solution form). \begin{equation} X^*=\arg\min_X \| (A+X)^{-1}\|_F \...
2
votes
0answers
15 views

optimization of a muti-variable function where convexity holds with respect to each variable

I know that sometimes a multi-variable function is convex with respect to each variable, for example $f(x,y)=x^2y^2$, but not convex in the whole. In such cases, can we use nested search methods to ...
0
votes
0answers
29 views

How to prove unimodality

I have a function $g(x)$ of $0\leq x \leq 1$, as the sum of the functions in the following forms \begin{align} f_1(x)&=(2-x)\frac{1-n}{m_1-n},\\ f_2(x)&=(2-x)x\frac{1-xn}{m_2-xn},\\ f_3(x)&...
1
vote
0answers
41 views

How to transform a cubic non convex problem into a quadratic convex problem

I have the following cost function for portfolio allocation to be maximise: $$ w^\top \mu-\frac{1}{2}\gamma w^\top \Sigma w+\frac{1}{6}\gamma^2 w^\top M_3(w\otimes w), $$ which considers the co-...
0
votes
1answer
34 views

$l_{0}$-norm constrained quadratic programming optimization

I intend to solve for vector $ x \in \mathbb{R}^{N \times 1} $ by solving the following optimization problem \begin{align} \arg \min_{x} \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x} ...
0
votes
1answer
13 views

How to know convexity of the following equation/Problem?

How can I find that the following type of problem is a convex of non-convex? $\max_{x,y} \sum_{i \in N} r_{i,O} + \sum_{i \in K\setminus N} r_{i,L} $ The equation is taken from a paper I am reading. $...
2
votes
0answers
27 views

Is there any generic list/table of convex and non-convex functions for references?

I am an Electrical Engineering, but I need to do optimization in my research. Often times, when I read papers, the authors say, "...the problem abc is non-convex". Sometimes I understand why ...
0
votes
0answers
18 views

Convexity with respect to a parameter

Given a cost function $f(a,b)$ where $\nabla_a^2 f(a,b) > 0$, i.e., it is convex if $b$ is fixed. Is there any efficient way to minimise this function with respect to $a, b$? What is this kind of ...
2
votes
1answer
115 views

Equality-constrained QCQP — what to do next?

I am studying the following problem. I want to obtain all the local minima of $$ \min_{x\in D} x^Tx \quad \quad \quad \quad \quad \quad (P.1) $$ where $x\in\mathbb{R}^n$ and $D = \{x: x^TA_ix = 1, \...
0
votes
1answer
37 views

How to minimize smooth non-convex function over the positive semidefinite cone?

I've been stuck with a minimization problem in hand for a while now. It's related to another question of mine (Ignoring positive (semi)definite condition for optimization), but here I'm asking about ...
2
votes
0answers
39 views

Muiltiobjective optimization problems with trivial solutions sets

Consider a multiobjective optimization problem $$\min\limits_{x\in \Omega} f(x),$$ where $f:\Bbb R^n \rightarrow \Bbb R^m$ and $\Omega \subseteq \Bbb R^m.$ A point $\bar{x} \in \Omega$ is said to be: ...
1
vote
1answer
101 views

Maximizing $\mathbf{x}^T A \mathbf{x}$ subject to $| \mathbf{x} | \preceq \mathbf{1}$

I am trying to find a maximum of quadratic function bounded above/below. The problem is formulated as \begin{align} &\underset{\mathbf{x}}{\max}~\mathbf{x}^T \mathbf{A} \mathbf{x} \label{eq:16a} \\...
0
votes
1answer
18 views

Convex “cost” function which has indicator function as limiting case

Suppose I have two variables, $o$ ("old") and $p$ ("new"), where $p>o$ so $p/o>1$. I have a convex cost function $C(o,p)$ of moving from old $o$ to the new $p$ which is ...
0
votes
0answers
19 views

Lower-bounded non-convex geometric program: Help me figure out how to approach this!

I am trying to solve an optimization problem of the form: $$\text{variables: } k \in \mathbb{N}, n \in \mathbb{N}^k, m \in \mathbb{N}^{k+1} \text{, indexing $n$ and $m$ from 0}$$ $$\text{constants: } ...
2
votes
0answers
34 views

Maximize Frobenius Norm constrained to Linear Dynamics

Dears, In a Control Systems context, i want to maximize the Frobenius norm of a matrix K (the controller of my system). Subject to the following constraints: The evolution of the Linear Time ...
1
vote
0answers
68 views

Transform non-convex optimization problem to convex one by add variable

my non-convex optimization problem is as follow: \begin{align} \min_x a_1 x_1^2 + a_2x_1 + a_3 - \frac{a_4}{x_1} \end{align} subject to: \begin{align} \frac{c_1}{x_1}+c_2\leq d_{\mathrm{max}} \end{...
3
votes
1answer
118 views

Maximizing a positive semidefinite quadratic form over the standard simplex

I am attempting to maximize a positive semidefinite quadratic form over the standard simplex. Given a symmetric positive semidefinite (Hessian) matrix $A \in \Bbb R^{d \times d}$ and a matrix $W \in \...
0
votes
0answers
64 views

How to check if a symmetric positive definite matrix is concave?

There is a simple routine for checking if a matrix is positive definite called the Cholesky decomposition. If the matrix isn't, Cholesky functions instantly return an error saying it is not positive ...
2
votes
1answer
45 views

References for finding sparse solutions of an unconstrained non-convex optimization problem.

Given a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ where $n$ is large and $f$ is non-convex. The following characterises the sparse minimizer of $f$. $$ x^* = \arg \min_{x} f + ||x||_0 $$ where ...
5
votes
2answers
195 views

What is the range of $\vec{z}^{ \mathrm{ T } }A\vec{z} $?

Let A be a 3 by 3 matrix $$\begin{pmatrix} 1 & -2 & -1\\ -2 & 1 & 1 \\ -1 & 1 & 4 \end{pmatrix}$$ Then we have a real-number vector $\vec{ z }= \left( \begin{array}{c} ...
0
votes
0answers
31 views

How to solve the following problem $P$?

How to solve the following problem $P$? $$P: \min_{\mathbf{x}}\sum_{n=1}^N\frac{a_n}{x_n} + \prod_{n=1}^Nb_nx_n \\ s.t.\quad \sum_{n=1}^N x_n = 1,\\ \quad 0\le x_n\le 1,\quad n\in\{1,2,\cdots,N\},$$...

1
2 3 4 5
9