Questions tagged [convex-optimization]
Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.
205
questions
2
votes
1answer
59 views
Reformulating a convex optimization problem with $x \mapsto \max(x,0)$ in the constraint
I am wondering if there is a well-known transformation allowing one to solve convex optimization problems of the form
$$\begin{array}{ll} \underset{x}{\text{maximize}} & r^T x\\ \text{subject to} &...
4
votes
0answers
93 views
Generally quadratic convex problem with one non-convex term
How would you approach a standard convex quadratic problem with convex constraints but one non-convex term ? Say $|x|^{0.4}$.
$$\min_x \frac{1}{2} x^{T}Qx + g^Tx + c^T \mathrm{sign}(x) |x|^{0.4} $$
...
2
votes
1answer
60 views
Project to nearest point on convex polyhedron
I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces:
$$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
0
votes
1answer
44 views
Norm constraint in CVXPY
I'm trying to implement the algorithm outlined in https://arxiv.org/abs/1211.5608 on a small scale. I have a linear operator $\mathcal{A}$ which is defined as $$\text{trace}(A^*_l(hm^*))$$ where $$A_l ...
1
vote
1answer
57 views
Solving a linear program with an active set method
Is it possible to solve a linear program with an active set method? If so what would be the similarities and differences to the simplex method?
6
votes
0answers
252 views
Finding points inside cells of power (generalized Voronoi) diagram
Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by:
$$\...
0
votes
0answers
18 views
Convex performance measure of classification
In the context of binary classifcation methods, I am looking for a performance metric that can be optimized in MATLAB.
Since the data is not balanced, a good choice seems to be the so-called F1-...
0
votes
1answer
57 views
3
votes
2answers
239 views
log(det(X)) in Semidefinite Programming
I have been solving problems of the form $$max \ log(det(A)) \\ s.t. \ A = A^{T} \succeq 0, \\ p_{i}^{T}Ap_{i} \leq b_{i}$$ where $b_{i}$ and $p_{i}$ are input vectors (to be clear there is more than ...
4
votes
1answer
176 views
Underdetermined Minimum Volume Enclosing Ellipsoid
Given three vectors in $\mathbb{R}^{512}$, my task is to compute a Minimum Volume Enclosing Ellipsoid (MVEE). I have tried Kachiyan's algorithm, but it requires at least as many vectors as there are ...
1
vote
1answer
79 views
In which cases does the nonlinear conjugate gradient method take more than $n$ steps?
I have programmed a couple of Matlab implementations of nonlinear Conjugate Gradient methods (Fletcher Reeves and Polak Ribeire). However, I am concerned with how many steps it's taking to optimise ...
2
votes
0answers
96 views
Proving convexity of Frobenius norm and correlation function formulations of an optimization problem
I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting.
Firstly, I would like to make the variables I used in the problem and ...
2
votes
0answers
44 views
Interior point of convex polytope
Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to ...
2
votes
1answer
58 views
Could the convex problem be tackled by CVX?
I want to solve the convex optimization as follows:
\begin{align}
\underset{X_1,X_2}{\min} &\ -\frac{1}{N}\sum_{i=1}^N\log\det\left(I+H_i^HX_2H_i\right)-\log\left[1+h^H(X_1+X_2)h\right]\\
&\...
1
vote
1answer
80 views
Disciplined convex programming expression of $x\sqrt{1-x}$
Anyone have an idea for a DCP (disciplined convex programming) representation of the concave function $x\sqrt{1-x}$, which is has domain $[0,1]$?
The Taylor series about $x=0$ is
$$x - \frac{x^2}{2}...
2
votes
1answer
125 views
Gradient descent in constrained optimization of barrier function
This question may be too basic, but I was wondering if it is possible to implement simple methods such as gradient descent or its variations to find the minimum of barrier functions in constrained ...
5
votes
0answers
103 views
Minimum of quadratic assignment (QAP) with convex objective
Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem:
$$
\min_{\textrm{permutation matrices }P}
\mathrm{tr}(BP^\top AP+C^\top ...
6
votes
1answer
64 views
Sparsity-Promoting Convex Optimization Over Simplex
Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + ...
3
votes
1answer
251 views
Convex optimization with constraints involving matrix inverse
I have the following convex optimization problem. I would like to ask is there any efficient way to solve it in Python? Can I use CVXOPT package? If so, any detailed instruction? Thanks a lot.
$$
\...
3
votes
0answers
108 views
A maximization problem, with motivation in machine learning
Consider the minimization problem described this paper. Let $f_{\lambda}$ be the minimizer. As a part of extending my work, I am able to show the following facts
$$\lim_\limits{\lambda \to 0}\|f_{\...
3
votes
1answer
75 views
Geometric Programming - symbolic version
I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
3
votes
2answers
251 views
Convexity of Sum of $k$-smallest Eigenvalue
If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $.
Define the function as $f(A)=\sum_{i=1}^{k} \...
4
votes
1answer
50 views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
0
votes
1answer
107 views
Optimize multivariable function with interdependent variables
I have a cost function with 2 parameters. The variables are dependent on each other. So, if I just take a partial derivative with respect to one variable the slope is in terms of the other variable ...
2
votes
0answers
43 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
0
votes
0answers
31 views
Minimizing the ratio of two specific non negative quadratic convex functions
$F$ is $m\times m$ diagonal, with real non negative elements
$D$ is $n \times m$ complex
$P$ is $n \times 1$ complex
$A$ is $m \times 1$ complex.
Minimize $\Gamma(A)$, with respect to $A$.
$$\...
6
votes
1answer
113 views
numerical solution of an under-determined linear equation in high dimensions
I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
0
votes
1answer
69 views
Formulate and solve a simple conic programs in cvxpy language [closed]
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty.
Question
(A)...
0
votes
1answer
29 views
Gradient ascent method with a constant step size?
I'm trying to use the gradient ascent method on a convex function like the multivariate-Normal density function with respect to its parameters (the original is a bit more complicated), something ...
2
votes
1answer
105 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
3
votes
0answers
89 views
Why the MIRACLE of Lanczos/CG-like?
Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy...
In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
-1
votes
1answer
25 views
Semi-Definite relaxation of non-linear constraint?
I am implementing an optimization problem using semi-definite approach. One of my constraints is of following form
$ trace(AāX)ā(kātrace(AāX))+(kā\sqrt {(trace(BāX)} )==0$
where k is a constant, A ...
2
votes
0answers
37 views
Where can I find sample data for large linear programming optimization problems?
I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
1answer
356 views
Why does Newton's method with Linear Equality Constraints use KKT condition?
Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.
The problem only has equality constraint. Why ...
1
vote
0answers
47 views
Order of a principal term
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a bound for the total number of iterations for some process. See page 109:
$$\left[\frac{1}{\ln(2(1-\kappa))} \ln\frac{t_0-t^...
2
votes
1answer
122 views
Convergence rate and complexity for convex minimization problem
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
3
votes
0answers
86 views
First order methods for a large scale semidefinite program
I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...
3
votes
1answer
972 views
How to transform this SOCP to the format required by cvxopt
I'm new to SOCP and want to try to get familiar with the format and how to solve it with cvxopt in python. However, for a simple toy example I'm struggling to get ...
0
votes
1answer
2k views
How to efficiently solve a QCQP with “dynamic” constraints in Python?
I want to solve a QCQP in Python. It is a problem from finance: maximise return (linear function) given some linear constraints and one quadratic constraint that turns it into a QCQP. Formally,
$$\...
1
vote
1answer
217 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
2
votes
0answers
230 views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
1
vote
0answers
33 views
Best Possible Convex bounds for optimization problems
Suppose we have a primal problem
$$
p^{*}=\min_x f(x), \\\text{s.t.}~~ h_i(x) \leq 0,
$$
where $f(.)$ and $h_i(.)$ are possibly non-convex.
Then its Lagrangian is
$$\mathcal{L}(x,z_i)= f(x) + \...
2
votes
0answers
30 views
Domain for convex perspective function
The perspective of a function $f : \mathbb{R}^n \to \mathbb{R}$ is the function $g: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}$ where $g$ is defined as $$g(x,t) = tf(x/t)$$ with $$\mathbf{\text{dom}...
1
vote
0answers
71 views
Nonlinear least square optimization
Problem description
Given data at many time instance $t$,
$$\min _{\alpha, \Lambda, \beta} \lVert y(t) - \alpha e^{\Lambda t} \beta \rVert_F$$
with $$ \lVert \alpha \rVert_2^F = 1 $$
where $y(t) \...
3
votes
2answers
215 views
How do I check if a loss function can achieve its minimum?
For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
6
votes
1answer
331 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
1
vote
1answer
2k views
How to Solve Optimisation Problems using Penalty Functions in Python
I am working on a implementing a simple quadratic optimisation problem:
$$\min _x \; {\underline{x}}^T Q {\underline{x}}$$
$$s.t. \,\quad {\underline{\mu}}^T{\underline{x}} = R^*$$
$$ \quad \quad \...
1
vote
0answers
21 views
How does the MADS algorithm work in practice
Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization
I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
1
vote
2answers
86 views
Making difference of log constraints convex
I have the discrete likelihood estimation problem $\max \sum m_i\log p_i $ where $m$ is a given vector of length $n$. The constraints are $0 \preceq p \preceq 1$, $\sum_{i=1}^n p_i = 1, $ and one ...
6
votes
2answers
1k views
What is the most appropriate derivative free optimization algorithm
We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$.
If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
