Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
0answers
29 views

Lagrange multiplier vs KKT

Suppose task 1: maximize $f(x, y)$ subject to $g(x, y) = 0$ and $h(x,y) = 0$ Suppose task 2: maximize $f(x, y)$ subject to $g(x, y) \geqslant 0$ and $h(x,y) = 0$ According to wiki for the first ...
0
votes
1answer
29 views

Algorithm for maximizing the overlap between sets of voxel points

I have a problem that I've formulated as follows. Given a finite target set $T$, and a set-generating function $F(x_i) = C_i$ that also produces finite sets, I'd like to find the set $C_i$ that has ...
0
votes
1answer
15 views

Find maxima and minima of the function

Given: $$f:\mathbb{R}^2 \rightarrow \mathbb{R}, f\left(x,y \right)=-x^4+x^3-3x^2y+3xy^2-y^3$$ Find all points where gradient is equal to zero. Decide whether in those points function has either maxima ...
0
votes
1answer
34 views

convex optimization?

I have a question about the convexity of an optimization problem and its solution. Suppose $f(X)=-tr(A^{T}XA)+tr(X)$, $A$ is any matrix with its dimension "matched" with $X$. The optimization problem ...
0
votes
0answers
6 views

concavity conditions with respect to s for $\Pi \left( s \right)=\underset{x}{\mathop{\max }}\,f\left( s,x(s) \right)$

Here is the function: $\Pi \left( s \right)=\underset{x}{\mathop{\max }}\,f\left( s,x(s) \right)$ I want to find the conditions of showing $\Pi \left( s \right)$ is concave with respect to s at $x^*$ ...
2
votes
0answers
25 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
1
vote
3answers
24 views

Minima problem?

This is a question in my textbook which I can't solve. Any help would be appreciated, thanks. "A piece of wire 10 metres long is cut into two portions. One piece is bent to form a circle, and the ...
14
votes
4answers
5k views

What does “curly (curved) less than” sign $\succcurlyeq$ mean?

I am reading "Convex Optimization" by Stephen Boyd. He is using a curved greater than and curved less than equal to signs. $f(x^*) \succcurlyeq \alpha$ or $f(x*) \preccurlyeq \alpha$ Can someone ...
0
votes
3answers
26 views

Global Optimization of a well-defined function with gradient information

I try to minimize the function $$ f(x_1, …x_n)=\sum\limits_{i}^n-a_icos(4(x_i-b_i)) +\sum\limits_{ij}^{edge}- cos(4(x_i-x_j)) $$ $$x_i,b_i\in (-\pi, \pi)$$ where $\sum\limits_{ij}^{edge}$ only sums ...
0
votes
1answer
42 views

simplify/solve nonlinear equations for constrained least squares problem

I am trying to find a simple, ideally closed form formula for the (not necessarily unique) unit vector $\vec{x}$ minimizing total squared cosine distance from a collection of unit vectors $\vec{v_i}$. ...
0
votes
0answers
29 views

Local global minimizers and maximizers

I want to find the local and global minimizers and maximizers of the following two functions. 1) $f(x)=x^2e^{-x^2}$ 2) $f(x)=x+ \sin x $ These are my answers. 1) $f(x)=x^2e^{-x^2}$ ...
0
votes
1answer
38 views

Find the cosine of the angle at the vertex of an isosceles triangle having the greatest area

Find the cosine of the angle at the vertex of an isosceles triangle having the greatest area for the given constant length $l$ of the median drawn to its lateral side. I tried to solve this ...
0
votes
0answers
27 views

Maximum volume inscribed ellipsoid inside nonconvex polyhedron

