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
1answer
38 views

Simplifying optimization problems by transforming the independent variable

In Regiomontanus' angle-maximization problem, one can maximize the angle by maximizing the tangent of the angle, since the tangent function is increasing. This makes the differentiation simpler. One ...
0
votes
1answer
32 views

Is it possible to always get the optimal formula regardless of the derivation method?

Today I've tried to solve a geometric problem (collision point between two circles in a specific situation). I found a working solution but I'm not sure if it was optimal (maybe my solution took more ...
0
votes
0answers
21 views

Change the operators to give the least result

I have this equation : $$C_n=a_0 r_0+a_1 r_1+a_2r_2+\ldots+a_{n-1}r_{n-1}+a_nr_n-2n,$$ where all values of $r_i$ are known and $$\sum_{i=1}^na_i=0\qquad |a|<n.$$ how can i find values of $a_i$ ...
1
vote
1answer
33 views

How to solve an Optimization problem with linear as well as Quadratic constraints.

I want to solve the following problem, \begin{equation} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & \mathbf{x^T}\mathbf{Px} \\ & \text{subject to} & & ...
2
votes
1answer
35 views

Monotonicity of an optimizer

Let us consider an optimization problem over $[0,1]$. That is, we are given two continuous functions $$ f,g:[0,1]^2\to \Bbb R $$ such that $f(x,y)$ is non-decreasing in $x$ and non-increasing in ...
0
votes
1answer
36 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
1answer
9 views

Conic hull of a proper function

Suppose $f$ is a proper function pn $\mathbb{R}^{n}$with $f(0)>0$.Now consider $$ g(x) = \text{inf}\{t: (t,x) \in \text{cl(cone(epi(}f)))\} $$ Can I always say that $\exists y \in \mathbb{R}^{n} : ...
2
votes
1answer
29 views

State of the art method for non-convex optimization of $\|x\|_p$

The following mathematical optimization program is non convex for $0\leq p<1$, and some convex function $f$: $$\text{minimize}_x \|x\|^p_p+f(x)$$ I'm wondering if any one knows the state of the ...
0
votes
0answers
31 views

Linear programming with quadratic constraints

I want to solve a problem of this form: $max_{y,k} \,\,\, w^\top y + C 1^\top k$ s.t. $k y^\top B^\top = I $ $A^\top y \geq b$ is there an algorithm that can solve such a problem? Is there an ...
2
votes
1answer
53 views

Difference between maximize $\sum\limits_{k=1}^Kg_k(\mathbf{x})$ and $\sum\limits_{k=1}^{K}\log(1+g_k(\mathbf{x}))$ in convex optimization

I have a problem of the following form: maximize $\;\;\;\,\sum\limits_{k=1}^Kg_k(\mathbf{x})$ subject to: $\;\,\,f_i(\mathbf{x})\leq\,1\,\forall\,i\in\{1, 2, \dotsc, m\}$ ...
0
votes
0answers
41 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
0
votes
2answers
17 views

Minimize error function with integer constraints

Much time has passed since I studied any form of math so I wanted to take this cheap shot of asking someone else to think for me. I need to write some software that, for any given real number ...
0
votes
0answers
20 views

How to optimize area distribution (and make more potatoes by tray)?

Let me present you to a problem I've been facing. Each night I have to put a tray with 8 potatoes in the oven. Frequently I slice them, but by the 7th potato, there is not enough space in between ...
0
votes
0answers
29 views

Maximum Set Selection Problem

Mike has N different items. He has M orders of customers and each customer has a set of items they want. Customer will not accept partial order. So Mike can give one item to atmost 1 customer. Find ...
0
votes
2answers
48 views

Minimizing the following objective function with matrices

Suppose $A$ and $B$ are known matrices, and we are to find matrix $X$ that minimizes the following function, $$\frac{1}{2}||X||^2+\frac{1}{2}||X^TAX-B||^2$$ Taking the relevant derivative w.r.t $X$ ...
0
votes
0answers
15 views

Bound for the greedy algorithm solution to the cover set problem

This is from Algorithms by Dasgupta et al.: Claim Suppose B contains $n$ elements and that the optimal cover consists of k sets. Then the greedy algorithm will use at most $k$ ln $n$ sets. ...
1
vote
2answers
45 views

Minimizing $\sum_{i=1}^n \frac{x_i^2}{w_i}$ subject to $\sum_{i=1}^n x_i=1$

Minimize $\displaystyle\sum_{i=1}^n \frac{x_i^2}{w_i}$ subject to $\displaystyle\sum_{i=1}^n x_i=1$. The answer is $x_i=\displaystyle\frac{w_i}{\sum_i w_i}$ but I don't know why apart from ...
0
votes
1answer
55 views

Semi-positive definite Hessian matrix and local minimum

Suppose we have a function $F(x)$ defined as \begin{equation} F(x) = \frac{1}{2}x^TAx + b^Tx +c, \end{equation} where \begin{equation} A = \begin{bmatrix} 4 & 2 \\ 2 & 1 \\ ...
3
votes
2answers
46 views

Can a non-extreme point be an optimal solution of a Linear Programming problem?

Consider a linear programming problem. Is it possible for an optimal solution to exist, but not at an extreme point? According to Bertsimas & Tsitsikalis ("Introduction to Linear Optimization", ...
1
vote
0answers
31 views

using lsqcurvefit to fit piece-wise linear

I would like to use this function to fit piece-wise linearly to a set of data. Namely, I want to fit them with several linear segments. Including other requirements, I would not want the segments ...
0
votes
0answers
16 views

Sparse coding with local sparseness of dictionary

The title is probably pretty unclear, I hope I am able to explain it better here. I am currently working on a problem in the field of sparse coding, that is Principal Component Analysis, Non-negative ...
0
votes
0answers
13 views

Is $S$ a polyhedral set?

Let $\textbf{x}=(x_1,x_2)^T$, $\textbf{y}=(y_1,y_2)^T$, is $$S=\{\textbf{x}|\textbf{x}^T\textbf{y}\le1 \text{ for all }\textbf{y}\text{ such that }y_1\ge0,y_2\ge0,y_1+y_2=5\}$$ a polyhedral set? How ...
0
votes
1answer
22 views

Finding minimum norm

Let $A$ be $k\times k$ positive symmetric matrix, $K$ is $k\times d$ full rank matrix with $d<k$, and $v\in\mathbb{R}^k$. I'd like to find $x\in \mathbb{R}^d$ such that $(Kx-v)^TA(Kx-v)$ minimum. ...
1
vote
0answers
184 views

Maximizing the number of groups

The problem is as follows, There is a restaurant which has N number of chairs each chair has a unique number written on it so the array of chairs is like [1,2,....N-1,N] , there are G number of groups ...
-1
votes
1answer
41 views

Optimization: Finding line connecting non-pareto-optimal allocation in Edgeworth Box to PO allocation

Two people, A and B, with respective utility functions of: $$U_a(X_a,Y_a) = X_a^2 Y_a\\ U_b(X_b,Y_b) = X_b Y_b^2$$ Total $X$ (that is, $X_a+X_b$) is fixed at $36$. Total $Y$ ($Y_a+Y_b$) is fixed ...
0
votes
1answer
52 views

What minimizes the Chebyshev Distance?

For an arbitrary number of dimensions, I know that the mean minimizes the distance using the L2 norm and that the geometric median minimizes the distance function using the L1 norm (though I have yet ...
0
votes
0answers
37 views

Distance metrics with kmeans

Context: I'm trying to derive some formulas for computing the "mean" in the K-means algorithm. So given an assignment of $m$ data points to $k$ clusters, find a formula to recompute the mean of the ...
2
votes
2answers
50 views

Find out minimize volume (V) of tetrahedral

I have this problem: On space $ (Oxyz)$ given point $M(1,2,3)$. Plane ($\alpha$) contain point $M$ and ($\alpha$) cross $Ox$ at $A(a,0,0)$; $Oy$ at $B(0,b,0)$; $C(0,0,c)$. Where a,b,c>0 Write the ...
0
votes
2answers
104 views

Simplify basic expression

Please, does anyone know which tool can simplify expressions like: $$a^4 - 4a^3b + 6a^2b^2 - 4ab^3 - a + b^4$$ into: $$(a - b)^4 - a$$ I tried SymPy, Maxima and W|A without success. PS: I'm ...
1
vote
0answers
12 views

Characterizing limit of value functions in a stochastic control problem

Consider a probability space $(\Omega, \mathcal F , \mathbb P)$, $(B_t)_{t\geq0}$ M-dimentional brownian motion adapted to a filtration $(\mathcal F_t)_{t\geq0}$ over $\Omega$. In this context ...
1
vote
0answers
16 views

The $K$-moment problem for measures with countable support?

Roughly the $K$-moment problem can be described as: Given a subset $K$ of $\mathbb{R}$ and a sequence of real numbers $(q)_{n\in\mathbb{N}}$, does there exists a Borel measure $\mu$ with support ...
1
vote
1answer
28 views

Minimizing a function of many variables

My friends asked me this question about minimizing a function, $$ E=\left( \frac{p_{2}}{p_{1}}\right)^2 + \left( \frac{p_{3}}{p_{2}}\right)^2 + ... + \left( \frac{p_{N+1}}{p_{N}}\right)^2 - N $$ ...
1
vote
1answer
16 views

Find the extrema of $f$ subject to the constraints.

find the extrema of $f(x,y)=x-y$ subject to the constraints $x^2-y^2=2$. I know that $\nabla$$f(x,y)= \lambda \nabla g(x,y) = (1, -1) =(2x, -2y)$, so $1=\lambda2x$, and $-1=-\lambda2y$, so $x=y$, ...
1
vote
0answers
26 views

Minimizing $L_\infty$ norm using gradient descent?

Curve fitting problems are solved by minimizing a cost/error function with respect to the model's parameters. Gradient descent and Newton's method are among many algorithms commonly used to minimize ...
0
votes
2answers
44 views

Minimize Frobenius norm with constraints

As a follow-up on my previous question, I would like to solve the following optimization problem: $\min \Vert MA-B \Vert_F^2-x^HMy\;\;s.t.\;\;M^HM=I$ where $A$ and $B$ are $N\times L$ complex ...
2
votes
2answers
31 views

Optimization for fat line intersecting most points

Let's say I have a bunch of $(X,Y)$ points in 2D space. I want to find the line $y=mx+b$ which intersects the most points. We can add some kind of buffer (a delta) so if the line $y=mx+b$ is within ...
2
votes
1answer
25 views

Lower semicontinuity of indicator function

For any set $\mathcal{S} \subseteq \mathbb{R}^{N}$, let us define the indicator function $$\delta_{\mathcal{S}}(\mathbf{x}) \triangleq \begin{cases} 0, & \quad \textrm{if } \mathbf{x} \in ...
1
vote
1answer
109 views

Which greedy algorithm is optimal?

The following question is a homework problem for a course called Design and Analysis of Algorithms. In the problem, there is a minimized cost function and two greedy algorithms. I am asked to show ...
1
vote
1answer
37 views

Bézier curves and optimization

I have a very peculiar problem. Assuming that you know how B-Splines or Bézier Curves work, you may also know that if we assume the result of the function, let's say tri-dimmensional, as a position in ...
0
votes
0answers
13 views

If the definition of pareto dominance is correct?

I want to use the following definition in my paper. The reviewer says the definition of Pareto dominance is incorrect or written carelessly. Would you please help me rewrite it.
0
votes
0answers
6 views

$H_{\infty}$ optimization of transfer function matrix - which method?

I have a two-dimensional (2 x 2) transfer function matrix like this: The aim is to solve optimization problem: I used the code below, but there is no convergence: ...
0
votes
2answers
59 views

Critical points of multivariable function

Im trying to find the critical points a function, but when setting the partial derivatives equal to zero, i cant figure out how to solve them, for this particular function: $\ f(x,y)= ...
0
votes
0answers
11 views

Epi-convergence to indicator function

Let the indicator function be defined as $$I(x) \triangleq \begin{cases} 1, & \quad x \geq 0 \\ 0, & \quad x < 0 \end{cases}$$ and $I_{\nu}(x) \in [0,1]$ be a continuous approximation of ...
1
vote
0answers
58 views

Prove that there exists a subset with sum >=1 such that the remaining integer sum reduces by 1

let $ n \in \mathbb{N} $ and $ \frac{1}{w_1},\ldots, \frac{1}{w_n} $ for some (not necessarily distinct) $ w_1,\ldots,w_n \in \mathbb{N} $ and $ w_1,\ldots,w_n \ge 2 $ be given. Assume that $ ...
1
vote
1answer
36 views

Intuition and counterexamples for higher-order derivative test

In the higher-order test we keep differentiating a function till we find the n'th derivative (n being even) to be greater than or less than zero thereby identifying it as a minimum or maximum. My two ...
1
vote
1answer
36 views

cost minimization

There are n cities $c_1,c_2,...c_n$(in decreasing order of popularity) where a company wants to open its N branches. There is cost $w_i$ for opening a branch in city $c_i$. If company has budget W , ...
2
votes
0answers
53 views

Maximize a function subject to the constraint $x^2+y^2=R^2$

Please help me how to deal with maximization of function $$f(x,y)=1-e^{-\pi x}+e^{\pi x}\left[1-\cos(\pi y)+\sin(\pi y)\right]$$ subject to the constraint $x^2+y^2=R^2$. Using Lagrange ...
2
votes
1answer
57 views

Am I doing something wrong here? Maximization of profit problem.

The cost and price functions for a new Internet search company are reasonably approximated by the following models: $C(x) = 37 + 1.42x – 0.0067x^2 + 0.00011x^3$ $p(x) = 3.7 – 0.007x$ Where $x$ ...
0
votes
1answer
29 views

Why is lower semicontinuity important for epi-convergence?

Why is the lower semicontinuity property important for epi-convergence (and, on the contrary, upper semicontinuity is not desirable)? A simple example would also help.
1
vote
1answer
14 views

Placing a shape on a grid

I am interested in a certain kind of geometrical optimisation problems. I will illustrate it on a semi-concrete example: You are given a two-dimensional shape, say a polygon, and a rectangular ...