Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
1answer
19 views

What is the maximum of the following function?

Let $f(x,y) = \frac{xy^\alpha}{x+y},\alpha\in(0,\infty)$. How to compute $$\sup_{(x,y)\in[a,b]\times [0,c]}\frac{xy^\alpha}{x+y},$$ with $b>a>0$?
0
votes
1answer
45 views

Convex function (vector composition rule)

I'm looking at the Boyd & Vandenberghe slides on Convex Optimization. In slide 18, it applies the rules of vector composition on an example to say that it is convex. The example given is ...
0
votes
1answer
26 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
2
votes
1answer
52 views

Are posynomial functions convex?

I know that you can transform a posynomial function into an exponential function, which is convex. Does this imply that all posynomial functions are convex?
0
votes
0answers
11 views

Find the dual problem to a quadratic program

Consider the quadratic program: minimize $x_1^2 + 2x_2^2 - x_1x_2 - x_1$ subject to $x_1 + 2x_2 \leq u_1, x_1 - 4x_2 \leq u_2, 5x_1 + 5x_2 \leq 1$ Could anyone explain to me how to find the dual ...
1
vote
1answer
49 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
1
vote
0answers
49 views

How to prove that unnormalized neg entropy is strongly convex with respect to 1-norm?

the unnormalized negative entropy of $\mathbf{x} \in \mathbb{R}^n_+$ is $$ g(\mathbf{x}) = \sum_i (x_i \log(x_i) - x_i) $$ it is stated that $g(\mathbf{x})$ is strongly convex with respect to 1-norm, ...
0
votes
0answers
14 views

Explain the dual problem to D-optimal design problem

Given the following D-optimal design problem $$ \text{minimize } \log \det (\sum_{i=1}^p x_i v_i v_i^T)^{-1}\\ \text{subject to } x \geq 0, {\bf{1}}^T x = 1 $$ Find the dual problem. I don't ...
0
votes
1answer
25 views

Is my proof correct? Convex optimization

There's a theorem that says that if $C \subset \mathbb R^n$ is a convex set, then $x^* \in C$ is the closest point in $C$ to $y \notin C$ if and only if $(y-x^*)\cdot(x-x^*)\leq 0$ for all $x \in C$. ...
0
votes
0answers
29 views

What non-convex functions be written as the $\min$ of multiple convex functions?

I am working on an optimization framework that can be used to optimize objective functions that can be written as the $\min$ of several convex functions. I was thinking about the generality of this ...
0
votes
0answers
27 views

Minimize $\|\mathbf{x-y}\|^2 $ subject to $x \in $ set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$

We are given the set $S=\{\mathbf{x} \in \mathbb{R}^n \;\;\;\mid \;\;\; \|\mathbf{x-x_c}\|^2\leq r^2 \}$ and a point $\mathbf{y} \in \mathbb{R}^n$. Our goal is to find point $\mathbf{\hat{x}}$ ...
3
votes
1answer
50 views

About a definition of “rank” of a matrix.

I am familiar with the definition of rank of a matrix as either (1) the maximal number of linearly independent rows or columns or (2) as the dimension of the image of the matrix. Another ...
1
vote
1answer
14 views

Log transformations of function domain and inequalities

If I know that for some function $f$, the following is true for $x, y \geq 0$: $f(\log (x^a y^b)) \leq f(\log x)^a f(\log y)^b$ Can I make the claim that $f(x^a y^b) \leq f(x)^a f(y)^b$ If I ...
0
votes
1answer
46 views

Probability that max cos(φ)x + sin(φ)y according to uniform distribution = (8,5)

max $x_2$ subject to $x_1 - 2x_2 \le 0$ $2x_1 - 3x_2 \le 2$ $x_1 - x_2 \le 3$ $-x_1 + 2x_2 \le 2$ $-2x_1 + x_2 \le 0$ Optimal solution: (8, 5) --> $x_2 = 5$ Now assume that the objective is ...
4
votes
1answer
146 views

Gradient of the dual function for a nonlinear program

I'm attempting to find a proof for a property from Floudas' Nonlinear and Mixed-Integer Optimization book. Consider a nonlinear optimization problem of the form \begin{align} \min_{{\bf x}}&\quad ...
0
votes
1answer
18 views

Tracking a vehicle moving with uniform velocity?