In Convex Optimization (Boyd, Vandenberghe), an algorithm for finding the maximum volume inscribed ellipsoid inside a convex polyhedron is given on p. 414 (8.4.2 Maximum volume inscribed ellipsoid) [I ...
1
vote
3answers
38 views

The value of $a$ for which $f(x)=x^3+3(a-7)x^2+3(a^2-9)x-1$ have a positive point of maximum lies in the interval $(a_1,a_2)\cup(a_3,a_4)$

The value of $a$ for which $f(x)=x^3+3(a-7)x^2+3(a^2-9)x-1$ have a positive point of maximum lies in the interval $(a_1,a_2)\cup(a_3,a_4)$.find the value of $a_2+11a_3+70a_4$ I differentiated ...
0
votes
1answer
291 views

Find pressure in a sinusoidal function

Tiffany is a model rocket enthusiast. She has been working on a pressurized rocket filled with laughing gas. According to her design, if the atmospheric pressure exerted on the rocket is less than 10 ...
3
votes
3answers
38 views

An upper bound for a function

I am trying to find an upper bound $b\ge f(x)~\forall x\ge0$ for the following function: $$f(x)=\frac{x}{(w+ux^2)^2},$$ where $w,u>0$ are parameter values. I am interested in the positive domain ...
1
vote
1answer
26 views

Maximizing a convex function under constraints

Consider the following non-convex problem: \begin{equation*} \begin{aligned} & \text{maximize} & & f(X) \\ & \text{subject to} & & f(X)\le b\\ &&& A_kX = c_k, \ ...
0
votes
0answers
23 views

How to prove $\int_{\Omega} \sum_{i=1}^{N} f_i(x)dx$ is equivilant with $\sum_{i=1}^{N} \int_{\Omega} f_i(x)u_i(x)dx$

I have a 2D image in $\Omega$ space. Assume that the space can be separated into $N$ sub-regions $\Omega_i$ such that $\Omega_i \cap\Omega_j=\emptyset$; $\Omega_i \cup \Omega_j=\Omega, \forall ...
1
vote
0answers
36 views

minimize smallest eigenvalue

Assume $P_A,P_B$ are probability transition matrices (each element is nonnegative and row sum is 1) and $v$ is probability row vector (each element is nonnegative and sum of elements is 1). How to ...
4
votes
2answers
118 views

Are these two optimization problems equivalent to each other?

Let $\mathbf{x}=[x_1,\ldots,x_K]^T$. For a fixed vector $\mathbf{a}$, I have the following optimization problem : \begin{array}{rl} \min \limits_{\mathbf{x}} & | \mathbf{a}^T \mathbf{x} | \\ ...
-1
votes
0answers
70 views

minimization problem labor and costs

I would appreciate it greatly if someone could provide me with a solution to the problem below: If the contract runs late the business will be penalized \$1000 for each late day. It is estimated that ...
1
vote
0answers
34 views

Proving Convergence of a Derivative Free Method

Hopefully this question is on topic for the mathematics community (rather than the statistics) since the optimization method I am using relies on a statistical model. Well I am building an algorithm ...
1
vote
1answer
27 views

Condition for guaranteed minimum-rank solution

Consider the following rank minimization problem of a positive semi-definite matrix $X$: \begin{equation*} \begin{aligned} & \underset{X}{\text{minimize }} & & rank(X) \\ ...
4
votes
1answer
57 views

Polynomial algorithm for problem in graphs which can also be solved as a linear programming problem.

I have an (undirected) graph $G = (V, E)$. For each vertex $i \in V$ we have a cost associated $v_i$ and for each edge $e \in E$ we have a prize associated $x_e$. My problem is to find $W \subseteq ...
1
vote
2answers
457 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
1
vote
1answer
35 views

How to minimise the upper boundary of this weird function?

Let $\{x\}$ denote the fractional part of $x$, which is $\{x\}=x-[x]$. Let $f_{a,b}(x)=\{x+a\}+2\{x+b\}$ and let its range be $\{m_{a,b},M_{a,b})$. Find the minimum value of $M_{a,b}$ as $a$ and ...
3
votes
2answers
61 views

How to find extrema of $\sqrt{x_1^2 + x^2_2 + x^2_3}$ defined on $\{x \in \mathbb{R}^3 : x_1^2 + 2x^2_2 + 3x^2_3 < 1\}$

I have a function $g: U \to\mathbb{R}$ where $$U :=\{x \in \mathbb{R}^3 : x_1^2 + 2x^2_2 + 3x^2_3 < 1\}$$ and $$g(x) = \sqrt{x_1^2 + x^2_2 + x^2_3}$$ I would like to find out if g(x) has any ...
1
vote
1answer
16 views

how to interpret local minima of combinatorial optimization

I am having a difficult time trying to interpret and visualize the local minima of a combinatorial optimization objective function. Here's a rough sketch of my problem: I have $m$ points ...
0
votes
1answer
34 views

Finding extreme point of a set determined by two planes in $\mathbb R^3$

Problem asks to find a extreme point the set $\{(x,y,z) \mid x-2y \leq 3 , 2y+3z \geq 4 \}$. But I don't think it has a extreme point, because it is intersection of two hyper planes in 3D, which ...
0
votes
1answer
46 views

Can a convex function have local maxima?

I have read that a convex function can have local maxima. It seems that this must happen on the boundary of the domain, otherwise there should be a region in which the function is concave. Is this ...
1
vote
1answer
33 views

Graphical solution (with two variables), solution properties.

(c) infeasibility depends on the constraints; if we look at the graph we can see that (1, 1) is the intersection of constraint (I) and (II), and for this to be infeasible we need t in constraint ...
0
votes
1answer
42 views

How can I find the critical curves for the following functional

Find the critical curves for the following functional : $$J[y,z]=\int_{0}^{1} \sqrt{1+y'^2+z'^2}$$ such that :$$y^2+z^2=1$$ and $$y(0)=z(1)=1$$ $$y(1)=z(0)=0$$
0
votes
0answers
7 views

How to optimize a system of equality an $\geqslant $ constraints?

In many cases, for example when we work with probably mass functions We may need to solve a system of this form: $$ max f(\vec{p_1})+g(\vec{p_2}) $$ when there are the obvious constraints of : $$ ...
1
vote
1answer
16 views

Inspecting a project network

From the given table one can draw the project/activity network above. There are four possible paths: (i) C, B. (ii) C, A, D. (iii) E, D. (iv) G, F, D. The first path's project time is 4+5=9, the ...
2
votes
1answer
166 views

optimization problem minimizing trace of a matrix with inverse

I am trying to solve the following problem $\min_{T} \operatorname{trace} \left( A(T^T M T + N)^{-1}A^T\right)$, where $T$ is the matrix I am solving for and $A$ is given, $M\succ0$ and $N\succ0$. ...
2
votes
1answer
59 views

Second-smallest eigenvalue as $\displaystyle \min_x \frac{x^TAx}{x^Tx}$

In Mining Massive Datasets, page 365, the following theorem is stated without proof: Let A be a symmetric matrix. then the second-smallest eigenvalue of A is equal to $\displaystyle \min_{x} ...
1
vote
0answers
37 views

sum of fractional functions optimization problem

Consider the following sum of fractional functions optimization problem $$ \begin{array}{l} \mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1}{{{\bf{a}}_i^T{\bf{x}} + {b_i}}}} \\ ...
0
votes
0answers
18 views

