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.

Filter by
Sorted by
Tagged with
4
votes
0answers
78 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
44 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
31 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
50 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?
5
votes
0answers
238 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
52 views
3
votes
2answers
198 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
175 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
75 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
89 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
55 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
79 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
110 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
101 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
56 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
198 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
107 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
181 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
49 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
95 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
42 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
99 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
85 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
35 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
316 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
118 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
85 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
912 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
208 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
207 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
29 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
69 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
194 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
315 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 ...
2
votes
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
81 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 ...
1
vote
1answer
1k views

How to define the derivative for Scipy.Optimize.Minimize

I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...

1
2 3 4 5