Suppose there are three cell towers at three positions $P_1$, $P_2$ and $P_3$. A vehicle is moving at uniform speed along a straight line. Three towers are pinging the vehicle at certain ...
0
votes
1answer
25 views

How to show the Hessian matrix of such functions are positive semi-definite?

Let $f:R\to R$, $g:R^n\to R$. Thus $f\circ g:R^n\to R$. Now suppose $f$ is non-decreasing and convex while $g$ is convex. In additon, $f,g$ are of $C^2$. I want to show that their composition is ...
0
votes
2answers
21 views

why Quasiconvex function is not concave?

A quasiconvex function is a function whose all sublevel set are convex. I am curious to know whether a quasiconvex function is a concave function.
0
votes
0answers
27 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
0
votes
1answer
37 views

Gradient of Least Squares function

I have trouble understand the gradient of equation 3.12 with respect to $W$. Tn is a scalar output variable, $\phi(x)$ and $W$ are $N \times 1$ dimensional. According to the book, the gradient ...
1
vote
1answer
59 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
0
votes
0answers
44 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
0answers
56 views

Do corner points optimise a linear function over a bounded convex region?

This proof says if $Z_P \ne Z_Q$... ...then $Z$ is maximised (or minimised, I guess) at one of the $\color{red}{\text{endpoints}}$ -- of what exactly? $\overline{PQ}$? So the maximum value of ...
1
vote
0answers
29 views

Moreau Decomposition with Bregman Distance

I am working with a non-Euclidean proximity operator defined by a Bregman distance function $D(\cdot, \cdot)$: $$ \operatorname{prox}_f(x) = \operatorname*{argmin}_u \{ f(u) + D(u, x) \} $$ Is ...
0
votes
1answer
39 views

Identify if optimization problem is convex or non-convex?

I have formulated optimization problem for building, where cost concerns with energy consumption and constraints are related to hardware limits and model of building. To solve this formulation, I need ...
0
votes
1answer
19 views

Optimization problem for non-symmetric normal cone inclusion or antiderivative of Ax+b

I have the following equation: $$ -(\mathbf{A}\mathbf{x} + \mathbf{c}) \in \mathcal{N}_{C}(\mathbf{x}) \qquad (1) $$ where $\mathbf{A} \in \mathbb{R}^{n\times n}$ is symmetric and positive definite, ...
1
vote
1answer
29 views

Duality and the Positive Lagrange Multiplier

Suppose I have the following optimization problem: \begin{align} \min &f(x) \\ & f_1(x) \leq 0 \\ & \vdots \\ & f_k(x) \leq 0 \\ & g_(x) = 0 \\ ...
0
votes
0answers
31 views

Number of optimas of product of convex functions

I am dealing with a function, which is a product of two strongly convex functions, and trying to determine the number of its local minimum. For example, I have $$H=f(x)\cdot g(x)$$, in which both $f$ ...
0
votes
1answer
43 views

Is closed convex set with finite number of extreme points convex polyhedron

I have this simple question related to convex set and convex polyhedron. As the content in the title, it's basically my question: Is closed convex set with finite number of extreme points convex ...
0
votes
1answer
19 views

How to interpret the regular condition in this theorem about cones in convex analysis?

Theorem:Let $K_1,\dots, K_m$ be convex cones in $R^n$ and let $K = K_1 \cap K_2 \cap \dots K_m$. If $K_1 \cap int(K_2) \cap \dots \cap int(K_m) \neq \emptyset$(regularity assumption), then $K^\circ = ...
0
votes
0answers
31 views

Connection between method of Lagrange multipliers and KKT conditions?

I understand that in general, the KKT conditions are not sufficient for optimality. However, if the primal problem is a convex optimization problem, then the KKT conditions are sufficient for ...
1
vote
1answer
49 views

Is $-\ln(1+e^x)$ a convex function?

Is $-\ln(1+e^x)$ a convex function? My answer book says no because its second derivative is $-\dfrac{e^{2x}}{(1+e^x)^2}$ but I am sure that it is incorrect. I have that the second derivative is ...
0
votes
0answers
12 views

uniform lower bound for convex combination of a sequence of positive semidefinite matrices

Assume: a sequence of positive semidefinite matrices $A_k^i\in M_{m,n}, m<n$, $i\in\mathcal{N}$, and they have the following property: $$\underline{a}I \leq A_k^i(A_k^i)^T\leq \overline{a}I.$$ ...
0
votes
1answer
29 views