Help for solving this optimization problem

Are given $2$ square matrices $M_1$ and $M_2$ of dimension $d \times d$ and two points in a $d$-dimensional space $p_1$ and $p_2$ ($d \times 1$). Now I need to find two other square matrices $X$ and ...
1
vote
1answer
540 views

Smooth approximation of maximum using softmax?

Look at the Wiki page for Softmax function (section "Smooth approximation of maximum"): https://en.wikipedia.org/wiki/Softmax_function It is saying that the following is a smooth approximation to the ...
0
votes
2answers
890 views

How to calculate the hessian of a matrix function

I am estimating a model minimizing the following objective function, $ M(\theta) = (Z'G(\theta))'W(Z'G(\theta))$ $Z$ is an $N \times L$ matrix of data, and $W$ is an $L\times L$ weight matrix, ...
0
votes
1answer
16 views

Plotting a convex optimization problem

I have an optimization problem like below: $\text{minimize } - \sum_k w_k \log r_k$ $ a \leq r_k \leq b_k, k = 1, \cdots, 10$ Here, $w $ and $b$ is a set of constant: $w = [w_1, \cdots, w_{10}]$ ...
0
votes
0answers
21 views

Significance of multiplying by weight

I have been reading optimization problems in communication area where it is a common practice to maximize rate of users as below objective function: $\hspace{28mm} \text{ Maximize } \sum_k w_k \log ...
2
votes
1answer
21 views

Is there a binary operator (besides composition) closed under permutations or a notion of a metric space on permutations?

When i say "a binary operator closed under permutations" I mean, given $2$ (finite, same number of elements) permutations $p_1$, $p_2$ , is there an operator "$+$" such that $p_1+p_2=p_3$ ($p_3$ a ...
20
votes
4answers
9k views

How do Lagrange multipliers work to find the lowest value of a function subject to a constraint?

I have been using Lagrange multipliers in constrained optimization problems, but I don't see how they actually work to simultaneously satisfy the constraint and find the lowest possible value of an ...
0
votes
1answer
26 views

Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
1
vote
0answers
24 views

finding the shortest distance of a hermitian matrix to a set of hermitian matricies with specific eigenvalues 2-norm

The title is more general, and all that I require is to show an inequality that I already have verified using random matrices in matlab. Let $\lambda_1 \leq ... \leq \lambda$ and $\mu_1 \leq ... \leq ...
1
vote
1answer
454 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
1
vote
7answers
83 views

Find min & max of $f(x,y) = x + y + x^2 + y^2$ when $x^2 + y^2 = 1$

Problem: Find the maximum and minimal value of $f(x,y) = x + y + x^2 + y^2$ when $x^2 + y^2 = 1$. Since $x^2 > x$ (edit $x^2 \geq x$) for all $x \in \mathbb{R}$, $f$ is bowl-ish with a minimal ...
0
votes
0answers
12 views

Distributing resource based on Efficiency

I am trying to form an optimization problem where I have $k$ nodes who transmits packets with rate $x_k$. The objective is to maximize the rate. $\hspace{28mm} \text{ Maximize } \sum_k \log x_k$ ...
1
vote
1answer
34 views

Taking Log to find MAXIMIZE summation of variables

I have been reading IEEE papers on communication and in several papers the authors formed objective function like: $\text{Maximize } \sum_k \log r_k $ to maximize the total rate of the system of ...