Solving SVM classifier with two weight vectors

I am trying to implement a paper that basically proposes the following way to train two classifiers on some data with two types of labels. I do not know how to tweak existing solvers for SVM to do the ...
0
votes
1answer
29 views

Stopping criteria for gradient method

For numerically solving a smooth convex optimization $\min\{f(x): x\in S\}$ where $S$ is a closed convex set, we can apply some different algorithms: gradient method, accelerated gradient, proximal ...
0
votes
1answer
26 views

Does the non-expansion property of the projection operator hold for all definitions of norm?

For convex problem, of course. I vaguely remember this holds for weighted norm also. But I am curious if there are some general conclusions about what kinds of norm will fit in this framework?
1
vote
3answers
48 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
1
vote
0answers
41 views

Scaled proximal operator for proximal Newton method

The scaled proximal operator was introduced as an extension of the (regular) proximal operator: $prox^H_h(x) = \arg\min_y h(y) + \frac{1}{2}\|y-x\|^2_H$. (See ...
0
votes
1answer
60 views

Is $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ concave? [closed]

I want to maximize the capacity function $\log \det \left( I + \frac 1 {\sigma^2} H F \bar H \right)$ with respect to $F$, subject to the constraints: (1) $\operatorname{trace} F \le Pt$ (2) ...
0
votes
1answer
30 views

Is this a concave function?

Suppose $\gamma \in R^{1}$ and $\beta \in R^{k}$. Let $f(\gamma,\beta) = (y_{2} - \gamma y_{1}) - (y_{3} - \gamma y_{2}) \exp(x^{\prime}\beta)$. Then is $f$ a concave function of ...
2
votes
0answers
28 views

Is it possible to use regularization to minimize the (expected) number of non-zero digits in a number?

This question may be slightly related to this question on length of the representation of a number in a certain basis. Introduction / Background In image and video coding, particularly the ...
1
vote
0answers
35 views

KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & ...
1
vote
1answer
35 views

Is this convex minimizer a continuous function?

Consider the function $g: \mathbb R^n \rightarrow \mathbb R$ given by: $$ g(x) = \arg\min_{y\in\mathbb R} \sum_{i=1}^n f_i(|y - x_i|) $$ where $f_i$ are convex, strictly increasing and continuous. ...
3
votes
3answers
84 views

Is there an efficient way to evaluate the proximal operator of $f(x) = \|x\|_2 + I_{\geq 0}(x)$?

Is there an efficient way to evaluate the proximal operator of the function $f:\mathbb R^n \to \mathbb R \cup \{ \infty \}$ defined by \begin{equation} f(x) = \| x \|_2 + I_{\geq 0}(x), \end{equation} ...
1
vote
1answer
33 views

Proof convexity of Logarithmic function

Prove that: $\ln(e^{x+y} +1 )$ is a convex function. I have tried to used $F \circ G$, while $F = \ln (t+1)$ and $G = e^{x+y}$ $G$ is convex but I need to prove that $F$ is convex and growing, ...
0
votes
0answers
25 views

How to solve the following convex constrained optimization problem?

\begin{equation}\label{constrained optimization} \begin{aligned} \min\limits_{\mathbf{X}}&\|X_{(1)}\|_{*}+\|X_{(2)}\|_{*}+\|X_{(3)}\|_{*}+\lambda\|Ax-b\|_2^2 &\ \ s.t. X_{ijk}=M_{ijk}\ \ ...
1
vote
0answers
27 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
0
votes
0answers
43 views

Existence of steepest descent curves of convex functions

Preliminaries. Let $f:\mathbb{R}^n\to\mathbb{R}$ be a convex function. Then for any point $x\in\mathbb{R}^n$ and direction $v\in\mathbb{R}^n$ the directional derivative $\nabla_v f(x)$ of $f$ at $x$ ...
1
vote
0answers
44 views

Quasiconcavity of a product of ratios

Given $f(x_1\ldots x_k) = \dfrac{x_1x_2\cdots x_k}{(x_0+c_1)(x_0+c_2)\cdots(x_0+c_k)}$ where $x_i > 0$, the $c_i > 0$ are constants, and $$x_0 = \sum_{i=1}^k x_i$$ is it true that $f$ is ...
0
votes
0answers
74 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...